論文の概要: Optimal Competitive Ratios for Chasing Convex Functions with Quadratic Growth

• arxiv url: http://arxiv.org/abs/2611.08078v1
• Date: Thu, 05 Nov 2026 14:27:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-07 04:55:13.536313
• Title: Optimal Competitive Ratios for Chasing Convex Functions with Quadratic Growth
• Title（参考訳）: 二次成長を伴う連接関数の最適競合比
• Abstract要約: チャット凸関数は近年注目を集めており、学習者と敵とのゲームとして定式化することができる。 各ラウンドにおいて、敵は凸関数を明らかにし、学習者は決定を選択して、その決定を変更するためのヒットコストと移動コストを発生させる。 2種類の移動コストの下で凸関数追従のための最適次元自由競争比を確立する。
• 参考スコア（独自算出の注目度）: 18.568024376970396
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Chasing convex function has attracted much attention in recent years, which can be formulated as a game between a learner and an adversary. In each round, the adversary reveals a convex function, and the learner selects a decision and incurs a hitting cost and a movement cost for changing its decision. The performance of the learner is measured by the \emph{competitive ratio}, which compares its cumulative cost with that of an optimal offline decision sequence. For Euclidean movement, existing upper and lower bounds for $κ$-well-conditioned functions exhibit a polynomial gap. For squared Euclidean movement, dimension-free competitive guarantees have been established under quadratic growth, but the optimal competitive ratio remains unclear. In this paper, we establish optimal dimension-free competitive ratios for convex function chasing under two types of movement costs. For Euclidean movement, we propose Clipped Proximal Descent (CPD), which combines a balanced proximal step with a clipped correction toward the current minimizer. CPD achieves an $O(κ^{1/3})$ competitive ratio for smooth convex functions satisfying quadratic growth, improving the previous $O(\sqrtκ)$ upper bound and matching the existing $Ω(κ^{1/3})$ lower bound. For squared Euclidean movement, we establish the exact optimal dimension-free competitive ratio for convex functions satisfying quadratic growth. Our result is based on a new tight competitive analysis of Regularized Online Balanced Descent (R-OBD) and a matching lower bound against randomized algorithms.
• Abstract（参考訳）: チャット凸関数は近年注目を集めており、学習者と敵とのゲームとして定式化することができる。 各ラウンドにおいて、敵は凸関数を明らかにし、学習者は決定を選択して、その決定を変更するためのヒットコストと移動コストを発生させる。 学習者の性能は, 累積コストと最適オフライン決定シーケンスの総和を比較対象とする<emph{competitive ratio}によって測定される。 ユークリッド運動に対しては、$κ$-well-conditioned function の既存の上界と下界は多項式ギャップを示す。 正方形ユークリッド運動では、2次成長の下で次元自由競争保証が確立されているが、最適競争比はいまだ不明である。 本稿では,2種類の移動コストの下で,凸関数追従のための最適次元自由競争比を確立する。 ユークリッド運動に対しては、平衡した近位ステップと電流最小値に対するクリップ補正を組み合わせたクリッピング近位周期(CPD)を提案する。 CPDは2次成長を満たす滑らかな凸函数に対する$O(κ^{1/3})$競争比を達成し、以前の$O(\sqrtκ)$上界を改善し、既存の$Ω(κ^{1/3})$下界と一致する。 正方形ユークリッド運動に対しては、二次成長を満たす凸函数の正確な次元自由競争比を確立する。 この結果は,R-OBD (Regularized Online Balanced Descent) の新たな厳密な競合解析と,ランダム化アルゴリズムとの整合性に基づく。

関連論文リスト

• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
  我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
  論文  参考訳（メタデータ） (2025-06-03T06:31:59Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Two-Timescale Optimization Framework for Sparse-Feedback Linear-Quadratic Optimal Control [3.746304628644379]
  The $mathcalHfeedback$-guaranteed sparse-feedback linear-quadratic (LQ) optimal control with convex parameterization and convex-bounded uncertainty。
  論文  参考訳（メタデータ） (2024-06-17T03:17:33Z)
• Online Convex Optimization with Switching Cost and Delayed Gradients [7.903539618132858]
  オンラインアルゴリズムは、前の目的関数の勾配情報のみを用いて、その動作を選択することができる。 2次切替コストのOCO問題の競合比は、少なくとも4(L + 5) + frac16(L + 5)mu$である。 2次・線形切替コストの最適競争比率は、制限情報設定において根本的に異なると結論付けている。
  論文  参考訳（メタデータ） (2023-10-18T11:06:06Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Chasing Convex Bodies and Functions with Black-Box Advice [7.895232155155041]
  ブラックボックスアドバイスによる凸関数追跡の問題点を考察する。 オンラインの意思決定者は、$textitConsistency$.com($textitConsistency$.com)と呼ばれる、うまく機能するときにアドバイスに匹敵するコストを求める。 本稿では,この問題の凸性を利用して,この制限を回避できる2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-23T15:30:55Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)

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

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