論文の概要: A Generalized Approach to Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2402.08621v1
- Date: Tue, 13 Feb 2024 17:42:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 14:15:17.124308
- Title: A Generalized Approach to Online Convex Optimization
- Title(参考訳): オンライン凸最適化への一般化アプローチ
- Authors: Mohammad Pedramfar, Vaneet Aggarwal
- Abstract要約: 完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。
完全情報フィードバックを必要とする任意のアルゴリズムは、半帯域フィードバックを持つアルゴリズムに変換される可能性があることを示す。
- 参考スコア(独自算出の注目度): 39.44092711734015
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we analyze the problem of online convex optimization in
different settings. 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, such
full-information feedback, bandit feedback, stochastic regret, adversarial
regret and various forms of non-stationary regret. Using our analysis, we
provide the first efficient projection-free online convex optimization
algorithm using linear optimization oracles.
- Abstract(参考訳): 本稿では,オンライン凸最適化の問題点を異なる設定で解析する。
完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。
また, 完全な情報フィードバックを必要とするアルゴリズムは, 半帯域フィードバックを持つアルゴリズムに変換される可能性があることを示す。
さらに, 決定論的半バンドフィードバックを用いた完全適応型敵に対するアルゴリズムは, 確率的半バンドフィードバックのみを用いて, 同様の境界を得ることができることを示した。
これを用いて、一般的なメタアルゴリズムを記述し、一階アルゴリズムを同様の後悔境界を持つゼロ階アルゴリズムに変換する。
本フレームワークは,全情報フィードバック,盗聴フィードバック,確率的後悔,反逆的後悔,非定常的後悔など,様々な場面でオンライン最適化を解析することができる。
解析により,線形最適化オラクルを用いたプロジェクションフリーオンライン凸最適化アルゴリズムを提案する。
関連論文リスト
- Online Combinatorial Linear Optimization via a Frank-Wolfe-based
Metarounding Algorithm [0.589889361990138]
そこで我々は,このクラスに緩和型近似アルゴリズムが存在するという自然な仮定の下で,新しいミートアラウンドアルゴリズムを提案する。
私たちのアルゴリズムは理論的にも実用的にもはるかに効率的です。
論文 参考訳(メタデータ) (2023-10-19T10:22:03Z) - Faster Margin Maximization Rates for Generic Optimization Methods [23.185655992407742]
1次最適化法は、与えられたトレーニング目標を複数の局所最適化で最小化する場合、他の方法よりも特定の解を好む傾向にある。
近年の研究では、勾配差に基づく手法は、$ell$-maximal margin classifierに対して暗黙の偏見を示すことが示されている。
本稿では,ミラー降下法と最急降下法について,最先端の暗黙バイアス率を示す。
論文 参考訳(メタデータ) (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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。