Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization

Abstract

We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variable. An extrapolation step on the primal variable is performed to obtain accelerated convergence rate. We also develop a mini-batch version of the SPDC method which facilitates parallel computing, and an extension with weighted sampling probabilities on the dual variables, which has a better complexity than uniform sampling on unnormalized data. Both theoretically and empirically, we show that the SPDC method has comparable or better performance than several state-of-the-art optimization methods.

References in corpus (4)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction

Cited by in corpus (34)

• A Universal Catalyst for First-Order Optimization
• Variance Reduction for Faster Non-Convex Optimization
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• A Primer on Coordinate Descent Algorithms
• Stochastic Dual Ascent for Solving Linear Systems
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Importance Sampling for Minibatches
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling
• L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework
• Primal-Dual Rates and Certificates
• Riemannian stochastic variance reduced gradient on Grassmann manifold
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
• Primal-dual block-proximal splitting for a class of non-convex problems
• Fast Saddle-Point Algorithm for Generalized Dantzig Selector and FDR Control with the Ordered l1-Norm
• SAGA and Restricted Strong Convexity
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
• Coordinate Linear Variance Reduction for Generalized Linear Programming
• Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem
• Reducing Runtime by Recycling Samples
• Stochastic variance reduced multiplicative update for nonnegative matrix factorization
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization
• Stochastic Variance Reduction Gradient for a Non-convex Problem Using Graduated Optimization
• Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problems
• Accelerated Variance Reduced Block Coordinate Descent
• On Structured Filtering-Clustering: Global Error Bound and Optimal First-Order Algorithms
• Random gradient extrapolation for distributed and stochastic optimization
• Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization
• Fast Global Convergence via Landscape of Empirical Loss