Asymptotic dynamics of alternating minimization for bilinear regression

Abstract This study investigates the dynamics of alternating minimization (AM) 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 AM. The theoretical framework developed in this work can be applied to the analysis of various iterative algorithms, extending beyond the scope of AM.