論文の概要: Lazy OCO: Online Convex Optimization on a Switching Budget
- arxiv url: http://arxiv.org/abs/2102.03803v1
- Date: Sun, 7 Feb 2021 14:47:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-09 15:51:17.022949
- Title: Lazy OCO: Online Convex Optimization on a Switching Budget
- Title（参考訳）: Lazy OCO: 切り替え予算によるオンライン凸最適化
- Authors: Uri Sherman, Tomer Koren
- Abstract要約: 我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。
離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
- 参考スコア（独自算出の注目度）: 26.613126943532357
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a variant of online convex optimization where the player is
permitted to switch decisions at most $S$ times in expectation throughout $T$
rounds. Similar problems have been addressed in prior work for the discrete
decision set setting, and more recently in the continuous setting but only with
an adaptive adversary. In this work, we aim to fill the gap and present
computationally efficient algorithms in the more prevalent oblivious setting,
establishing a regret bound of $O(T/S)$ for general convex losses and
$\widetilde O(T/S^2)$ for strongly convex losses. In addition, for stochastic
i.i.d.~losses, we present a simple algorithm that performs $\log T$ switches
with only a multiplicative $\log T$ factor overhead in its regret in both the
general and strongly convex settings. Finally, we complement our algorithms
with lower bounds that match our upper bounds in some of the cases we consider.
- Abstract（参考訳）: 我々は、プレイヤーが$ T$ラウンドを通じて予想で最大$ S$で決定を切り替えることができるオンライン凸最適化の変形を研究します。
同様の問題は、離散的な決定セットの設定の事前作業や、より最近の連続的な設定では、適応的な敵のみに対処されている。
本研究では,このギャップを埋めて計算効率の高いアルゴリズムを,より広く普及し,一般凸損失に対してo(t/s)$,強凸損失に対してo(t/s^2)$という後悔の限度を確立することを目的とする。
さらに,確率的 i.i.d.~losses に対して,一般的な凸設定と強い凸設定の両方において,乗算的$\log t$ factor のオーバーヘッドのみで $\log t$ スイッチを実行する単純なアルゴリズムを提案する。
最後に、我々はアルゴリズムを、考慮すべきいくつかのケースにおいて上界に一致する下界で補完する。
関連論文リスト
- Online Convex Optimization with a Separation Oracle [10.225358400539719]
本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
論文 参考訳（メタデータ） (2024-10-03T13:35:08Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Second Order Methods for Bandit Optimization and Control [34.51425758864638]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳（メタデータ） (2024-02-14T04:03:38Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Iterative Hard Thresholding with Adaptive Regularization: Sparser
Solutions Without Sacrificing Runtime [17.60502131429094]
本稿では,条件数関数としてスペーサー解を復元する反復型ハードしきい値決定アルゴリズムの簡単な修正を提案する。
提案するアルゴリズムである正規化IHTは、疎度$O(skappa)$の解を返す。
我々のアルゴリズムはARHTよりも大幅に改善され、またスパーシティ$O(skappa)$の解も見つかる。
論文 参考訳（メタデータ） (2022-04-11T19:33:15Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文 参考訳（メタデータ） (2021-03-21T11:43:35Z) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。
一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2020-10-16T05:42:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。