Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization

By Yuchen Zhang, Xiao Lin. 2014

271 citations recorded by the source corpus.

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 method, which alternates between maximizing over one (or more) randomly chosen dual variable and minimizing over the primal variable. We also develop an extension to non-smooth and nonstrongly convex loss functions, and an extension with better convergence rate 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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “To get around this requirement, previous work has suggested implementing the Nesterov smoothing technique used in, e.g., Shalev-Shwartz and Zhang (2014); Zhang and Lin (2015) — adding a small amount of strong convexity δ (cid:107) α 22 to the objective for lasso regression.”
Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “nd Chambolle and Pork [6] discussed improved algorithms for problems with strongly convex primal or dual functions. Randomized versions of the primal-dual method have been discussed by Zhang and Xiao [64], and Dang and Lan [13]. Lan and Zhou [26] revealed some inherent relationship between Nesterov’”
A Universal Catalyst for First-Order Optimization (2015, background): “It was only known to be the case for dual coordinate ascent approaches such as SDCA [26] or SDPC [28] for strongly convex objectives.”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, methodology): “, a sum of functions of individual variables, we may apply exist ing fast gradient-techniques [1, 2, 3] to the primal problemminx∈Rd g ∗(Kx) + f(x) or the dual problemmaxy∈Rn −g(y)− f∗(K⊤y), as well as methods dedicated to separable saddle-point proble ms [11, 12].”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “SPDC can be revised to work with non-Euclidean norms, and that was done very recently by [4].”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, background): “We also mention some recent progress in accelerated stochastic coordinate gradient methods [43, 27, 53], which can be more efficient both in theory and practice.”
Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, methodology): “This minimax optimization formulation includes many machine learning applications such as regularized empirical risk minimization [41, 52], AUC maximization [39, 48], robust optimization [14, 46], adversarial training [16, 17, 40] and reinforcement learning [13, 43].”
Accelerating SVRG via second-order information (2015, methodology): “The problem of slow convergence of SGD due to high variance of the gradient estimate has been addressed successfully by the recent development of various variance-reducing stochastic gradient methods such as SVRG [8], SAG [13], SDCA [15] and Nesterov-accelerated counterparts [14, 17, 9], resulting i”
Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives (2015, background): “(cid:0) (cid:1) We work directly with smooth functions f i ( x ) rather than the more structured In the structured case, AccSDCA [23], along with subsequent works APCG [13] and SPDC [28], obtains a slightly better gradient complexity O n + min L/ε, nL/ε log 1 ε for non-strongly convex objectives.”
Coordinate descent with arbitrary sampling I: algorithms and complexity† (2014, background): “The possibility to assign different selection probabilities to different coordinates—also known as importance sampling—was considered in [24,30] and recently in [46,47].”
Optimal Black-Box Reductions Between Optimization Objectives (2016, methodology): “Some machine learning algorithms such as APCG [18], SPDC [32], AccSDCA [29] and SDCA [28] either do not satisfy HOOD or incur some additional log(L/σ) factor in its running time so cannot benefit from our new reductions in theory.”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, methodology): “This algorithm is adapted from the mini-batch stochastic primal-dual coordinate method in [200] to the problem of AUC maximization with the pairwise square loss and a strongly convex regularizer.”
Stabilizing Adversarial Nets With Prediction Methods (2017, background): “…for convex saddle-point problems can be roughly divided into two categories: stochastic coordinate descent (Dang & Lan, 2014; Lan & Zhou, 2015; Zhang & Lin, 2015; Zhu & Storkey, 2015; 2016; Wang & Xiao, 2017; Shibagaki & Takeuchi, 2017) and stochastic gradient descent (Chen et al., 2014; Qiao…”
AdaDelay: Delay Adaptive Distributed Stochastic Optimization (2016, background): “It should be distinguished from (the easier) finite-sum optimization problems [3, 18, 23, 24], for which sharper results on the empirical loss are possible but not on the generalization error.”
Less than a Single Pass: Stochastically Controlled Stochastic Gradient (2016, methodology): “[42] Yuchen Zhang and Lin Xiao.”
Importance Sampling for Minibatches (2016, methodology): “These methods include SCD [31], RCDM [20, 26], SDCA [34], Hydra [25, 6], mSDCA [36], APCG [15], AsySPDC [16], RCD [18], APPROX [5], SPDC [39], ProxSDCA [32], ASDCA [33], IProx-SDCA [40], and QUARTZ [23].”