論文の概要: New Bounds for the Last Iterate of the Stochastic subGradient Method
- arxiv url: http://arxiv.org/abs/2606.24879v1
- Date: Tue, 23 Jun 2026 17:55:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-24 22:16:49.136646
- Title: New Bounds for the Last Iterate of the Stochastic subGradient Method
- Title（参考訳）: 確率的部分勾配法の最終繰り返しに対する新しい境界
- Authors: Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni, Andrea Paudice,
- Abstract要約: 本稿では,1次元凸リプシッツ目標に対する下段法の最後の繰り返しについて検討する。
最後の繰り返しは1/sqrt n$の順序の最適化誤差を特徴とする。
i.d.仮定がなければ、最適化誤差は位数 $(log n)/sqrt n$ となる。
- 参考スコア（独自算出の注目度）: 11.179752660122281
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon $n$, we consider the standard fixed stepsizes $η=Θ(1/\sqrt n)$. We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order $1/\sqrt n$, thereby removing the extra $(\log n)$ factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order $(\log n)/\sqrt n$. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.
- Abstract（参考訳）: 一次元凸リプシッツ目的に対する確率的下次法の最後の繰り返しについて検討する。
固定地平線$n$ に対して、標準固定段数 $η= η(1/\sqrt n)$ を考える。
そのような段階的なポリシー、すなわち一様有界な分散を持つ劣次雑音の下では、最後の繰り返しは位数1/\sqrt n$の最適化誤差を特徴とし、従って既存の一般境界に存在する余分な$(\log n)$ factorを除去する。
一方、i.d.仮定がなければ、最適化誤差は位数 $(\log n)/\sqrt n$ となる。
したがって、一様有界分散仮定だけでは、SsGMの最後の繰り返しは次元 1 においても最適であり、コーレンとセガル(英語版)(COLT, 2020)で生じる負の開問題を解く。
関連論文リスト
- Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - Gradient Descent's Last Iterate is Often (slightly) Suboptimal [30.492009313545257]
我々は、勾配降下(GD)または最適変量(SGD)を用いて凸リプシッツ関数を最小化する設定を考える。
GDのノイズレスの場合においても、常に繰り返し保証を考えると、$T$の過剰なポリログ係数を避けることは不可能である。
論文 参考訳（メタデータ） (2026-04-15T13:33:08Z) - 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) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - The Convergence Rate of SGD's Final Iterate: Analysis on Dimension
Dependence [2.512827436728378]
Gradient Descent (SGD) は最適化において最も単純で一般的な手法の一つである。
定次元設定におけるSGDの最終点収束を特徴付ける方法を示す。
論文 参考訳（メタデータ） (2021-06-28T11:51:04Z) - 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) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。