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

Chiraag Kaushik, Justin Romberg, Vidya Muthukumar

Precise Asymptotics of Reweighted Least-Squares Algorithms for Linear Diagonal Networks

Introduction

In high-dimensional signal processing and machine learning, the search for "sparse" solutions—where most parameters are zero—is a fundamental challenge. Traditionally, this is addressed using non-smooth optimization techniques like the LASSO. Recently, attention has shifted toward Hadamard over-parameterization, where a single parameter $\theta$ is represented as a product of two factors ($u \odot v$). This transformation converts a non-smooth problem into a smooth, albeit non-convex, optimization task that mirrors the structure of a Linear Diagonal Neural Network (LDNN).

While these methods demonstrate strong empirical performance, a precise theoretical characterization of their iteration-by-iteration behavior has been missing. Most existing theories focus on worst-case scenarios or final fixed points. This paper addresses this gap by providing an average-case trajectory analysis: exactly how does the error drop at each step of the algorithm in a high-dimensional setting?

A Unified Algorithmic Framework

The authors provide a unified asymptotic analysis for a family of algorithms that utilize different reweighting policies. These include classic methods like Iteratively Reweighted Least-Squares (IRLS) and Alternating Minimization (AM), as well as newer approaches like linear recursive feature machines (lin-RFM).

Mapping common sparse recovery algorithms to their corresponding reweighting functions.

To analyze these, the researchers utilize the Convex Gaussian Min-Max Theorem (CGMT). This framework transforms complex, high-dimensional optimization problems into simpler scalar "min-max" problems. The analysis assumes a "batched" setting, where a fresh set of independent Gaussian data is used at each iteration to maintain statistical independence, allowing for a precise distributional characterization of the parameter entries as dimensions $d$ and sample size $n$ tend toward infinity.

Theoretical Predictions vs. Empirical Results

A core achievement of this work is demonstrating that theoretical predictions (the "asymptotics") align almost perfectly with numerical simulations, even for moderate dimensions. The analysis reveals that these algorithms do not need to run to infinity; with an appropriate reweighting policy, a statistically favorable solution can be reached in fewer than 10 iterations.

Comparison of theoretical predictions (dashed lines) and empirical simulations (markers) for various reweighting functions across iterations.

As shown in the figure above, the framework captures nuanced behaviors such as the oscillatory decay in test error exhibited by Alternating Minimization (where $\psi = u$). In contrast, more "aggressive" weighting schemes, such as those employing tanh functions (e.g., $\psi = \tanh u^2$), demonstrate more stable and competitive performance. This "weather forecast" for algorithmic behavior allows researchers to select reweighting functions that optimize for both speed and stability.

The Power of Group-Awareness

Beyond individual parameter recovery, the paper explores structured sparsity. The authors demonstrate that "tying" weights together in the hidden layer—creating a grouped Hadamard parameterization—acts as a powerful structural prior. They prove that a group-aware reweighting scheme allows the error to scale with the number of groups rather than the total number of parameters. In experiments, the group-aware version of IRLS consistently outperformed "group-blind" versions, showing steady improvement as group size increased, whereas blind versions stagnated.

Limitations and Future Work

While the current analysis provides unprecedented precision, it relies on the "fresh batch" assumption to maintain statistical independence across iterations. In practice, many practitioners reuse the same dataset (the "non-batched" setting). Extending these precise predictions to the non-batched case remains a significant open challenge. Additionally, while Gaussian data serves as a robust proxy, future work could extend these results to more general data distributions and derive finite-sample guarantees for specific, smaller-scale applications.

Summary updated

Abstract

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 $\ell_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.
BibTeX
@inproceedings{kaushik2024precise,
  author = {Chiraag Kaushik and Justin Romberg and Vidya Muthukumar},
  title = {{Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=nv7ox1vd3q},
}
Figure