論文の概要: Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization
Problems
- arxiv url: http://arxiv.org/abs/2206.11523v1
- Date: Thu, 23 Jun 2022 08:10:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-24 14:35:40.533206
- Title: Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization
Problems
- Title（参考訳）: 非滑らかかつ低ランク行列最適化問題に対する低ランクミラープロキシ
- Authors: Dan Garber, Atara Kaplan
- Abstract要約: 低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。
本稿では,このような問題に対する標準凸緩和について考察する。
本研究は, テクスト性相補性条件の下で, 比較的軽度な仮定の下では, 非滑らかな目的が2つの一般的なテクストミラー-プロキシ法の近似変種であるスムーズな関数の最大値として記述できることを証明した。
- 参考スコア（独自算出の注目度）: 19.930021245647705
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Low-rank and nonsmooth matrix optimization problems capture many fundamental
tasks in statistics and machine learning. While significant progress has been
made in recent years in developing efficient methods for \textit{smooth}
low-rank optimization problems that avoid maintaining high-rank matrices and
computing expensive high-rank SVDs, advances for nonsmooth problems have been
slow paced. In this paper we consider standard convex relaxations for such
problems. Mainly, we prove that under a \textit{strict complementarity}
condition and under the relatively mild assumption that the nonsmooth objective
can be written as a maximum of smooth functions, approximated variants of two
popular \textit{mirror-prox} methods: the Euclidean \textit{extragradient
method} and mirror-prox with \textit{matrix exponentiated gradient updates},
when initialized with a "warm-start", converge to an optimal solution with rate
$O(1/t)$, while requiring only two \textit{low-rank} SVDs per iteration.
Moreover, for the extragradient method we also consider relaxed versions of
strict complementarity which yield a trade-off between the rank of the SVDs
required and the radius of the ball in which we need to initialize the method.
We support our theoretical results with empirical experiments on several
nonsmooth low-rank matrix recovery tasks, demonstrating both the plausibility
of the strict complementarity assumption, and the efficient convergence of our
proposed low-rank mirror-prox variants.
- Abstract（参考訳）: 低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。
近年,高階行列の維持や高価な高階SVDの計算が困難になるような低階最適化問題に対する効率的な手法の開発が進んでいるが,非滑らかな問題の進歩は遅れている。
本稿では,このような問題に対する標準凸緩和について考察する。
Mainly, we prove that under a \textit{strict complementarity} condition and under the relatively mild assumption that the nonsmooth objective can be written as a maximum of smooth functions, approximated variants of two popular \textit{mirror-prox} methods: the Euclidean \textit{extragradient method} and mirror-prox with \textit{matrix exponentiated gradient updates}, when initialized with a "warm-start", converge to an optimal solution with rate $O(1/t)$, while requiring only two \textit{low-rank} SVDs per iteration.
さらに, 厳密な相補性の緩和版も検討し, 必要なSVDのランクと, 初期化が必要なボール半径とのトレードオフを導出する。
我々は, 厳密な相補性仮定の妥当性と提案する低階ミラープロキシの効率的な収束の両立を実証し, 非滑らかな低階行列復元タスクを実験的に実験し, 理論的結果を支持した。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。
これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
論文 参考訳（メタデータ） (2024-02-14T10:48:00Z) - Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and
Eigenvector Disjunctions [6.537257913467247]
低ランク行列の完備化は、与えられた観測セットをできるだけ正確に回復する最小の複雑さの行列からなる。
新たな凸緩和は、既存の方法に比べて最大値を大幅に下げる。
論文 参考訳（メタデータ） (2023-05-20T22:04:34Z) - Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix
Optimization Problems [19.930021245647705]
低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。
本稿では,このような問題に対する標準凸緩和について考察する。
テキストテキストラグラディエント法は,1イテレーションあたり2つのテキスト低ランクSVDしか必要とせず,$O (1/t)$のレートで最適解に収束することを示す。
論文 参考訳（メタデータ） (2022-02-08T17:47:40Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - On the Efficient Implementation of the Matrix Exponentiated Gradient
Algorithm for Low-Rank Matrix Optimization [26.858608065417663]
スペクトル上の凸最適化は、機械学習、信号処理、統計学に重要な応用がある。
低ランク行列による最適化に適したMEGの効率的な実装を提案し、各イテレーションで単一の低ランクSVDのみを使用する。
また,本手法の正しい収束のための効率よく計算可能な証明書も提供する。
論文 参考訳（メタデータ） (2020-12-18T19:14:51Z) - Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank
Constraints [3.179831861897336]
低ランク最適化問題を証明可能な最適性に解決するためのフレームワークを提供する。
我々のフレームワークは、ラウンドリングや局所探索技術を通じて、ほぼ最適のソリューションを提供する。
論文 参考訳（メタデータ） (2020-09-22T08:59:06Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Support recovery and sup-norm convergence rates for sparse pivotal
estimation [79.13844065776928]
高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。
非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
論文 参考訳（メタデータ） (2020-01-15T16:11:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。