論文の概要: Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2606.08028v1
• Date: Sat, 06 Jun 2026 07:40:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:05.672871
• Title: Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
• Title（参考訳）: オンライン凸最適化のための雑音適応型高確率レギュレータ境界
• Abstract要約: オンライン凸最適化 (OCO) における高い確率的後悔境界について, 強い凸損失を伴って検討した。 雑音適応性, フィードバック構造, 制約満足度の交点において, オープンな質問を解決するための3つの結果を確立する。
• 参考スコア（独自算出の注目度）: 12.903796669387809
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses and establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction. For the full-information setting with sub-Gaussian stochastic gradients, we prove a noise-adaptive high-probability regret bound in which the martingale deviation term scales with the noise level $σ$ rather than the gradient bound $G$, yielding a multiplicative improvement of $G/σ$ over the classical Azuma-Hoeffding baseline. Our analysis introduces an exponential supermartingale argument that bypasses the bounded-difference requirement of Freedman's inequality, enabling direct treatment of unbounded sub-Gaussian noise without truncation artifacts. For bandit feedback, we prove a minimax lower bound: the high-probability regret scales linearly in $\log(1/δ)$, in contrast to the $\sqrt{\log(1/δ)}$ confidence cost under full information. This constitutes a formal separation in the confidence cost of strongly convex OCO across feedback models. Regarding constrained OCO with stochastic constraints satisfying a Slater condition, we provide simultaneous high-probability guarantees for both cumulative regret and long-run constraint violation, achieving $\mathcal{O}(\sqrt{T\log(m/δ)})$ regret and $\mathcal{O}(\sqrt{T}/(ζδ) + m\sqrt{T\log(m/δ)})$ violation. Synthetic experiments corroborate all theoretical predictions.
• Abstract（参考訳）: 我々は,オンライン凸最適化(OCO)における高確率後悔境界について,強い凸損失を伴って検討し,雑音適応性,フィードバック構造,制約満足度の交点におけるオープン質問を解決する3つの結果を確立する。 ガウス以下の確率勾配を持つ完全情報集合に対して、マルティンゲール偏差項が勾配境界の$G$よりも$σ$でスケールし、古典的な東ホエーフディング基底線に対して$G/σ$の乗法的改善をもたらすような雑音適応的高確率的後悔境界を証明した。 解析では,フリードマンの不等式の有界差要求を回避し,非ガウス雑音の非有界化を回避できるという指数関数的スーパーマーチンゲーレの議論を紹介した。 バンドイットフィードバックでは、極小値の最小値が証明される: 高確率の後悔は、フル情報の下での信頼コストと対照的に$\log(1/δ)$で線形にスケールする。 これは、フィードバックモデル間で強い凸OCOの信頼性コストを正式に分離する。 Slater 条件を満たす確率的制約を持つ制約付き OCO について、累積的後悔と長期的制約違反を同時に保証し、$\mathcal{O}(\sqrt{T\log(m/δ)})$ regret と $\mathcal{O}(\sqrt{T}/(\sqrt) + m\sqrt{T\log(m/δ)})$ violation を達成する。 合成実験はすべての理論的予測を裏付ける。

関連論文リスト

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise [7.7753818665096945]
  勾配雑音を考慮したスムーズな非適応最適化のためのシャープな下界を証明した。 これは標準上界と一致し、[Arvani et al.] によって提起された、ほぼ確実に有界なオラクル誤差が有界な分散よりも優れているかどうかの問題を解く。
  論文  参考訳（メタデータ） (2026-08-10T01:45:56Z)
• Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
  Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。 このような悪条件下でSGDが確実に成功できるかどうかを精査する。
  論文  参考訳（メタデータ） (2025-08-06T20:09:41Z)
• Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises [55.43924214633558]
  本稿では,サブワイブルノイズとSsBCノイズの2種類のノイズに着目した。 これら2つのノイズ仮定の下では、凸最適化と滑らかな最適化の文脈において、SFOMの不規則および高確率収束が研究されている。
  論文  参考訳（メタデータ） (2025-07-17T16:48:45Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。 ノイズモーメントを仮定することなく、幅広い種類の非線形性を保証する。
  論文  参考訳（メタデータ） (2024-10-17T18:25:28Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noise [4.9495085874952895]
  我々はAdamが高い確率で定常点に収束できることを示し、$mathcalOleft(rm poly(log T)/sqrtTright)$を座標ワイドな「アフィン」ノイズ分散の下で表す。 また、Adamの閉包は$mathcalOleft(rm poly(left T)right)$の順序でノイズレベルに適応していることも明らかにされている。
  論文  参考訳（メタデータ） (2023-11-03T15:55:53Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。 我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。 我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
  論文  参考訳（メタデータ） (2022-04-06T13:50:33Z)
• Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
  雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。 我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。 他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
  論文  参考訳（メタデータ） (2021-10-21T19:22:14Z)

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

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