論文の概要: Parameter-free Locally Accelerated Conditional Gradients
- arxiv url: http://arxiv.org/abs/2102.06806v1
- Date: Fri, 12 Feb 2021 22:50:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-16 15:58:21.969985
- Title: Parameter-free Locally Accelerated Conditional Gradients
- Title(参考訳): パラメータフリー局所加速条件勾配
- Authors: Alejandro Carderera, Jelena Diakonikolas, Cheuk Yin Lin, Sebastian
Pokutta
- Abstract要約: 私たちは小説を紹介します。
自由局所加速cg(pf-lacg)アルゴリズムは,厳密な収束保証を提供する。
我々の理論結果は,局所加速度を実証し,非加速アルゴリズムに対するPF-LaCGの実用的改善を示す数値実験によって補完される。
- 参考スコア(独自算出の注目度): 91.19349793915615
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Projection-free conditional gradient (CG) methods are the algorithms of
choice for constrained optimization setups in which projections are often
computationally prohibitive but linear optimization over the constraint set
remains computationally feasible. Unlike in projection-based methods, globally
accelerated convergence rates are in general unattainable for CG. However, a
very recent work on Locally accelerated CG (LaCG) has demonstrated that local
acceleration for CG is possible for many settings of interest. The main
downside of LaCG is that it requires knowledge of the smoothness and strong
convexity parameters of the objective function. We remove this limitation by
introducing a novel, Parameter-Free Locally accelerated CG (PF-LaCG) algorithm,
for which we provide rigorous convergence guarantees. Our theoretical results
are complemented by numerical experiments, which demonstrate local acceleration
and showcase the practical improvements of PF-LaCG over non-accelerated
algorithms, both in terms of iteration count and wall-clock time.
- Abstract(参考訳): プロジェクションフリー条件勾配(CG)法は、プロジェクションがしばしば計算的に禁止されるが、制約セットに対する線形最適化が計算的に可能であるような制約付き最適化のアルゴリズムである。
プロジェクションベースの方法とは異なり、グローバルに加速された収束率は一般的にCGでは実現できない。
しかし, 局所加速CG (LaCG) に関する最近の研究は, CGの局所加速度が多くの興味ある設定で可能であることを実証している。
LaCGの主な欠点は、目的関数の滑らかさと強い凸性パラメータの知識を必要とすることである。
パラメータフリー局所加速CG(PF-LaCG)アルゴリズムを導入し,厳密な収束を保証することにより,この制限を解消する。
我々の理論結果は, 局所加速度を実証する数値実験によって補完され, 繰り返し回数とウォールクロック時間の両方において, 非加速アルゴリズムよりもPF-LaCGの実用的改善を示す。
関連論文リスト
- Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness [0.0]
非常に多くのスムーズで可能な非サイズの関数の平均を考慮し、この問題に対処するために2つの広く最小限のフレームワークを使用します。
IG/RRスキームの簡易制御による修正を定義する。
我々は、完全なバッチ勾配(L-BFGS)とIG/RR手法の実装の両方で実装を証明し、アルゴリズムが同様の計算作業を必要とすることを証明した。
論文 参考訳(メタデータ) (2022-12-04T15:26:36Z) - Stochastic Reweighted Gradient Descent [4.355567556995855]
SRG(stochastic reweighted gradient)と呼ばれる重要サンプリングに基づくアルゴリズムを提案する。
我々は、提案手法の時間とメモリオーバーヘッドに特に注意を払っています。
我々はこの発見を裏付ける実験結果を示す。
論文 参考訳(メタデータ) (2021-03-23T04:09:43Z) - Acceleration Methods [57.202881673406324]
まず2次最適化問題を用いて加速法を2つ導入する。
我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。
我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
論文 参考訳(メタデータ) (2021-01-23T17:58:25Z) - Improved Analysis of Clipping Algorithms for Non-convex Optimization [19.507750439784605]
最近、citetzhang 2019gradient show that clipped (stochastic) Gradient Descent (GD) converges faster than vanilla GD/SGD。
実験は、深層学習におけるクリッピングに基づく手法の優位性を確認する。
論文 参考訳(メタデータ) (2020-10-05T14:36:59Z) - Fast Gravitational Approach for Rigid Point Set Registration with
Ordinary Differential Equations [79.71184760864507]
本稿では,FGA(Fast Gravitational Approach)と呼ばれる厳密な点集合アライメントのための物理に基づく新しい手法を紹介する。
FGAでは、ソースとターゲットの点集合は、シミュレーションされた重力場内を移動しながら、世界規模で多重リンクされた方法で相互作用する質量を持つ剛体粒子群として解釈される。
従来のアライメント手法では,新しいメソッドクラスには特徴がないことを示す。
論文 参考訳(メタデータ) (2020-09-28T15:05:39Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳(メタデータ) (2020-09-23T20:02:00Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳(メタデータ) (2020-06-11T18:49:06Z) - Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart
for Nonconvex Optimization [73.38702974136102]
アルゴリズムの高速化のために,パラメータ再起動方式が提案されている。
本論文では,非滑らかな問題を解くアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-26T16:06:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。