# Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks

arXiv: https://arxiv.org/abs/2406.02769 · HTML: https://mlsanity.com/paper/2406.02769/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 4 Jun 2024.

## Builds on (most cited first, 13 of 13)

- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity](https://mlsanity.com/paper/2106.09524/) (2021)
- [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019)
- [Provable Benefits of Overparameterization in Model Compression: From Double Descent to Pruning Neural Networks](https://mlsanity.com/paper/2012.08749/) (2020)
- [High-Dimensional Linear Regression via Implicit Regularization](https://mlsanity.com/paper/1903.09367/) (2019)
- [More is Less: Inducing Sparsity via Overparameterization](https://mlsanity.com/paper/2112.11027/) (2021)
- [Linear Recursive Feature Machines provably recover low-rank matrices](https://mlsanity.com/paper/2401.04553/) (2024)
- [Smooth Bilevel Programming for Sparse Regularization](https://mlsanity.com/paper/2106.01429/) (2021)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization](https://mlsanity.com/paper/2207.09660/) (2022)
- [Implicit Regularization for Group Sparsity](https://mlsanity.com/paper/2301.12540/) (2023)
- [Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensing](https://mlsanity.com/paper/2402.01599/) (2024)
- [Random Features Model with General Convex Regularization: A Fine Grained Analysis with Precise Asymptotic Learning Curves](https://mlsanity.com/paper/2204.02678/) (2022)

## Built on by (most cited first, 2 of 2)

- [Accurate, provable and fast polychromatic tomographic reconstruction: A variational inequality approach](https://mlsanity.com/paper/2503.19925/) (2025)
- [Extending Occam's inversion with lasso fusion, overcomplete dictionaries, and isotropic total variation regularisation](https://mlsanity.com/paper/2608.14225/) (2026)

## Abstract (arXiv)

The classical iteratively reweighted least-squares (IRLS) algorithm aims to recover an unknown signal from linear measurements by performing a sequence of weighted least squares problems, where the weights are recursively updated at each step. Varieties of this algorithm have been shown to achieve favorable empirical performance and theoretical guarantees for sparse recovery and ℓp-norm minimization. Recently, some preliminary connections have also been made between IRLS and certain types of non-convex linear neural network architectures that are observed to exploit low-dimensional structure in high-dimensional linear models. In this work, we provide a unified asymptotic analysis for a family of algorithms that encompasses IRLS, the recently proposed lin-RFM algorithm (which was motivated by feature learning in neural networks), and the alternating minimization algorithm on linear diagonal neural networks. Our analysis operates in a "batched" setting with i.i.d. Gaussian covariates and shows that, with appropriately chosen reweighting policy, the algorithm can achieve favorable performance in only a handful of iterations. We also extend our results to the case of group-sparse recovery and show that leveraging this structure in the reweighting scheme provably improves test error compared to coordinate-wise reweighting.