Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization

2020/04/09 by Junyu Zhang, Lin Xiao, Zhang, Junyu +1 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2004.04357

openalex publication_date 2020/04/09 · openalex created_date 2020/04/17 · openalex updated_date 2026/07/28

Abstract

We consider minimization of composite functions of the form f(g(x))+h(x), where f and h are convex functions (which can be nonsmooth) and g is a smooth vector mapping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an ε-stationary point in terms of the total number of evaluations of the component mappings and their Jacobians. When g is a finite average of N components, we obtain sample complexity O(N+ N^4/5ε^-1) for both mapping and Jacobian evaluations. When g is a general expectation, we obtain sample complexities of O(ε^-5/2) and O(ε^-3/2) for component mappings and their Jacobians respectively. If in addition f is smooth, then improved sample complexities of O(N+N^1/2ε^-1) and O(ε^-3/2) are derived for g being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations.

Citations

• Strong Metric (Sub)regularity of KKT Mappings for Piecewise Linear-Quadratic Convex-Composite Optimization
• Composite optimization for robust blind deconvolution

Cited by

• Hinge-Proximal Stochastic Gradient Methods for Convex Optimization with Functional Constraints
• DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing
• Non-smooth stochastic gradient descent using smoothing functions

Related

• Variance-Reduced Proximal Stochastic Gradient Descent for Non-convex Composite optimization
• An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization
• A Stochastic Composite Gradient Method with Incremental Variance Reduction
• Some Unified Theory for Variance Reduced Prox-Linear Methods
• ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization