PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Variance Reduction Methods for Saddle-Point Problems

P Balamurugan, Francis Bach

arXiv:1605.06398v2cs.LGmath.OC

TL;DR

The paper addresses large-scale convex-concave saddle-point problems whose objectives can be split into many components, extending stochastic variance-reduction methods beyond separable convex minimization. It provides monotone-operator convergence analysis for SVRG- and SAGA-style algorithms, studies splitting and sampling choices, and adds catalyst acceleration. The authors report the first linearly convergent incremental gradient algorithms for saddle-point problems, improving over existing batch or stochastic algorithms in theory and practice.

  • Problem

    Large-scale saddle-point problems with component structure are common in machine learning, but existing accelerated stochastic methods apply only to separable objective functions.

  • Method

    The paper extends SVRG and SAGA to saddle-point problems, analyzes them through monotone operators, and supports multiple splits with non-uniform sampling and catalyst acceleration.

  • Results

    The authors report the first linearly convergent incremental gradient algorithms for saddle-point problems, improving over existing batch or stochastic algorithms in theory and practice.

  • Takeaways & Limitations

    The same algorithms extend beyond saddle-point problems to variational inequalities, while splitting and sampling choices are central to efficiency.

  • Takeaways & Limitations

    The current approach requires knowledge of the strong convexity-concavity constants, and the SAGA bound under non-uniform sampling requires resampling operators after updates.

Abstract

from arXiv · show

We consider convex-concave saddle-point problems where the objective functions may be split in many components, and extend recent stochastic variance reduction methods (such as SVRG or SAGA) to provide the first large-scale linearly convergent algorithms for this class of problems which is common in machine learning. While the algorithmic extension is straightforward, it comes with challenges and opportunities: (a) the convex minimization analysis does not apply and we use the notion of monotone operators to prove convergence, showing in particular that the same algorithm applies to a larger class of problems, such as variational inequalities, (b) there are two notions of splits, in terms of functions, or in terms of partial derivatives, (c) the split does need to be done with convex-concave terms, (d) non-uniform sampling is key to an efficient algorithm, both in theory and practice, and (e) these incremental algorithms can be easily accelerated using a simple extension of the "catalyst" framework, leading to an algorithm which is always superior to accelerated batch algorithms.

1 Introduction

The paper extends stochastic variance-reduction methods to component-split convex-concave saddle-point problems, where standard convex-minimization analyses do not apply. It develops monotone-operator convergence analysis, identifies split and sampling choices, and accelerates the resulting incremental algorithms.

  • Motivation: The paper targets saddle-point problems with non-separable losses or regularizers by exploiting component structure in the saddle-point formulation.Such structure may exist in the saddle-point problem even when the associated primal and dual optimization problems are not separable.
  • Contribution: SVRG and SAGA are extended to saddle-point problems, addressing the need for methods that otherwise access all components at every iteration.The algorithmic extension is described as straightforward, but its convergence analysis differs substantially from convex minimization.
  • Contribution: The convergence analysis uses monotone operators and establishes linear convergence beyond saddle-point problems, including variational inequalities.This analysis relies on monotonicity rather than the convex-minimization framework.
  • Contribution: Saddle-point splitting supports function-based and partial-derivative-based decompositions, without requiring every component to arise from a convex-concave function.The paper also identifies non-uniform sampling as important for efficient algorithms in theory and practice.
  • Contribution: A simple extension of the catalyst framework accelerates the incremental algorithms and is reported to be always superior to accelerated batch algorithms.The acceleration applies to the proposed incremental saddle-point methods.

2 Composite Decomposable Saddle-Point Problems

This section formulates composite saddle-point problems with convex-concave structure and decomposable operators, then motivates stochastic and accelerated methods for settings where primal or dual objectives are non-separable.

  • Problem formulation: The framework assumes strongly convex-concave M with an efficiently computable proximal operator and smooth convex-concave K.These assumptions ensure a unique saddle-point solution and equality of the min-max and max-min values.
  • Decompositions: The gradient operator B may be split into Lipschitz components without requiring each component to derive from a scalar function.Factored splits separately sample row and column contributions and reduce storage requirements for SAGA.
  • Decompositions: Two natural bilinear decompositions use individual matrix elements or factored row-column operators, corresponding to different sketches of K.The individual split uses gradient operators of bilinear functions, whereas factored elements need not be gradients of functions.
  • Applications: Saddle-point formulations cover machine-learning problems with non-separable losses or regularizers, robust optimization, and convex relaxations of unsupervised learning.Examples include structured prediction, overlapping grouped norms, total variation, discriminative clustering, and matrix factorization.
  • Algorithms and convergence: Acceleration replaces the batch rate (1 − 1/(1 + L^2))^t with (1 − 1/(1 + 2L))^t, improving strongly when L is large.The acceleration extends the catalyst framework and can also yield a similar rate for the batch setting with nonlinear K.
  • Algorithms and convergence: The proposed stochastic extensions use non-uniform sampling, whose convergence bounds are superior to uniform-sampling SAGA/SVRG and batch forward-backward.Experiments report that accelerated SVRG with non-uniform sampling is the most efficient method, while uniform SAGA may fail to improve on batch methods.

3 SVRG: Stochastic Variance Reduction for Saddle Points

SVRG is extended to decomposable saddle-point operators by estimating the full operator from a periodically refreshed reference point and sampled component corrections, yielding linear convergence and improved bilinear complexity.

  • Algorithm: SVRG estimates B(x, y) using a known full value at a reference iterate plus sampled component differences, preserving expectation while reducing variance.The method operates in epochs and permits mini-batches of size m.
  • Algorithm: The algorithm uses a prescribed number of updates per epoch proportional to L^2 + 3L̄(π)^2/m.The reference point and full operator value are refreshed between epochs.
  • Complexity: Increasing the mini-batch size m can reduce the contribution of the proximal-operator cost, while replacing L^2 by L̄^2 worsens the complexity bound.These are explicit trade-offs in the generic computational-complexity result.
  • Complexity: For bilinear problems, factored updates with m = 1 and individual updates with m = n + d have complexity proportional to [nd + max{n, d}∥K∥^2 F/(λγ)] log(1/ε).The stated complexity applies under non-uniform sampling and improves significantly over non-accelerated batch methods.

4 SAGA: Online Stochastic Variance Reduction for Saddle Points

SAGA provides an online variance-reduced saddle-point method by storing component operator values, with linear convergence and storage-complexity trade-offs that depend on the chosen split.

  • Algorithm: SAGA stores past component values g_i = B_i(x_old(i), y_old(i)) and updates an unbiased estimate of the full operator from sampled indices.The stored values correspond to potentially different old iterates for each component.
  • Convergence: The method has linear-convergence guarantees under the paper’s assumptions, including an option to resample operators after updates for non-uniform sampling.The resampling requirement is needed for the non-uniform-sampling bound, although experiments used a uniform/non-uniform mixture without resampling.
  • Trade-offs: SVRG uses epochs and little storage, whereas SAGA is online with fewer parameters but requires storage for component values.For bilinear problems, factored SAGA stores O(n + d) elements, compared with O(dn) for individual splits.
  • Trade-offs: For individual splits, SAGA and SVRG have the same overall running-time complexity, while factored splits change the relevant dependence to max{|J|, |K|}.Factored storage updates the two operator parts independently.

5 Acceleration

The paper accelerates incremental saddle-point methods by embedding SVRG in a Catalyst-style sequence of regularized problems, with complexity gains determined by operator-cost imbalance.

  • Catalyst acceleration: Catalyst acceleration solves a sequence of saddle-point problems with added regularization using SVRG and periodically updated reference iterates.The modification updates the reference point after a prescribed number of epochs, with optional more aggressive updates.
  • Complexity: The accelerated method has per-update complexity proportional, up to logarithmic terms, to T(B) + L̄^2(1 + τ)^−2 max_i∈I T(B_i), excluding the proximal cost.
  • Complexity: The trade-off is optimized at 1 + τ = L̄ sqrt(max_i∈I T(B_i)/T(B)), yielding a potential acceleration when component costs are sufficiently favorable.
  • Results: For bilinear problems, the resulting complexity improves significantly up to logarithmic factors, as reported in Table 1.
  • Scope: The same acceleration idea should apply to SAGA and to batch methods, where it becomes valid for all functions K rather than only bilinear ones.

6 Extension to Monotone Operators

The analysis extends variance-reduced saddle-point algorithms to sums of operators, using resolvents and monotonicity rather than convex-minimization-specific arguments.

  • Operator framework: The framework considers a maximal strongly monotone operator A and Lipschitz component operators B_i whose sum B is monotone.
  • Operator framework: The algorithm finds zeros of A + B using the resolvent of A and forward evaluations of the component operators B_i.
  • Applications: Saddle-point problems recover this framework by representing K through B and M through a potentially set-valued operator A.
  • Applications: Convex minimization is a special case with A = ∂g and B_i = ∂f_i, but its operators additionally satisfy co-coercivity.
  • Analysis: The analysis does not use co-coercivity, covering broader problems than prior operator extensions; co-coercive step-sizes can diverge in the general setting.

7 Experiments

Experiments on non-separable and separable supervised-learning problems show that non-uniformly sampled SAGA and accelerated SVRG outperform relevant batch or non-separable baselines.

  • Setup: The experiments use binary classification with non-separable regularization and smooth loss, including a clustering-inducing regularizer and an AUC surrogate.
  • Setup: The study evaluates sido with n = 10142 and d = 4932, and rcv1 with n = 20242 and d = 47236, under regularization settings including λ/λ0 = 10^−1.
  • Results: Uniformly sampled SAGA does not improve on batch methods, whereas SAGA and accelerated SVRG with non-uniform sampling improve significantly over existing methods.
  • Results: Accelerated SVRG gains more strongly on ill-conditioned problems, while primal methods that ignore separability are inferior on the separable-loss comparison.

8 Conclusion

The paper concludes that its incremental algorithms and operator analysis apply beyond saddle-point problems, while requiring strong monotonicity and currently known strong convexity-concavity constants.

  • Conclusion: The authors present the first linearly convergent incremental gradient algorithms for saddle-point problems, improving over existing batch or stochastic algorithms in theory and practice.
  • Limitation: The current method requires knowledge of the strong convexity-concavity constants, with adaptivity left for future work.
  • Assumptions: The proof framework assumes A is maximal and μ-strongly monotone, while B is monotone and L-Lipschitz-continuous.
  • Saddle-point specialization: For saddle-point problems, scaled operators A and B preserve the problem solutions after rescaling and connect the resolvent of A to the proximal operator of M.
  • Limitation: The operator proof transfers Euclidean-norm convergence but does not readily provide bounds on primal and dual gaps.

B Proof for Deterministic Algorithms

The deterministic analysis proves linear convergence by treating saddle-point iterations as contractions of a Lyapunov quantity under monotonicity and Lipschitz assumptions. Without co-coercivity, the resulting guarantee is slower than the standard convex-minimization rate.

  • Proof strategy: A Lyapunov function contracts by a factor strictly below one at every algorithmic step.For forward-backward iterations, the Lyapunov function is the squared distance to the optimum; the accelerated method uses a different quantity.
  • Forward-backward algorithm: The forward-backward iteration applies a resolvent of a strongly monotone operator A after a step along a monotone L-Lipschitz operator B.The optimum remains invariant because it is a zero of A + B.
  • Forward-backward algorithm: Linear convergence requires 1 + σ^2L^2 < (1 + σµ)^2.The contraction condition follows from monotonicity of A and Lipschitz continuity of B.
  • Rate comparison: The monotone-operator analysis is slower for convex minimization because it does not use co-coercivity of B.Co-coercivity would replace the factor 1 + σ^2L^2 by 1 for σ ≤ 2/L, yielding an approximately 1 − 2µ/L rate.
  • Accelerated algorithm: The accelerated iteration adds an extrapolated previous-step difference inside B and extends the analysis to general monotone operators.Its parameter choice is obtained by regrouping terms and using firm non-expansiveness of the resolvent.

C Proof for Existing Stochastic Algorithms

The existing stochastic analysis studies unbiased random operator perturbations around a strongly monotone, Lipschitz operator. It obtains sublinear convergence whose constant depends on noise at the optimum and supports sampling from finite operator families, including non-uniform sampling.

  • Stochastic operator iteration: The stochastic iteration combines a strongly monotone resolvent step with an unbiased random operator perturbation C_t.The random operators are independent, need not be monotone, and satisfy E C_t(z) = 0.
  • Proof strategy: The analysis uses resolvent contractivity, conditional expectations, monotonicity, and Lipschitz continuity to expand the error recursion.These ingredients yield bounds on the expected squared distance to the optimum.
  • Convergence result: O(1/t) convergence is obtained, with the constant determined by noise in the operator values at the optimum.Initial conditions are forgotten faster, at rate O(1/t^2).
  • Finite-family sampling: Sampling from a finite family can use a probability vector π, with an expected Lipschitz bound summarized by the corresponding aggregate constant.A computable upper bound may replace the exact global Lipschitz constant when the latter is unknown or expensive.
  • Relation to convex minimization: The monotone-operator proof does not use function values and uses shorter step sizes to address the lack of co-coercivity.This identifies the main analytical difference from convex minimization algorithms.

D.1 SVRG: Stochastic-Variance reduced saddle-point problems (Theorem 1)

SVRG is extended to split saddle-point operators by proving geometric contraction of iterates and by controlling estimator noise through stored operator values and sampling. The same framework supports factored splits, monotone-operator formulations, and catalyst-style acceleration.

  • SVRG: A single SVRG epoch shrinks the expected squared distance to the optimum by a factor of 3/4 when its iteration count is chosen appropriately.The epoch starts from the reference estimate ˜z.
  • SVRG: The proof uses unbiased sampling, resolvent contractivity, monotonicity of the aggregate operator B, and Lipschitz bounds to control the stochastic recursion.The variance is bounded using sampled component operators and the sampling distribution π.
  • SVRG: The analysis never requires individual operators B_i to be monotone, provided their sum B is monotone.This permits arbitrary component splits under the aggregate monotonicity condition.
  • SAGA-style storage: The Lyapunov function combines iterate error with the stored operator-value error, allowing geometric decay without function values or averaged iterates.The stored-gradient construction is updated through sampled components, including sampling with replacement.
  • Factored splits: Factored splits replace the component-count factor |I| by max{|J|, |K|} in the Lyapunov analysis.The two vector parts are treated separately for row-and-column factorizations.
  • Acceleration: The accelerated scheme approximately solves a regularized resolvent problem through SVRG epochs and updates the reference estimate periodically.Its theory improves the convergence rate, while the implementation uses a primal-dual-gap heuristic to avoid excessive precision.

F Additional Experimental Results

Experiments compare batch, stochastic, variance-reduced, accelerated, and primal methods across machine-learning settings using convergence and test-loss diagnostics. Non-uniform sampling and acceleration improve practical performance, while separability determines which primal baselines apply.

  • Experimental setup: The experiments track test losses, distances to optimum, and primal-dual gaps against the number of data passes across three machine-learning settings.The compared methods use step sizes from their respective convergence analyses.
  • Observed convergence: Non-uniform sampling is key to good performance, and the distance to optimum shows clear linear convergence, unlike the more erratic primal-dual gap.The primal-dual gap still converges, but its trajectory is less regular.
  • Acceleration and conditioning: As λ decreases and problems become more ill-conditioned, accelerated methods gain more over their non-accelerated counterparts.For two of three settings, smaller regularization also produces a smaller final test loss, while non-accelerated methods require more data passes to reach good testing losses.
  • Primal baselines: Primal methods without separability can run on all instances but are not competitive, although they can perform well early before variance-reduced saddle-point methods catch up.The comparison notes that their dual candidates are computed indirectly, which may disadvantage them.
  • Primal baselines: When applicable, separability-based primal SAGA is significantly faster than the saddle-point techniques, but it cannot run on non-separable problems.The authors attribute part of this advantage to adaptivity to strong convexity.
Loading 1605.06398v2…