論文の概要: Random extrapolation for primal-dual coordinate descent
- arxiv url: http://arxiv.org/abs/2007.06528v1
- Date: Mon, 13 Jul 2020 17:39:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-10 23:42:47.203405
- Title: Random extrapolation for primal-dual coordinate descent
- Title(参考訳): 原始-双対座標降下に対するランダム外挿法
- Authors: Ahmet Alacaoglu, Olivier Fercoq, Volkan Cevher
- Abstract要約: 本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。
一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
- 参考スコア(独自算出の注目度): 61.55967255151027
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a randomly extrapolated primal-dual coordinate descent method
that adapts to sparsity of the data matrix and the favorable structures of the
objective function. Our method updates only a subset of primal and dual
variables with sparse data, and it uses large step sizes with dense data,
retaining the benefits of the specific methods designed for each case. In
addition to adapting to sparsity, our method attains fast convergence
guarantees in favorable cases \textit{without any modifications}. In
particular, we prove linear convergence under metric subregularity, which
applies to strongly convex-strongly concave problems and piecewise linear
quadratic functions. We show almost sure convergence of the sequence and
optimal sublinear convergence rates for the primal-dual gap and objective
values, in the general convex-concave case. Numerical evidence demonstrates the
state-of-the-art empirical performance of our method in sparse and dense
settings, matching and improving the existing methods.
- Abstract(参考訳): 本稿では,データ行列のスパーシティと目的関数の好適な構造に適応するランダムに外挿した原始二元座標降下法を提案する。
提案手法は,スパースデータを用いた基本変数と双変数のサブセットのみを更新し,各ケース用に設計した特定のメソッドの利点を保ちながら,高密度データを用いた大きなステップサイズを使用する。
スパーシリティに適応することに加えて、我々の手法は、いかなる修正も伴わない好ましい場合において、高速収束を保証する。
特に、計量部分正則性の下での線型収束を証明し、強い凸強凸凸問題や分数次二次函数に適用する。
一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
数値的エビデンスにより,提案手法のスパースおよび密接な設定における最先端の実証的性能,マッチングと既存手法の改良が実証された。
関連論文リスト
- Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。
バイマックス性能問題を解くための優れた外挿が得られることが示されている。
論文 参考訳(メタデータ) (2022-01-19T16:14:27Z) - Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive
Step Size [29.15132344744801]
本研究では,行列逆変換などの問題に対して,適応的なステップサイズを持つ勾配勾配の局所収束性を確立する。
これらの一階最適化法は線形あるいは線形収束を実現することができることを示す。
論文 参考訳(メタデータ) (2021-12-30T00:50:30Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional
Optimization: Sharp Analysis and Lower Bounds [37.03247707259297]
2次統計が入力データを反映する相関ランダム行列をサンプリングすることにより、適切な適応部分空間を生成することができる。
ランダム化された近似の相対誤差は、データ行列のスペクトルの観点から厳密に特徴付けることができることを示した。
実験の結果,提案手法は様々な機械学習および最適化問題において,大幅な高速化を可能にすることがわかった。
論文 参考訳(メタデータ) (2020-12-13T13:02:31Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳(メタデータ) (2020-07-16T13:27:47Z) - To Each Optimizer a Norm, To Each Norm its Generalization [31.682969645989512]
過度なパラメータ化と過度なパラメータ化の条件下でのトレーニングデータを補間する線形モデルに対する最適化手法の暗黙的な正規化について検討する。
我々は、標準最大値 l2-margin への収束解析は任意であり、データによって誘導されるノルムの最小化がより良い一般化をもたらすことを示す。
論文 参考訳(メタデータ) (2020-06-11T21:07:38Z) - The Strength of Nesterov's Extrapolation in the Individual Convergence
of Nonsmooth Optimization [0.0]
ネステロフの外挿は、非滑らかな問題に対して勾配降下法の個人収束を最適にする強さを持つことを証明している。
提案手法は,設定の非滑らかな損失を伴って正規化学習タスクを解くためのアルゴリズムの拡張である。
本手法は,大規模な1-正規化ヒンジロス学習問題の解法として有効である。
論文 参考訳(メタデータ) (2020-06-08T03:35:41Z) - Accurate Optimization of Weighted Nuclear Norm for Non-Rigid Structure
from Motion [15.641335104467982]
2次法によりより正確な結果が得られることを示す。
我々の主な結果は、一般正規化子のクラスに対して双線型定式化を構築する方法を示している。
動作問題からの多くの構造について実験により,本手法が最先端の手法より優れていることを示す。
論文 参考訳(メタデータ) (2020-03-23T13:52:16Z) - Clustering Binary Data by Application of Combinatorial Optimization
Heuristics [52.77024349608834]
本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。
近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。
準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
論文 参考訳(メタデータ) (2020-01-06T23:33:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。