Source-linked AI summary
An optimal randomized incremental gradient method
Guanghui Lan, Yi Zhou
TL;DR
The paper addresses finite-sum composite convex optimization, where deterministic methods process all smooth components while randomized incremental methods seek lower total gradient cost. It develops primal-dual gradient methods, including an RPDG variant that samples one component per iteration, and shows favorable O(√m) savings with matching lower-complexity results.
Problem
Finite-sum composite convex problems need methods that preserve optimal deterministic iteration complexity while reducing the total cost of processing m smooth components.
Method
The paper reformulates the problem in primal-dual form, develops deterministic PDG, and extends it to randomized RPDG using one randomly selected component gradient per iteration.
Results
Under favorable situations, RPDG uses O(√m) fewer gradient computations than corresponding optimal deterministic first-order methods, in expectation and with high probability.
Takeaways & Limitations
A matching lower bound for randomized incremental gradient methods shows that RPDG’s complexity is optimal when the dimension is sufficiently large.
Takeaways & Limitations
Without component Lipschitz constants, uniform sampling may yield bounds involving the larger condition number m max_i Li/µ; the stated lower-bound optimality requires sufficiently large dimension.
Abstract
from arXiv · showhide
In this paper, we consider a class of finite-sum convex optimization problems whose objective function is given by the summation of $m$ ($\ge 1$) smooth components together with some other relatively simple terms. We first introduce a deterministic primal-dual gradient (PDG) method that can achieve the optimal black-box iteration complexity for solving these composite optimization problems using a primal-dual termination criterion. Our major contribution is to develop a randomized primal-dual gradient (RPDG) method, which needs to compute the gradient of only one randomly selected smooth component at each iteration, but can possibly achieve better complexity than PDG in terms of the total number of gradient evaluations. More specifically, we show that the total number of gradient evaluations performed by RPDG can be ${\cal O} (\sqrt{m})$ times smaller, both in expectation and with high probability, than those performed by deterministic optimal first-order methods under favorable situations. We also show that the complexity of the RPDG method is not improvable by developing a new lower complexity bound for a general class of randomized methods for solving large-scale finite-sum convex optimization problems. Moreover, through the development of PDG and RPDG, we introduce a novel game-theoretic interpretation for these optimal methods for convex optimization.
1 Introduction
The paper studies finite-sum composite convex optimization and develops primal-dual methods that retain optimal deterministic complexity while reducing component-gradient evaluations through randomization. It also establishes matching lower bounds and extends the randomized method beyond strongly convex settings.
- Problem setting: The problem combines m smooth convex component functions with relatively simple convex terms over a closed convex domain.The regularization term ω may be strongly convex with respect to an arbitrary norm, while µ controls strong convexity of the objective.
- Motivation: Deterministic first-order methods require information from all m components per iteration, whereas stochastic methods evaluate one randomly selected component.For general nonsmooth components, suitably chosen sampling probabilities can make stochastic and deterministic iteration complexities comparable, yielding up to m-fold fewer subgradients.
- Motivation: Smooth finite-sum problems expose a complexity gap: stochastic methods improve dependence on m but worsen dependence on accuracy and other parameters such as L and µ.The paper contrasts optimal deterministic bounds with accelerated stochastic approximation bounds involving gradient variance σ.
- Contributions: PDG reformulates the problem as a primal-dual saddle point problem and uses dual prox-functions based on conjugate component functions to attain optimal black-box iteration complexity.PDG includes a variant of Nesterov’s accelerated gradient method and interprets its extrapolation computation as primal prediction plus dual ascent.
- Contributions: RPDG computes only one randomly selected component gradient per iteration and provides complexity bounds in expectation and with high probability using distance and ergodic primal-gap criteria.The method adds a dual prediction step before primal descent and handles more general composite structures and strongly convex regularizers than some dual-coordinate alternatives.
- Contributions: O(√m) fewer gradient computations, up to logarithmic factors, are achieved by RPDG versus corresponding optimal deterministic methods across generalized settings.The paper also proves a lower bound showing RPDG is optimal for sufficiently large dimension and reports advantages in dual-subproblem counts over several deterministic methods.
2 An optimal primal-dual gradient method
The paper develops a primal-dual gradient method for composite convex optimization, with prox-functions in both primal and dual spaces. It establishes optimal convergence using primal-dual gaps and connects the method to accelerated gradient schemes and a buyer–supplier game.
- Method: PDG reformulates the problem as a primal-dual saddle-point problem and uses a dual prox-function based on conjugate functions of the smooth objective.The dual prox-mapping can be implemented through gradient computation.
- Prox-functions: The method defines primal prox-functions from the strongly convex regularizer and assumes the associated prox-mapping is easily computable.When the prox-function is nondifferentiable, subgradient selections are specified recursively across iterations.
- Connections and interpretation: PDG generalizes a variant of Nesterov’s accelerated gradient method and interprets optimization as iterative interaction between a primal buyer and a dual supplier.The game couples local costs with a bilinear interaction term, while the PDG formulation permits more flexible parameter choices.
- Convergence: PDG provides optimal convergence guarantees for both strongly convex and non-strongly convex cases, using different parameter settings.For the strongly convex case, guarantees cover individual iterates and their ergodic mean; for the non-strongly convex case, bounds are established for the ergodic mean.
- Termination criterion: The convergence analysis uses primal-dual optimality gaps, which are stronger than the usual primal objective gap and can provide online accuracy certificates when X is bounded.The gap may require modification when X is unbounded and h is not strictly convex.
3 Randomized primal-dual gradient methods
RPDG reformulates finite-sum composite optimization as a multi-dual-player saddle-point problem and updates only one randomly selected component per iteration. Its analyses provide expected and high-probability complexity bounds, while lower bounds show the resulting gradient complexity is optimal in sufficiently large dimensions.
- Algorithm: RPDG computes the gradient of only one randomly selected component function at each iteration, reducing gradient evaluations at the expense of more primal prox-mappings.The method is therefore an incremental gradient method with a computation-versus-proximal-operation trade-off.
- Multi-dual-player reformulation: The method reformulates the finite-sum problem as a saddle-point problem with one dual space and conjugate function for each smooth component.The dual variables are grouped as y = (y_1, ..., y_m), and the primal-dual gap characterizes optimality.
- Algorithm: RPDG modifies PDG by computing one randomly selected dual prox-mapping, adding a dual prediction step, and using the predicted dual variable in the primal update.This preserves the primal-dual structure while making the component-gradient computation incremental.
- Convergence: The convergence analysis bounds both expected distance to the optimum and expected primal optimality gap, but not the expected primal-dual gap.The method also supports stochastic ε-solutions and stochastic (ε, λ)-solutions.
- Complexity: When L_f and L are of the same order, RPDG can save up to O(√m) component-gradient evaluations relative to optimal deterministic first-order methods.The paper notes that L_f can instead be much smaller than L; in particular, L_f = L/m when all component smoothness constants equal L_f.
- Lower bounds: A new lower complexity bound shows that randomized incremental gradient methods cannot improve RPDG’s complexity when the dimension n is sufficiently large.The result is obtained through specially constructed separable quadratic programs and applies more broadly to randomized block coordinate descent.
4 Generalization of randomized primal-dual gradient methods
The paper extends RPDG beyond smooth strongly convex problems by using perturbation or smoothing-based approximations. These extensions retain expected and high-probability guarantees and can preserve an O(√m) gradient-evaluation advantage over deterministic methods.
- Scope: The generalization section addresses convex problems that are not necessarily smooth and strongly convex.For smooth problems without strong convexity, the paper uses a perturbed problem with positive strong-convexity modulus.
- Smooth non-strongly-convex problems: For smooth problems with µ = 0, RPDG is applied to a perturbed problem, requiring the feasible set X to be bounded.An approximate solution of the perturbed problem is also an approximate solution of the original problem when the perturbation parameter δ is sufficiently small.
- Structured nonsmooth problems: When smooth components are approximated by smooth surrogates, RPDG yields complexity results for structured nonsmooth problems.The approximation construction produces continuously differentiable functions with Lipschitz-continuous gradients before applying RPDG.
- Structured nonsmooth problems: For strongly convex structured nonsmooth problems, the approximation-based RPDG analysis provides expected and high-probability objective-gap guarantees.The corresponding bounds are established through Proposition 2 and its approximation framework.
- Complexity comparison: After disregarding logarithmic factors, RPDG can use O(√m) fewer gradient computations than deterministic first-order methods for the generalized settings.This comparison includes Nesterov’s smoothing technique as a deterministic baseline.
- Unconstrained convex programming: For unconstrained basic convex programming, the method assumes a nonempty optimal-solution set and measures relative accuracy because the optimal-solution size is unavailable.The resulting complexity bounds cover expected and high-probability relative-accuracy guarantees.
5 Complexity analysis
The analysis develops shared convergence bounds for deterministic and randomized primal-dual gradient methods, then specializes them to PDG complexity results. The proofs combine prox-mapping properties, gap recursions, parameter conditions, and telescoping inequalities.
- General convergence framework: The proofs establish a general convergence result covering both PDG and RPDG, with PDG treated as the special case m = 1.Proposition 5 supplies the common framework from which the main convergence theorems follow.
- Randomized recursion: The analysis uses prox-mapping characterizations and identities for randomized dual iterates to derive the key RPDG gap recursion.Conditional expectations and summation over component indices connect individual randomized updates to the aggregate gap function.
- Deterministic PDG specialization: The deterministic specialization satisfies the general conditions with m = 1 and yields the fundamental inequality Q_f(¯z_k, z) + θ_k(µ + η_k)P(x_k, x) ≤ θ_1η_1P(x_0, x) + θ_1τ_1D_f(g_0, g).This inequality simultaneously controls the ergodic primal-dual gap and distance from the current primal iterate to a comparison point.
- Deterministic PDG specialization: The resulting PDG bounds give the stated rates in (2.26) and (2.29), with additional bounded-domain conclusions in (2.27) and (2.30).The bounded-domain results use nonnegativity of the prox-distance term and the relation ∑_{t=1}^k θ_t = k(k + 1)/2.
6 Concluding remarks
The paper introduces optimal primal-dual gradient methods for finite-sum composite convex optimization and establishes convergence and lower-complexity results for randomized variants. It also discusses extensions beyond strongly convex, smooth, and bounded settings.
- Contributions: The paper presents PDG methods whose optimal convergence is established using a primal-dual optimality gap and distance to an optimal solution.The gap is evaluated for the ergodic mean of iterates, while distance is measured at x_k.
- Contributions: RPDG computes the gradient of only one randomly selected component per iteration and provides complexity bounds for distance and expected primal optimality gap.The expected gap is evaluated at the ergodic mean of iterates.
- Complexity bounds: The paper develops lower complexity bounds showing that RPDG’s complexity is not improvable when the dimension is sufficiently large.The lower bound applies to randomized incremental gradient methods.
- Scope: Extensions are discussed for non-strongly convex, nonsmooth, and unbounded problems, while the paper focuses on theoretical convergence.The scope explicitly includes these broader problem settings, but the stated focus remains theoretical.