論文の概要: Optimized projection-free algorithms for online learning: construction and worst-case analysis
- arxiv url: http://arxiv.org/abs/2506.05855v1
- Date: Fri, 06 Jun 2025 08:22:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-09 17:28:43.375731
- Title: Optimized projection-free algorithms for online learning: construction and worst-case analysis
- Title（参考訳）: オンライン学習のための最適化プロジェクションフリーアルゴリズムの構築と最悪のケース分析
- Authors: Julien Weibel, Pierre Gaillard, Wouter M. Koolen, Adrien Taylor,
- Abstract要約: 本研究は線形最適化オラクル(Frank-Wolfe)を用いたオンライン学習のためのプロジェクションフリーアルゴリズムの研究と開発である。
半定値プログラミングを利用してオンラインFrank-Wolfe型アルゴリズムを数値的に設計・解析する方法を示す。
- 参考スコア（独自算出の注目度）: 16.086904272719593
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work studies and develop projection-free algorithms for online learning with linear optimization oracles (a.k.a. Frank-Wolfe) for handling the constraint set. More precisely, this work (i) provides an improved (optimized) variant of an online Frank-Wolfe algorithm along with its conceptually simple potential-based proof, and (ii) shows how to leverage semidefinite programming to jointly design and analyze online Frank-Wolfe-type algorithms numerically in a variety of settings-that include the design of the variant (i). Based on the semidefinite technique, we conclude with strong numerical evidence suggesting that no pure online Frank-Wolfe algorithm within our model class can have a regret guarantee better than O(T^3/4) (T is the time horizon) without additional assumptions, that the current algorithms do not have optimal constants, that the algorithm benefits from similar anytime properties O(t^3/4) not requiring to know T in advance, and that multiple linear optimization rounds do not generally help to obtain better regret bounds.
- Abstract（参考訳）: この研究は、制約集合を扱うための線形最適化オラクル(Frank-Wolfe)を用いたオンライン学習のためのプロジェクションフリーアルゴリズムの研究と開発である。
より正確には、この作品。
i) オンラインFrank-Wolfeアルゴリズムの(最適化された)改良版と、概念上は単純なポテンシャルベース証明を提供し、
(ii) オンラインFrank-Wolfe型アルゴリズムを多種多様な設定で数値的に設計・解析するために半定値プログラミングを利用する方法を示す。
(i)
半定値法に基づいて、我々のモデルクラス内の純粋なオンラインFrank-Wolfeアルゴリズムは、追加の仮定なしにO(T^3/4)よりも後悔の保証が得られないこと、現在のアルゴリズムが最適定数を持っていないこと、アルゴリズムがTを事前に知る必要のない類似の任意の時間特性O(t^3/4)から恩恵を受けていること、そして複数の線形最適化ラウンドが一般的により後悔の限界を得る助けにならないことを示唆する強い数値的な証拠で結論付けた。
関連論文リスト
- Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。
ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。
ゲームにおける高速収束と拡張逆最適化への応用について述べる。
論文 参考訳（メタデータ） (2024-08-17T02:22:08Z) - A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization [33.38582292895673]
完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。
これを用いて、一般メタアルゴリズムを記述し、決定論的アルゴリズムを同様の後悔境界を持つゼロ次アルゴリズムに変換する。
論文 参考訳（メタデータ） (2024-02-13T17:42:27Z) - Online Combinatorial Linear Optimization via a Frank-Wolfe-based
Metarounding Algorithm [0.589889361990138]
そこで我々は,このクラスに緩和型近似アルゴリズムが存在するという自然な仮定の下で,新しいミートアラウンドアルゴリズムを提案する。
私たちのアルゴリズムは理論的にも実用的にもはるかに効率的です。
論文 参考訳（メタデータ） (2023-10-19T10:22:03Z) - Efficient Methods for Non-stationary Online Learning [61.63338724659592]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
また、さらに強化された測度、すなわち「インターバル・ダイナミック・リピート」を研究し、ラウンド当たりの射影数を$mathcalO(log2 T)$から$$$$に減らした。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。
そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。
後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
論文 参考訳（メタデータ） (2022-03-19T13:39:49Z) - Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient
adaptive algorithms for neural networks [0.0]
本稿では,Langevinベースのアルゴリズムを新たに導入し,一般的な適応的消滅アルゴリズムの欠点の多くを克服する。
特に、この新しいクラスのアルゴリズムの収束性についての漸近解析と完全な理論的保証を提供し、TH$varepsilon$O POULA(あるいは単にTheoPouLa)と名付けた。
論文 参考訳（メタデータ） (2021-05-28T15:58:48Z) - Boosting for Online Convex Optimization [64.15578413206715]
多数の専門家とオンライン凸最適化の意思決定フレームワークを検討します。
弱学習アルゴリズムは、基本クラスの専門家に対するおよその後悔を保証するメカニズムとして定義します。
ベースクラスの凸船体に対するほぼ最適の後悔を保証する効率的なブースティングアルゴリズムを提供します。
論文 参考訳（メタデータ） (2021-02-18T12:30:49Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳（メタデータ） (2020-02-13T05:42:27Z) - Faster Projection-free Online Learning [34.96927532439896]
我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。
提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
論文 参考訳（メタデータ） (2020-01-30T21:18:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。