Source-linked AI summary
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford
TL;DR
The paper addresses sub-optimal condition-number dependence in stochastic empirical risk minimization. It introduces black-box approximate proximal-point reductions that use large regularizations and existing randomized minimizers, obtaining accelerated ERM running-time guarantees. The framework provides several algorithms with different generality and regime-specific advantages, while the exposition focuses on core ERM settings and selected extensions.
Problem
Recent ERM algorithms have sub-optimal condition-number dependence, while methods with accelerated dependence solve only explicitly regularized objectives rather than the unregularized ERM problem.
Method
The paper develops black-box reductions that solve strongly convex ERM through repeated approximate minimizations of large-λ regularized objectives using approximate proximal-point algorithms.
Results
The reductions achieve accelerated running-time guarantees for ERM when instantiated with known randomized algorithms, including eO(nd√κ log(1/ϵ)) under the stated assumptions.
Takeaways & Limitations
The framework provides three approximate proximal-point algorithms whose advantages vary by regime, with Accelerated APPA more efficient in many regimes and Dual APPA useful with dual inner minimizers.
Takeaways & Limitations
The exposition focuses on the core ERM formulation, although the analysis can apply to broader normed spaces, non-uniform smoothness, and explicit regularization.
Abstract
from arXiv · showhide
We develop a family of accelerated stochastic algorithms that minimize sums of convex functions. Our algorithms improve upon the fastest running time for empirical risk minimization (ERM), and in particular linear least-squares regression, across a wide range of problem settings. To achieve this, we establish a framework based on the classical proximal point algorithm. Namely, we provide several algorithms that reduce the minimization of a strongly convex function to approximate minimizations of regularizations of the function. Using these results, we accelerate recent fast stochastic algorithms in a black-box fashion. Empirically, we demonstrate that the resulting algorithms exhibit notions of stability that are advantageous in practice. Both in theory and in practice, the provided algorithms reap the computational benefits of adding a large strongly convex regularization term, without incurring a corresponding bias to the original problem.
1 Introduction
The paper targets sub-optimal condition-number dependence in stochastic ERM algorithms by using approximate proximal-point reductions. Its framework repeatedly solves strongly regularized problems, yielding accelerated guarantees while retaining applicability across several ERM settings.
- Motivation: Recent randomized ERM methods either depend linearly on the condition number or solve only explicitly regularized objectives, making small regularization unsuitable for the unregularized problem.The paper motivates this gap by noting that high-dimensional data can make the ERM condition number very large.
- Approach: The paper reduces strongly convex ERM to repeated approximate minimizations of large-λ regularized objectives through black-box proximal-point methods.The reductions avoid requiring full inner minimization and can use existing randomized minimizers as inner procedures.
- Theory: Theorem 1.1 gives an accelerated reduction whose overhead is O(⌈λ/µ⌉polylog(λ/µ)) when regularized minimizations are available.The theorem uses a linearly convergent method for f(x) + λ∥x − x0∥2 to minimize f.
- Implications: The analysis separates proximal-point and inner-minimization errors, producing concrete end-to-end runtime guarantees and improved algorithmic guarantees.The paper also identifies extensions to broader norms, non-uniform smoothness, and explicit regularization, while focusing its exposition on the core ERM formulation.
- Results: Instantiating the framework with fast randomized minimizers yields ERM algorithms with running time eO(nd√κ log(1/ϵ)) under the stated assumptions.The guarantees apply under Assumptions 1.2 and 1.3.
- Approach: Three approximate proximal-point algorithms provide different trade-offs, with Accelerated APPA offering a more efficient reduction in many regimes and applying to any strongly convex F.The framework includes APPA, Accelerated APPA, and Dual APPA; Dual APPA is less general because it relies on ERM structure.
2 Approximate proximal point algorithm (APPA)
APPA minimizes a strongly convex ERM objective by repeatedly applying an approximate inner minimizer to regularized subproblems. Primal-oracle guarantees yield geometric convergence and accelerated running times when instantiated with APCG.
- 2.2 Algorithm: APPA reduces solving a strongly convex ERM problem to repeated approximate minimizations of regularized objectives using a primal oracle.The method applies the oracle iteratively and returns the final iterate.
- 2.1 Inner approximation: A primal (c, λ)-oracle reduces the regularized objective error by a 1/c fraction, with runtime depending on λ, c, and F's regularity.Typical first-order methods provide such oracles with runtime scaling inversely in λ and logarithmically in c.
- 2.3 Analysis: APPA contracts the objective error geometrically when each inner solve satisfies the primal-oracle guarantee.The exact proximal method decreases error by the multiplicative factor λ/(λ + µ), supporting the approximate contraction analysis.
- 2.3 Analysis: APPA with an arbitrary primal oracle solves general ERM to accuracy ϵ in O(TP⌈λ/µ⌉log(ϵ0/ϵ)) time.This bound follows from the un-regularizing analysis and applies to the stated oracle setting.
- 2.2 Algorithm: Using APCG as the primal oracle and setting λ = µ gives eO(nd√κ log(ϵ0/ϵ)) time for ERM problem (1).APCG supplies a primal-oracle runtime of eO(nd√κλ log c) for this problem.
- 2.3 Analysis: The analysis assumes only µ-strong convexity of F, without requiring smoothness or differentiability.Randomized oracles are analyzed through expected accuracy.
3 Accelerated APPA
Accelerated APPA accelerates approximate proximal-point iterations by using inner minimizers more efficiently, yielding improved ERM running-time guarantees when instantiated with stochastic oracles.
- 3 Accelerated APPA: Accelerated APPA uses inner minimizers more efficiently than APPA, while requiring a minimization factor polynomial in λ/µ rather than a fixed constant.The algorithm still makes one primal-oracle call per iteration.
- 3 Accelerated APPA: Theorem 3.1 shows that Accelerated APPA minimizes the general ERM problem to accuracy ϵ using a suitable approximate primal oracle.Its guarantee follows from a convergence analysis based on approximate proximal iterations and lower bounds.
- 3 Accelerated APPA: SVRG as the primal oracle with λ = 2µ + LR2 yields running time eO(nd√κ log(ϵ0/ϵ)) for general ERM.This instantiation supplies the stated accelerated guarantee for the broader ERM formulation.
- 3 Accelerated APPA: The analysis constructs quadratic lower bounds from approximate inner solutions, accelerates these bounds, and requires only constant-factor error reduction from the primal oracle.The proof is organized around Lemmas 3.3–3.6, which establish the lower bounds, acceleration, oracle requirements, and initialization conditions.
- 3 Accelerated APPA: The regularization analysis tolerates approximation errors while losing only a factor of 2 in the strong-convexity parameter.The choice of β can vary between its current value and 1 without invalidating the relevant comparison.
4 Dual APPA
Dual APPA performs approximate proximal-point iterations in the regularized ERM dual, using dual-oracle progress to obtain accelerated guarantees for the original ERM problem.
- 4 Dual APPA: Dual APPA operates entirely in the regularized ERM dual and produces primal iterates through dual-to-primal mappings.The method repeatedly queries a dual oracle while maintaining primal iterates.
- 4 Dual APPA: Dual APPA is less general than the other reductions because it requires the ERM structure, but it supports dual inner minimizers that are otherwise incompatible with APPA.The algorithm is motivated by dual objectives and warm starts between iterations.
- 4 Dual APPA: APCG is a dual oracle with runtime eO(nd√κλ log c), and λ = µ yields Dual APPA time eO(nd√κ log(ϵ0/ϵ)).This instantiation provides the stated accelerated running time for ERM.
- 4 Dual APPA: Theorem 4.3 gives time eO(TD⌈λ/µ⌉log(ϵ0/ϵ)) for minimizing ERM to accuracy ϵ with a dual (σ, λ)-oracle.The guarantee reduces the original problem to repeated approximate dual regularized-ERM solves.
- 4.3 Analysis: The convergence proof controls re-centering by bounding dual regularized-ERM error with previous dual-error and gradient-norm measurements.These bounds establish invariants for the primal and dual iterates across Dual APPA iterations.
5 Implementation
The implementation study evaluates Dual APPA with SDCA against stochastic baselines on binary classification tasks, emphasizing stability, bias, and practical overhead.
- 5 Implementation: Dual APPA avoids SVRG’s end-of-stage exact-gradient pass by updating primal variables alongside dual coordinate updates with O(d) overhead.Warm-started primal-dual pairs allow stage initialization in O(d) time.
- 5.2 Empirical analysis: The proximal term introduces vanishing bias while adding strong convexity, and Dual APPA can retain desired ℓ2 bias after a few stages with improved speed and stability.The empirical discussion frames this as a bias-variance tradeoff distinct from fixed regularized ERM.
- 5.2 Empirical analysis: The experiments cover binary classification tasks derived from MNIST, CIFAR-10, and Protein, including nonlinear feature transformations for MNIST and CIFAR.MNIST and CIFAR use randomized Fourier features, while Protein is a pre-featurized benchmark.
- 5.2 Empirical analysis: On MNIST and CIFAR, APPA uses λ at least an order of magnitude larger than SDCA while achieving faster and more stable convergence to a lower final value.The comparison concerns the same strong convexity added by APPA and SDCA.
- 5.2 Empirical analysis: APPA and SDCA converge smoothly as λ is overestimated, whereas SGD and SVRG exhibit sharp divergence thresholds; APPA degrades most gracefully after 20 stages.Figure 3 compares final objective values across λ choices for the algorithms.
A Technical lemmas
The technical appendix collects standard inequalities and quadratic identities used to analyze smooth, strongly convex objectives and their linear perturbations.
- A Technical lemmas: Lemma A.1 relates function suboptimality, distance to the optimizer, and gradient norm for smooth and strongly convex functions.These inequalities provide the basic bounds used throughout the analysis.
- A Technical lemmas: Lemma A.2 bounds the effect of adding a linear term to a strongly convex function, including when differentiability is not assumed.Its proof uses strong convexity directly rather than gradients.
- A Technical lemmas: Lemma A.3 characterizes convex combinations of quadratic functions through combined centers and objective offsets.The resulting identities support the quadratic lower-bound constructions in Accelerated APPA.
B Regularized ERM duality
This section develops the dual formulation and error bounds for computing the proximal operator of an ERM objective.
- The analysis targets the dual formulation of the proximal-operator problem for the ERM objective.
- It establishes bounds on both primal and dual errors.
- The derivation uses notation and assumptions introduced earlier for the ERM problem.
B.1 Dual derivation
The dual derivation rewrites the proximal optimization as a Lagrangian saddle-point problem and obtains primal–dual mappings from KKT conditions.
- The proximal optimization is reformulated through convex duality as a Lagrangian saddle-point problem.
- The resulting negated optimization problem is the dual formulation.
- KKT conditions yield mappings between primal and dual variables by solving the stationary system for x, y, and z.
- The duality gap is nonnegative for every primal–dual pair and vanishes at primal and dual optima.
B.2 Error bounds
This section states bounds connecting dual errors, primal errors, and the duality gap for regularized ERM, using smoothness and strong convexity.
- The section provides a lemma bounding primal error through dual error.
- The proofs use smoothness of the regularized objectives and strong convexity of the associated function.
- A second lemma characterizes the duality gap for primal–dual pairs.
- The section also states a corollary giving an initial dual-error bound.
- The analysis relates the gradient of the regularized objective to the original objective gradient.