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

Chiraag Kaushik, Justin Romberg, Vidya Muthukumar

TL;DR

This paper provides a unified theoretical framework to precisely predict the performance of a popular family of iterative algorithms—including IRLS and alternating minimization—used to train linear diagonal neural networks. The authors show that these algorithms can recover sparse signals in just a few iterations and that leveraging group-sparse structures in the network architecture significantly boosts performance.

What Problem Does This Paper Address?

In high-dimensional machine learning, we often want to find "sparse" solutions—models where only a few parameters are non-zero. The traditional way to do this is through non-smooth optimization like the LASSO. However, a recent trend involves "Hadamard over-parameterization," where a parameter $\theta$ is replaced by the product of two factors, $u \odot v$. This transforms the problem into a smooth, albeit non-convex, optimization task equivalent to training a Linear Diagonal Neural Network (LDNN).

While these LDNNs perform well in practice, theoretical understanding has lagged. Most existing analyses focus on "worst-case" scenarios or the properties of final fixed points. They don't tell us exactly how the estimation error evolves step-by-step or how different reweighting strategies compare in a typical "average-case" setting. This paper fills that gap by providing a precise, iteration-by-iteration characterization of these algorithms in the high-dimensional limit.

Methods

The authors analyze a general class of algorithms that alternate between two steps:

  1. Weighted Least-Squares: Updating one set of weights ($u$) based on the current state of the other ($v$).
  2. Reweighted Update: Updating $v$ using a "reweighting function" $\psi(u, v)$.

This framework is broad enough to encompass several well-known methods, as summarized in the table below:

Table 1: Some algorithms taking the form (4)

To achieve their precise characterization, the authors use the Convex Gaussian Min-Max Theorem (CGMT). They apply this tool recursively across iterations in a "sample-splitting" or "batched" setting, where each iteration uses a fresh batch of data. This allows them to track the exact distribution of the model parameters as the number of samples ($n$) and dimensions ($d$) both go to infinity.

Datasets

The paper focuses on theoretical analysis and validates its findings using synthetic datasets designed to simulate high-dimensional sparse recovery:

  • Covariates ($X$): i.i.d. standard Gaussian entries.
  • Signals ($\theta^*$): Sparse vectors with entries drawn from a Bernoulli distribution (e.g., only 1% non-zero).
  • Structured Signals: Group-sparse signals where non-zero entries appear in specific blocks.
  • Noise: i.i.d. Gaussian noise added to linear measurements.

Key Insights and Ideas

  • Unified Theory: A single asymptotic result can predict the trajectory of diverse algorithms like IRLS, lin-RFM, and Alternating Minimization (AM).
  • Efficiency: Statistically favorable solutions (low test error) are often reached in just a handful of iterations (e.g., 4–8 steps), even when the number of samples is much smaller than the total number of dimensions.
  • Oscillatory Behavior: The analysis reveals that some algorithms, particularly Alternating Minimization, can exhibit non-monotonic, "bouncing" test error trajectories before settling.
  • The Power of Grouping: By "tying" weights together in the hidden layer to match the group structure of the signal, the algorithms become much more sample-efficient. The performance then scales with the number of non-zero groups rather than the total number of non-zero coordinates.

Key Results

The authors' asymptotic predictions show remarkable alignment with numerical simulations, even for relatively modest values of $n$ and $d$.

As seen in Figure 1, different reweighting functions $\psi$ lead to distinct convergence behaviors. More "aggressive" weightings like $\psi = \text{tanh}|uv|$ can find better solutions more quickly than standard alternating minimization.

Figure 1: Theoretical predictions and simulations of the test error 1

In the group-sparse setting, the "group-aware" version of the algorithm consistently outperforms the "group-blind" version. As the group size $b$ increases, the group-aware method shows a steady improvement in test error, whereas the group-blind method's performance remains stagnant because it cannot exploit the underlying signal structure.

Limitations and Future Work

The primary limitation is the batching assumption. The current proof relies on using a new, independent batch of data at every iteration. In practice, practitioners often reuse the same dataset repeatedly. Extending this precise analysis to the "non-batched" setting remains a significant open challenge.

Additionally, while the results are exact in the limit as $n, d \to \infty$, the authors note that providing finite-sample guarantees—especially for very small batch sizes—would be a valuable direction for future research. Finally, the current analysis assumes Gaussian covariates; extending this to more general data distributions would broaden the impact of the work.

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