論文の概要: Exploiting the Curvature of Feasible Sets for Faster Projection-Free
Online Learning
- arxiv url: http://arxiv.org/abs/2205.11470v1
- Date: Mon, 23 May 2022 17:13:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-24 20:19:52.912427
- Title: Exploiting the Curvature of Feasible Sets for Faster Projection-Free
Online Learning
- Title（参考訳）: プロジェクションフリーオンライン学習における実現可能集合の曲率の活用
- Authors: Zakaria Mhammedi
- Abstract要約: 我々はオンライン凸最適化(OCO)のための新しい効率的なプロジェクションフリーアルゴリズムを開発した。
我々は,LOOracleを1ラウンドに2回呼び出すOCOアルゴリズムを開発し,ほぼ最適の$widetildeO(sqrtT)を後悔する。
また, 一般凸集合に対して, 1ラウンド当たりのO(d)$ LO Oracleへのコール数を$widetilde O(d)$に設定するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 8.461907111368628
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we develop new efficient projection-free algorithms for Online
Convex Optimization (OCO). Online Gradient Descent (OGD) is an example of a
classical OCO algorithm that guarantees the optimal $O(\sqrt{T})$ regret bound.
However, OGD and other projection-based OCO algorithms need to perform a
Euclidean projection onto the feasible set $\mathcal{C}\subset \mathbb{R}^d$
whenever their iterates step outside $\mathcal{C}$. For various sets of
interests, this projection step can be computationally costly, especially when
the ambient dimension is large. This has motivated the development of
projection-free OCO algorithms that swap Euclidean projections for often much
cheaper operations such as Linear Optimization (LO). However, state-of-the-art
LO-based algorithms only achieve a suboptimal $O(T^{3/4})$ regret for general
OCO. In this paper, we leverage recent results in parameter-free Online
Learning, and develop an OCO algorithm that makes two calls to an LO Oracle per
round and achieves the near-optimal $\widetilde{O}(\sqrt{T})$ regret whenever
the feasible set is strongly convex. We also present an algorithm for general
convex sets that makes $\widetilde O(d)$ expected number of calls to an LO
Oracle per round and guarantees a $\widetilde O(T^{2/3})$ regret, improving on
the previous best $O(T^{3/4})$. We achieve the latter by approximating any
convex set $\mathcal{C}$ by a strongly convex one, where LO can be performed
using $\widetilde {O}(d)$ expected number of calls to an LO Oracle for
$\mathcal{C}$.
- Abstract（参考訳）: 本稿では,オンライン凸最適化(OCO)のための効率的なプロジェクションフリーアルゴリズムを提案する。
Online Gradient Descent (OGD) は、最適$O(\sqrt{T})$ regret boundを保証する古典的なOCOアルゴリズムの例である。
しかし、ogd や他の投影ベースの oco アルゴリズムは、イテレートが $\mathcal{c}$ を外へ踏み出すたびに、実行可能集合 $\mathcal{c}\subset \mathbb{r}^d$ に対してユークリッド射影を実行する必要がある。
様々な利害関係に対して、この射影ステップは特に周囲次元が大きい場合、計算的にコストがかかる。
これはユークリッド射影をリニア最適化(LO)のようなより安価な演算に置き換えるプロジェクションフリーなOCOアルゴリズムの開発を動機付けている。
しかし、最先端のloベースのアルゴリズムは、ocoを後悔するサブオプション$o(t^{3/4})しか達成しない。
本稿では,パラメータフリーオンライン学習の最近の成果を活用し,OCOアルゴリズムを開発した。このアルゴリズムは1ラウンドあたり2回のLOOracle呼び出しを行い,実現可能な集合が強い凸であれば,ほぼ最適の$\widetilde{O}(\sqrt{T})を後悔する。
また、一般的な凸集合に対するアルゴリズムとして、$\widetilde O(d)$ 1ラウンド当たりのLO Oracleへのコール数を期待し、$\widetilde O(T^{2/3})$の後悔を保証し、以前の$O(T^{3/4})$を改良する。
我々は、強い凸集合によって任意の凸集合 $\mathcal{C}$ を近似することで、後者を達成する。そこで、LOは$\widetilde {O}(d)$ LO Oracleへの期待される呼び出し数$\mathcal{C}$ を使って実行することができる。
関連論文リスト
- 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) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Projection-Free Online Convex Optimization via Efficient Newton
Iterations [10.492474737007722]
本稿では、凸領域$mathcalKサブセットmathbbRd$に対するオンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-19T18:48:53Z) - A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic
Composite Optimization [10.762749887051546]
本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。
以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
論文 参考訳（メタデータ） (2023-02-20T05:16:18Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。