論文の概要: Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

• arxiv url: http://arxiv.org/abs/2611.01155v1
• Date: Sat, 31 Oct 2026 17:47:59 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:31:13.061083
• Title: Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
• Title（参考訳）: ポリークラッパート平均確率勾配の予測複雑性に関する下界
• Abstract要約: すべての固定指数 $in(1/2,1)$ に対して、一次元の滑らかで強凸な例は、コルモゴロフと凸距離における位数 $n1/2-+n-1$ の制限的分散を伴う近似誤差を持つ。 非線形バイアスは、ガウス参照が有限線型化分散を使用するときでさえ$n1/2-$に寄与する。
• 参考スコア（独自算出の注目度）: 15.054399128586232
• License:
• Abstract: In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent $γ\in(1/2,1)$, a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order $n^{1/2-γ}+n^{γ-1}$ in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of $γ$. The nonlinear bias contributes $n^{1/2-γ}$ even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order $n^{-(1-γ)/2}$ for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error $\varepsilon$ on this example takes order $\varepsilon^{-4}$ iterations for the best choice $γ=3/4$. Achieving both Gaussian approximation and relative mean variance-estimation errors at most $\varepsilon$ uniformly over the model class requires at least order $\varepsilon^{-6}$ iterations for every fixed $γ$.
• Abstract（参考訳）: 本稿では,ポリアク・ルパートト平均確率勾配勾配のガウス近似の急激な下界を多項式的に減少するステップサイズで確立する。 すべての固定指数 $γ\in(1/2,1)$ に対して、一次元の滑らかで強凸な例は、コルモゴロフと凸距離において位数 $n^{1/2-γ}+n^{γ-1}$ の制限分散を持つ近似誤差を持つ。 これは、$γ$の範囲における既存の上限値と一致する。 非線形バイアスは、ガウス参照が有限線型化分散を使用するときでさえ$n^{1/2-γ}$に寄与する。 また、スカラー二次族上の1つのSGD軌道からの制限分散を推定する相対平均誤差に対して、$n^{-(1-γ)/2} の下位境界を導出する。 この例で近似誤差 $\varepsilon$ を達成するには、最良の選択に対して $γ=3/4$ を順序 $\varepsilon^{-4}$ とする。 モデルクラス上で、ガウス近似と相対平均分散推定誤差を最大$\varepsilon$均一に達成するには、固定されたすべての$γ$に対する少なくとも順序$\varepsilon^{-6}$反復が必要である。

関連論文リスト

• When Momentum Helps Polyak--Ruppert Averaging [75.70186756364649]
  有限ランの到達速度と、それらがどの程度並列化できるかを特徴付ける。 加法雑音を伴う強凸二次群に対しては、オンライン・オフライン橋の証明を行う。
  論文  参考訳（メタデータ） (2026-10-20T10:29:50Z)
• Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization [2.834413535942792]
  非畳み込みミニマックス最適化における一階アルゴリズムの下位境界を確立する。 私たちの貢献は、分散還元を許容するゼロ境界クラスに対する下界である。 これらの結果は、凹凸と凹凸構造をまたいだ複雑さの障壁を同定する。
  論文  参考訳（メタデータ） (2026-10-01T13:24:15Z)
• Convex Optimization Is Free When Accuracy Is Expensive [18.56538898519597]
  我々は、勾配を正確に評価できないときに凸最適化を研究するが、精度$$$で$-$のように計算が成長するアルゴリズムの階層によってのみ近似される。 損失関数の最小化に要するコストは,問題要求の精度での勾配の1つの評価よりも,$のみに依存する。
  論文  参考訳（メタデータ） (2026-09-28T15:30:18Z)
• Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds [1.6582968942719265]
  一様雑音-モーメンタリティ境界は、距離によって変動が増加する勾配を除外する。 直接降下すると、スムーズな転位引数が3エプシロン6$を回復する。 局所化半径は、非レート仮定、クリッピング正規化、運動量、バッチサイズの増加といった境界から導かれる。
  論文  参考訳（メタデータ） (2026-09-24T19:37:07Z)
• Estimation of the sub-Gaussian parameter [7.4076878426925035]
  準ガウス確率変数 $X$ は 2_* = s_upin mathbbR L()$ ここで $L() = frac22 log mathbbE eX$ は重み付き累積生成関数である。 ガウス以下の確率変数が多用されているにもかかわらず、$2_*$の推定はほとんど注目されず、まだよく理解されていない。
  論文  参考訳（メタデータ） (2026-06-04T16:48:31Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• 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)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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