論文の概要: From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization

• arxiv url: http://arxiv.org/abs/2606.02948v1
• Date: Mon, 01 Jun 2026 23:01:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-03 22:00:04.634028
• Title: From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
• Title（参考訳）: 非凸から強凸へ:オンライン最適化のための曲率適応FTPL
• Authors: Moses Charikar, Chirag Pabbaraju, Ambuj Tewari,
• Abstract要約: 曲率適応性はオンライン最適化における古典的なテーマである。 提案アルゴリズムは,過去の情報のみを用いて選択した様々なスケールで,固定スケールを置換することを示す。
• 参考スコア（独自算出の注目度）: 31.38302438096483
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Curvature adaptivity is a classical theme in online optimization: for convex Lipschitz losses, adaptive methods interpolate between the optimal $O(\sqrt{T})$ regret for general convex losses and $O(\log T)$ regret under strong convexity. Recent work has shown that Follow-the-Perturbed-Leader (FTPL) achieves optimal $O(\sqrt{T})$ regret even for online non-convex Lipschitz losses, assuming access to an approximate offline-optimization oracle, but these guarantees do not exploit curvature. We show that FTPL can be made curvature-adaptive in the non-convex setting, without knowing in advance how curvature will accumulate over time. Our algorithm replaces the fixed perturbation scale of standard FTPL with a time-varying scale chosen using only past information. We give a simple follow-the-leader tuning rule for this scale and show that it competes, up to constants, with the best choice in hindsight. The resulting method achieves $O(\sqrt{T})$ regret for arbitrary non-convex Lipschitz losses and improves as cumulative curvature grows; with sufficiently accurate oracle calls, it achieves $O(\log T)$ regret when cumulative curvature grows linearly, which includes the classical strongly convex regime. We complement these upper bounds with matching lower bounds for prescribed cumulative-curvature sequences, already for one-dimensional convex losses, showing that the tradeoff between worst-case non-convex regret and curvature-driven fast rates is intrinsic.
• Abstract（参考訳）: 曲率適応性はオンライン最適化における古典的なテーマであり、凸リプシッツの損失に対して、最適$O(\sqrt{T})$後悔と強い凸性の下での後悔$O(\log T)$後悔とを補間する。 最近の研究によると、Follow-the-Perturbed-Leader (FTPL) はオンラインの非凸リプシッツ損失に対しても最適な$O(\sqrt{T})$ regretを達成している。 FTPLは時間とともにどのように曲率を蓄積するかを事前に知ることなく、非凸設定で曲率に適応できることを示す。 提案アルゴリズムは,標準FTPLの固定摂動尺度を過去の情報のみを用いて選択した時間変化尺度に置き換える。 我々は、このスケールで単純なフォロー・ザ・リードのチューニングルールを与え、それが競合し、定数まで、そして後見で最良の選択であることを示す。 その結果、任意の非凸リプシッツ損失に対して$O(\sqrt{T})$ regretを達成し、累積曲率の増加とともに改善する。 この上界と, 所定の累積曲率列に対する下界との整合性は, 既に1次元凸損失に対して成立しており, 最悪の非凸後悔と曲率駆動の速さとのトレードオフが本質的であることを示す。

関連論文リスト

• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  本研究では, 楽観的な勾配予測が, 最悪の後悔の保証を予測順応的に改善できるかどうかを考察する。 鍵となるアイデアは、分散が勾配ノルムではなく予測誤差でスケールする、新しい分散還元勾配推定器である。 我々は、$(sqrtmathbbE[S_T])$としてスケールする情報理論の下限を確立し、最も達成可能な予測適応的後悔の基本的な特徴を提供する。
  論文  参考訳（メタデータ） (2026-05-21T08:57:38Z)
• Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle [51.714334316332476]
  Local Lは制約付き最適化のための新しいプロジェクションフリー型である。 局所LMOはGD(Gradient Descent)のオラクルと見なされる。
  論文  参考訳（メタデータ） (2026-05-09T10:03:24Z)
• Non-stationary Bandit Convex Optimization: A Comprehensive Study [28.086802754034828]
  Bandit Convex Optimizationは、シーケンシャルな意思決定問題のクラスである。 非定常環境でこの問題を研究する。 非定常性の標準的な3つの基準の下で、後悔を最小限に抑えることを目指しています。
  論文  参考訳（メタデータ） (2025-06-03T15:18:41Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness [2.315156126698557]
  我々は,非Lipschitz,非滑らかな損失を伴って,オンライン凸最適化のためのデータ依存境界の最初の例を紹介する。 最悪事例におけるサブ線形後悔率を示すアルゴリズムを提案するとともに、データが「容易」である場合の対数的後悔を実現する。
  論文  参考訳（メタデータ） (2023-05-23T11:16:01Z)
• Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter [14.040676498310198]
  我々は、全てのデータに対して最悪のリプシッツパラメータを持つ損失関数を持つ差分プライベート(DP)不等式最適化(SO)について検討する。 スムーズな損失関数に対して、我々は最先端の過剰リスクを持つ線形時間アルゴリズムを提供する。 また,非最適凸損失関数を扱う最初のアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2022-09-15T16:03:23Z)
• Scale-free Unconstrained Online Learning for Curved Losses [1.5147172044848798]
  コンパレータのノルム$U$と勾配の最大ノルム$G$に同時に適応する可能性を検討する。 意外なことに、最近の研究では1ドル=Lipschitz損失の特定のケースにおいて、適応性に対するそのような価格が不要であることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T14:10:35Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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