論文の概要: Projection-free Online Exp-concave Optimization
- arxiv url: http://arxiv.org/abs/2302.04859v1
- Date: Thu, 9 Feb 2023 18:58:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 14:42:32.462044
- Title: Projection-free Online Exp-concave Optimization
- Title（参考訳）: プロジェクションフリーオンラインExp-concave最適化
- Authors: Dan Garber, Ben Kretzu
- Abstract要約: LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
- 参考スコア（独自算出の注目度）: 21.30065439295409
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the setting of online convex optimization (OCO) with
\textit{exp-concave} losses. The best regret bound known for this setting is
$O(n\log{}T)$, where $n$ is the dimension and $T$ is the number of prediction
rounds (treating all other quantities as constants and assuming $T$ is
sufficiently large), and is attainable via the well-known Online Newton Step
algorithm (ONS). However, ONS requires on each iteration to compute a
projection (according to some matrix-induced norm) onto the feasible convex
set, which is often computationally prohibitive in high-dimensional settings
and when the feasible set admits a non-trivial structure. In this work we
consider projection-free online algorithms for exp-concave and smooth losses,
where by projection-free we refer to algorithms that rely only on the
availability of a linear optimization oracle (LOO) for the feasible set, which
in many applications of interest admits much more efficient implementations
than a projection oracle. We present an LOO-based ONS-style algorithm, which
using overall $O(T)$ calls to a LOO, guarantees in worst case regret bounded by
$\widetilde{O}(n^{2/3}T^{2/3})$ (ignoring all quantities except for $n,T$).
However, our algorithm is most interesting in an important and plausible
low-dimensional data scenario: if the gradients (approximately) span a subspace
of dimension at most $\rho$, $\rho << n$, the regret bound improves to
$\widetilde{O}(\rho^{2/3}T^{2/3})$, and by applying standard deterministic
sketching techniques, both the space and average additional per-iteration
runtime requirements are only $O(\rho{}n)$ (instead of $O(n^2)$). This improves
upon recently proposed LOO-based algorithms for OCO which, while having the
same state-of-the-art dependence on the horizon $T$, suffer from regret/oracle
complexity that scales with $\sqrt{n}$ or worse.
- Abstract（参考訳）: 我々は、\textit{exp-concave}損失を伴うオンライン凸最適化(oco)の設定を検討する。
この設定で知られている最大の後悔は$O(n\log{}T)$であり、$n$は次元であり、$T$は予測ラウンドの数であり(他の全ての量を定数として扱い、$T$が十分大きいと仮定する)、よく知られたオンラインニュートンステップアルゴリズム(ONS)を通して達成可能である。
しかし、ons は(ある行列誘起ノルムによる)射影を高次元の設定や非自明な構造を持つ場合にしばしば計算的に禁止される可換凸集合上に計算するために各イテレーションで要求される。
この作業では、プロジェクションフリーのオンラインアルゴリズムをexp-concaveとスムースな損失のために考慮し、プロジェクションフリーのアルゴリズムでは、実行可能集合に対する線形最適化オラクル(loo)の可用性のみに依存するアルゴリズムを参照します。
loo をベースとする ons 方式のアルゴリズムでは,合計 $o(t)$ を loo にコールすることで,$\widetilde{o}(n^{2/3}t^{2/3})$ (n,t$ を除くすべての量を無視する) という最悪の場合の後悔を保証する。
しかし、我々のアルゴリズムは、重要かつ妥当な低次元データシナリオにおいて最も興味深い: もし勾配が最大$\rho$, $\rho << n$ で次元の部分空間を(概ね)またぐ場合、後悔の境界は$\widetilde{o}(\rho^{2/3}t^{2/3})$に改善され、標準決定論的スケッチ技術を適用することにより、空間と平均的な追加毎のランタイム要求は$o(\rho{}n)$($o(n^2)$の代わりに)である。
これは、最近提案されたOCOのLOOベースのアルゴリズムの改善であり、このアルゴリズムは水平線に対する最先端の依存性と同じ$T$を持つが、$\sqrt{n}$以上でスケールする後悔とオークルの複雑さに悩まされている。
関連論文リスト
- Online Convex Optimization with a Separation Oracle [10.225358400539719]
本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
論文 参考訳（メタデータ） (2024-10-03T13:35:08Z) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Quasi-Newton Steps for Efficient Online Exp-Concave Optimization [10.492474737007722]
Online Newton Step (ONS)は、$O(dln T)$を保証できる。
本稿では,自己協和性バリアを正規化器として使用することにより,一般化された投影をサイドステップで行う。
最終的なアルゴリズムはONSのより効率的なバージョンと見なすことができる。
論文 参考訳（メタデータ） (2022-11-02T17:57:21Z) - Exploiting the Curvature of Feasible Sets for Faster Projection-Free
Online Learning [8.461907111368628]
我々はオンライン凸最適化(OCO)のための新しい効率的なプロジェクションフリーアルゴリズムを開発した。
我々は,LOOracleを1ラウンドに2回呼び出すOCOアルゴリズムを開発し,ほぼ最適の$widetildeO(sqrtT)を後悔する。
また, 一般凸集合に対して, 1ラウンド当たりのO(d)$ LO Oracleへのコール数を$widetilde O(d)$に設定するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-23T17:13:46Z) - New Projection-free Algorithms for Online Convex Optimization with
Adaptive Regret Guarantees [21.30065439295409]
オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。
提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。
我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
論文 参考訳（メタデータ） (2022-02-09T20:56:16Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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) - An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear
Bandits [16.103685478563072]
本稿では,一般制約付き線形帯域について考察する。
目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。
本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-10T07:30:37Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。