論文の概要: Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems

• arxiv url: http://arxiv.org/abs/2202.04026v1
• Date: Tue, 8 Feb 2022 17:47:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-09 15:03:22.425518
• Title: Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems
• Title（参考訳）: 非滑らか・低ランク行列最適化問題に対する低ランク超勾配法
• Authors: Dan Garber, Atara Kaplan
• Abstract要約: 低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。 本稿では,このような問題に対する標準凸緩和について考察する。 テキストテキストラグラディエント法は,1イテレーションあたり2つのテキスト低ランクSVDしか必要とせず,$O (1/t)$のレートで最適解に収束することを示す。
• 参考スコア（独自算出の注目度）: 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 natural \textit{generalized strict complementarity} condition and under the relatively mild assumption that the nonsmooth objective can be written as a maximum of smooth functions, the \textit{extragradient method}, when initialized with a "warm-start" point, converges to an optimal solution with rate $O(1/t)$ while requiring only two \textit{low-rank} SVDs per iteration. We give a precise 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 that using simple initializations, the extragradient method produces exactly the same iterates when full-rank SVDs are replaced with SVDs of rank that matches the rank of the (low-rank) ground-truth matrix to be recovered.
• Abstract（参考訳）: 低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。 近年,高階行列の維持や高価な高階SVDの計算が困難になるような低階最適化問題に対する効率的な手法の開発が進んでいるが,非滑らかな問題の進歩は遅れている。 本稿では,このような問題に対する標準凸緩和について考察する。 主に、自然な \textit{ Generalized strict complementarity} 条件と、非滑らかな目的が滑らかな関数の最大値として記述できるという比較的穏やかな仮定の下では、 \textit{extragradient method} が "warm-start" 点で初期化されると、反復毎に2つの \textit{low-rank} SVD しか必要とせず、速度$O(1/t)$ で最適解に収束する。 我々は,必要なSVDのランクと,そのメソッドを初期化する必要があるボールの半径との間に,正確なトレードオフを与える。 我々は,非滑らかな低ランク行列回復タスクに関する実験的な実験を行い,全ランクSVDを(低ランクの)接地トラス行列のランクに一致するランクの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)
• Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis [17.596465452814883]
  現在の双レベル最適化アルゴリズムは、上層関数の反復が非有界な滑らかであると仮定する。 最近の研究では、あるニューラルネットワークがそのような非有界な滑らかさを示すことが示されている。
  論文  参考訳（メタデータ） (2024-01-17T20:28:15Z)
• Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems [19.930021245647705]
  低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。 本稿では,このような問題に対する標準凸緩和について考察する。 本研究は, テクスト性相補性条件の下で, 比較的軽度な仮定の下では, 非滑らかな目的が2つの一般的なテクストミラー-プロキシ法の近似変種であるスムーズな関数の最大値として記述できることを証明した。
  論文  参考訳（メタデータ） (2022-06-23T08:10:54Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。 クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  そこで我々は,適応的かつ音質の高い"核フロベニウスノルム"と呼ばれる新しい非スケーラブルな低ランク正規化器を提案する。 特異値の計算をバイパスし、アルゴリズムによる高速な最適化を可能にする。 既存の行列学習手法では最速でありながら、最先端の回復性能が得られる。
  論文  参考訳（メタデータ） (2020-08-14T18:47:58Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Learning Low-rank Deep Neural Networks via Singular Vector Orthogonality Regularization and Singular Value Sparsification [53.50708351813565]
  各ステップにSVDを適用することなく、トレーニング中に低ランクDNNを明示的に達成する最初の方法であるSVDトレーニングを提案する。 SVDトレーニングがDNN層のランクを著しく低減し,同じ精度で計算負荷の低減を実現することを実証的に示す。
  論文  参考訳（メタデータ） (2020-04-20T02:40:43Z)
• On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems [19.24470467199451]
  本研究では, 凸緩和に有効な凸最適化問題の解法として, SGD (Gradient Descent) の利用を再検討する。 我々は,SGDが低ランク行列回復問題の大規模凸緩和に実際に適用可能であることを示した。
  論文  参考訳（メタデータ） (2020-01-31T06:00:34Z)

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

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