論文の概要: A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2402.08621v3
• Date: Wed, 13 Nov 2024 03:24:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-14 16:09:02.982215
• Title: A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization
• Title（参考訳）: オンライン凸最適化におけるメタアルゴリズム解析のための統一フレームワーク
• Authors: Mohammad Pedramfar, Vaneet Aggarwal,
• Abstract要約: 完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。 これを用いて、一般メタアルゴリズムを記述し、決定論的アルゴリズムを同様の後悔境界を持つゼロ次アルゴリズムに変換する。
• 参考スコア（独自算出の注目度）: 33.38582292895673
• License:
• Abstract: In this paper, we analyze the problem of online convex optimization in different settings, including different feedback types (full-information/semi-bandit/bandit/etc) in either stochastic or non-stochastic setting and different notions of regret (static adversarial regret/dynamic regret/adaptive regret). This is done through a framework which allows us to systematically propose and analyze meta-algorithms for the various settings described above. We show that any algorithm for online linear optimization with fully adaptive adversaries is an algorithm for online convex optimization. We also show that any such algorithm that requires full-information feedback may be transformed to an algorithm with semi-bandit feedback with comparable regret bound. We further show that algorithms that are designed for fully adaptive adversaries using deterministic semi-bandit feedback can obtain similar bounds using only stochastic semi-bandit feedback when facing oblivious adversaries. We use this to describe general meta-algorithms to convert first order algorithms to zeroth order algorithms with comparable regret bounds. Our framework allows us to analyze online optimization in various settings, recovers several results in the literature with a simplified proof technique, and provides new results.
• Abstract（参考訳）: 本稿では, オンライン凸最適化の問題点を, 確率的, 非確率的, あるいは後悔的(静的な反逆的, ダイナミックな後悔, 適応的後悔)のいずれにおいても異なるフィードバックタイプ (全情報/半帯域/帯域/etc) を含む, 異なる設定で分析する。 これは、上述した様々な設定に対するメタアルゴリズムを体系的に提案し、分析することを可能にするフレームワークを通じて行われる。 完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。 また, 完全な情報フィードバックを必要とするアルゴリズムは, 半帯域フィードバックを持つアルゴリズムに変換される可能性があることを示す。 さらに、決定論的半帯域フィードバックを用いて、完全に適応的な敵に対して設計されたアルゴリズムは、難解な敵に直面するとき、確率的半帯域フィードバックのみを用いて、類似のバウンダリを得ることができることを示す。 これを用いて、一般的なメタアルゴリズムを記述し、一階アルゴリズムを同様の後悔境界を持つゼロ階アルゴリズムに変換する。 本フレームワークは,様々な設定でオンライン最適化を解析し,簡易な証明手法を用いて文献のいくつかの結果を復元し,新たな結果を提供する。

関連論文リスト

• Online Sequential Decision-Making with Unknown Delays [42.06479169761205]
  本稿では,様々な種類のフィードバックを処理するために,近似解に基づく遅延アルゴリズムの3つのファミリを提案する。 各アルゴリズムに対して、一般凸性および相対的強凸性の場合の対応する後悔境界を提供する。 我々の理論的結果は、標準設定に分解されたときの現在の最良の境界と一致している。
  論文  参考訳（メタデータ） (2024-02-12T15:17:31Z)
• Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods [20.118513136686452]
  一階最適化法は、未決定の訓練目標を最小化する際に、本質的に他よりも特定の解を優先する傾向がある。 本稿では,ミラー降下法と最急降下法について,最先端の暗黙バイアス率を示す。 私たちの加速速度は、このゲームフレームワークにおけるオンライン学習アルゴリズムの残念な部分を活用することによって導き出されます。
  論文  参考訳（メタデータ） (2023-05-27T18:16:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Optimistic Optimisation of Composite Objective with Exponentiated Update [2.1700203922407493]
  このアルゴリズムは指数勾配と$p$-normアルゴリズムの組み合わせと解釈できる。 彼らはシーケンス依存の後悔の上界を達成し、スパース目標決定変数の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-08-08T11:29:55Z)
• Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting [21.584183030149084]
  パラメータフリーオンライン線形最適化アルゴリズムのクラスを提案する。 彼らは、いくつかの側情報を適用することによって、敵列の構造を利用する。 提案アルゴリズムは、全ての適応アルゴリズムに対して最高の性能を達成するためにさらに改良されている。
  論文  参考訳（メタデータ） (2022-02-04T21:56:29Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• Optimizing Optimizers: Regret-optimal gradient descent algorithms [9.89901717499058]
  我々は,後悔最適アルゴリズムの存在,一意性,一貫性について検討する。 制御問題に対する一階最適条件を提供することにより、後悔最適アルゴリズムはそれらの力学において特定の構造を満たす必要があることを示す。 それらを近似する高速な数値法を提案し,長期的後悔を直接最適化する最適化アルゴリズムを生成する。
  論文  参考訳（メタデータ） (2020-12-31T19:13:53Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Comparator-adaptive Convex Bandits [77.43350984086119]
  我々は,コンパレータのノルムが小さい場合,残差が小さい凸バンディットアルゴリズムを開発した。 アイデアを拡張して、リプシッツや滑らかな損失関数で包帯を凸する。
  論文  参考訳（メタデータ） (2020-07-16T16:33:35Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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