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).
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.
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