論文の概要: Universal Online Learning with Gradual Variations: A Multi-layer Online Ensemble Approach

• arxiv url: http://arxiv.org/abs/2307.08360v1
• Date: Mon, 17 Jul 2023 09:55:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-18 13:54:32.546884
• Title: Universal Online Learning with Gradual Variations: A Multi-layer Online Ensemble Approach
• Title（参考訳）: 経時変化を伴うユニバーサルオンライン学習:多層オンラインアンサンブルアプローチ
• Authors: Yu-Hu Yan, Peng Zhao, Zhi-Hua Zhou
• Abstract要約: 本稿では,2種類の適応性を持つオンライン凸最適化手法を提案する。 我々は、強い凸、exp-凹、凸損失関数に対して $mathcalO(ln V_T)$, $mathcalO(d ln V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds を得る。
• 参考スコア（独自算出の注目度）: 82.09804762411953
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose an online convex optimization method with two different levels of adaptivity. On a higher level, our method is agnostic to the specific type and curvature of the loss functions, while at a lower level, it can exploit the niceness of the environments and attain problem-dependent guarantees. To be specific, we obtain $\mathcal{O}(\ln V_T)$, $\mathcal{O}(d \ln V_T)$ and $\hat{\mathcal{O}}(\sqrt{V_T})$ regret bounds for strongly convex, exp-concave and convex loss functions, respectively, where $d$ is the dimension, $V_T$ denotes problem-dependent gradient variations and $\hat{\mathcal{O}}(\cdot)$-notation omits logarithmic factors on $V_T$. Our result finds broad implications and applications. It not only safeguards the worst-case guarantees, but also implies the small-loss bounds in analysis directly. Besides, it draws deep connections with adversarial/stochastic convex optimization and game theory, further validating its practical potential. Our method is based on a multi-layer online ensemble incorporating novel ingredients, including carefully-designed optimism for unifying diverse function types and cascaded corrections for algorithmic stability. Remarkably, despite its multi-layer structure, our algorithm necessitates only one gradient query per round, making it favorable when the gradient evaluation is time-consuming. This is facilitated by a novel regret decomposition equipped with customized surrogate losses.
• Abstract（参考訳）: 本稿では,2つの異なる適応レベルを有するオンライン凸最適化手法を提案する。 高レベルでは、本手法は損失関数の特定の型や曲率に依存しないが、低レベルでは環境の優美さを活用し、問題依存の保証を得ることができる。 具体的に言うと、$\mathcal{O}(\ln V_T)$, $\mathcal{O}(d \ln V_T)$ and $\hat{\mathcal{O}}(\sqrt{V_T})$ regret bounds for strong convex, exp-concave and convex loss function, where $d$ is the dimension, $V_T$は問題依存の勾配変動と$\hat{\mathcal{O}}(\cdot)$-notation omits logarithmic factor on $V_T$である。 我々の結果は幅広い意味と応用を見出す。 最悪のケースの保証を保護できるだけでなく、分析の小さな損失の範囲を直接含んでいる。 さらに、逆/確率凸最適化とゲーム理論との深い関係を描き、さらにその実用可能性を検証する。 提案手法は, 多様な機能種別を統一するための最適化や, アルゴリズム安定性のためのカスケード補正など, 新規成分を取り入れた多層オンラインアンサンブルに基づく。 注目すべきは、その多層構造にもかかわらず、我々のアルゴリズムはラウンド毎に1つの勾配クエリしか必要とせず、勾配評価が時間を要する場合に有利である。 これは、カスタマイズされた代理損失を備えた新規な後悔分解によって促進される。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
  非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。 いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
  論文  参考訳（メタデータ） (2023-11-08T08:17:09Z)
• Adaptive Bandit Convex Optimization with Heterogeneous Curvature [40.368893108265056]
  本研究では,学習者が決定を下すと,各関数が独自の曲率を持つ異種環境について検討する。 我々は, 高速で曲率に適応できる効率的なアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-02-12T21:55:42Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。 このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)
• Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
  本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。 このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。 本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
  論文  参考訳（メタデータ） (2020-08-13T08:56:24Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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