Source-linked AI summary
Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization
Shai Shalev-Shwartz, Tong Zhang
TL;DR
The paper addresses efficient regularized loss minimization for linear predictors, including settings with broad regularizer and loss-function structures. It introduces proximal SDCA and accelerates it through strongly regularized inner problems. The resulting runtime improves state-of-the-art results across several machine-learning optimization problems, while the acceleration procedure remains tied to Euclidean-strongly-convex regularizers.
Problem
The paper studies how to efficiently solve regularized loss minimization for linear predictors across convex losses and regularizers.
Method
It combines proximal stochastic dual coordinate ascent with an inner-outer acceleration procedure that solves a sequence of more strongly regularized problems.
Results
The resulting method improves state-of-the-art runtime results for several machine-learning optimization problems, including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM.
Takeaways & Limitations
The framework supports general strongly convex regularizers and vector-valued losses, extending proximal SDCA to multiclass and nonsmooth-loss settings.
Takeaways & Limitations
The acceleration procedure is designed for regularizers strongly convex with respect to the Euclidean norm, leaving extension to arbitrary norms open.
Abstract
from arXiv · showhide
We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates that improve state-of-the-art results for various key machine learning optimization problems including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM. Experiments validate our theoretical findings.
1 Introduction
The paper develops a proximal stochastic dual coordinate ascent method and accelerates it through an inner-outer procedure, targeting regularized loss minimization across broad problem classes. Its runtime improves prior results, including for SVM, logistic regression, ridge regression, Lasso, and multiclass prediction.
- The framework solves regularized loss minimization for linear predictors with convex losses, convex regularizers, and a regularization parameter.
- When the condition number 1/(λγ) is O(n), the runtime is nearly linear in the data size, ˜O(dn).
- The method improves state-of-the-art runtime results across key applications, including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM.
- The proximal SDCA method generalizes prior analysis to arbitrary strongly convex regularizers and vector-valued losses smooth or Lipschitz under general norms.
- The acceleration procedure repeatedly approximately minimizes objectives with stronger regularization, centered around vectors from previous iterates.
- The analysis adapts Nesterov’s estimation-sequence technique to approximate and stochastic proximal mappings, while allowing multiple passes over the data to avoid polynomial dependence on 1/ϵ.
2 Preliminaries
The preliminaries establish the convex-analytic setting, norm and smoothness conventions, and the primal–dual relationship used throughout the paper.
- All functions are proper convex functions over a Euclidean space, with extended-real values allowed for function ranges.
- The paper defines conjugate functions, dual norms, standard L2, L1, and L∞ norms, and norm-induced matrix operator norms.
- L-Lipschitzness, (1/γ)-smoothness, and γ-strong convexity are defined relative to norms and their associated dual norms.
- The primal objective has a dual formulation, and strong convexity of g implies differentiability of its conjugate g∗.
- Primal–dual optimal solutions share the same objective value, while the duality gap upper-bounds both primal and dual sub-optimality.
3 Main Results
The paper develops Prox-SDCA for a broad regularized loss-minimization problem and accelerates it through an inner–outer procedure. The analysis covers smooth and Lipschitz losses, with runtime guarantees for different condition-number regimes.
- Prox-SDCA: Prox-SDCA generalizes stochastic dual coordinate ascent to strongly convex regularizers and vector-valued losses smooth or Lipschitz under general norms.This includes non-smooth regularizers such as L1 regularization.
- Prox-SDCA: At each iteration, the method selects one training example uniformly at random and updates only its associated dual vector.The remaining dual vectors stay unchanged.
- Prox-SDCA: The proximal dual update replaces direct maximization with a lower-bounding proximal objective when the conjugate regularizer is difficult to optimize.Alternative gradient-based updates are also analyzed for complex loss conjugates.
- Acceleration: The accelerated procedure improves dependence on the condition number when R2/(λγ) is much larger than n, under a Euclidean strong-convexity assumption.Generalization to strongly convex regularizers under general norms is left for future work.
- Acceleration: Acceleration iteratively minimizes objectives with stronger regularization centered at a momentum point formed from previous iterates.Each outer iteration calls Prox-SDCA on a modified objective containing a quadratic proximal term.
- Lipschitz losses: For non-smooth, non-differentiable losses that are L-Lipschitz, the paper applies smoothing so the resulting conjugate has bounded domain and the smoothed loss is smooth.The conjugate of an L-Lipschitz loss is infinite outside the dual-norm ball of radius L.
4 Proof of Theorem 3
The proof of acceleration combines approximate proximal minimization with lower-bounding quadratic functions and an estimation-sequence argument. It establishes both geometric error decay and bounded runtime for the inner Prox-SDCA calls.
- Lower bounds: An approximate minimizer of the strongly regularized objective yields a quadratic lower bound on the original objective.This lower bound is the bridge from inner proximal solves to progress on P.
- Estimation sequence: The algorithm maintains convex combinations of quadratic lower bounds, producing functions h_t that lower-bound P everywhere.The induction uses the recurrence defining h_t and the proximal lower-bound lemma.
- Estimation sequence: The proof controls the gap between P(w(t)) and h_t(v(t)) by an error term ξ_t that contracts geometrically.The stated contraction is ξ_t ≤ ξ_1 e^{-(t−1)η/2}.
- Convergence: Choosing η and the momentum centers y(t) appropriately makes the stopping condition imply P(w(t))−P(w*)≤ϵ after O(η^-1 log(ξ_1/ϵ)) iterations.The proof uses ξ_t ≤ e^{-η(t−1)/2}ξ_1 to derive the iteration requirement.
- Runtime: Each outer iteration approximately minimizes a strongly regularized objective, and its averaged cost is bounded through the Prox-SDCA runtime result.The proof explicitly returns to the modified objective used by the accelerated procedure.
5 Applications
The paper instantiates its framework for common losses and regularizers, deriving Prox-SDCA and accelerated runtimes for ridge regression, logistic regression, Lasso, SVM, and related problems.
- Application framework: The framework covers ridge regression, SVM, Lasso, logistic regression, and multiclass prediction through specific losses, conjugates, and regularizers.The application section describes these models and their algorithmic specializations.
- Loss functions: Smooth hinge loss is (1/γ)-smooth, while the smoothed max-of-hinge loss supports multiclass prediction.The smoothed hinge construction preserves a controlled approximation to vanilla hinge loss.
- Regularization: L1-L2 regularization adds slight L2 curvature to the L1 norm, enabling the framework to handle otherwise non-strongly-convex regularization.For sufficiently small λ, the resulting objective approximates σ∥w∥1.
- Ridge regression: For ridge regression, Prox-SDCA has a runtime depending on R2/λ, while acceleration improves the runtime when R2/λ is much larger than n.Here R = max_i ∥x_i∥.
- Lasso: For Lasso, the method provides runtime bounds parameterized by either σ and the optimal solution scale or B = ∥w̄∥2, and improves a prior bound by at least √n.The bounds use λ = ϵ(σ/ȳ)2 or λ = ϵ/B2 under the stated assumptions.
- SVM: For SVM, choosing γ = ϵ yields an ϵ-accurate solution, with the accelerated rate reported as better than SGD in the stated regime.The comparison is expressed through the condition involving λϵ and n.
6 Experiments
Experiments compare Prox-SDCA, Accelerated-Prox-SDCA, and FISTA on three binary-classification datasets across several L1-L2 regularization settings. Accelerated-Prox-SDCA is consistently fastest and often significantly outperforms the alternatives.
- Experimental setup: The experiments compare Prox-SDCA, Accelerated-Prox-SDCA, and FISTA on three large, diverse datasets.The datasets are astro-ph, CCAT, and cov1, with differing feature counts and sparsity.
- Experimental setup: The binary-classification experiments use normalized features, smooth hinge loss with γ = 1, and σ = 10^-5.λ varies over {10^-6, 10^-7, 10^-8, 10^-9}.
- Evaluation: The plots report primal objective versus passes over the training data, with methods stopped at guaranteed accuracy 10^-3.FISTA uses one pass per iteration, while n coordinate updates correspond to one pass for the SDCA methods.
- Results: Accelerated-Prox-SDCA yields the best results and often significantly outperforms Prox-SDCA and FISTA.Prox-SDCA slows substantially when λ is small, while the relative performance of FISTA and Prox-SDCA depends on λ and n.
7 Discussion and Open Problems
The paper concludes that its proximal and accelerated SDCA framework improves state-of-the-art runtimes in many cases, while identifying two unresolved extensions.
- Conclusion: The resulting method improves state-of-the-art runtime results in many machine-learning optimization cases.The conclusion follows the paper’s proximal SDCA method and its acceleration procedure.
- Open problems: When 1/(λγ) is larger than n, the authors leave open whether the accelerated procedure can achieve a better runtime.This is identified as the first main open problem.
- Open problems: The acceleration procedure is currently designed for Euclidean strongly convex regularizers, leaving extension to general norms open.The underlying Prox-SDCA procedure and analysis already support strongly convex regularizers with respect to arbitrary norms.
A Proofs of Iteration Bounds for Prox-SDCA
The proofs establish iteration and accuracy guarantees for randomized Prox-SDCA by combining coordinate-wise dual progress, norm-based smoothness, and high-probability conversion arguments.
- Proof strategy: The proof generalizes prior SDCA analysis to strongly convex regularizers and loss smoothness or Lipschitzness under general norms.The argument follows Shalev-Shwartz and Zhang while extending the handled setting.
- Prox-SDCA analysis: Each randomized iteration updates one dual vector selected uniformly at random, leaving the remaining dual vectors unchanged.The analysis conditions on the current dual iterate and bounds expected progress.
- Prox-SDCA analysis: The key progress argument uses smoothness of the regularizer conjugate and strong convexity of the loss conjugate.These properties control the dual improvement under a coordinate update.
- Accuracy guarantees: The theorems convert expected dual progress into primal accuracy and duality-gap guarantees through averaging, random selection, Markov’s inequality, and repetition.Repeating logarithmically many trials yields probability at least 1 − δ.