Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS

• URL: http://arxiv.org/abs/2608.23765v1
• Date: Mon, 24 Aug 2026 18:56:13 GMT
• Title: Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS
• Abstract summary: Iteratively reweighted least squares (IRLS) methods constitute a natural approach to nuclear norm minimization.<n>This paper shows sharp convergence rates for IRLS methods for constrained nuclear norm minimization in low-rank recovery.
• Score: 10.210183771730536
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Iteratively reweighted least squares (IRLS) methods constitute a natural approach to nuclear norm minimization, but their convergence rates and the role of the weight operator have remained poorly understood. This paper establishes sharp convergence rates for IRLS methods for constrained nuclear norm minimization in low-rank recovery. A central ingredient is a new majorization analysis for the smoothed nuclear norm: we prove that the harmonic-mean weight operator defines a valid global quadratic majorizer. Furthermore, we show that this weight operator is optimal within the family of power-mean weights, clarifying why it improves over classical one-sided reweighting schemes that use only row- or column-space information. Under a Schatten-1 null space property, we prove global linear convergence of IRLS algorithms using a variety of weight operators, including the harmonic-mean weights. For IRLS with harmonic-mean weights, we prove a dimension-independent, locally linear convergence rate. We provide a counterexample showing that this dimension-independent local rate cannot in general be obtained for IRLS algorithms using one-sided weight operators, which predominate in the literature. Numerical experiments corroborate the theoretical results and illustrate the practical advantage of harmonic-mean reweighting across square, rectangular, and adversarially initialized recovery problems.

Related papers

• Spectral-Transport Stability and Benign Overfitting in Interpolating Learning [0.0]
  We develop a theoretical framework for generalization in the interpolating regime of statistical learning.<n>We prove finite-sample risk bounds, establish a sharp benign-overfitting index, and derive explicit phase-transition rates under spectral decay.<n>The framework also clarifies implicit regularization by showing how dynamics can select interpolating solutions of minimal spectral-transport energy.
  arXiv  Detail & Related papers  (2026-04-09T15:19:00Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• ODELoRA: Training Low-Rank Adaptation by Solving Ordinary Differential Equations [54.886931928255564]
  Low-rank adaptation (LoRA) has emerged as a widely adopted parameter-efficient fine-tuning method in deep transfer learning.<n>We propose a novel continuous-time optimization dynamic for LoRA factor matrices in the form of an ordinary differential equation (ODE)<n>We show that ODELoRA achieves stable feature learning, a property that is crucial for training deep neural networks at different scales of problem dimensionality.
  arXiv  Detail & Related papers  (2026-02-07T10:19:36Z)
• A General Weighting Theory for Ensemble Learning: Beyond Variance Reduction via Spectral and Geometric Structure [0.0]
  This paper develops a general weighting theory for ensemble learning.<n>We formalize ensembles as linear operators acting on a hypothesis space.<n>We show how non-uniform, structured weights can outperform uniform averaging.
  arXiv  Detail & Related papers  (2025-12-25T08:51:01Z)
• Deterministic Coreset Construction via Adaptive Sensitivity Trimming [0.2864713389096699]
  We develop a framework for deterministic coreset construction in empirical risk minimization.<n>Our central contribution is the Adaptive Deterministic Uniform-Weight Trimming (ADUWT) algorithm.<n>We conclude with open problems on instance-optimal oracles, deterministic streaming, and fairness-constrained ERM.
  arXiv  Detail & Related papers  (2025-08-25T17:19:13Z)
• Global Convergence of Iteratively Reweighted Least Squares for Robust Subspace Recovery [16.7214745962719]
  Iteratively Reweighted Least Squares (IRLS) is an elegant and empirically effective approach to subspace estimation.<n>This paper establishes that, under deterministic conditions, a variant IRLS with dynamic regularization converges linearly to the underlying subspace.<n>We extend these guarantees to subspace estimation, a setting that lacks prior recovery theory.
  arXiv  Detail & Related papers  (2025-06-25T15:23:32Z)
• Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization [4.7464518249313805]
  Sub-gradient method (SubGM) is used to recover a low-rank matrix from a limited number of measurements. We show that SubGM converges to the true solution, even under arbitrarily large and arbitrarily dense noise values.
  arXiv  Detail & Related papers  (2022-02-17T17:50:04Z)
• Hyperspectral Image Denoising Using Non-convex Local Low-rank and Sparse Separation with Spatial-Spectral Total Variation Regularization [49.55649406434796]
  We propose a novel non particular approach to robust principal component analysis for HSI denoising. We develop accurate approximations to both rank and sparse components. Experiments on both simulated and real HSIs demonstrate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2022-01-08T11:48:46Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)

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.