論文の概要: Online Convex Optimization with Continuous Switching Constraint
- arxiv url: http://arxiv.org/abs/2103.11370v1
- Date: Sun, 21 Mar 2021 11:43:35 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-23 14:14:21.365793
- Title: Online Convex Optimization with Continuous Switching Constraint
- Title（参考訳）: 連続スイッチング制約によるオンライン凸最適化
- Authors: Guanghui Wang, Yuanyu Wan, Tianbao Yang, Lijun Zhang
- Abstract要約: 連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
- 参考スコア（独自算出の注目度）: 78.25064451417082
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In many sequential decision making applications, the change of decision would
bring an additional cost, such as the wear-and-tear cost associated with
changing server status. To control the switching cost, we introduce the problem
of online convex optimization with continuous switching constraint, where the
goal is to achieve a small regret given a budget on the \emph{overall}
switching cost. We first investigate the hardness of the problem, and provide a
lower bound of order $\Omega(\sqrt{T})$ when the switching cost budget
$S=\Omega(\sqrt{T})$, and $\Omega(\min\{\frac{T}{S},T\})$ when $S=O(\sqrt{T})$,
where $T$ is the time horizon. The essential idea is to carefully design an
adaptive adversary, who can adjust the loss function according to the
cumulative switching cost of the player incurred so far based on the orthogonal
technique. We then develop a simple gradient-based algorithm which enjoys the
minimax optimal regret bound. Finally, we show that, for strongly convex
functions, the regret bound can be improved to $O(\log T)$ for $S=\Omega(\log
T)$, and $O(\min\{T/\exp(S)+S,T\})$ for $S=O(\log T)$.
- Abstract（参考訳）: 多くのシーケンシャルな意思決定アプリケーションでは、意思決定の変更により、サーバの状態変更に伴う摩耗と耳のコストなどの追加コストが発生する。
スイッチングコストを制御するために,連続的なスイッチング制約を伴うオンライン凸最適化の問題を導入する。
まず問題の難易度を調査し,スイッチングコストが$s=\omega(\sqrt{t})$,$\omega(\min\{\frac {t}{s},t\})$ when $s=o(\sqrt{t})$,ただし$t$が時間軸である場合,$s=\omega(\sqrt{t})$ の順に下限を与える。
本研究の基本的な考え方は, 直交技術に基づいて, これまでのプレイヤーの累積スイッチングコストに応じて損失関数を調整可能な適応敵を慎重に設計することである。
次に,ミニマックス最適後悔境界を満足する簡単な勾配に基づくアルゴリズムを開発した。
最後に、強い凸関数の場合、後悔境界は$O(\log T)$ for $S=\Omega(\log T)$, $O(\min\{T/\exp(S)+S,T\})$ for $S=O(\log T)$に改善できることを示す。
関連論文リスト
- Online Convex Optimization with a Separation Oracle [10.225358400539719]
本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
論文 参考訳（メタデータ） (2024-10-03T13:35:08Z) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost [31.04961854943877]
我々は,$widetildeO(sqrtH4S2AT)$を,切り替えコストが$O(HSA loglog T)$を要求されたことを後悔する新しいアルゴリズムを提案する。
副産物として、我々の新しいアルゴリズムは、最適な切替コストが$O(HSA)$のエンフレワードフリー探索アルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2022-02-13T19:01:06Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。
私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
論文 参考訳（メタデータ） (2021-02-19T11:03:51Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。
離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
論文 参考訳（メタデータ） (2021-02-07T14:47:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。