Hyperparameter tuning via trajectory predictions: stochastic prox-linear methods in matrix sensing

• 成果类型: Article; Early Access
• 署名作者: Lou, Mengqi; Verchand, Kabir Aladin; Pananjady, Ashwin
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Southern California; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02279-0
• 发表日期: 2025
• 关键词: Nonconvex optimization; GLOBAL CONVERGENCE; composite

摘要

Motivated by the desire to understand stochastic algorithms for nonconvex optimization that are robust to their hyperparameter choices, we analyze a mini-batched prox-linear iterative algorithm for the canonical problem of recovering an unknown rank-1 matrix from rank-1 Gaussian measurements corrupted by noise. We derive a deterministic recursion that predicts the error of this method and show, using a non-asymptotic framework, that this prediction is accurate for any batch-size and a large range of step-sizes. In particular, our analysis reveals that this method, though stochastic, converges linearly from a local initialization with a fixed step-size to a statistical error floor. Our analysis also exposes how the batch-size, step-size, and noise level affect the (linear) convergence rate and the eventual statistical estimation error, and we demonstrate how to use our deterministic predictions to perform hyperparameter tuning (e.g. step-size and batch-size selection) without ever running the method. On a technical level, our analysis is enabled in part by showing that the fluctuations of the empirical iterates around our deterministic predictions scale with the error of the previous iterate.