Preconditioned subgradient method for composite optimization: overparameterization and fast convergence
This addresses convergence issues in composite optimization for data science and signal processing applications like phase retrieval and matrix sensing, offering a method with improved performance.
The paper tackles the slow convergence of subgradient methods in composite optimization when the smooth map is ill-conditioned or overparameterized, introducing a Levenberg-Morrison-Marquardt subgradient method that achieves linear convergence under mild conditions, with numerical experiments demonstrating its benefits.
Composite optimization problems involve minimizing the composition of a smooth map with a convex function. Such objectives arise in numerous data science and signal processing applications, including phase retrieval, blind deconvolution, and collaborative filtering. The subgradient method achieves local linear convergence when the composite loss is well-conditioned. However, if the smooth map is, in a certain sense, ill-conditioned or overparameterized, the subgradient method exhibits much slower sublinear convergence even when the convex function is well-conditioned. To overcome this limitation, we introduce a Levenberg-Morrison-Marquardt subgradient method that converges linearly under mild regularity conditions at a rate determined solely by the convex function. Further, we demonstrate that these regularity conditions hold for several problems of practical interest, including square-variable formulations, matrix sensing, and tensor factorization. Numerical experiments illustrate the benefits of our method.