Incremental Methods for Weakly Convex Optimization

Abstract

Incremental methods are widely utilized for solving finite-sum optimization problems in machine learning and signal processing. In this paper, we study a family of incremental methods -- including incremental subgradient, incremental proximal point, and incremental prox-linear methods -- for solving weakly convex optimization problems. Such a problem class covers many nonsmooth nonconvex instances that arise in engineering fields. We show that the three said incremental methods have an iteration complexity of $O({\epsilon }^{-4})$ for driving a natural stationarity measure to below $\epsilon$. Moreover, we show that if the weakly convex function satisfies a sharpness condition, then all three incremental methods, when properly initialized and equipped with geometrically diminishing stepsizes, can achieve a local linear rate of convergence. Our work is the first to extend the convergence rate analysis of incremental methods from the nonsmooth convex regime to the weakly convex regime. Lastly, we conduct numerical experiments on the robust matrix sensing problem to illustrate the convergence performance of the three incremental methods.

26 pages

References in corpus (1)

• Composite optimization for robust blind deconvolution

Cited by in corpus (8)

• Random Reshuffling: Simple Analysis with Vast Improvements
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machine
• A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning
• SMG: A Shuffling Gradient-Based Method with Momentum
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates
• Zero Order Stochastic Weakly Convex Composite Optimization