# Asymptotic Dynamics of Alternating Minimization for Bilinear Regression

arXiv: https://arxiv.org/abs/2402.04751 · HTML: https://mlsanity.com/paper/2402.04751/

## Key facts

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

## Builds on (most cited first, 29 of 29)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Self-Consistent Dynamical Field Theory of Kernel Evolution in Wide Neural Networks](https://mlsanity.com/paper/2205.09653/) (2022)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification](https://mlsanity.com/paper/2006.06098/) (2020)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization](https://mlsanity.com/paper/2006.06560/) (2020)
- [Phase retrieval in high dimensions: Statistical and computational phase transitions](https://mlsanity.com/paper/2006.05228/) (2020)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models](https://mlsanity.com/paper/1902.00139/) (2019)
- [Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula](https://mlsanity.com/paper/1606.04142/) (2016)
- [Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference](https://mlsanity.com/paper/1812.09066/) (2018)
- [Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions](https://mlsanity.com/paper/1804.02686/) (2018)
- [Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem](https://mlsanity.com/paper/2103.04902/) (2021)
- [Solvable Model for Inheriting the Regularization through Knowledge Distillation](https://mlsanity.com/paper/2012.00194/) (2020)
- [Phase retrieval with random Gaussian sensing vectors by alternating projections](https://mlsanity.com/paper/1609.03088/) (2016)
- [Landscape Complexity for the Empirical Risk of Generalized Linear Models](https://mlsanity.com/paper/1912.02143/) (2019)
- [Upper-bounding ℓ1-optimization weak thresholds](https://mlsanity.com/paper/1303.7289/) (2013)
- [Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA](https://mlsanity.com/paper/1711.01742/) (2017)
- [Alternating Minimization Converges Super-Linearly for Mixed Linear Regression](https://mlsanity.com/paper/2004.10914/) (2020)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization](https://mlsanity.com/paper/2207.09660/) (2022)
- [The Role of Pseudo-labels in Self-training Linear Classifiers on High-dimensional Gaussian Mixture Data](https://mlsanity.com/paper/2205.07739/) (2022)
- [Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems](https://mlsanity.com/paper/2102.11755/) (2021)
- [Phase retrieval using alternating minimization in a batch setting](https://mlsanity.com/paper/1706.08167/) (2017)

## Built on by (most cited first, 3 of 3)

- [Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens](https://mlsanity.com/paper/2410.18858/) (2024)
- [The Effect of Optimal Self-Distillation in Noisy Gaussian Mixture Model](https://mlsanity.com/paper/2501.16226/) (2025)
- [Transfer Learning in ℓ1 Regularized Regression: Hyperparameter Selection Strategy based on Sharp Asymptotic Analysis](https://mlsanity.com/paper/2409.17704/) (2024)

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