論文の概要: Improved Impossible Tuning and Lipschitz-Adaptive Universal Online Learning with Gradient Variations

• arxiv url: http://arxiv.org/abs/2505.21095v1
• Date: Tue, 27 May 2025 12:22:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-28 17:05:58.635736
• Title: Improved Impossible Tuning and Lipschitz-Adaptive Universal Online Learning with Gradient Variations
• Title（参考訳）: リプシッツ適応型ユニバーサルオンライン学習と非可視チューニングの改善
• Authors: Kei Takemura, Ryuta Matsuno, Keita Sakuma,
• Abstract要約: オンライン学習における中心的な目標は、未知の問題の特徴への適応性を達成することである。 本稿では,大規模学習率を用いた予備的な初期ラウンドによる新しい楽観的オンラインミラー降下アルゴリズムを提案する。 我々は、標準仮定の下で最先端のGV境界とLAを同時に達成する最初のUOLアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 1.9897061813159418
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: A central goal in online learning is to achieve adaptivity to unknown problem characteristics, such as environmental changes captured by gradient variation (GV), function curvature (universal online learning, UOL), and gradient scales (Lipschitz adaptivity, LA). Simultaneously achieving these with optimal performance is a major challenge, partly due to limitations in algorithms for prediction with expert advice. These algorithms often serve as meta-algorithms in online ensemble frameworks, and their sub-optimality hinders overall UOL performance. Specifically, existing algorithms addressing the ``impossible tuning'' issue incur an excess $\sqrt{\log T}$ factor in their regret bound compared to the lower bound. To solve this problem, we propose a novel optimistic online mirror descent algorithm with an auxiliary initial round using large learning rates. This design enables a refined analysis where a generated negative term cancels the gap-related factor, resolving the impossible tuning issue up to $\log\log T$ factors. Leveraging our improved algorithm as a meta-algorithm, we develop the first UOL algorithm that simultaneously achieves state-of-the-art GV bounds and LA under standard assumptions. Our UOL result overcomes key limitations of prior works, notably resolving the conflict between LA mechanisms and regret analysis for GV bounds -- an open problem highlighted by Xie et al.
• Abstract（参考訳）: オンライン学習における中心的な目標は、勾配変動(GV)、関数曲率(Universal Online Learning, UOL)、勾配スケール(Lipschitz Adaptivity, LA)など、未知の問題特性への適応性を達成することである。 同時にこれらを最適な性能で達成することは大きな課題であり、一部には専門家のアドバイスによる予測アルゴリズムの制限がある。 これらのアルゴリズムはしばしばオンラインアンサンブルフレームワークのメタアルゴリズムとして機能し、そのサブ最適性はUOL全体のパフォーマンスを阻害する。 具体的には、'inpossible tuning'' 問題に対処する既存のアルゴリズムは、下界と比較して、余剰な$\sqrt{\log T}$因子を発生させる。 この問題を解決するために,大規模な学習率を用いた補助的な初期ラウンド付き楽観的なオンラインミラー降下アルゴリズムを提案する。 この設計は、生成した負項がギャップ関連因子をキャンセルし、不可能なチューニング問題を最大$\log\log T$ factorまで解決する洗練された解析を可能にする。 改良されたアルゴリズムをメタアルゴリズムとして活用し、標準仮定の下で最先端のGV境界とLAを同時に達成する最初のUOLアルゴリズムを開発した。 我々の UOL の結果は,従来の作業の重要な制限を克服している。特に LA メカニズムと GV 境界に対する後悔解析の矛盾を解消する - Xie らによって強調されたオープンな問題である。

関連論文リスト

• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。 ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。 ゲームにおける高速収束と拡張逆最適化への応用について述べる。
  論文  参考訳（メタデータ） (2024-08-17T02:22:08Z)
• Online Dynamic Submodular Optimization [0.0]
  オンラインバイナリ最適化のための証明可能な性能を持つ新しいアルゴリズムを提案する。 高速な需要応答とリアルタイム分散ネットワーク再構成という2つのパワーシステムアプリケーションでアルゴリズムを数値的にテストする。
  論文  参考訳（メタデータ） (2023-06-19T10:37:15Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Learning-Augmented Algorithms for Online Linear and Semidefinite Programming [9.849604820019394]
  Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。 SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。 予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
  論文  参考訳（メタデータ） (2022-09-21T19:16:29Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Online estimation and control with optimal pathlength regret [52.28457815067461]
  オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。 OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
  論文  参考訳（メタデータ） (2021-10-24T22:43:15Z)
• Meta-Regularization: An Approach to Adaptive Choice of the Learning Rate in Gradient Descent [20.47598828422897]
  第一次下降法における学習率の適応的選択のための新しいアプローチであるtextit-Meta-Regularizationを提案する。 本手法は,正規化項を追加して目的関数を修正し,共同処理パラメータをキャストする。
  論文  参考訳（メタデータ） (2021-04-12T13:13:34Z)

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

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