Some Unified Theory for Variance Reduced Prox-Linear Methods

2024/12/19 by Wu, Yue, Grimmer, Benjamin
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2412.15008

Abstract

This work considers the nonconvex, nonsmooth problem of minimizing a composite objective of the form f(g(x))+h(x) where the inner mapping g is a smooth finite summation or expectation amenable to variance reduction. In such settings, prox-linear methods can enjoy variance-reduced speed-ups despite the existence of nonsmoothness. We provide a unified convergence theory applicable to a wide range of common variance-reduced vector and Jacobian constructions. All the technical conditions we required for variance-reduced methods can be summarized in a single unified assumption. Our theory (i) only requires operator norm bounds on Jacobians (whereas prior works used potentially much larger Frobenius norms), (ii) provides state-of-the-art high probability guarantees, and (iii) allows inexactness in proximal computations.

Related

• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Stochastic Variance Reduction for Nonconvex Optimization
• A Stochastic Composite Gradient Method with Incremental Variance Reduction
• Variance Reduction for Faster Non-Convex Optimization
• Variance-Reduced Proximal Stochastic Gradient Descent for Non-convex Composite optimization