PaperlayerView exact revision on arXiv

Source-linked AI summary

Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting

Jakub Konečný, Jie Liu, Peter Richtárik, Martin Takáč

arXiv:1504.04407v2cs.LGstat.ML

TL;DR

The paper addresses composite finite-sum optimization where stochastic methods offer cheaper updates but mini-batching has not been analyzed for primal proximal methods. It introduces mS2GD, which combines a full-gradient epoch step with mini-batched proximal stochastic updates, and shows improved work up to a batch-size threshold together with simple parallelization.

  • Problem

    The paper studies strongly convex composite optimization with a smooth finite-sum term and a nonsmooth regularizer, where stochastic methods face variance and mini-batching had not been analyzed for primal proximal methods.

  • Method

    mS2GD performs a full-gradient step at each epoch's starting point, then uses mini-batched stochastic proximal updates within the inner loop.

  • Results

    mS2GD can require fewer gradient evaluations than S2GD up to a threshold mini-batch size, with complexity worsening beyond that threshold.

  • Takeaways & Limitations

    The method is designed for simple parallel implementation and is reported as competitive in theory and faster in practice, including for sparse datasets.

Abstract

from arXiv · show

We propose mS2GD: a method incorporating a mini-batching scheme for improving the theoretical complexity and practical performance of semi-stochastic gradient descent (S2GD). We consider the problem of minimizing a strongly convex function represented as the sum of an average of a large number of smooth convex functions, and a simple nonsmooth convex regularizer. Our method first performs a deterministic step (computation of the gradient of the objective function at the starting point), followed by a large number of stochastic steps. The process is repeated a few times with the last iterate becoming the new starting point. The novelty of our method is in introduction of mini-batching into the computation of stochastic steps. In each step, instead of choosing a single function, we sample $b$ functions, compute their gradients, and compute the direction based on this. We analyze the complexity of the method and show that it benefits from two speedup effects. First, we prove that as long as $b$ is below a certain threshold, we can reach any predefined accuracy with less overall work than without mini-batching. Second, our mini-batching scheme admits a simple parallel implementation, and hence is suitable for further acceleration by parallelization.

I. INTRODUCTION

The paper studies composite optimization with a smooth finite-sum component and a possibly nonsmooth regularizer, focusing on stochastic methods for large-scale problems. It introduces mini-batching for proximal semi-stochastic gradient descent to improve complexity and enable parallel computation.

  • Problem setting: The objective combines a smooth convex function F with a possibly nonsmooth convex regularizer R, which can also model constraints.The smooth term often has finite-sum structure, F as an average of convex functions.
  • Stochastic methods: SGD reduces per-iteration gradient cost but suffers from non-vanishing variance, motivating variance-reduction strategies and mini-batches.At an optimum, individual component gradients need not vanish, so stochastic updates can move away from the solution.
  • Modern stochastic methods: Modern stochastic methods such as SAG, SDCA, SVRG, and S2GD improve substantially over classical deterministic methods in theoretical complexity and practical efficiency.The cited comparison gives n + κ versus nκ for proximal gradient descent and states that FISTA is outperformed when κ ≤ O(n^2).
  • Contributions: The paper fills a gap by analyzing mini-batching for primal modern stochastic methods, including the proximal setting rather than only the R ≡ 0 case.Earlier mini-batch analyses covered dual methods, while S2GD itself had been analyzed only without the proximal term.
  • Contributions: mS2GD can use fewer gradient evaluations than S2GD up to a threshold mini-batch size, while also admitting a simple parallel implementation.Beyond the threshold, the complexity deteriorates; the method continues from the last inner-loop iterate rather than averaging iterates.

III. THE ALGORITHM

mS2GD combines proximal gradient updates with semi-stochastic variance reduction and mini-batching. Each epoch computes a full reference gradient, then performs randomly sized inner-loop updates using mini-batch stochastic estimates.

  • Inner loop: Each new inner-loop iterate is produced by a proximal update using the mini-batch stochastic estimate G_k,t.This replaces the full gradient in the standard proximal update.
  • Method: mS2GD applies proximal updates using stochastic estimates of the full gradient formed from an old reference point and a current inner-loop iterate.The stochastic estimate is unbiased, and the proximal operator handles the nonsmooth regularizer.
  • Outer loop: Each epoch begins by computing and storing the full gradient g_k at the reference point x_k, then initializes the inner loop at x_k.The outer-loop reference point is updated across epochs.
  • Inner loop: The inner loop samples a uniformly random number of iterations and selects a uniformly random mini-batch of b examples at each iteration.The mini-batch has size |A_k,t| = b.
  • Cost and convergence: Each inner iteration requires 2b units of work, while the outer loop provides a reference gradient whose variance-reduction effect supports fast convergence.The squared norm of the stochastic estimate approaches zero across the outer and inner loops.

A. Assumptions

The analysis assumes a closed convex regularizer, smooth component functions, and strong convexity of the objective. Under these assumptions, mS2GD has linear convergence and interpolates between stochastic and deterministic proximal-gradient rates as the mini-batch grows.

  • Assumptions: The regularizer R is closed and convex, while every component function f_i has an L-Lipschitz continuous gradient.The averaged function F inherits the same Lipschitz constant L.
  • Assumptions: The objective P is assumed strongly convex with parameter μ > 0, while the individual strong-convexity constants μ_F and μ_R may both equal zero.Thus, strong convexity need not come separately from F or R.
  • Main result: Under the stated assumptions and parameter conditions, Theorem 1 gives mS2GD linear convergence in expectation with rate ρ.The conditions include 0 < h ≤ 1/L and 4hLα(b) < 1.
  • Parameter choice: With suitable parameter choices, linear convergence uses k = O(log(1/ϵ)) outer loops, generally h = O(1/L), and m = O(κ).Choosing parameters that make ρ arbitrarily small can instead produce suboptimal workload dependence on ϵ.
  • Special cases: For b = 1, mS2GD recovers the analyzed rates of Prox-SVRG and S2GD in their respective settings.The S2GD comparison applies when R = 0.
  • Special cases: For b = n, α(b) = 0 and the method obtains the standard proximal-gradient rate O(nκ log(1/ϵ)).The corresponding choices are h = 1/L and m = 2κ.
  • Mini-batch speedup: Mini-batching can reduce overall work when the optimized inner-loop workload satisfies m_b*/b < m_1*.The analysis states that the optimized quantity decreases faster than 1/b in the relevant regime.

E. Convergence rate

For sufficiently small mini-batches, mS2GD preserves the b = 1 workload while enabling linear parallel speedup; with larger batches, Acc-Prox-SVRG can become preferable because of acceleration.

  • Convergence rate: Small enough mini-batches leave mS2GD's total work unchanged from the b = 1 case.The result applies in the analyzed small-mini-batch regime.
  • Convergence rate: Parallel execution of the b updates yields linear speedup when the mini-batch is within the workload-preserving range.The speedup is conditional on performing the updates in parallel.
  • Convergence rate: mS2GD is theoretically better than Acc-Prox-SVRG for sufficiently small mini-batches on both ill-conditioned and well-conditioned data.The comparison concerns theoretical complexity bounds.
  • Convergence rate: Large mini-batches reverse the comparison because Acc-Prox-SVRG's acceleration becomes advantageous.For b = 64, the plots show no observable difference between the methods.
  • Convergence rate: Sparse-data implementation uses lazy or delayed updates because dense stochastic gradients would otherwise require updating all d coordinates.The implementation tracks coordinate update times and refreshes coordinates when they are read.
  • Convergence rate: The lazy-update approach preserves the same final iterate as the original algorithm and admits closed-form repeated proximal updates for ℓ2- and ℓ1-regularizers.The equivalence is stated for the end of the inner loop.

and let [·]+

The supplied passages primarily introduce proximal lazy-update cases and relate mS2GD's lazy-update formulation to prior work.

  • and let [·]+: The proximal lazy-update operator for an ℓ1-regularizer is expressed through cases involving the gradient coordinate and threshold parameters.The cited passages identify the case structure but do not provide the complete preceding definition.
  • and let [·]+: The paper presents lazy updates as a more general stochastic-gradient result under its structural and separability assumptions.The authors distinguish their setting from earlier online-learning and multinomial-logistic-regression applications.

VI. EXPERIMENTS

The experiments evaluate mS2GD on sparse binary-classification problems using ℓ2 regularization and logistic loss across four public datasets.

  • VI. EXPERIMENTS: The experiments use R(x) = λ∥x∥2^2 and logistic loss for binary classification.The data consist of example-label pairs.
  • VI. EXPERIMENTS: Four publicly available datasets—rcv1, news20, covtype, and astro-ph—form the binary-classification test set.These datasets are used in the reported experimental sections.
  • VI. EXPERIMENTS: The logistic-regression analysis uses Li = ∥ai∥2/4 and sets the regularization parameter to λ = 1/n.The analysis assumes a common Lipschitz constant L equal to maxi∈[n] Li.
  • VI. EXPERIMENTS: Figure 4 compares several algorithms on the four datasets using mS2GD with mini-batch size b = 8.The figure arranges rcv1, news20, covtype, and astro-ph in a four-panel layout.
  • VI. EXPERIMENTS: Table I summarizes dataset sizes n, dimensions d, sparsity proportions, and Lipschitz constants L.The table is the experiment section's dataset summary.

A. Speedup of mS2GD

mS2GD uses mini-batches to accelerate proximal semi-stochastic optimization both through unchanged workload below a threshold and through parallel execution. Experiments report competitive or superior performance against several algorithms, including on image deblurring.

  • Speedup of mS2GD: Mini-batches up to a threshold leave mS2GD’s total workload unchanged, enabling linear speedup when the b updates run in parallel.The ideal parallelization assumes b gradients can be evaluated simultaneously in the time required for one gradient.
  • Speedup of mS2GD: With b = 2, 4, or 8, mS2GD performs the same or better than S2GD without parallelism on rcv1 and astro-ph.Performance is measured using effective passes, where n units of work constitute one pass.
  • Speedup of mS2GD: Larger mini-batches are worse without parallelism but remain promising under ideal parallel execution.In practice, component-gradient evaluation times cannot always be made identical.
  • mS2GD vs other algorithms: Figure 4 reports that mS2GD outperforms other algorithms in the test pool on four datasets.The comparison includes SGDcon, SGD+, FISTA, and SAG among the implemented methods.
  • Image deblurring: In deblurring experiments, mS2GD is compared with SGD+, S2GD, and FISTA over 100 epochs, while SGD+ slows after 10–20 epochs.Reconstructions are shown after T = 20, 60, and 100 epochs.
  • Conclusion: The method is designed for strongly convex composite minimization and is reported as efficient for sparse data sets.The paper situates such problems in inverse problems in signal processing and statistics.

APPENDIX A TECHNICAL RESULTS

The appendix establishes the stochastic-gradient properties and convergence argument underlying mS2GD’s proximal updates. It derives unbiasedness, controls variance, and obtains a linear convergence relation for the outer iterates.

  • Technical results: Conditioned on y_k,t, the mini-batch gradient estimator G_k,t is unbiased for ∇F(y_k,t), with variance controlled by the mini-batch sampling scheme.The variance expression depends on the mini-batch size b and the component-gradient differences.
  • Technical results: The proof uses the stepsize condition h ≤ 1/L and the nonexpansiveness of the proximal operator to bound successive iterates.The proximal operator satisfies ∥prox_R(x) − prox_R(y)∥ ≤ ∥x − y∥.
  • Technical results: The proximal full-gradient update is introduced as an analytical comparison point and is not computed by the algorithm.The analysis compares the stochastic proximal step with this hypothetical full-gradient update.
  • Technical results: The proof combines the inner-loop bounds over t = 1,…,m and recursively applies the resulting outer-iteration relation.The derivation proceeds by summing the inequalities and chaining expectations across outer iterations.
  • Technical results: Strong convexity and the optimality of x* provide the inequality needed to relate the stochastic iterates to the optimum.The argument combines this relation with nonnegative squared distance terms and conditional expectations.
  • Technical results: The resulting linear convergence bound is E[P(x_k) − P(x*)] ≤ ρ^k[P(x_0) − P(x*)].The contraction factor ρ is defined from the method parameters and is used to establish convergence.

C. Proof of Theorem 2

Theorem 2’s proof studies the inner-loop length m as a function of the stepsize h and identifies the admissible interval and optimal parameter choice. It also separates parameter behavior across mini-batch regimes.

  • Proof of Theorem 2: For a fixed stepsize h, the required inner-loop length m is determined by the target convergence relation.The proof treats m as a function m(h).
  • Proof of Theorem 2: The denominator governing m(h) is positive only under a stronger condition involving ρ, α(b), h, and L.This condition defines the admissible stepsize interval I_h.
  • Proof of Theorem 2: m(h) diverges as h approaches either endpoint of its admissible interval, so an interior stationary point gives the global minimum.The proof establishes continuity and differentiability inside I_h before applying the first-order condition.
  • Proof of Theorem 2: The candidate stepsize ẑh_b lies in I_h, and when it is optimal, substituting it into m(h) yields the theorem’s parameter expression.The proof verifies the interval membership through an equivalent inequality.
  • Proof of Theorem 2: When ẑh_b exceeds the admissible regime, the stepsize is instead set to 1/(4α(b)L) times ρ/(ρ+1).The theorem distinguishes the two cases through the mini-batch-dependent threshold.

D. Proof of Corollary 3

The corollary converts the convergence relation into an ε-accuracy guarantee and gives the resulting complexity for sufficiently small mini-batches. The analysis identifies a threshold below which mini-batching preserves efficient speedup.

  • Proof of Corollary 3: For b below the threshold, h_b equals ẑh_b and m_b is given by the theorem’s first parameter formula.For larger b, h_b is assigned the alternate boundary value.
  • Proof of Corollary 3: Choosing b < ⌈b_0⌉ and the stated constant stepsize yields the corollary’s convergence rate.The inner loop is run for the number of iterations specified in the corollary.
  • Proof of Corollary 3: k = ⌈log(1/ε)⌉ outer iterations ensure ρ^k ≤ ε under the selected rate.The proof uses ρ = e^-1 to obtain e^-k ≤ ε.
  • Proof of Corollary 3: The total complexity is O((n + κ) log(1/ε)) for mini-batch sizes below the threshold.The stated threshold is approximately b_0 ≈ 29.75.

APPENDIX C PROXIMAL LAZY UPDATES FOR ℓ1 AND ℓ2-REGULARIZERS

The appendix gives a proximal lazy-update recurrence for the iterates, expressing each update through a proximal operator and a scalar factor β.

  • For each step s from 1 to τ, the iterate is updated as prox_hR applied to the previous iterate minus hg.The passage writes the update as ỹ_s = prox_hR(ỹ_{s−1} − hg).
  • The proximal update is represented equivalently as β(ỹ_{s−1} − hg).
  • The resulting gradient-related quantity g is expressed using β, τ, y, and h.The displayed expression includes β^τ y and a factor involving hβ/(1−β)[1−β^τ].

B. Proof of Lemma 2

The proof analyzes the proximal lazy updates coordinatewise by partitioning cases according to the gradient component g_j and the coordinate value y_j. It derives piecewise expressions for the resulting iterate after τ updates.

  • Case analysis: The proof distinguishes three cases according to g_j: g_j ≥ λ, −λ < g_j < λ, and g_j ≤ −λ.These cases determine the signs and relative ordering of the update thresholds m and M.
  • Case analysis: When g_j ≥ λ, the thresholds satisfy M > m = −(λ − g_j)h ≥ 0.
  • Case analysis: When −λ < g_j < λ, the proof sets M = (λ + g_j)h > 0 and defines m from the corresponding threshold expression.
  • Piecewise updates: After simplification, the proof expresses the final coordinate using max{y_j − τM, 0} for y_j ≥ 0 and min{y_j − τm, 0} for y_j < 0.
  • Case analysis: When g_j ≤ −λ, the thresholds satisfy m < M = (λ + g_j)h ≤ 0.
  • Piecewise updates: The coordinatewise τ-step result is piecewise, with separate formulas depending on whether the update horizon crosses thresholds p, q, or τ.The resulting expressions use y_j − τM, y_j − pM − (τ − p)m, and analogous m- or M-based forms.
Loading 1504.04407v2…