論文の概要: Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity

• arxiv url: http://arxiv.org/abs/2604.00060v1
• Date: Tue, 31 Mar 2026 05:20:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-02 16:44:31.654668
• Title: Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity
• Title（参考訳）: 最適サンプリング複雑度を有するIll-Conditioned Low-Rank MatrixリカバリのためのスケールドグラディエントDescent
• Authors: Zhenxuan Li, Meng Huang,
• Abstract要約: 最適サンプリング設定を施した不条件サンプルに対して,スケールド・イテレーションが高速化されることを示す。 さらに, 最適サンプリング設定による不条件試料に対するスケールド収束が促進されることが示唆された。
• 参考スコア（独自算出の注目度）: 1.655804338897892
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The low-rank matrix recovery problem seeks to reconstruct an unknown $n_1 \times n_2$ rank-$r$ matrix from $m$ linear measurements, where $m\ll n_1n_2$. This problem has been extensively studied over the past few decades, leading to a variety of algorithms with solid theoretical guarantees. Among these, gradient descent based non-convex methods have become particularly popular due to their computational efficiency. However, these methods typically suffer from two key limitations: a sub-optimal sample complexity of $O((n_1 + n_2)r^2)$ and an iteration complexity of $O(κ\log(1/ε))$ to achieve $ε$-accuracy, resulting in slow convergence when the target matrix is ill-conditioned. Here, $κ$ denotes the condition number of the unknown matrix. Recent studies show that a preconditioned variant of GD, known as scaled gradient descent (ScaledGD), can significantly reduce the iteration complexity to $O(\log(1/ε))$. Nonetheless, its sample complexity remains sub-optimal at $O((n_1 + n_2)r^2)$. In contrast, a delicate virtual sequence technique demonstrates that the standard GD in the positive semidefinite (PSD) setting achieves the optimal sample complexity $O((n_1 + n_2)r)$, but converges more slowly with an iteration complexity $O(κ^2 \log(1/ε))$. In this paper, through a more refined analysis, we show that ScaledGD achieves both the optimal sample complexity $O((n_1 + n_2)r)$ and the improved iteration complexity $O(\log(1/ε))$. Notably, our results extend beyond the PSD setting to general low-rank matrix recovery problem. Numerical experiments further validate that ScaledGD accelerates convergence for ill-conditioned matrices with the optimal sampling complexity.
• Abstract（参考訳）: 低ランク行列回復問題は、未知の$n_1 \times n_2$ rank-$r$ matrixを$m$線型測度から再構成し、$m\ll n_1n_2$とする。 この問題は過去数十年にわたって広く研究され、しっかりとした理論的保証を持つ様々なアルゴリズムが導かれた。 これらのうち、勾配降下に基づく非凸法は、その計算効率のために特に人気がある。 しかし、これらの手法には2つの重要な制限がある:$O((n_1 + n_2)r^2)$の準最適サンプル複雑性と$O(κ\log(1/ε))$の反復複雑性。 ここで、$κ$は未知行列の条件数を表す。 近年の研究では、スケールド勾配勾配勾配 (ScaledGD) と呼ばれるGDの事前条件付き変種が、反復の複雑さを$O(\log(1/ε))$に著しく減少させることが示されている。 それでも、サンプルの複雑さは、$O((n_1 + n_2)r^2)$で準最適のままである。 対照的に繊細な仮想シーケンス法では、正半定値(PSD)設定の標準GDが最適なサンプル複雑性$O((n_1 + n_2)r)$を達成するが、よりゆっくりと反復複雑性$O(κ^2 \log(1/ε))$に収束する。 本稿では、より洗練された解析により、ScaledGD が最適なサンプル複雑性 $O((n_1 + n_2)r)$ と改善された反復複雑性 $O(\log(1/ε))$ の両方を達成することを示す。 特に,本研究の結果はPSD設定を超えて,一般的な低ランク行列回復問題にまで拡張されている。 数値実験により、ScaledGDは最適サンプリング複雑性で不条件行列の収束を加速することが示された。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。 本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。 本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
  論文  参考訳（メタデータ） (2024-06-18T20:14:52Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  多くの機械学習タスクにおいて重要なボトルネックとなっているが、大規模な線形システムの解決コストは定量化が難しいことが証明されている。 低次元構造を示すアプリケーションによって動機づけられた線形システムの解法における複雑性の微妙な概念を考察する。 線形システム $Ax = b$, すなわち $|Abarx - b| le epsilon |b|$ であるような $barx$ を求める。
  論文  参考訳（メタデータ） (2024-05-09T14:56:49Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
  目的関数が複数の最適でない関数の制限である多段階合成最適化の問題を解く。 また,適応型多レベル分散低減法 (SMVR) を用いることで,同じ複雑性を実現するが,実際はより高速に収束する。
  論文  参考訳（メタデータ） (2022-02-15T16:02:32Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates [12.783783498844022]
  目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。 citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。 これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
  論文  参考訳（メタデータ） (2020-08-24T15:57:50Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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