論文の概要: Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
- arxiv url: http://arxiv.org/abs/2002.11860v6
- Date: Thu, 8 Sep 2022 08:48:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-28 09:25:51.955937
- Title: Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
- Title（参考訳）: 有限和最小化のための確率フランクウルフ
- Authors: Geoffrey N\'egiar, Gideon Dresdner, Alicia Tsai, Laurent El Ghaoui,
Francesco Locatello, Robert M. Freund, Fabian Pedregosa
- Abstract要約: 線形予測・構造を一般化した制約付き有限滑らかサム最小化アルゴリズムを提案する。
提案手法は実装が簡単で,ステップサイズチューニングを必要としない。
オープンソースパッケージで検討されたすべてのメソッドの実装を提供する。
- 参考スコア（独自算出の注目度）: 30.980431848476925
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a novel Stochastic Frank-Wolfe (a.k.a. conditional gradient)
algorithm for constrained smooth finite-sum minimization with a generalized
linear prediction/structure. This class of problems includes empirical risk
minimization with sparse, low-rank, or other structured constraints. The
proposed method is simple to implement, does not require step-size tuning, and
has a constant per-iteration cost that is independent of the dataset size.
Furthermore, as a byproduct of the method we obtain a stochastic estimator of
the Frank-Wolfe gap that can be used as a stopping criterion. Depending on the
setting, the proposed method matches or improves on the best computational
guarantees for Stochastic Frank-Wolfe algorithms. Benchmarks on several
datasets highlight different regimes in which the proposed method exhibits a
faster empirical convergence than related methods. Finally, we provide an
implementation of all considered methods in an open-source package.
- Abstract（参考訳）: 線形予測・構造を一般化した制約付き滑らかな有限サム最小化のための新しい確率的フランク・ウルフアルゴリズムを提案する。
この種の問題には、スパース、ローランク、その他の構造的制約を伴う経験的リスク最小化が含まれる。
提案手法は実装が簡単であり,ステップサイズのチューニングを必要としない。
さらに, 本手法の副産物として, 停止基準として使用できるフランク=ウルフギャップの確率的推定値を求める。
設定に応じて、提案手法は確率的フランク・ウルフアルゴリズムの最良の計算保証に適合するか改善する。
いくつかのデータセットのベンチマークは、提案手法が関連する手法よりも高速に経験的収束を示す異なるレジームを強調する。
最後に、オープンソースパッケージで検討されたすべてのメソッドの実装を提供する。
関連論文リスト
- Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。
この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文 参考訳（メタデータ） (2023-11-04T11:12:24Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - A Multistep Frank-Wolfe Method [2.806911268410107]
フランク=ウルフ法におけるジグザグ現象を離散化の成果物として検討した。
多重ステップのフランク・ウルフ変種は、トラニケート誤差が$O(Deltap)$として崩壊し、$p$はメソッドの順序である。
論文 参考訳（メタデータ） (2022-10-14T21:12:01Z) - 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) - Fuzzy Clustering by Hyperbolic Smoothing [0.0]
本研究では,スムーズな数値手法を用いて,大規模データセットのファジィクラスタを構築する手法を提案する。
この平滑化により、強微分不可能な問題から低次元の制約を伴わずに、最適化の微分可能部分確率に変換することができる。
論文 参考訳（メタデータ） (2022-07-09T12:40:46Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Self-Concordant Analysis of Frank-Wolfe Algorithms [3.3598755777055374]
ポアソン逆問題 (Poisson inverse problem) や量子状態トモグラフィー (quantum state tomography) など、多くの応用において、損失は非有界曲率を持つ自己協和関数 (SC) によって与えられる。
SC関数の理論を用いて、FW法の新たな適応ステップサイズを提供し、k反復後の大域収束率 O(1/k) を証明する。
論文 参考訳（メタデータ） (2020-02-11T11:30:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。