論文の概要: Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications

• arxiv url: http://arxiv.org/abs/2508.07473v1
• Date: Sun, 10 Aug 2025 20:17:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 21:23:28.871634
• Title: Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications
• Title（参考訳）: 重機によるオンライン凸最適化 - 古いアルゴリズム,新しいレグレット,アプリケーション
• Authors: Zijian Liu,
• Abstract要約: オンライン凸最適化 (Online Convex Optimization, OCO) では、勾配が有限な場合、多くのアルゴリズムは確実にサブ線形後悔を保証する。 この研究は、より困難な重み付け設定において、OCOの異なる古いアルゴリズムを調べる。 注目すべきは、これらの後悔境界は全てのパラメータで完全に最適であることである。
• 参考スコア（独自算出の注目度）: 7.195047020440563
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In Online Convex Optimization (OCO), when the stochastic gradient has a finite variance, many algorithms provably work and guarantee a sublinear regret. However, limited results are known if the gradient estimate has a heavy tail, i.e., the stochastic gradient only admits a finite $\mathsf{p}$-th central moment for some $\mathsf{p}\in\left(1,2\right]$. Motivated by it, this work examines different old algorithms for OCO (e.g., Online Gradient Descent) in the more challenging heavy-tailed setting. Under the standard bounded domain assumption, we establish new regrets for these classical methods without any algorithmic modification. Remarkably, these regret bounds are fully optimal in all parameters (can be achieved even without knowing $\mathsf{p}$), suggesting that OCO with heavy tails can be solved effectively without any extra operation (e.g., gradient clipping). Our new results have several applications. A particularly interesting one is the first provable convergence result for nonsmooth nonconvex optimization under heavy-tailed noise without gradient clipping. Furthermore, we explore broader settings (e.g., smooth OCO) and extend our ideas to optimistic algorithms to handle different cases simultaneously.
• Abstract（参考訳）: オンライン凸最適化 (Online Convex Optimization, OCO) では、確率勾配が有限分散であるとき、多くのアルゴリズムが確実に機能し、サブ線形後悔を保証する。 しかし、勾配推定が重い尾を持つ場合、すなわち確率勾配は、ある$\mathsf{p}$-th Central moment に対して有限$\mathsf{p}$-th Central moment しか持たない。 この研究は、OCO(Online Gradient Descentなど)のさまざまな古いアルゴリズムを、より困難なヘビーテール設定で検証する。 標準的な有界領域仮定の下では、アルゴリズム的な修正なしにこれらの古典的手法に対する新たな後悔を確立する。 注目すべきは、これらの後悔境界は全てのパラメータにおいて完全に最適であり($\mathsf{p}$を知らない場合でも達成できる)、重い尾を持つOCOは余分な操作(勾配クリッピングなど)なしで効果的に解けることを示唆している。 我々の新しい結果にはいくつかの応用がある。 特に興味深いのは、勾配切り抜きのない重み付き雑音下での非滑らかな非凸最適化のための最初の証明可能な収束結果である。 さらに、より広い設定(例えば、スムーズなOCO)を探求し、アイデアを楽観的なアルゴリズムに拡張し、異なるケースを同時に処理します。

関連論文リスト

• Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints [12.624604051853657]
  線形不等式制約を用いた非コンパクト最適化問題に対するスムーズな原始双対アルゴリズムを提案する。 我々のアルゴリズムは、各サンプルの1つの勾配に基づいて、シングルループの反復である。 既存の手法とは異なり、我々のアルゴリズムは自由なサブ、大きなサイズ、パラメータの増加であり、実現可能性を保証するためにデュアル変数更新を使用する。
  論文  参考訳（メタデータ） (2025-04-10T09:59:43Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。 本手法の主な考え方は,状況認識による$alphaの適応である。 これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
  論文  参考訳（メタデータ） (2023-09-12T14:36:13Z)
• Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
  重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。 本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
  論文  参考訳（メタデータ） (2023-03-22T03:05:28Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。 ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。 1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
  論文  参考訳（メタデータ） (2021-09-18T07:08:11Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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