Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity

• URL: http://arxiv.org/abs/2604.00060v1
• Date: Tue, 31 Mar 2026 05:20:20 GMT
• Title: Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity
• Abstract summary: We show that Scaled iteration accelerates for ill-conditioned samples with the optimal sampling setting.<n>Results further show that Scaled convergence accelerates for ill-conditioned samples with the optimal sampling setting.
• Score: 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.

Related papers

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  First-order algorithms require at least $mathcalO(varepsilonepsilon-4)$ complexity to find an $varepsilon-stationary point.<n>We introduce novel momentum algorithms utilizing efficient variable complexity.<n>The effectiveness of the method is validated through robust logistic regression using real-world datasets.
  arXiv  Detail & Related papers  (2024-06-18T20:14:52Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  Despite being a key bottleneck in many machine learning tasks, the cost of solving large linear systems has proven challenging to quantify.<n>We consider a fine-grained notion of complexity for solving linear systems, which is motivated by applications where the data exhibits low-dimensional structure.<n>We give a algorithm based on the Sketch-and-Project paradigm, that solves the linear system $Ax = b$, that is, finds $barx$ such that $|Abarx - b| le epsilon |b|$, in time
  arXiv  Detail & Related papers  (2024-05-09T14:56:49Z)
• Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis [36.646876613637325]
  We study finite-sum distributed optimization problems involving a master node and $n-1$ local nodes. We propose two new algorithms, SVRS and AccSVRS, motivated by previous works.
  arXiv  Detail & Related papers  (2023-04-15T08:18:47Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  We propose and analyze several inexact regularized Newton-type methods for finding a global saddle point of emphconcave unconstrained problems.<n>Our method improves the existing line-search-based min-max optimization by shaving off an $O(loglog(1/eps)$ factor in the required number of Schur decompositions.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
  We solve the problem of multi-level compositional optimization, where the objective function is a limitation of multiple but possibly non-optimal functions. To make use of the Adaptive Multi-level Variance Reduction method (SMVR), we also achieves the same optimal complexities but converges faster in practice.
  arXiv  Detail & Related papers  (2022-02-15T16:02:32Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  We consider non-SBO problems that have many applications in machine learning. This paper proposes fast randomized algorithms for non-SBO problems.
  arXiv  Detail & Related papers  (2021-05-05T18:28:42Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates [12.783783498844022]
  We study smooth multi-level composition optimization problems, where the objective function is a nested composition of $T$ functions. We show that the first algorithm, which is a generalization of citeGhaRuswan20 to the $T$ level case, can achieve a sample complexity of $mathcalO (1/epsilon$6) This is the first time that such an online algorithm designed for the (un) multi-level setting, obtains the same sample complexity under standard assumptions.
  arXiv  Detail & Related papers  (2020-08-24T15:57:50Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  Zeroth-order (a.k.a, derivative-free) methods are a class of effective optimization methods for solving machine learning problems. In this paper, we propose a class faster faster zerothorder alternating gradient method multipliers (MMADMM) to solve the non finitesum problems. We show that ZOMMAD methods can achieve a lower function $O(frac13nfrac1)$ for finding an $epsilon$-stationary point. At the same time, we propose a class faster zerothorder online ADM methods (M
  arXiv  Detail & Related papers  (2019-07-30T02:21:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.