論文の概要: 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$ スイッチを実行する単純なアルゴリズムを提案する。
最後に、我々はアルゴリズムを、考慮すべきいくつかのケースにおいて上界に一致する下界で補完する。
関連論文リスト
- Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises [22.758674468435302]
重み付き雑音系では、勾配と真の分散の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳（メタデータ） (2023-03-22T03:05:28Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Accelerated First-Order Optimization under Nonlinear Constraints [97.16266088683061]
制約付きFrankWolf-e-eに対して,高速化された1次アルゴリズムの新たなクラスを設計する。
これらのアルゴリズムの重要な性質は制約の数である。
我々は,非制約を効率的に扱えるとともに,最先端のパフォーマンスを$ellp1$で回復できることを示す。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - 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 [27.875251633343666]
我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受していることを最初に証明した。
一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2020-10-16T05:42:50Z) - Quantum Algorithm for Online Convex Optimization [4.702729080310267]
ゼロ階オンライン凸最適化問題に対して量子的優位性を求める。
本稿では,この問題に対する量子アルゴリズムを提案し,量子的優位性の可能性を示す。
論文 参考訳（メタデータ） (2020-07-29T18:34:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。