論文の概要: A Multistep Frank-Wolfe Method
- arxiv url: http://arxiv.org/abs/2210.08110v1
- Date: Fri, 14 Oct 2022 21:12:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-18 21:34:27.015206
- Title: A Multistep Frank-Wolfe Method
- Title（参考訳）: 多段階Frank-Wolfe法
- Authors: Zhaoyue Chen, Yifan Sun
- Abstract要約: フランク=ウルフ法におけるジグザグ現象を離散化の成果物として検討した。
多重ステップのフランク・ウルフ変種は、トラニケート誤差が$O(Deltap)$として崩壊し、$p$はメソッドの順序である。
- 参考スコア（独自算出の注目度）: 2.806911268410107
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Frank-Wolfe algorithm has regained much interest in its use in
structurally constrained machine learning applications. However, one major
limitation of the Frank-Wolfe algorithm is the slow local convergence property
due to the zig-zagging behavior. We observe the zig-zagging phenomenon in the
Frank-Wolfe method as an artifact of discretization, and propose multistep
Frank-Wolfe variants where the truncation errors decay as $O(\Delta^p)$, where
$p$ is the method's order. This strategy "stabilizes" the method, and allows
tools like line search and momentum to have more benefits. However, our results
suggest that the worst case convergence rate of Runge-Kutta-type discretization
schemes cannot improve upon that of the vanilla Frank-Wolfe method for a rate
depending on $k$. Still, we believe that this analysis adds to the growing
knowledge of flow analysis for optimization methods, and is a cautionary tale
on the ultimate usefulness of multistep methods.
- Abstract（参考訳）: frank-wolfeアルゴリズムは、構造的に制約された機械学習アプリケーションでの使用に対する多くの関心を取り戻した。
しかし、フランク・ウルフアルゴリズムの主な制限は、ジグザグ動作による局所収束性が遅いことである。
我々は,フランク=ウルフ法におけるジグザゲング現象を離散化の成果として観察し,トランケーション誤差が$O(\Delta^p)$として崩壊する多段階フランク=ウルフ変法を提案する。
この戦略はメソッドを"安定化"し、行検索やモメンタムのようなツールにより多くのメリットをもたらす。
しかし,runge-kutta型離散化スキームの最悪のケース収束率は,バニラ・フランク・ウルフ法では,$k$に依存するレートでは改善できないことが示唆された。
しかし,本解析は,最適化手法におけるフロー解析の知識の増大に寄与し,多段階手法の究極的有用性に留意すべき点である。
関連論文リスト
- Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates
and Practical Features [79.39965431772626]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Reducing Discretization Error in the Frank-Wolfe Method [2.806911268410107]
Frank-Wolfeアルゴリズムは、構造的に制約された機械学習アプリケーションで一般的な方法である。
この手法の1つの大きな制限は、不安定なジグザグングステップの方向のために加速が難しい収束速度の遅いことである。
最適化された高次離散化スキームを直接適用するマルチステップFrank-Wolfe法と、離散化誤差を低減したLMO-averagingスキームの2つの改善を提案する。
論文 参考訳（メタデータ） (2023-04-04T00:43:05Z) - Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method
for Empirical Risk Minimization [1.4504054468850665]
In Empirical Minimization -- Minimization -- We present a novel computer step-size approach to we have compute guarantees。
提案手法は実世界のバイナリデータセットに非常に重要な問題を示す。
また、計算の保証を得るための新しい適応的なステップサイズアプローチを提案する。
論文 参考訳（メタデータ） (2022-08-30T00:08:37Z) - Accelerating Frank-Wolfe via Averaging Step Directions [2.806911268410107]
ステップ方向が過去のオラクル呼び出しの単純な重み付け平均であるフランク=ウルフの修正を考える。
本手法は, スパース多様体が検出された後に, いくつかの問題に対して収束率を向上することを示す。
論文 参考訳（メタデータ） (2022-05-24T05:26:25Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-08-22T16:00:45Z) - Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps [66.88729048402082]
一般化自己一致は、多くの学習問題の目的関数に存在する重要な特性である。
検討対象の領域が一様凸あるいは多面体である場合など,様々な症例に対する収束率の改善を示す。
論文 参考訳（メタデータ） (2021-05-28T15:26:36Z) - RNN Training along Locally Optimal Trajectories via Frank-Wolfe
Algorithm [50.76576946099215]
小領域の損失面に局所的なミニマを反復的に求めることにより,RNNの新規かつ効率的なトレーニング手法を提案する。
新たなRNNトレーニング手法を開発し,追加コストを伴っても,全体のトレーニングコストがバックプロパゲーションよりも低いことを実証的に観察した。
論文 参考訳（メタデータ） (2020-10-12T01:59:18Z) - Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization [30.980431848476925]
線形予測・構造を一般化した制約付き有限滑らかサム最小化アルゴリズムを提案する。
提案手法は実装が簡単で,ステップサイズチューニングを必要としない。
オープンソースパッケージで検討されたすべてのメソッドの実装を提供する。
論文 参考訳（メタデータ） (2020-02-27T00:47:21Z) - A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization [60.90222082871258]
本稿では,制約集合上の線形最小化オラクル(LMO)を用いて,制約付き自己調和最小化問題のクラスをカラフルに解く方法を示す。
L-smoothの場合、我々の手法のLMO呼び出し数はFrank-Wolfe法とほぼ同じであることを示す。
論文 参考訳（メタデータ） (2020-02-17T15:28:31Z) - Global Convergence of Frank Wolfe on One Hidden Layer Networks [121.96696298666014]
隠れた1つのニューラルネットワークをトレーニングする際、Frank Wolfeアルゴリズムに対してグローバル収束境界を導出する。
ReLUアクティベーション関数を用い、サンプルデータセット上のトラクタブルプレコンディショニング仮定の下では、解をインクリメンタルに形成する線形最小化オラクルを第2次コーンプログラムとして明示的に解くことができる。
論文 参考訳（メタデータ） (2020-02-06T11:58:43Z) - Faster Projection-free Online Learning [34.96927532439896]
我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。
提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
論文 参考訳（メタデータ） (2020-01-30T21:18:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。