論文の概要: Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression
- arxiv url: http://arxiv.org/abs/2604.10814v1
- Date: Sun, 12 Apr 2026 20:49:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-14 20:13:16.230509
- Title: Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression
- Title（参考訳）: 平均SGDにおけるオンライン共分散推定:軌道回帰によるバッチ平均速度と最小最適度の改善
- Authors: Yijin Ni, Xiaoming Huo,
- Abstract要約: 我々はPolyak-Ruppert averaged gradient descent (SGD)のオンライン共分散行列推定について検討した。
この構造は、このボトルネックがSGDドリフトからヘッセンの情報をサブ線形に蓄積していることを明らかにする。
- 参考スコア（独自算出の注目度）: 12.805268849262243
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study online covariance matrix estimation for Polyak--Ruppert averaged stochastic gradient descent (SGD). The online batch-means estimator of Zhu, Chen and Wu (2023) achieves an operator-norm convergence rate of $O(n^{-(1-α)/4})$, which yields $O(n^{-1/8})$ at the optimal learning-rate exponent $α\rightarrow 1/2^+$. A rigorous per-block bias analysis reveals that re-tuning the block-growth parameter improves the batch-means rate to $O(n^{-(1-α)/3})$, achieving $O(n^{-1/6})$. The modified estimator requires no Hessian access and preserves $O(d^2)$ memory. We provide a complete error decomposition into variance, stationarity bias, and nonlinearity bias components. A weighted-averaging variant that avoids hard truncation is also discussed. We establish the minimax rate $Θ(n^{-(1-α)/2})$ for Hessian-free covariance estimation from the SGD trajectory: a Le Cam lower bound gives $Ω(n^{-(1-α)/2})$, and a trajectory-regression estimator--which estimates the Hessian by regressing SGD increments on iterates--achieves $O(n^{-(1-α)/2})$, matching the lower bound. The construction reveals that the bottleneck is the sublinear accumulation of information about the Hessian from the SGD drift.
- Abstract（参考訳）: 本稿では,Polyak-Ruppert平均確率勾配勾配(SGD)のオンライン共分散行列推定について検討する。
Zhu, Chen and Wu (2023) のオンラインバッチ平均推定器は演算子-ノルム収束率$O(n^{-(1-α)/4})$、最適学習率指数$α\rightarrow 1/2^+$で$O(n^{-1/8})$を得る。
厳密なブロックごとのバイアス分析により、ブロック成長パラメータの修正により、バッチ平均レートが$O(n^{-(1-α)/3})$に改善され、$O(n^{-1/6})$が達成されることが明らかになった。
修正された推定器はヘッセンアクセスを必要とせず、$O(d^2)$メモリを保持する。
我々は、分散、定常性バイアス、非線形性バイアス成分に対する完全な誤差分解を提供する。
また、ハードトランケーションを回避する重み付きアベリング変種についても論じる。
我々は、SGD 軌跡から Hessian-free な共分散を推定するミニマックス率 $ (n^{-(1-α)/2})$ for Hessian-free covariance Estimation from the SGD trajectory: Le Cam lower bound give $Ω(n^{-(1-α)/2}, and a trajectory-regression estimator-- which estimated the Hessian by regressing SGD increments on iterates---achieves $O(n^{-(1-α)/2})$。
この構造は、このボトルネックがSGDドリフトからヘッセンの情報をサブ線形に蓄積していることを明らかにする。
関連論文リスト
- Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions [3.6997773420183866]
本研究では,フォワード反射逆スプリッティング法(FRBS)のための新しい分散還元法を開発した。
ミニバッチのような偏見のない推定器とは異なり、偏見のある変種の開発は基本的な技術的課題に直面している。
ループレスSVRGやSAGAを利用する場合,$mathcalO(n2/3-2)$と$mathcalO(-10/3)$が最良であることを示す。
論文 参考訳（メタデータ） (2026-03-16T17:39:25Z) - Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。
任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。
本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
論文 参考訳（メタデータ） (2026-02-19T17:21:15Z) - Statistical Inference for Linear Functionals of Online Least-squares SGD when $t \gtrsim d^{1+δ}$ [7.884611719110979]
グラディエント・Descent (SGD) は、現代のデータ科学における基礎的な手法となっている。
本研究では,オンライン最小二乗 SGD の線型汎函数に対して,非漸近的ベリー-エッセイン境界を確立する。
論文 参考訳（メタデータ） (2025-10-22T16:25:49Z) - Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime [26.711510824243803]
本研究では, 最適騒音が0または0に近い政権において, 円滑な凸目標に対する勾配降下(SGD)の集団収束保証について検討した。
十分に調整されたステップサイズでは、最後の繰り返しに対してほぼ最適な$widetildeO (1/T + sigma_star/sqrtT)$レートを得る。
論文 参考訳（メタデータ） (2025-07-15T12:52:47Z) - From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。
実現可能な最小二乗の設定において、新しい最上界を創出する。
我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
論文 参考訳（メタデータ） (2025-04-06T18:39:45Z) - TIC-TAC: A Framework for Improved Covariance Estimation in Deep Heteroscedastic Regression [109.69084997173196]
奥行き回帰は、予測分布の平均と共分散を負の対数類似度を用いて共同最適化する。
近年の研究では, 共分散推定に伴う課題により, 準最適収束が生じる可能性が示唆されている。
1)予測共分散は予測平均のランダム性を真に捉えているか?
その結果, TICは共分散を正確に学習するだけでなく, 負の対数類似性の収束性の向上も促進することがわかった。
論文 参考訳（メタデータ） (2023-10-29T09:54:03Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers [13.244654316770815]
我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。
スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。
PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
論文 参考訳（メタデータ） (2021-11-04T15:59:44Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。