論文の概要: Settling the Burn-in Gap: Sharp Risk Bounds for Tail-Averaged SGD in Linear Regression
- arxiv url: http://arxiv.org/abs/2611.13383v1
- Date: Tue, 10 Nov 2026 00:00:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-12 04:24:43.630096
- Title: Settling the Burn-in Gap: Sharp Risk Bounds for Tail-Averaged SGD in Linear Regression
- Title(参考訳): バーンインギャップの定着:リニア回帰における平均SGDのシャープリスク境界
- Abstract要約: 本研究では,高次元線形回帰に対するテール・アブリゲーティングによるオンライン勾配勾配勾配の一定段階の過大なリスクについて検討した。
我々は, スペクトルフィードバック条件が2つの具体的な定常状態で満たされていることを証明した。
- 参考スコア(独自算出の注目度): 50.91983233376599
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the excess risk of constant-stepsize online stochastic gradient descent (SGD) with tail-averaging for high-dimensional linear regression. Building on the instance-dependent spectral framework of Zou et al. (2021), we establish matching initialization-explicit upper and lower bounds on the total excess risk of tail-averaged SGD in terms of the population covariance spectrum $\mathbf{H}$ and initialization $\mathbf{w}_0-\mathbf{w}^*$ whenever a trajectory spectral feedback condition holds. Existing analyses exhibit a fundamental gap in the effective variance: the upper bound of Zou et al. (2021) retains an undamped contribution from the initial error in the head eigenspace $\mathbf{I}_{0:k^\dagger}$, whereas their lower bound omits the variance induced by the head initialization altogether. We show that both the existing upper and lower bounds are loose: the single-hop fast-mode variance contribution from the head initialization is exponentially damped during the burn-in phase, whereas fourth-moment energy scattered from the head initialization into slow spectral modes during the early burn-in steps survives undamped into the averaging window. We prove that our spectral feedback condition is satisfied in two concrete constant-stepsize regimes: (i) for arbitrary covariance spectra $\mathbf{H}$ and any finite horizon, under an explicit horizon-dependent stepsize chosen prior to execution; and (ii) for polynomially decaying spectra $λ_i\asymp i^{-a}$ ($a>1$), under a single horizon-independent positive stepsize. Finally, we complement these positive results with explicit one- and two-dimensional separation constructions proving an exponential-versus-polynomial gap in the lower bound of Zou et al. (2021) and showing why fourth-moment assumptions alone cannot determine the asymptotic exponential decay rate without additional structural conditions.
- Abstract(参考訳): 本研究では,高次元線形回帰に対するテール・アラギングを用いた一定段階オンライン確率勾配勾配勾配(SGD)の過大なリスクについて検討した。
Zou et al (2021) のインスタンス依存スペクトルフレームワークに基づいて、軌道的スペクトルフィードバック条件が成立するたびに、人口共分散スペクトル $\mathbf{H}$ と初期化 $\mathbf{w}_0-\mathbf{w}^*$ で、テール平均 SGD の総過剰リスクに関する初期化-明示的上界と下界を一致させる。
Zou et al (2021) の上界は、ヘッド固有空間 $\mathbf{I}_{0:k^\dagger}$ の初期誤差からの無害な寄与を保ち、一方、それらの下界はヘッド初期化によって引き起こされる分散を完全に省略する。
その結果, ヘッド初期化による単一ホップの高速モード分散寄与は, バーンイン段階で指数的に減衰し, 一方, 初期燃焼時にヘッド初期化から緩やかなスペクトルモードに分散した4次モーメントエネルギーは, 平均燃焼窓に無害で残されていることがわかった。
我々は、我々のスペクトルフィードバック条件が2つの具体的な一定段階の条件で満たされていることを証明した。
(i) 任意の共分散スペクトル $\mathbf{H}$ および任意の有限地平線に対して、実行前に選択された明示的地平依存性のステップサイズの下で
(ii) 多項式崩壊スペクトル $λ_i\asymp i^{-a}$$ (a>1$) に対して、1つの地平線非依存の正の次数である。
最後に、これらの正の結果を、Zau et al (2021) の下界における指数-逆-ポリノミアルギャップを示す明示的な1次元と2次元の分離構造で補い、なぜ4次モーメント仮定だけでは追加構造条件なしで漸近的指数的崩壊速度を決定できないのかを示す。
関連論文リスト
- Global Exponential Convergence of Two-Layer Linear Network Training [18.359948110720747]
我々は,スムーズなPolyak-Lojasiewicz予測器の損失で訓練された広帯域2層線形ネットワークに対して,リッチスケーリングの明示的な速度で大域指数(線形)収束を証明した。
論文 参考訳(メタデータ) (2026-10-07T03:13:18Z) - Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds [1.6582968942719265]
一様雑音-モーメンタリティ境界は、距離によって変動が増加する勾配を除外する。
直接降下すると、スムーズな転位引数が3エプシロン6$を回復する。
局所化半径は、非レート仮定、クリッピング正規化、運動量、バッチサイズの増加といった境界から導かれる。
論文 参考訳(メタデータ) (2026-09-24T19:37:07Z) - Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
重畳の非線形観測回数が限られていることから, スパースベクトルの回復を考察する。
本稿では, 一般化畳み込みペナルティとハマー化データ忠実度を組み合わせた正規化に基づくフレームワークを提案する。
仮に局所的な定常点を保った位数$sqrtslog(n)/m$の誤差境界を導出する。
論文 参考訳(メタデータ) (2026-07-12T07:29:39Z) - Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence [50.719298242863744]
Underdamped Langevin dynamics (ULD) は Gibbs 分布の$propto e-V$ に広く使われているサンプルである。
離散化LDDにおける最初の次元自由なKL分散境界を証明した。
論文 参考訳(メタデータ) (2026-03-02T22:14:38Z) - Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression [28.3662709740417]
ロジスティック回帰では、勾配降下(GD)は最大$ell$-margin解に収束しながらノルムで分岐する。
本研究は,高次元ロジスティック回帰における早期停止による追加正則化効果について検討する。
論文 参考訳(メタデータ) (2025-02-18T21:04:06Z) - A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。
この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
論文 参考訳(メタデータ) (2022-10-27T17:59:09Z) - Sharp Bounds for Federated Averaging (Local SGD) and Continuous
Perspective [49.17352150219212]
Federated AveragingFedAvg(ローカルSGD)は、Federated Learning(FL)で最も人気のあるアルゴリズムの1つである。
微分方程式(SDE)の観点から、この量を解析する方法を示す。
論文 参考訳(メタデータ) (2021-11-05T22:16:11Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳(メタデータ) (2021-09-24T14:48:20Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳(メタデータ) (2021-03-23T17:15:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。