論文の概要: 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（参考訳）: 本稿では,データ行列のスパーシティと目的関数の好適な構造に適応するランダムに外挿した原始二元座標降下法を提案する。
提案手法は,スパースデータを用いた基本変数と双変数のサブセットのみを更新し,各ケース用に設計した特定のメソッドの利点を保ちながら,高密度データを用いた大きなステップサイズを使用する。
スパーシリティに適応することに加えて、我々の手法は、いかなる修正も伴わない好ましい場合において、高速収束を保証する。
特に、計量部分正則性の下での線型収束を証明し、強い凸強凸凸問題や分数次二次函数に適用する。
一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
数値的エビデンスにより,提案手法のスパースおよび密接な設定における最先端の実証的性能,マッチングと既存手法の改良が実証された。
関連論文リスト
- A Bayesian Approach Toward Robust Multidimensional Ellipsoid-Specific Fitting [0.0]
本研究は, ノイズおよび外周波の汚染における散乱データに多次元楕円体を適合させる, 新規で効果的な方法を提案する。
楕円体領域内でのプリミティブパラメータの探索を制約するために、均一な事前分布を組み込む。
本研究では, 顕微鏡細胞計数, 3次元再構成, 幾何学的形状近似, 磁力計の校正タスクなど, 幅広い応用に応用する。
論文 参考訳（メタデータ） (2024-07-27T14:31:51Z) - Improved Distribution Matching for Dataset Condensation [91.55972945798531]
本稿では,分布マッチングに基づく新しいデータセット凝縮法を提案する。
提案手法は,計算資源の少ない従来の最適化指向手法よりも優れている。
論文 参考訳（メタデータ） (2023-07-19T04:07:33Z) - 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) - 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) - Clustering Binary Data by Application of Combinatorial Optimization
Heuristics [52.77024349608834]
本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。
近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。
準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
論文 参考訳（メタデータ） (2020-01-06T23:33:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。