Fugu-MT 論文翻訳(概要): Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting

論文の概要: Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting

arxiv url: http://arxiv.org/abs/2607.28703v1
Date: Thu, 30 Jul 2026 14:41:34 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-03 14:29:40.410929
Title: Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting
Title（参考訳）: 純DP連続計数における任意実行列分解のコスト
Abstract要約: 我々は(eps)-DP行列力学クラスを最適化された最大値と平均二乗誤差が(eps-2log3(n+1))であることが証明する。クレームは純粋(eps)-DPラプラス行列機構と2つの二乗誤差基準に制限される。
参考スコア（独自算出の注目度）: 0.9023847175654603
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Let $T_n$ be the lower-triangular prefix-sum matrix and let $\cfrob(T_n)$ and $\ctwo(T_n)$ be the factorization costs that govern mean and maximum per-coordinate squared error of the Laplace matrix mechanism under pure $\eps$-differential privacy, for $\eps>0$. We prove $\cfrob(T_n),\ctwo(T_n)=Θ\bigl((\log(n+1))^{3/2}\bigr)$ with no sign, sparsity, or squareness restriction and with arbitrary finite inner dimension. Consequently, within the pure-$\eps$-DP matrix-mechanism class the optimized maximum and mean squared errors are both $Θ(\eps^{-2}\log^{3}(n+1))$. Under the factorization contract of Arkhipov and Kalinin (arXiv:2607.08963v1), who prove the matching lower order for factors with entries in $\{0,1\}$ and state the arbitrary-factor extension as open, the theorem below establishes the order for arbitrary real factors. The lower bound runs through a $p$-nuclear obstruction: an aggregate column-width estimate $D_k(T_n)\asymp n^{3/2}k^{-1/2}$, valid in the low-rank range $1\leq k\leq n/16$, for the prefix chain, fed into the classical approximation-space conversion of Pietsch and Hinrichs--Pietsch, becomes harmonic at the critical exponent $p=2/3$, and Hölder's inequality transfers it to both factorization costs. The same computation determines $\nucpow_p(T_n)$ for each fixed $0<p<1$: order $n$ below $2/3$, $n\log n$ at $2/3$, and $n^{3p/2}$ above. A Fenwick interval factorization supplies matching upper bounds. The claims are confined to pure-$\eps$-DP Laplace matrix mechanisms and the two stated squared-error criteria; they do not cover non-matrix continual mechanisms, approximate-DP sensitivity, or expected maxima across coordinates.
Abstract（参考訳）: T_n) を下三角形の接頭辞行列とし、 $\cfrob(T_n)$ と $\ctwo(T_n)$ を、純粋な $\eps$-微分プライバシーの下でラプラス行列機構の平均および最大2乗誤差を管理する因子化コストとする。符号、空間性、あるいは正方性制限を伴わず、任意の有限内次元で、 $\cfrob(T_n),\ctwo(T_n)=\bigl((\log(n+1))^{3/2}\bigr)$ を証明する。したがって、純-(\eps\)-DP行列力学クラスでは、最適化された最大誤差と平均二乗誤差はともに $\eps^{-2}\log^{3}(n+1))\ である。 Arkhipov と Kalinin の因子化契約 (arXiv:2607.08963v1) の下では、(\{0,1\}$ の成分を持つ因子に対して一致する低次を証明し、任意の要素拡大を開として述べる。下界は $p$-核閉塞を通す: アグリゲート列幅推定 $D_k(T_n)\asymp n^{3/2}k^{-1/2}$ プレフィックス鎖に対して低ランク範囲 $1\leq k\leq n/16$ で有効であり、ピエッチュとヒンリッヒ=ピエッチュの古典的な近似空間変換に供給され、臨界指数 $p=2/3$ で調和し、ヘルダーの不等式は両方の因子化コストに変換する。同じ計算により、各固定された $0<p<1$: $2/3$, $n\log n$, $2/3$, $n^{3p/2}$ に対する $\nucpow_p(T_n)$ が決定される。フェンウィック区間分解は、一致する上界を供給する。クレームは純-$\eps$-DPラプラス行列機構と2つの二乗誤差基準に制限されており、非行列連続機構、近似DP感度、座標間の最大値などをカバーするものではない。

関連論文リスト

Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
論文参考訳（メタデータ） (2026-07-22T17:27:20Z)
Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice [1.0152838128195467]
ランダム短環要素から対数単位格子への$L2$CVP距離が$frac2sqrt6sqrtn$ as $n=2k-1toinfty$に収束することを示す。 Linfty$ノルムに対して、$n$以下のガウス座標の最大値は$O(sqrtlog n)$となり、短発生問題に対する多項式近似係数に変換される。
論文参考訳（メタデータ） (2026-05-17T12:00:59Z)
Tikhonov-regularised projected gradient flow for equality-constrained bilinear quantum control [0.0]
本研究では,$mathcalH=L(0,T;mathbbR)$に対する等式制約制御対象に対する投影型勾配流について検討する。 i) $(_varepsilon)=(_min2+varepsilon2)$; (ii) Objective monotonicity $mathrmdJ/
論文参考訳（メタデータ） (2026-04-29T12:53:58Z)
Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文参考訳（メタデータ） (2026-03-20T01:53:44Z)
Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
制約付き部分空間近似のための一般的なフレームワークを導入する。分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
論文参考訳（メタデータ） (2025-04-29T15:56:48Z)
Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems [2.3721580767877257]
提案手法は,非強弱畳み込みミニマックス問題の解法である。提案アルゴリズムは$tell内の上位定常点であることが証明された。エル $. $. $. $. $. $. $. $. $. $. $. $. $. $. $. $. $
論文参考訳（メタデータ） (2024-11-24T09:46:36Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文参考訳（メタデータ） (2024-08-16T02:33:07Z)
Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
非対称行列分解対象に一定のステップサイズを施した交互勾配降下(AGD)について検討した。階数-r$行列 $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be a absolute constant。
論文参考訳（メタデータ） (2023-05-11T16:07:47Z)
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)
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文参考訳（メタデータ） (2022-11-10T00:40:37Z)
Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文参考訳（メタデータ） (2022-05-27T00:34:03Z)
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)
Constant matters: Fine-grained Complexity of Differentially Private Continual Observation [10.624505781812385]
連続的な観測をカウントするための差分プライベートアルゴリズムに対するきめ細かい誤差境界について検討する。我々は連続観察下で様々な問題に対して具体的な誤差境界を初めて与えている。
論文参考訳（メタデータ） (2022-02-23T11:50:20Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文参考訳（メタデータ） (2021-09-06T14:21:43Z)

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

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