Research map / Learning theory and algorithms / Matrix and tensor methods
Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives an exact asymptotic (high-dimensional, batched, sample-split) characterization of reweighted least-squares iterates for linear diagonal networks, covering AM, reparameterized IRLS and lin-RFM, and extends it to group-reweighting for group-sparse recovery.
Problem
Understanding the average-case (test error) behavior of iterative reweighted least-squares and related algorithms for learning Hadamard/linear diagonal network parameterizations of sparse linear models, which worst-case analyses do not capture.
Approach
Uses a batched setting with fresh i.i.d. Gaussian data each iteration and applies a perturbed Convex Gaussian Min-Max argument to derive a scalar recursion (tau, beta, Q, Pi) that exactly predicts the joint empirical distribution of iterates; extends this to block-wise (grouped) reweighting that exploits group structure.
Key results
- Asymptotic predictions match simulations (n=250, d=2000, E[s]=20) across four reweighting functions over iterations, with aggressive weightings like tanh|uv| and tanh u^2 finding better solutions after several iterations.
- Group-aware reweighting psi_ga improves l1 test error over group-blind tanh|uv| for group size b>1 at n=500, d=4000, with error scaling with number of groups rather than total sparsity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use group-aware reweighting instead of coordinate-wise group-blind reweighting | Grouped IRLS · Group-sparse linear regression | ℓ1 test error | Helped |
| Increase group size with group-aware reweighting | Grouped IRLS with ψ_ga · Group-sparse linear regression | test error | Helped |
| Increase group size with group-blind coordinate-wise reweighting | Grouped IRLS with ψ_gb · Group-sparse linear regression | test error | No clear effect |
| Use aggressive weightings tanh|uv| or tanh u² | Iterative least-squares algorithms for linear diagonal networks · Sparse linear regression | test error | Helped |
| Use a weighting function of u² rather than alternating minimization's u-based weighting | Iterative least-squares algorithms for linear diagonal networks · Sparse linear regression | test error | No clear effect |
Surprising findings
- Reweighting functions depending only on u (alternating minimization) show non-monotonic, oscillatory test loss decay, with steady decrease only after every pair of iterations.
Limitations
- Requires batched setting with fresh i.i.d. Gaussian data per iteration; analysis does not cover the non-batched setting.
- Proof needs bounded entries of target signal and bounded reweighting assumptions; aggressive weightings like |uv| are excluded and need bounded activation.
- Asymptotic only, no finite-sample guarantees.
Experimental setup
Metrics: normalized l1 test error test loss trajectory
Baselines: alternating minimization reparameterized IRLS lin-RFM group-blind reweighting
Builds on: convex gaussian min-max theorem eta-trick iteratively reweighted least squares lin-RFM Hadamard parameterization
Closest papers by meaning
- Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate (NeurIPS 2021 · similarity 0.91)
- Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares (NeurIPS 2023 · similarity 0.89)
- Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks (NeurIPS 2025 · similarity 0.86)
- Reweighted Solutions for Weighted Low Rank Approximation (ICML 2024 · similarity 0.86)
- Iterative Regularization with k-support Norm: An Important Complement to Sparse Recovery (AAAI 2024 · similarity 0.85)
- The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.