論文の概要: Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules

• arxiv url: http://arxiv.org/abs/2608.25551v1
• Date: Wed, 26 Aug 2026 09:02:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-27 14:15:15.694754
• Title: Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules
• Title（参考訳）: 確率最適化における最適速度を超える:軌道適応型停止規則
• Abstract要約: 我々は、新しい信頼系列法と、適応されたプロセスに対する時間一様経験的バーンスタイン不等式を開発する。 結果の停止規則は、自然勾配の地平線より少ない数桁の順序を必要とすることが示される。
• 参考スコア（独自算出の注目度）: 42.38093055717409
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic gradient descent (SGD) is typically analyzed at a deterministic horizon chosen before the algorithm is run, even though practical stopping decisions are made adaptively by inspecting the evolving trajectory. This mismatch creates a fundamental certification problem: fixed-time guarantees do not generally remain valid at data-dependent stopping times, while deterministic horizons derived from worst-case bounds can be highly conservative. We address this problem for strongly convex stochastic optimization by constructing fully observable, trajectory-adaptive upper confidence sequences for the squared distance of the last iterate to the optimizer and the suboptimality of a weighted average. These bounds hold simultaneously over time, attain the optimal $1/t$ decay rate up to iterated-logarithmic factors in the worst case, and adapt to the realized stochastic gradients, allowing SGD to stop as soon as a prescribed accuracy is certified without sacrificing statistical validity. Our approach treats the evolving SGD trajectory as a sequential experiment whose observations provide evidence about the unknown optimization error. To formalize this perspective, we develop new recursive confidence-sequence techniques and a general time-uniform empirical Bernstein inequality for adapted processes with time-varying conditional means and predictable ranges that may grow without bound. We further extend these confidence-sequence constructions to minibatch SGD, with the empirical Bernstein bounds exploiting the realized second-moment structure within each minibatch. Numerical experiments show that the resulting stopping rules can require several orders of magnitude fewer iterations than natural deterministic horizons.
• Abstract（参考訳）: 確率勾配降下(SGD)は、アルゴリズムが実行される前に決定論的地平線で解析されるのが一般的である。 このミスマッチは基本的な認証問題を生じさせる: 固定時間保証はデータ依存の停止時間では一般的に有効ではなく、最悪のケース境界から導かれる決定論的水平線は極めて保守的である。 重み付き平均の2乗距離と2乗平均の2乗距離に対して、完全に観測可能で軌道適応的な高信頼シーケンスを構築することにより、強凸確率最適化のためのこの問題に対処する。 これらの境界は時間とともに同時に保持され、最悪の場合において、最適1/t$の崩壊率を反復対数因子まで達成し、実現された確率勾配に適応することで、統計的妥当性を犠牲にすることなく、SGDが所定の精度で停止できるようにする。 提案手法は,SGD軌道の進化を,未知の最適化誤差の証拠を提供する逐次実験として扱う。 この視点を定式化するために、時間変化条件付きおよび有界に成長する可能性のある予測可能な範囲を持つ適応プロセスに対して、新しい再帰的信頼系列法と、一般の時間一様経験的ベルンシュタイン不等式を開発する。 さらに、これらの信頼系列構造を SGD のミニバッチに拡張し、各ミニバッチ内で実現された第二モーメント構造を利用した経験的ベルンシュタイン境界を求める。 数値実験により、結果の停止規則は自然決定論的地平線よりも数桁少ない繰り返しを必要とすることが示されている。

関連論文リスト

• High-Probability Convergence of SGD via Batched Updates [4.862625283098196]
  Batched SGDは、オンラインエポックを最適化に反復するシンプルなバリエーションである。 我々の主な貢献は、このメカニズムが驚くほど単純な高確率解析を可能にすることを示している。
  論文  参考訳（メタデータ） (2026-09-11T12:17:18Z)
• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max最適化は、現代の機械学習に応用されているため、注目を集めている。 我々は、勾配降下(SGDA)の包括的理論を提供する。 我々は,Stoc-GDAMとStoc-TRmaxという新たなクリッピングフリーアルゴリズムを開発し,グラディエントクリッピングを使わずに,目標精度への最適依存を実現する。
  論文  参考訳（メタデータ） (2026-09-05T12:49:28Z)
• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences [51.56484100374058]
  凸最適化のための勾配降下(SGD)の停止規則について検討した。 我々は、投影されたSGDの重み付き平均準最適度に対して、任意の有意、データ依存の高信頼シーケンスを開発する。 これらは、厳格でタイムユニフォームなパフォーマンス保証と、有限時間$varepsilon$-optimality証明書である。
  論文  参考訳（メタデータ） (2025-12-15T09:26:45Z)
• Learning the Optimal Stopping for Early Classification within Finite Horizons via Sequential Probability Ratio Test [11.199585259018459]
  時系列の早期分類に最適な停止時間を提供するSPRT(Sequential Probability Ratio Test)による、時間に敏感な機械学習の利点。 入力長が有限である有限地平線シナリオでは、後ろ向きの誘導を必要とするため、最適停止規則を決定することが計算集約化される。 本稿では,SPRTベースのフレームワークであるFIRMBOUNDを紹介する。
  論文  参考訳（メタデータ） (2025-01-29T23:54:46Z)
• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。 本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
  論文  参考訳（メタデータ） (2024-04-03T00:41:19Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Bounding the expected run-time of nonconvex optimization with early stopping [2.7648976108201815]
  本研究は,検証関数に基づく早期停止を用いた勾配に基づく最適化アルゴリズムの収束性について検討する。 我々は、この停止規則が適切に定義されていることを保証する条件を導出し、この基準を満たすのに必要なイテレーション数と勾配評価の期待値のバウンダリを提供する。
  論文  参考訳（メタデータ） (2020-02-20T16:43:37Z)

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

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