論文の概要: New Projection-free Algorithms for Online Convex Optimization with
Adaptive Regret Guarantees
- arxiv url: http://arxiv.org/abs/2202.04721v3
- Date: Sun, 19 Mar 2023 10:11:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 05:14:34.548498
- Title: New Projection-free Algorithms for Online Convex Optimization with
Adaptive Regret Guarantees
- Title（参考訳）: Adaptive Regret Guaranteesを用いたオンライン凸最適化のための新しいプロジェクションフリーアルゴリズム
- Authors: Dan Garber, Ben Kretzu
- Abstract要約: オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。
提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。
我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
- 参考スコア（独自算出の注目度）: 21.30065439295409
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present new efficient \textit{projection-free} algorithms for online
convex optimization (OCO), where by projection-free we refer to algorithms that
avoid computing orthogonal projections onto the feasible set, and instead relay
on different and potentially much more efficient oracles. While most
state-of-the-art projection-free algorithms are based on the
\textit{follow-the-leader} framework, our algorithms are fundamentally
different and are based on the \textit{online gradient descent} algorithm with
a novel and efficient approach to computing so-called \textit{infeasible
projections}. As a consequence, we obtain the first projection-free algorithms
which naturally yield \textit{adaptive regret} guarantees, i.e., regret bounds
that hold w.r.t. any sub-interval of the sequence. Concretely, when assuming
the availability of a linear optimization oracle (LOO) for the feasible set, on
a sequence of length $T$, our algorithms guarantee $O(T^{3/4})$ adaptive regret
and $O(T^{3/4})$ adaptive expected regret, for the full-information and bandit
settings, respectively, using only $O(T)$ calls to the LOO. These bounds match
the current state-of-the-art regret bounds for LOO-based projection-free OCO,
which are \textit{not adaptive}. We also consider a new natural setting in
which the feasible set is accessible through a separation oracle. We present
algorithms which, using overall $O(T)$ calls to the separation oracle,
guarantee $O(\sqrt{T})$ adaptive regret and $O(T^{3/4})$ adaptive expected
regret for the full-information and bandit settings, respectively.
- Abstract（参考訳）: 我々は、オンライン凸最適化(OCO)のための新しい効率的な \textit{projection-free} アルゴリズムを提案する。
ほとんどの最先端のプロジェクションフリーアルゴリズムは \textit{follow-the-leader} フレームワークに基づいているが、我々のアルゴリズムは根本的に異なり、いわゆる \textit{infeasible projections} を計算するための新しい効率的なアプローチによる \textit{onlinegradient descent} アルゴリズムに基づいている。
結果として、自然に \textit{adaptive regret} 保証、すなわち w.r.t を持つ後悔境界、すなわち、シーケンスの任意の部分インターバルを与える最初のプロジェクションフリーアルゴリズムを得る。
具体的には、実現可能な集合に対する線形最適化オラクル(LOO)の可用性を$T$のシーケンスで仮定すると、我々のアルゴリズムは、LOOへの$O(T^{3/4})$適応的後悔と$O(T^{3/4})$適応的期待的後悔を保証する。
これらの境界は、現在の LOO ベースの射影自由 OCO の後悔境界と一致し、これは \textit{not adapt} である。
また、分離オラクルを通して実現可能な集合にアクセス可能な新しい自然設定も検討する。
我々は,全体$O(T)$を分離オラクルに呼び出し,$O(\sqrt{T})$適応的後悔と$O(T^{3/4})$適応的期待的後悔をそれぞれ全情報および盗賊設定に対して保証するアルゴリズムを提案する。
関連論文リスト
- Online Convex Optimization with a Separation Oracle [10.225358400539719]
本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
論文 参考訳（メタデータ） (2024-10-03T13:35:08Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive
Regret Bounds [27.92755687977196]
本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。
高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。
提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
論文 参考訳（メタデータ） (2023-02-24T00:02:24Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - 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 [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。
GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。
我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
論文 参考訳（メタデータ） (2022-11-22T23:53:06Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。
このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。
本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
論文 参考訳（メタデータ） (2020-08-13T08:56:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。