mlsanityData to 7 Oct 2026

Asymptotic Dynamics of Alternating Minimization for Bilinear Regression

arXiv 2402.04751 ↗First posted 7 Feb 2024math.OC cond-mat.dis-nn stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

This study investigates the dynamics of alternating minimization applied to a bilinear regression task with normally distributed covariates, under the asymptotic system size limit where the number of parameters and observations diverge at the same rate. This is achieved by employing the replica method to a multi-temperature glassy system which unfolds the algorithm's time evolution. Our results show that the dynamics can be described effectively by a two-dimensional discrete stochastic process, where each step depends on all previous time steps, revealing the structure of the memory dependence in the evolution of alternating minimization. The theoretical framework developed in this work can be applied to the analysis of various iterative algorithms, extending beyond the scope of alternating minimization.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 29 of its 65 references that are in the map. First posted on arXiv 7 Feb 2024.

Builds on

29 of 65 references.

References · 29

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  2. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 133
  3. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  4. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  5. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
  6. 2014Matrix Completion and Low-Rank SVD via Fast Alternating Least Squarescited by 104
  7. 2022Self-Consistent Dynamical Field Theory of Kernel Evolution in Wide Neural Networkscited by 104
  8. 2020Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classificationcited by 60
  9. 2013Phase Retrieval using Alternating Minimizationcited by 58
  10. 2020Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimizationcited by 51
  11. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  12. 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
17 more
  1. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
  2. 2019Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Modelscited by 28
  3. 2016Mutual information for symmetric rank-one matrix estimation: A proof of the replica formulacited by 26
  4. 2018Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inferencecited by 24
  5. 2018Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitionscited by 23
  6. 2021Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problemcited by 23
  7. 2016Phase retrieval with random Gaussian sensing vectors by alternating projectionscited by 15
  8. 2019Landscape Complexity for the Empirical Risk of Generalized Linear Modelscited by 15
  9. 2020Solvable Model for Inheriting the Regularization through Knowledge Distillationcited by 15
  10. 2013Upper-bounding ℓ1-optimization weak thresholdscited by 13
  11. 2017Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCAcited by 12
  12. 2020Alternating Minimization Converges Super-Linearly for Mixed Linear Regressioncited by 12
  13. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  14. 2022Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initializationcited by 9
  15. 2022The Role of Pseudo-labels in Self-training Linear Classifiers on High-dimensional Gaussian Mixture Datacited by 7
  16. 2021Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problemscited by 5
  17. 2017Phase retrieval using alternating minimization in a batch settingcited by 3

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 1.

3 papers.

  1. 2024Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokenscited by 3
  2. 2025The Effect of Optimal Self-Distillation in Noisy Gaussian Mixture Modelcited by 1
  3. 2024Transfer Learning in ℓ1 Regularized Regression: Hyperparameter Selection Strategy based on Sharp Asymptotic Analysiscited by 0