論文の概要: On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization

• arxiv url: http://arxiv.org/abs/2012.10469v1
• Date: Fri, 18 Dec 2020 19:14:51 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-01 18:19:05.209257
• Title: On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization
• Title（参考訳）: 低ランク行列最適化のための行列指数勾配アルゴリズムの効率的な実装について
• Authors: Dan Garber, Atara Kaplan
• Abstract要約: スペクトル上の凸最適化は、機械学習、信号処理、統計学に重要な応用がある。 低ランク行列による最適化に適したMEGの効率的な実装を提案し、各イテレーションで単一の低ランクSVDのみを使用する。 また,本手法の正しい収束のための効率よく計算可能な証明書も提供する。
• 参考スコア（独自算出の注目度）: 26.858608065417663
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Convex optimization over the spectrahedron, i.e., the set of all real $n\times n$ positive semidefinite matrices with unit trace, has important applications in machine learning, signal processing and statistics, mainly as a convex relaxation for optimization with low-rank matrices. It is also one of the most prominent examples in the theory of first-order methods for convex optimization in which non-Euclidean methods can be significantly preferable to their Euclidean counterparts, and in particular the Matrix Exponentiated Gradient (MEG) method which is based on the Bregman distance induced by the (negative) von Neumann entropy. Unfortunately, implementing MEG requires a full SVD computation on each iteration, which is not scalable to high-dimensional problems. In this work we propose efficient implementations of MEG, both with deterministic and stochastic gradients, which are tailored for optimization with low-rank matrices, and only use a single low-rank SVD computation on each iteration. We also provide efficiently-computable certificates for the correct convergence of our methods. Mainly, we prove that under a strict complementarity condition, the suggested methods converge from a "warm-start" initialization with similar rates to their full-SVD-based counterparts. Finally, we bring empirical experiments which both support our theoretical findings and demonstrate the practical appeal of our methods.
• Abstract（参考訳）: spectrahedron上の凸最適化、すなわち、単位トレースを持つすべての実$n\times n$正半定行列の集合は、機械学習、信号処理、統計学において重要な応用であり、主に低ランク行列による凸緩和のために用いられる。 これはまた、非ユークリッド法がユークリッド法に対して著しく好まれる凸最適化のための一階法の理論、特に(負の)フォン・ノイマンのエントロピーによって引き起こされるブレグマン距離に基づく行列指数勾配(meg)法の理論の最も顕著な例の1つである。 残念ながら、MEGの実装には各イテレーションで完全なSVD計算が必要である。 本稿では,低ランク行列の最適化に適した決定的勾配と確率的勾配を併用したMEGの効率的な実装を提案し,各イテレーションで1つの低ランクSVD計算のみを使用する。 また,本手法の正しい収束のための効率よく計算可能な証明書も提供する。 主に,厳密な相補条件下では,提案手法が完全svdベースと類似した「ウォームスタート」初期化から収束することを証明する。 最後に,我々の理論的知見を裏付ける実証実験を行い,本手法の実用的魅力を実証する。

関連論文リスト

• Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems [19.930021245647705]
  低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。 本稿では,このような問題に対する標準凸緩和について考察する。 本研究は, テクスト性相補性条件の下で, 比較的軽度な仮定の下では, 非滑らかな目的が2つの一般的なテクストミラー-プロキシ法の近似変種であるスムーズな関数の最大値として記述できることを証明した。
  論文  参考訳（メタデータ） (2022-06-23T08:10:54Z)
• Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms [5.011150818987905]
  まず、行列の順序付け問題に対する基本的な統計的限界を決定理論の枠組みで確立する。 そこで我々は,性能の向上を保証した新しい時間適応ソートアルゴリズムを提案する。 既存の手法よりも適応的ソートアルゴリズムの方が優れていることがシミュレーション研究および2つの実シングルセルRNAシークエンシングデータセットの解析で示されている。
  論文  参考訳（メタデータ） (2022-01-17T14:53:52Z)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。 プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。 基本的に無視可能なコストで、同時に分散を低減することができる。
  論文  参考訳（メタデータ） (2021-07-01T06:43:11Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。 クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit models [15.541264326378366]
  近年,深層ニューラルネットワークの深度を高める手法として暗黙の深度学習が登場している。 トレーニングは双レベル問題として実行され、その計算複雑性は巨大なヤコビ行列の反復反転によって部分的に駆動される。 本稿では,この計算ボトルネックに対処する新たな手法を提案する。
  論文  参考訳（メタデータ） (2021-06-01T15:07:34Z)
• On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
  本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。 これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• Automatic differentiation for Riemannian optimization on low-rank matrix and tensor-train manifolds [71.94111815357064]
  科学計算および機械学習アプリケーションでは、行列およびより一般的な多次元配列(テンソル)は、しばしば低ランク分解の助けを借りて近似することができる。 低ランク近似を見つけるための一般的なツールの1つはリーマン最適化を使うことである。
  論文  参考訳（メタデータ） (2021-03-27T19:56:00Z)
• Efficient Semi-Implicit Variational Inference [65.07058307271329]
  効率的でスケーラブルな半単純外挿 (SIVI) を提案する。 本手法はSIVIの証拠を低勾配値の厳密な推測にマッピングする。
  論文  参考訳（メタデータ） (2021-01-15T11:39:09Z)
• Gradient Descent Averaging and Primal-dual Averaging for Strongly Convex Optimization [15.731908248435348]
  強凸の場合の勾配降下平均化と主双進平均化アルゴリズムを開発する。 一次二重平均化は出力平均化の観点から最適な収束率を導出し、SC-PDAは最適な個々の収束を導出する。 SVMとディープラーニングモデルに関するいくつかの実験は、理論解析の正確性とアルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2020-12-29T01:40:30Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)

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

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