Alternating Minimizations Converge to Second-Order Optimal Solutions
Authors: Qiuwei Li, Zhihui Zhu, Gongguo Tang
ICML 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This work studies the second-order convergence for both standard alternating minimization and proximal alternating minimization. We show that under mild assumptions on the (nonconvex) objective function, both algorithms avoid strict saddles almost surely from random initialization. Together with known first-order convergence results, this implies that both algorithms converge to a second-order stationary point. |
| Researcher Affiliation | Academia | 1Department of Electrical Engineering, Colorado School of Mines 2Mathematical Institute for Data Science, Johns Hopkins University. Correspondence to: Gongguo Tang <gtang@mines.edu>. |
| Pseudocode | Yes | Algorithm 1 Alternating Minimization 1: Initialization: x0. 2: For k = 1, 2, . . . , recursively generate (xk, yk) by yk = arg min y Rm f(xk 1, y), xk = arg min x Rn f(x, yk). (2) Algorithm 2 Proximal Alternating Minimization 1: Input: β > Lf. 2: Initialization: (x0, y0). 3: For k = 1, 2, . . . , recursively generate (xk, yk) by yk = arg min y Rm f(xk 1, y) + β 2 y yk 1 2 2, xk = arg min x Rn f(x, yk) + β 2 x xk 1 2 2. (3) |
| Open Source Code | No | The paper does not contain an explicit statement about the release of open-source code for the described methodology, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper is purely theoretical, focusing on mathematical convergence proofs and 'stylized applications' which are theoretical problem formulations, not empirical studies using datasets. Therefore, no information about publicly available or open datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with data splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments or software implementations with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, so no experimental setup details such as hyperparameters or training settings are provided. |