論文の概要: Accelerating Frank-Wolfe via Averaging Step Directions

• arxiv url: http://arxiv.org/abs/2205.11794v1
• Date: Tue, 24 May 2022 05:26:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-25 15:22:13.286116
• Title: Accelerating Frank-Wolfe via Averaging Step Directions
• Title（参考訳）: 歩数平均化によるフランクウルフの加速
• Authors: Zhaoyue Chen, Yifan Sun
• Abstract要約: ステップ方向が過去のオラクル呼び出しの単純な重み付け平均であるフランク=ウルフの修正を考える。 本手法は, スパース多様体が検出された後に, いくつかの問題に対して収束率を向上することを示す。
• 参考スコア（独自算出の注目度）: 2.806911268410107
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Frank-Wolfe method is a popular method in sparse constrained optimization, due to its fast per-iteration complexity. However, the tradeoff is that its worst case global convergence is comparatively slow, and importantly, is fundamentally slower than its flow rate--that is to say, the convergence rate is throttled by discretization error. In this work, we consider a modified Frank-Wolfe where the step direction is a simple weighted average of past oracle calls. This method requires very little memory and computational overhead, and provably decays this discretization error term. Numerically, we show that this method improves the convergence rate over several problems, especially after the sparse manifold has been detected. Theoretically, we show the method has an overall global convergence rate of $O(1/k^p)$, where $0< p < 1$; after manifold identification, this rate speeds to $O(1/k^{3p/2})$. We also observe that the method achieves this accelerated rate from a very early stage, suggesting a promising mode of acceleration for this family of methods.
• Abstract（参考訳）: Frank-Wolfe法は、その高速な解法によるスパース制約最適化において一般的な方法である。 しかし、このトレードオフは、世界収束が相対的に遅く、そして最も重要なことは、その流量よりも根本的に遅く、つまり、収束速度が離散化誤差によって損なわれることである。 本研究では、ステップ方向が過去のオラクル呼び出しの単純な重み付き平均であるフランク=ウルフの修正を考える。 この方法は非常に少ないメモリと計算オーバーヘッドを必要とし、この離散化誤差項を確実に減衰させる。 数値解析により, この手法は, スパース多様体が検出された後に, いくつかの問題に対する収束率を向上させることを示す。 理論的には、全球収束率は$o(1/k^p)$であり、ここでは$0<p < 1$; 多様体の識別後に、この速度は$o(1/k^{3p/2})$となる。 また,本手法がごく初期の段階からこの加速速度を達成することを観察し,この手法群に対して有望な加速モードを提案する。

関連論文リスト

• Stochastic Newton Proximal Extragradient Method [18.47705532817026]
  そこで本稿では,これらの境界を改良するNewton Extragradient法を提案する。 我々はHybrid Proximal Extragradient(HPE)フレームワークを拡張してこれを実現する。
  論文  参考訳（メタデータ） (2024-06-03T16:06:23Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。 本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:54:51Z)
• Reducing Discretization Error in the Frank-Wolfe Method [2.806911268410107]
  Frank-Wolfeアルゴリズムは、構造的に制約された機械学習アプリケーションで一般的な方法である。 この手法の1つの大きな制限は、不安定なジグザグングステップの方向のために加速が難しい収束速度の遅いことである。 最適化された高次離散化スキームを直接適用するマルチステップFrank-Wolfe法と、離散化誤差を低減したLMO-averagingスキームの2つの改善を提案する。
  論文  参考訳（メタデータ） (2023-04-04T00:43:05Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。 我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
  論文  参考訳（メタデータ） (2022-11-03T14:12:51Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• A Multistep Frank-Wolfe Method [2.806911268410107]
  フランク=ウルフ法におけるジグザグ現象を離散化の成果物として検討した。 多重ステップのフランク・ウルフ変種は、トラニケート誤差が$O(Deltap)$として崩壊し、$p$はメソッドの順序である。
  論文  参考訳（メタデータ） (2022-10-14T21:12:01Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
  このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。 我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。 数値シミュレーションはアルゴリズムの効率を実証する。
  論文  参考訳（メタデータ） (2022-02-07T21:23:17Z)
• Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps [66.88729048402082]
  一般化自己一致は、多くの学習問題の目的関数に存在する重要な特性である。 検討対象の領域が一様凸あるいは多面体である場合など,様々な症例に対する収束率の改善を示す。
  論文  参考訳（メタデータ） (2021-05-28T15:26:36Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Accelerate the Warm-up Stage in the Lasso Computation via a Homotopic Approach [2.538209532048867]
  ホモトピック法は、ラッソ型推定器で使われる$ell_1$ペナルティを近似するために用いられる。 ラッソ型推定器の計算における既存の手法よりも高速な数値収束率を示す。
  論文  参考訳（メタデータ） (2020-10-26T22:37:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。