Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk\n Minimization

2014/09/10 by Yuchen Zhang, Lin Xiao, Zhang, Yuchen +1 · 13 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1409.3257

openalex publication_date 2014/09/10 · openalex created_date 2025/10/27 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Stochastic Optimization with Importance Sampling
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence\n Results and Optimal Averaging Schemes
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Smooth minimization of non-smooth functions
• MapReduce
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Numerical optimization

Cited by

• Accelerated Variance Reduced Block Coordinate Descent
• Stochastic Dual Ascent for Solving Linear Systems
• Unbiased Gradient Low-Rank Projection
• A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization
• Reducing Runtime by Recycling Samples
• Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problems
• Optimal Black-Box Reductions Between Optimization Objectives
• Fast Global Convergence via Landscape of Empirical Loss
• Stochastic versus Deterministic in Stochastic Gradient Descent
• A Universal Catalyst for First-Order Optimization
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization
• Stochastic variance reduced multiplicative update for nonnegative matrix factorization
• Fast Saddle-Point Algorithm for Generalized Dantzig Selector and FDR Control with the Ordered l1-Norm

Related

• Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity
• Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems