論文の概要: Revisiting Projection-free Online Learning: the Strongly Convex Case
- arxiv url: http://arxiv.org/abs/2010.07572v2
- Date: Tue, 23 Feb 2021 15:28:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-07 05:21:47.850952
- Title: Revisiting Projection-free Online Learning: the Strongly Convex Case
- Title（参考訳）: プロジェクションフリーオンライン学習の再検討: 強い凸の場合
- Authors: Dan Garber and Ben Kretzu
- Abstract要約: 射影のない最適化アルゴリズムは主に古典的フランク・ウルフ法に基づいている。
オンラインFrank-Wolfe法は、強い凸関数上でのO(T2/3)$の高速化を実現する。
- 参考スコア（独自算出の注目度）: 21.30065439295409
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Projection-free optimization algorithms, which are mostly based on the
classical Frank-Wolfe method, have gained significant interest in the machine
learning community in recent years due to their ability to handle convex
constraints that are popular in many applications, but for which computing
projections is often computationally impractical in high-dimensional settings,
and hence prohibit the use of most standard projection-based methods. In
particular, a significant research effort was put on projection-free methods
for online learning. In this paper we revisit the Online Frank-Wolfe (OFW)
method suggested by Hazan and Kale \cite{Hazan12} and fill a gap that has been
left unnoticed for several years: OFW achieves a faster rate of $O(T^{2/3})$ on
strongly convex functions (as opposed to the standard $O(T^{3/4})$ for convex
but not strongly convex functions), where $T$ is the sequence length. This is
somewhat surprising since it is known that for offline optimization, in
general, strong convexity does not lead to faster rates for Frank-Wolfe. We
also revisit the bandit setting under strong convexity and prove a similar
bound of $\tilde O(T^{2/3})$ (instead of $O(T^{3/4})$ without strong
convexity). Hence, in the current state-of-affairs, the best projection-free
upper-bounds for the full-information and bandit settings with strongly convex
and nonsmooth functions match up to logarithmic factors in $T$.
- Abstract（参考訳）: 従来のFrank-Wolfe法に基づくプロジェクションフリー最適化アルゴリズムは、多くのアプリケーションで広く使われている凸制約を扱う能力から、近年、機械学習コミュニティにおいて大きな関心を集めている。
特に、オンライン学習のためのプロジェクションフリー手法の研究が盛んに行われた。
本稿では、Hazan と Kale \cite{Hazan12} によって提案された Online Frank-Wolfe (OFW) 法を再検討し、数年の間気付かれていないギャップを埋める: OFW は強凸関数に対して$O(T^{2/3})$ の高速な速度を達成する(標準の$O(T^{3/4})$ は凸関数に対して$O(T^{3/4})$ に対して、$T$ は列長ではない)。
オフライン最適化では、一般的に強い凸性はフランク=ウルフの速度を速くしないことが知られているので、これは少々驚きである。
また、強い凸性の下でバンディットの設定を再検討し、同じ境界の$\tilde O(T^{2/3})$(強い凸性を持たない$O(T^{3/4})$)を証明する。
したがって、現在の状況下では、強い凸関数と非滑らか関数を持つ全情報および帯域設定のための最良のプロジェクションフリー上のバウンドは、$T$の対数係数に一致する。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。
GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。
我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
論文 参考訳（メタデータ） (2022-11-22T23:53:06Z) - Frank Wolfe Meets Metric Entropy [0.0]
フランク=ウルフの領域固有かつ容易に推定できる下界を確立する手法を提案する。
次元自由線型上界は、最悪の場合だけでなく、Emph平均の場合も失敗しなければならないことを示す。
また、核標準球にもこの現象が成立する。
論文 参考訳（メタデータ） (2022-05-17T21:23:36Z) - Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。
一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2020-10-16T05:42:50Z) - Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method [54.93433440034386]
実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
論文 参考訳（メタデータ） (2020-10-05T08:16:56Z) - Faster Projection-free Online Learning [34.96927532439896]
我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。
提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
論文 参考訳（メタデータ） (2020-01-30T21:18:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。