論文の概要: Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method
for Empirical Risk Minimization
- arxiv url: http://arxiv.org/abs/2208.13933v2
- Date: Tue, 21 Nov 2023 23:06:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 19:31:53.512411
- Title: Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method
for Empirical Risk Minimization
- Title（参考訳）: 経験的リスク最小化のためのfrank-wolfe法の改良にtaylor近似勾配を用いる
- Authors: Zikai Xiong and Robert M. Freund
- Abstract要約: In Empirical Minimization -- Minimization -- We present a novel computer step-size approach to we have compute guarantees。
提案手法は実世界のバイナリデータセットに非常に重要な問題を示す。
また、計算の保証を得るための新しい適応的なステップサイズアプローチを提案する。
- 参考スコア（独自算出の注目度）: 1.4504054468850665
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Frank-Wolfe method has become increasingly useful in statistical and
machine learning applications, due to the structure-inducing properties of the
iterates, and especially in settings where linear minimization over the
feasible set is more computationally efficient than projection. In the setting
of Empirical Risk Minimization -- one of the fundamental optimization problems
in statistical and machine learning -- the computational effectiveness of
Frank-Wolfe methods typically grows linearly in the number of data observations
$n$. This is in stark contrast to the case for typical stochastic projection
methods. In order to reduce this dependence on $n$, we look to second-order
smoothness of typical smooth loss functions (least squares loss and logistic
loss, for example) and we propose amending the Frank-Wolfe method with Taylor
series-approximated gradients, including variants for both deterministic and
stochastic settings. Compared with current state-of-the-art methods in the
regime where the optimality tolerance $\varepsilon$ is sufficiently small, our
methods are able to simultaneously reduce the dependence on large $n$ while
obtaining optimal convergence rates of Frank-Wolfe methods, in both the convex
and non-convex settings. We also propose a novel adaptive step-size approach
for which we have computational guarantees. Last of all, we present
computational experiments which show that our methods exhibit very significant
speed-ups over existing methods on real-world datasets for both convex and
non-convex binary classification problems.
- Abstract（参考訳）: フランク=ウルフ法(frank-wolfe method)は、イテレートの構造誘導性や、特に可算集合上の線形最小化が射影よりも計算効率が高い設定により、統計学や機械学習の応用においてますます有用である。
統計的および機械学習における基本的な最適化問題の1つである経験的リスク最小化の設定において、フランク・ウルフ法の計算効率は通常、データ観測数n$で線形に増加する。
これは典型的な確率的射影法の場合とは全く対照的である。
n$への依存を減らすために、典型的な滑らかな損失関数(例えば、左方形損失とロジスティック損失)の2階の滑らかさを調べ、決定論的および確率的設定の変種を含むテイラー級数近似勾配でフランク=ウルフ法を修正を提案する。
最適性トレランス$\varepsilon$が十分小さい体制における現在の最先端手法と比較して、我々の手法は凸と非凸の両方の設定においてフランク・ウルフ法の最適収束率を得ながら、大きな$n$への依存を同時に低減することができる。
また,計算保証を実現するための適応的なステップサイズアプローチを提案する。
最後に,コンベックスおよび非凸二項分類問題に対する実世界のデータセット上での既存手法に対する高速化を示す計算実験を行った。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
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) - A Multistep Frank-Wolfe Method [2.806911268410107]
フランク=ウルフ法におけるジグザグ現象を離散化の成果物として検討した。
多重ステップのフランク・ウルフ変種は、トラニケート誤差が$O(Deltap)$として崩壊し、$p$はメソッドの順序である。
論文 参考訳（メタデータ） (2022-10-14T21:12:01Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳（メタデータ） (2021-04-09T14:50:59Z) - RNN Training along Locally Optimal Trajectories via Frank-Wolfe
Algorithm [50.76576946099215]
小領域の損失面に局所的なミニマを反復的に求めることにより,RNNの新規かつ効率的なトレーニング手法を提案する。
新たなRNNトレーニング手法を開発し,追加コストを伴っても,全体のトレーニングコストがバックプロパゲーションよりも低いことを実証的に観察した。
論文 参考訳（メタデータ） (2020-10-12T01:59:18Z) - Projection-Free Adaptive Gradients for Large-Scale Optimization [22.0439695290991]
フランク=ウルフアルゴリズムは、目的から近似した一階情報のみをクエリすることで、両方の計算負担を軽減するため、ユニークな位置を占める。
本手法は,制約付き最適化のための適応アルゴリズムの性能を向上させることができることを示す。
論文 参考訳（メタデータ） (2020-09-29T15:56:12Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization [30.980431848476925]
線形予測・構造を一般化した制約付き有限滑らかサム最小化アルゴリズムを提案する。
提案手法は実装が簡単で,ステップサイズチューニングを必要としない。
オープンソースパッケージで検討されたすべてのメソッドの実装を提供する。
論文 参考訳（メタデータ） (2020-02-27T00:47:21Z) - Faster Projection-free Online Learning [34.96927532439896]
我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。
提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
論文 参考訳（メタデータ） (2020-01-30T21:18:39Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。