PaperlayerView exact revision on arXiv

Source-linked AI summary

Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey

Dimitri P. Bertsekas

arXiv:1507.01030v2eess.SYcs.DSmath.NAmath.OC

TL;DR

The paper addresses optimization problems with many additive convex components, where processing the full cost can be costly. It surveys single-component gradient, subgradient, and proximal methods within a unified framework, concluding that these methods cover important large-data applications while leaving substantial evaluation work ahead.

  • Problem

    Optimization problems with a large number of component functions motivate methods that avoid operating on the entire cost function at every iteration.

  • Method

    The paper surveys gradient, subgradient, and proximal incremental methods and unifies them in a combined analytical framework.

  • Results

    The surveyed algorithms have convergence properties and apply to important problems studied in large-data, inference, and distributed-optimization settings.

  • Takeaways & Limitations

    Incremental algorithms can address challenges posed by large data and may substantially outperform nonincremental methods when the number of components is large.

  • Takeaways & Limitations

    The authors state that much work remains to apply and evaluate the methods broadly, and constant stepsizes typically cannot guarantee convergence.

Abstract

from arXiv · show

We survey incremental methods for minimizing a sum $\sum_{i=1}^mf_i(x)$ consisting of a large number of convex component functions $f_i$. Our methods consist of iterations applied to single components, and have proved very effective in practice. We introduce a unified algorithmic framework for a variety of such methods, some involving gradient and subgradient iterations, which are known, and some involving combinations of subgradient and proximal methods, which are new and offer greater flexibility in exploiting the special structure of $f_i$. We provide an analysis of the convergence and rate of convergence properties of these methods, including the advantages offered by randomization in the selection of components. We also survey applications in inference/machine learning, signal processing, and large-scale and distributed optimization.

1. INTRODUCTION

The paper surveys incremental methods for large convex additive-cost problems, focusing on single-component iterations and a unified framework spanning gradient, subgradient, and proximal approaches.

  • Incremental methods operate on a single component function at each iteration instead of the entire cost function.
  • When the number of components is large, incremental methods may outperform nonincremental methods by orders of magnitude.
  • The survey unifies gradient, subgradient, and proximal methods through a combined method used for later analysis.
  • Additive-cost structures arise in linear and nonlinear least squares, including differentiable or nondifferentiable regularization.
  • Applications include inference and machine learning, least-squares and regression models, robust estimation, maximum likelihood, and neural-network training.

Example 1.2: (Dual Optimization in Separable Problems)

Additive-cost formulations arise in dual optimization, many-constraint penalties, expected-value approximations, and stochastic programming.

  • Assigning a dual vector to separable constraints produces an additive dual cost whose components are convex.
  • Dual component values and subgradients can often be computed conveniently, especially when the underlying variable is scalar or its feasible set is simple.
  • Many-constraint problems can be converted to additive-cost problems through penalty functions applied to constraint violations.
  • For convex problems, the original and nondifferentiably penalized problems have coinciding optimal solutions when the penalty parameter is sufficiently large.
  • Sample averages approximate expected-value minimization, while stochastic programming yields an additive objective over possible outcomes and their probabilities.

Example 1.5: (Weber Problem in Location Theory)

The Weber location problem minimizes the sum of weighted distances from an unknown point to many given points, making it relevant when the point count is large.

  • The Weber problem seeks a planar point minimizing the sum of weighted distances to given points.
  • The paper’s incremental algorithms may be useful when the number of points m is large.

Example 1.6: (Distributed Incremental Optimization – Sensor Networks)

Sensor-network inference can be formulated as an additive-cost problem and solved distributively by passing iterates between sensors, each processing only its local component.

  • In a sensor network, each component function can represent an error penalty for data collected by one sensor.
  • A distributed approach can reduce data-communication overhead and exploit parallel computation instead of centralizing all sensor data.
  • Sensors pass the current iterate from one to another and perform incremental iterations using only their local component functions.
  • The approach extends to asynchronous distributed computation in which network nodes process components and suitably combine results.

1.2 Incremental Gradient Methods - Differentiable Problems

Incremental gradient methods update using individual differentiable cost components, reducing computation per iteration but creating convergence trade-offs. Their behavior depends strongly on stepsize choice and can vary across optimization stages.

  • Incremental gradient iteration: Each iteration uses one component gradient, reducing computation relative to evaluating the full gradient.In an extreme case with identical components, the incremental iteration requires m times less computation and gives the same result with an appropriately scaled stepsize.
  • Behavior across convergence: Incremental methods can progress faster far from convergence when component gradients point roughly in the right direction.The paper attributes this advantage to using a single component update instead of computing the complete gradient.
  • Behavior across convergence: Near convergence, diminishing stepsizes imply a sublinear rate, compared with the typically linear rate of classical gradient descent using a small constant stepsize.This is the principal asymptotic trade-off identified for incremental gradient methods.
  • Stepsize and convergence: With a constant stepsize, iterates may oscillate around a solution, with oscillation size roughly proportional to α.Within cycles, the iterates can converge to different points in a sequence of m points, even for linear least squares.
  • Stepsize and convergence: A diminishing stepsize, such as αk = O(1/k), reduces gradient error and can yield convergence to a stationary point under a Lipschitz condition.The diminishing stepsize makes the incremental gradient error diminish as well.
  • Variants: Incremental momentum and aggregated-gradient variants extend the method, but favorable complexity guarantees for incremental Nesterov-type methods are not currently known.For aggregated gradients, a linear rate is reported for sufficiently small constant α and quadratic component functions, while comparison with basic incremental gradients remains unclear.

1.3 Incremental Subgradient Methods - Nondifferentiable Problems

Incremental subgradient methods extend incremental updates to convex component functions that may be nondifferentiable. They resemble gradient methods in stepsize requirements but use a different convergence analysis based on distance to the optimal solution set.

  • Method: Incremental subgradient methods use an arbitrary subgradient of the selected cost component in place of its gradient.The subgradient is chosen from the component’s subdifferential.
  • Convergence: Like their gradient counterparts, incremental subgradient methods require a diminishing stepsize for convergence.The paper identifies this as their most important similarity to incremental gradient methods.
  • Convergence analysis: The convergence analysis focuses on decreasing the iterates’ distance to the optimal solution set rather than decreasing the cost-function value.This distinguishes the subgradient analysis from the usual incremental-gradient argument based on cost decrease.
  • Nondifferentiable components: Nondifferentiability makes convexity essential because the subgradient notion is connected with convexity.The paper notes that subgradient-like methods for nondifferentiable nonconvex problems are more complicated and have seen limited application.
  • Rate comparison: Nonincremental subgradient methods also require diminishing stepsizes and typically achieve a sublinear convergence rate.Thus, the theoretical advantage associated with constant-stepsize nonincremental gradient methods does not carry over to their subgradient counterparts.
  • Randomization: Randomizing component selection can provide a potentially significant advantage by turning the incremental method into a stochastic one.The paper discusses randomized selection as a major extension of incremental subgradient methods.

1.4 Incremental Proximal Methods

Incremental proximal methods combine proximal updates with subgradient or gradient updates within a unified framework. This lets different components be treated according to whether proximal minimization is convenient, while retaining analyzed convergence and rate properties.

  • Proximal updates: Proximal iterations can be preferable when a component’s proximal minimization is available in closed form or is relatively simple.This motivation relies on favorable structure in individual components.
  • Combined updates: Some components are inconvenient for proximal minimization, motivating combinations of proximal and gradient or subgradient iterations.The combined approach assigns update types according to the structure of the component functions.
  • Scope: The paper restricts proximal methods to quadratic regularization, although the approach could in principle use a nonquadratic term matched to the problem structure.Alternative nonquadratic algorithms are outside the paper’s scope.
  • Unified framework: The unified framework includes incremental gradient, subgradient, proximal, and combined methods, highlighting their common structure and behavior.The framework is applied to sums of real-valued convex functions over a nonempty closed convex constraint set.
  • Special cases: Setting all f_i or all h_i identically to zero recovers the incremental proximal or subgradient iterations as special cases.The mixed formulation therefore contains these methods within one algorithmic family.
  • Method structure: The methods use proximal iterations on f_i components and subgradient iterations on h_i components.This split is the basic per-component design choice in the framework.
  • Convergence and rates: Under the paper’s analyzed settings, a constant stepsize yields convergence within an error bound, while an appropriately diminishing stepsize yields exact convergence to an optimal solution.Randomized component selection can improve convergence rate or iteration complexity.

2. INCREMENTAL SUBGRADIENT-PROXIMAL METHODS

The section develops incremental methods that combine proximal and subgradient iterations, including new algorithms for exploiting different component structures. It also analyzes component-selection order, emphasizing cyclic and randomized schemes.

  • Algorithmic framework: The section introduces incremental algorithms that combine proximal and subgradient iterations for component functions.The framework includes methods in which different components can receive different iteration types.
  • Novelty and relation to prior work: The proposed incremental proximal algorithms were new to the authors’ knowledge and had appeared in recent related work.The closest existing connection identified is the nonincremental proximal gradient method.
  • Algorithmic framework: Incremental proximal iterations are closely related to incremental subgradient iterations, differing in where the subgradient is evaluated.The subgradient is evaluated at the iteration endpoint rather than its starting point.
  • Component selection: Component pairs can be selected cyclically in fixed order or randomly by uniform sampling independently of the algorithm’s past history.Cyclic selection uses each component once per cycle and keeps the stepsize constant within a cycle.
  • Component selection: Uniform sampling must include every component with equal probability; otherwise unequal sampling frequencies can bias convergence.Random reshuffling also converges and gives each component exactly one computation slot per cycle.
  • Component selection: Random reshuffling is argued to work better than uniform sampling because uniform sampling can produce greater variance in the incremental error.The analysis focuses on uniform sampling, while the reshuffling explanation is presented heuristically and supported by experimental observations.

3. CONVERGENCE FOR METHODS WITH CYCLIC ORDER

For cyclic component selection, the analysis establishes a cycle-level descent estimate for the incremental algorithms and derives convergence and complexity consequences. Constant stepsizes yield neighborhood convergence, while the bounds expose an unfavorable dependence on the number of components.

  • Cycle-level estimate: Incremental proximal and subgradient effects become increasingly interchangeable as the stepsize decreases.The analysis bounds the discrepancy caused by evaluating component subgradients at nearby intermediate points.
  • Cycle-level estimate: Proposition 3.1 provides a key cycle-level estimate for algorithms (2.12)–(2.14) under cyclic component selection.The estimate applies at cycle beginnings and controls progress relative to any y in X.
  • Constant stepsize: For any ε > 0, if the cyclic iterate is not within the corresponding optimality tolerance, its squared distance to an optimal point decreases by at least 2αkε.This supplies the descent mechanism used in the cyclic convergence proofs.
  • Constant stepsize: With a constant stepsize, the cyclic methods converge to a neighborhood of the optimum whose size shrinks to zero as α → 0.The neighborhood has a tolerance involving αβm^2c^2/2.
  • Iteration complexity: To obtain O(ε) cost accuracy, the cyclic analysis requires α = O(ε/m^2c^2) and N = O(m^3c^2/ε^2) iterations.The resulting estimate has the same type as the nonincremental subgradient estimate when a cycle is counted as one iteration.
  • Iteration complexity: The cyclic complexity estimate does not reveal an advantage for the incremental methods presented in this section.A more favorable iteration-complexity estimate is deferred to randomized component selection.

Exact Convergence for a Diminishing Stepsize

With diminishing stepsizes, the cyclic incremental methods can approach arbitrarily small neighborhoods of the optimum under suitable rate conditions. If an optimal solution exists and the stepsizes satisfy the stated conditions, the full iterate sequence converges to an optimal solution.

  • Exact convergence: The proof first establishes that the lim inf of cycle-end costs equals the optimal value.It uses the cycle-level estimate to rule out a persistent positive gap from optimality.
  • Stepsize conditions: A diminishing stepsize can reduce the attainable neighborhood around the optimum, provided it is not decreased too quickly.The stepsizes must also satisfy a divergent-sum condition so the method can continue traveling when necessary.
  • Exact convergence: When X* is nonempty and the stepsizes meet the stated conditions, the entire sequence {xk} converges to some x* ∈ X*.The argument transfers convergence from cycle-end iterates to all iterates using vanishing successive differences.

4. CONVERGENCE FOR METHODS WITH RANDOMIZED ORDER

For randomized component selection, the paper analyzes uniformly sampled incremental methods using conditional expectations and a supermartingale convergence theorem. Randomization improves the stated constant-stepsize error and expected-complexity bounds, while diminishing stepsizes give almost-sure convergence under suitable conditions.

  • Randomized framework: The randomized methods sample each component uniformly and independently of the algorithm’s past history.The convergence analysis relies on these sampling assumptions and bounded-slope conditions.
  • Randomized framework: The randomized convergence analysis is more complicated than the cyclic analysis and uses a supermartingale convergence theorem.Conditional expectations exploit the equal probability 1/m assigned to each component.
  • Constant stepsize: With a constant stepsize, randomized methods reach an objective-value neighborhood bounded by F* + αβmc^2/2 with probability 1.This bound applies to the randomized incremental methods analyzed in Proposition 4.1.
  • Constant stepsize: Randomized methods improve the constant-stepsize error bound by a factor m relative to their nonrandomized counterparts.The comparison is between O(αmc^2) for randomized selection and a worst-case O(αm^2c^2) cyclic bound.
  • Iteration complexity: The randomized complexity comparison suggests a factor-m smaller error tolerance in the same expected number of iterations.The paper cautions that this compares upper bounds and worst-case quantities with expected quantities, which are not strictly identical.
  • Diminishing stepsize: With diminishing stepsizes, the randomized methods converge to an optimal solution with probability 1 when X* is nonempty and the stated conditions hold.The result parallels the cyclic diminishing-stepsize convergence theorem.

5. SOME APPLICATIONS

The paper applies incremental methods to least-squares, ℓ1-regularized, and feasibility problems, including settings with sequentially revealed data or constraint sets. Proximal steps exploit simple regularizers or penalties, while exact penalties can preserve constrained minimizers under stated assumptions.

  • Least squares: Incremental gradient methods are suitable for large or sequentially arriving least-squares data when the regularizer is differentiable.The discussion highlights quadratic regularization and the long history of incremental gradient methods, beginning with LMS.
  • Regularization: Nonquadratic regularizers can be handled when their proximal iterations have a simple form, such as separable coordinatewise minimizations.For separable regularization, the proximal step decomposes into n one-dimensional problems and can be computed in closed form.
  • Regularization: The incremental algorithms are well-suited to ℓ1-regularization by combining a proximal regularization step with a gradient step on a selected data-fit component.The resulting procedure is related to iterative shrinkage/thresholding methods in signal processing.
  • Feasibility: Feasibility problems with constraint sets revealed progressively can be converted into additive-cost problems using exact distance penalties.For Lipschitz continuous f and sufficiently large penalty parameters, the penalized and constrained problems have the same minima under the stated set assumptions.
  • Feasibility: The corresponding proximal step projects onto a selected constraint set and then interpolates between the current point and that projection.This structure supports incremental algorithms for penalized feasibility formulations.

6. CONCLUSIONS

The paper surveys incremental algorithms for large-data additive problems and unifies proximal, gradient, and subgradient methods. This framework separates components by how conveniently they can be handled, outlines convergence properties, and identifies applications while leaving substantial evaluation work for future research.

  • Conclusions: Incremental algorithms address challenges from large data sets, machine-learning constraint sets, additive problem structure, and duality-related problems.The conclusion presents these as the broad contexts motivating the survey.
  • Conclusions: A unified analytical framework includes incremental proximal algorithms and their combinations with established gradient and subgradient methods.The framework brings these algorithmic families into a common treatment.
  • Conclusions: The combinations allow cost functions to be separated between parts handled by proximal iterations and remaining parts handled by subgradient iterations.The proximal-handled parts may admit essentially closed-form updates.
  • Conclusions: The paper outlines convergence properties and shows that the algorithms apply to important problems studied in recent applications.The conclusion states applicability without reporting a single aggregate numerical result.
  • Conclusions: Further work includes applying and evaluating the methods more broadly, along with alternative iterations, stepsizes, distributed or asynchronous implementations, and error-tolerant variants.These items are presented as subjects for future investigation rather than established results of the survey.
Loading 1507.01030v2…