A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions

Abstract

We consider the problem of minimizing the sum of three convex functions: i) a smooth function $f$ in the form of an expectation or a finite average, ii) a non-smooth function $g$ in the form of a finite average of proximable functions $g_j$, and iii) a proximable regularizer $R$. We design a variance-reduced method which is able to progressively learn the proximal operator of $g$ via the computation of the proximal operator of a single randomly selected function $g_j$ in each iteration only. Our method can provably and efficiently accommodate many strategies for the estimation of the gradient of $f$, including via standard and variance-reduced stochastic estimation, effectively decoupling the smooth part of the problem from the non-smooth part. We prove a number of iteration complexity results, including a general $\mathcal{O}(1/t)$ rate, $\mathcal{O}(1/t^2)$ rate in the case of strongly convex smooth $f$, and several linear rates in special cases, including accelerated linear rate. For example, our method achieves a linear rate for the problem of minimizing a strongly convex function $f$ subject to linear constraints under no assumption on the constraints beyond consistency. When combined with SGD or SAGA estimators for the gradient of $f$, this leads to a very efficient method for empirical risk minimization. Our method generalizes several existing algorithms, including forward-backward splitting, Douglas-Rachford splitting, proximal SGD, proximal SAGA, SDCA, randomized Kaczmarz and Point-SAGA. However, our method leads to many new specific methods in special cases; for instance, we obtain the first randomized variant of the Dykstra's method for projection onto the intersection of closed convex sets.

arXiv comment39 pages, 3 figures, 4 tables

References in corpus (15)

• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Non-convex Finite-Sum Optimization Via SCSG Methods
• A Simple Practical Accelerated Method for Finite Sums
• SEGA: Variance Reduction via Gradient Sketching
• Proximal-Proximal-Gradient Method
• Accelerated Variance Reduced Stochastic ADMM
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
• Stochastic Three-Composite Convex Minimization
• Randomized projection methods for convex feasibility problems: conditioning and convergence rates
• Proximal Splitting Meets Variance Reduction
• A Stochastic Penalty Model for Convex and Nonconvex Optimization with Big Constraints
• Fast Stochastic Variance Reduced ADMM for Stochastic Composition Optimization
• SAGA with Arbitrary Sampling

Cited by in corpus (7)

• Federated Learning of a Mixture of Global and Local Models
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Revisiting Stochastic Extragradient
• Local SGD: Unified Theory and New Efficient Methods
• An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints
• Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters