PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization

Yuchen Zhang, Lin Xiao

arXiv:1409.3257v2math.OCstat.ML

TL;DR

The paper addresses efficient optimization of regularized empirical risk minimization when datasets are large and full-gradient methods are expensive. It proposes SPDC and extensions for accelerated convergence, parallel mini-batch updates, and unnormalized data, with theory and experiments showing strong performance.

  • Problem

    Large-sample regularized empirical risk minimization makes full-gradient evaluation expensive, motivating methods that process individual component functions despite higher iteration complexity.

  • Method

    The paper proposes SPDC for the saddle-point formulation, plus mini-batch parallelization and non-uniform sampling with adaptive regularization based on feature norms.

  • Results

    SPDC converges substantially faster than SAG, SDCA, and L-BFGS on ill-conditioned synthetic ridge-regression problems, while its batch complexity can be lower than the stated batch complexity when κ > n.

  • Takeaways & Limitations

    Mini-batch SPDC preserves O(d) wall-clock time per iteration with m processors, while non-uniform sampling mitigates problems caused by uneven feature norms.

  • Takeaways & Limitations

    The κ-based complexity estimates can be loose upper bounds when the objective is strongly convex for reasons beyond the stated regularization, and convergence results rely on the specified random-coordinate sampling framework.

Abstract

from arXiv · show

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.

1 Introduction

The paper targets large-scale regularized ERM by reformulating it as a convex-concave saddle-point problem and introducing SPDC with accelerated, mini-batch, and non-uniform-sampling variants.

  • 1 Introduction: Regularized ERM of linear predictors covers classification and regression models including SVM, logistic regression, ridge regression, and Lasso.The formulation combines convex component losses with a convex regularizer.
  • 1 Introduction: Large sample counts make full-gradient methods expensive, while stochastic methods reduce per-iteration cost but require many more iterations.Full passes cost O(nd) for dense features, whereas single-sample updates cost O(d).
  • 1.1 Condition number and batch complexity: The proposed complexity is lower than O((1+κ/n) log(1/ǫ)) when κ > n and is close to a finite-sum lower bound.Batch complexity measures equivalent dataset passes needed to reach expected precision ǫ.
  • 1 Introduction: SPDC reformulates ERM as a convex-concave saddle-point problem and alternates randomized dual-coordinate maximization with primal minimization and extrapolation.The method uses convex conjugation to construct the saddle-point formulation.
  • 1.2 Outline of the paper: The framework includes smoothing and strongly convex perturbations when Assumption A fails, plus a non-uniform variant for unnormalized data.The non-uniform method adjusts sampling, regularization, and primal-update weights according to feature norms.

2 The SPDC method

SPDC solves the saddle-point formulation by updating randomly selected dual coordinates, minimizing over the primal variable, and extrapolating the primal iterate. Its mini-batch extension supports parallel updates and achieves favorable iteration and batch complexities under the stated assumptions.

  • The SPDC method: SPDC alternates between maximizing over one randomly selected dual coordinate and minimizing over the primal variable, reducing each iteration’s cost to O(d).Quadratic regularization terms stabilize the dual and primal updates.
  • The SPDC method: The primal update extrapolates from consecutive iterates, in a step similar to Nesterov’s acceleration technique that yields faster convergence.
  • Mini-Batch SPDC: Mini-Batch SPDC randomly selects m dual coordinates per iteration, extending SPDC and enabling multiple coordinate updates in one iteration.The basic SPDC method is the special case m = 1.
  • Mini-Batch SPDC: With m processors, mini-batch updates run in parallel, reducing wall-clock time per iteration to O(d), while a single processor requires O(md).The coordinate updates are independent before aggregation into the primal update.
  • Convergence and complexity: Under smooth losses and strongly convex regularization, the analysis establishes expected convergence for the iterates and the weighted primal-dual objective gap.The primal-dual gap bound uses a lemma relating primal and dual objectives to saddle-point quantities.
  • Convergence and complexity: Larger mini-batches reduce iteration counts, whereas smaller batches require fewer equivalent data passes; m = 1 is most efficient in passes, and processor-matched m minimizes wall-clock time.

3 Extensions to non-smooth or non-strongly convex functions

The method is extended beyond smooth losses and strongly convex regularizers by perturbing the saddle-point problem with strongly convex terms. With an appropriate perturbation, SPDC still provides an approximate solution to the original objective.

  • Motivation: When smoothness or strong convexity fails, the saddle-point function can be slightly perturbed so SPDC remains applicable to general loss functions.The paper discusses hinge loss and ℓ1-regularization as examples.
  • Perturbed saddle-point problem: Adding δ-strongly convex quadratic perturbations to the conjugate losses and regularizer makes the losses (1/δ)-smooth and permits Mini-Batch SPDC analysis.The construction sets γ = λ = δ in the parameter choices.
  • Convergence guarantee: Choosing δ ≤ ǫ/C1 allows optimization of the perturbed problem to yield E[P(x(T)) − P(x⋆)] ≤ ǫ for the original objective after sufficient iterations.The corresponding iteration requirement is obtained from the perturbation and convergence bounds.
  • Complexity across assumptions: The complexity table covers combinations where the losses or regularizer lack smoothness or strong convexity, using δ = ǫ/C1 for the last three cases.

4 SPDC with non-uniform sampling

The weighted-sampling SPDC method addresses sensitivity to unusually large feature norms by sampling coordinates non-uniformly and adapting regularization and primal-update weights. Its convergence parameters depend on average feature norms, improving robustness for unnormalized data.

  • Motivation: SPDC can perform badly on unnormalized data because its convergence rate depends on the largest feature-vector norm R.The issue is especially pronounced when some feature norms substantially exceed others.
  • Weighted sampling: Weighted SPDC samples dual coordinates non-uniformly, with larger-norm instances selected more frequently through a parameter α.The sampling distribution combines uniform sampling with sampling proportional to feature norms.
  • Weighted sampling: The method simultaneously applies stronger adaptive regularization to large-norm instances and adjusts their primal-update weights.These changes accompany the non-uniform sampling scheme.
  • Convergence parameters: Algorithm 3 uses the average feature norm R̄ rather than the maximum norm R to determine τ, σ, and θ, making it more robust to unnormalized features.This replaces the largest-norm dependence in the convergence parameters.
  • Convergence parameters: For i.i.d. multivariate-normal features, the maximum norm diverges as n grows while the average norm converges to E[∥a_i∥2].This illustrates why average-norm scaling can be more stable as the dataset grows.
  • Sampling choice: The optimal α varies with n/R̄κ: it is 1/2 when R̄κ = n, decreases toward zero as n/R̄κ grows, and increases toward one as the ratio falls.The paper recommends relatively uniform sampling for well-conditioned problems and more aggressive weighting for ill-conditioned ones.
  • Extension: The non-uniform sampling scheme can also be extended to Mini-Batch SPDC with m > 1, although technical details are omitted.Algorithm 3 presents the single-coordinate case m = 1.

5 Related Work

The paper situates SPDC among primal-dual, coordinate, proximal, ADMM, and incremental-gradient methods for regularized empirical risk minimization. It emphasizes SPDC’s single-loop coordinate structure and comparisons in batch complexity, including advantages in ill-conditioned settings.

  • Primal-dual methods: Chambolle–Pock’s batch primal-dual method applies to strongly convex saddle-point problems and achieves accelerated linear convergence with suitable parameters.SPDC extends this framework by replacing the full dual update with coordinate or mini-batch updates and modifying the primal step.
  • Primal-dual methods: SPDC maps the empirical-risk saddle problem into the Chambolle–Pock form using A = [a1, …, an]T and corresponding strong-convexity parameters.The paper compares equivalent parameters and batch complexities in Table 2.
  • Generalizations: The formulation generalizes to matrix-valued operators and smooth convex component losses, and related randomized incremental-gradient methods achieve the same order of iteration complexity.Lan identifies the dual coordinate proximal mapping with primal gradients at particular points in a special case.
  • Coordinate methods: Coordinate methods reduce cost relative to full gradients by updating one dual coordinate, while full-gradient passes over dense data cost O(nd) operations.SDCA has iteration complexity O((n + κ) log(1/ε)) and equivalent batch complexity O((1 + κ/n) log(1/ε)).
  • Coordinate methods: Compared with SDCA, SPDC uses additional primal updates and has better complexity for ill-conditioned problems when the mini-batch size is one.Accelerated mini-batch SDCA matches AFG at m = n, but at m = 1 its complexity is the same as SDCA and worse than SPDC for ill-conditioned problems.
  • Proximal coordinate methods: Accelerated proximal SDCA and APCG attain the same batch complexity order as SPDC, but their procedures include additional algorithmic steps.Accelerated proximal SDCA uses an inner–outer procedure, while APCG requires an extra primal proximal-gradient step for primal-dual-gap guarantees.
  • ADMM methods: ADMM-type methods provide another route through constrained reformulations, while stochastic ADMM variants operate on one component function per iteration and obtain sublinear convergence rates.The batch primal-dual algorithm is equivalent to a preconditioned ADMM or inexact Uzawa method.
  • ADMM methods: For more complex regularizers without simple proximal mappings, Suzuki combines SDCA and ADMM and establishes a linear convergence rate under conditions similar to Assumption A.The paper notes this as a setting where SPDC’s primal updates are not efficiently computable.

6 Efficient Implementation with Sparse Data

Sparse feature vectors let SPDC avoid full d-dimensional primal operations by delaying inactive coordinate updates and processing only coordinates touched by the sampled features. The resulting per-iteration cost depends on feature sparsity rather than ambient dimension.

  • Sparse implementation: Standard SPDC primal updates require full d-dimensional vector operations, giving O(d) cost per iteration, which can be expensive in high dimensions.The sparse implementation exploits the structure of feature vectors to avoid this cost.
  • Squared ℓ2-norm penalty: For squared ℓ2 regularization, the primal coordinates update independently and can be computed coordinate-wise in closed form.The implementation uses the resulting recurrence to recover delayed coordinates efficiently.
  • Delayed updates: When sampled feature vectors are sparse, J(t) denotes their non-zero coordinates, and coordinates outside J(t) need not be used in the current dual update.Their missing primal updates can be processed later when those coordinates become active.
  • Delayed updates: Primal-coordinate updates can be delayed because inactive coordinates do not affect the sampled dual update and can be recovered when they next enter J(t).This preserves the required updates while avoiding work on untouched coordinates.
  • Squared ℓ2-norm penalty: The delayed update in the sparse squared-ℓ2 implementation takes O(1) time to compute using the recursive formula.The same formula also recovers the previous iterate coordinate before computing the current update.
  • Complexity: With sparse features, a single SPDC iteration has computational complexity proportional to |J(t)| and independent of d.The same sparsity-dependent scaling is stated for the ℓ1 + ℓ2 penalty case.
  • ℓ1 + ℓ2 penalty: For the ℓ1 + ℓ2 penalty, decomposability makes coordinate updates independent, and inactive coordinates have Δu_j = 0.The update can therefore be simplified and delayed similarly to the squared-ℓ2 case.

7 Experiments

The experiments compare SPDC with batch and stochastic optimization methods on synthetic ridge-regression and real-data classification tasks. Across the tested scenarios, SPDC is comparable or better, with advantages depending on conditioning and regularization.

  • Experimental setup: The experiments compare SPDC with accelerated full gradient, L-BFGS, SAG, SDCA, and ASDCA on synthetic and real datasets.The evaluation includes batch and randomized incremental or coordinate methods.
  • Experimental setup: The evaluation uses logarithmic optimality gap against passes through the entire dataset as its convergence measure.For the synthetic experiment, the regularization coefficient varies over λ ∈ {10^-3, 10^-4, 10^-5, 10^-6}.
  • Ridge regression with synthetic data: When λ is relatively large, stochastic methods including SPDC converge substantially faster than AFG and L-BFGS on the synthetic problem.This regime corresponds to a well-conditioned problem.
  • Ridge regression with synthetic data: When the condition number exceeds n, SPDC converges substantially faster than SAG and SDCA and is notably faster than L-BFGS.The reported batch-complexity comparisons are up to √n faster than AFG and (λn)^-1/2 faster than SAG and SDCA.
  • Binary classification with real data: On real classification data, SPDC is faster than AFG and L-BFGS for relatively large λ, while the batch methods become comparable as λ decreases to 10^-8.The datasets cover n ≫ d, n ≈ d, and n ≪ d regimes.
  • Binary classification with real data: For small λ on real data, SPDC is faster than SAG and SDCA; ASDCA is faster on Covtype, whereas SPDC is faster on RCV1 and News20.SPDC’s convergence curve is described as almost linear and more stable than ASDCA’s, whose error rate oscillates.
  • Binary classification with real data: Across Figures 2 and 3, SPDC’s performance is always comparable or better than the other methods in comparison.This summarizes the reported real-data comparisons.

A Proof of Theorem 1

The proof establishes a one-step contraction for a potential function tracking primal and dual progress under random coordinate updates. Recursive application yields the theorem’s convergence bound.

  • Coordinate updates: The proof characterizes the updated dual coordinates and primal iterate after each mini-batch coordinate update.Coordinates in K are updated with probability m/n; unselected coordinates retain their previous values.
  • One-step bounds: Strong convexity of the primal subproblem and strong concavity of the dual subproblem provide inequalities relating successive primal and dual iterates.The dual curvature is expressed through the strong convexity of the conjugate terms.
  • Potential contraction: The proof combines the primal, dual, and saddle-point inequalities, then chooses τ, σ, and θ so corresponding potential terms contract by θ.The parameter matching is used to derive the recursive inequality for the potential sequence.
  • Conclusion: Bounds on the matrix norm and the random-update terms complete the conversion from the auxiliary potential to the desired theorem statement.The argument uses ∥A∥_F^2 ≤ nR^2 and m ≤ n.
  • Conclusion: The resulting recursion E∆(t+1) ≤ θ E∆(t) is applied repeatedly to obtain a geometric convergence relation.Initial-iterate terms are handled by setting x(-1) = x(0) and showing the remaining terms are nonnegative.
  • Conclusion: The proof concludes by establishing the stated bound and identifying it as the desired result.

B Proof of Lemma 1

The lemma proof uses smoothness of the primal and dual reduced objectives to relate their gaps to primal and dual saddle-point quantities. Norm bounds then yield the stated inequalities.

  • Primal bound: Assumption A makes F smooth with gradient-Lipschitz constant ∥A∥_2^2/(nγ), bounded above by R^2/γ.The bound follows from ∥A∥_2^2 ≤ ∥A∥_F^2 ≤ nR^2.
  • Primal bound: At the saddle point, ∇F(x⋆) = (1/n)A^T y⋆, allowing the smoothness inequality to be combined with P(x) = F(x) + g(x).
  • Primal bound: The first desired inequality follows from the preceding smoothness and saddle-point relations.
  • Dual bound: The dual reduced objective has gradient-Lipschitz constant at most R^2/(nλ), obtained from the corresponding spectral-norm bound.
  • Dual bound: Using the dual saddle-point identity yields the second inequality, completing the lemma proof.

C Proof of Theorem 2

The proof of Theorem 2 extends the one-step primal-dual analysis to weighted coordinate sampling. Sampling probabilities and parameter choices produce a contraction recursion and the claimed result.

  • Iterate relations: The proof derives relations for successive dual and primal iterates using the same update analysis as the basic method.It also uses strong convexity of the dual conjugate terms and of the primal objective around x⋆.
  • Weighted sampling: Weighted sampling probabilities satisfy bounds involving the data-dependent quantity R̄, which enters the step-size analysis.
  • Contraction: Combining the update inequalities with the parameter assignments yields a recursive potential relation ∆(t+1) ≤ θ · ∆(t).The proof uses στR̄^2 = α^2/4 and the lower bound on p_i in this combination.
  • Conclusion: The remaining potential terms are eliminated using strong convexity and norm identities, completing the theorem.The argument substitutes the resulting bound into the preceding inequality.

D Efficient update for (ℓ1 + ℓ2)-norm penalty

The appendix develops an efficient procedure for calculating x(t1)_j by examining signs, using recursive or closed-form updates, and selecting boundary times. Monotonicity ensures that the resulting algorithm has O(1) time complexity.

  • Sign-based cases: The procedure begins by examining the sign of x(t0+1)_j and then uses corresponding closed-form expressions or recursive updates.Positive and negative cases are handled separately, with recursive formula (57) used when needed.
  • Boundary-time selection: For positive or negative trajectories, t+ or t− is chosen as the largest integer in [t0 + 1, t1] satisfying the relevant positivity condition or inequality.The procedure then treats the selected boundary time as the new t0 for subsequent case handling.
  • Complexity: Monotonicity of x(t)_j means that Case I, Case II, or Case III is executed at most once.This monotonicity follows from formula (57) over the relevant iterations.
  • Complexity: The algorithm for calculating x(t1)_j has O(1) time complexity.The constant-time result follows from the monotonicity-based restriction on case execution.
Loading 1409.3257v2…