論文の概要: Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting

• arxiv url: http://arxiv.org/abs/2509.14334v1
• Date: Wed, 17 Sep 2025 18:04:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-19 17:26:52.934949
• Title: Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting
• Title（参考訳）: 正規化正方形根:離散的連続計数のためのシャーパ行列分解境界
• Authors: Monika Henzinger, Nikita P. Kalinin, Jalaj Upadhyay,
• Abstract要約: この研究に先立ち、$gamma_2(M_count)$の最もよく知られている上限は1 + fraclog npi$である。 $ 0.701 + fraclog npi + o(1) ;leq; gamma_2(M_count) ;leq; 0.846 + fraclog npi + o(1) を示す。 改良された下界も確立する:$ 0.701 + fraclog npi + o
• 参考スコア（独自算出の注目度）: 16.381810189243406
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The factorization norms of the lower-triangular all-ones $n \times n$ matrix, $\gamma_2(M_{count})$ and $\gamma_{F}(M_{count})$, play a central role in differential privacy as they are used to give theoretical justification of the accuracy of the only known production-level private training algorithm of deep neural networks by Google. Prior to this work, the best known upper bound on $\gamma_2(M_{count})$ was $1 + \frac{\log n}{\pi}$ by Mathias (Linear Algebra and Applications, 1993), and the best known lower bound was $\frac{1}{\pi}(2 + \log(\frac{2n+1}{3})) \approx 0.507 + \frac{\log n}{\pi}$ (Matou\v{s}ek, Nikolov, Talwar, IMRN 2020), where $\log$ denotes the natural logarithm. Recently, Henzinger and Upadhyay (SODA 2025) gave the first explicit factorization that meets the bound of Mathias (1993) and asked whether there exists an explicit factorization that improves on Mathias' bound. We answer this question in the affirmative. Additionally, we improve the lower bound significantly. More specifically, we show that $$ 0.701 + \frac{\log n}{\pi} + o(1) \;\leq\; \gamma_2(M_{count}) \;\leq\; 0.846 + \frac{\log n}{\pi} + o(1). $$ That is, we reduce the gap between the upper and lower bound to $0.14 + o(1)$. We also show that our factors achieve a better upper bound for $\gamma_{F}(M_{count})$ compared to prior work, and we establish an improved lower bound: $$ 0.701 + \frac{\log n}{\pi} + o(1) \;\leq\; \gamma_{F}(M_{count}) \;\leq\; 0.748 + \frac{\log n}{\pi} + o(1). $$ That is, the gap between the lower and upper bound provided by our explicit factorization is $0.047 + o(1)$.
• Abstract（参考訳）: 下位三角形のAll-ones $n \times n$ matrix, $\gamma_2(M_{count})$と$\gamma_{F}(M_{count})$の分解ノルムは、Googleによって知られているディープニューラルネットワークの唯一の生産レベルのプライベートトレーニングアルゴリズムの正確さを理論的に正当化するために使用されるため、差分プライバシにおいて中心的な役割を果たす。 この研究に先立ち、$\gamma_2(M_{count})$の最もよく知られた上限はMathias (Linear Algebra and Applications, 1993)による$ + \frac{\log n}{\pi}$であり、最もよく知られている下限は$\frac{1}{\pi}(2 + \log(\frac{2n+1}{3})) \approx 0.507 + \frac{\log n}{\pi}$ (Matou\v{s}ek, Nikolov, Talwar, IMRN 2020)である。 近年、ヘンジンガーとウパヒアイ (SODA 2025) はマティアスの境界を満たす最初の明示的因数分解を与え(1993)、マティアスの境界を改善する明示的因数分解が存在するかどうかを問うた。 私たちはこの質問を肯定的に答える。 さらに、我々は下限を大幅に改善する。 具体的には、$ 0.701 + \frac{\log n}{\pi} + o(1) \;\leq\; \gamma_2(M_{count}) \;\leq\; 0.846 + \frac{\log n}{\pi} + o(1) を示す。 つまり、上界と下界の間のギャップを0.14 + o(1)$に減らします。 また、我々の因子は以前の研究と比較して$\gamma_{F}(M_{count})$に対してより良い上限を達成できることを示し、改善された下限を確立する:$ 0.701 + \frac{\log n}{\pi} + o(1) \;\leq\; \gamma_{F}(M_{count}) \;\leq\; 0.748 + \frac{\log n}{\pi} + o(1)。 つまり、明示的な分解によって得られる下限と上限の間のギャップは、0.047 + o(1)$である。

関連論文リスト

• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space [10.292118864147097]
  ワッサーシュタイン空間上の有限次元多面体部分集合の理論を開発し、一階法による函数の最適化を行う。 我々の主な応用は平均場変動推論の問題であり、これは分布の$pi$ over $mathbbRd$を製品測度$pistar$で近似しようとするものである。 解析の副産物として,MFVIのための勾配に基づくアルゴリズムの最初のエンドツーエンド解析を求める。
  論文  参考訳（メタデータ） (2023-12-05T16:02:04Z)
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
  任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。 我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
  論文  参考訳（メタデータ） (2023-04-06T16:15:19Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
  本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。 低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
  論文  参考訳（メタデータ） (2021-03-17T18:18:57Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。