TL;DR
This paper introduces mS2GD, a novel mini-batching approach for semi-stochastic gradient descent. By processing small batches of data instead of single data points for gradient estimation, mS2GD achieves faster convergence and enables parallelization, offering significant speedups for large-scale optimization problems.
What Problem Does This Paper Address?
Many real-world machine learning problems involve minimizing a composite function, which is a sum of a large number of smooth convex functions and a non-smooth convex function (often a regularizer). Traditional methods like FISTA become computationally prohibitive when the number of smooth functions ($n$) is very large. Stochastic gradient descent (SGD) offers a way to handle large $n$ by using noisy gradient estimates, but it's inherently sequential and hard to parallelize. Semi-stochastic gradient descent (S2GD) improves upon SGD by reducing gradient variance, but it still processes one data point at a time. The challenge is to develop an optimization method that is both efficient for large-scale problems and amenable to parallel computation.
Methods
The core innovation of this paper is the mini-batch semi-stochastic gradient descent (mS2GD) algorithm. It builds upon the S2GD framework, which involves an outer loop for deterministic gradient computation and an inner loop for stochastic updates. The key difference is in the inner loop: instead of sampling a single function to estimate the gradient, mS2GD samples a mini-batch of $b$ functions. The gradients of these $b$ functions are computed and then averaged to form a more stable, less noisy estimate of the overall gradient. This mini-batching technique is applied within the proximal setting, meaning it's designed to handle the non-smooth part of the objective function efficiently. The authors provide a theoretical analysis of mS2GD, proving that it achieves faster convergence rates than non-mini-batched methods, especially when the mini-batch size $b$ is below a certain threshold. They also highlight that this mini-batching naturally lends itself to parallel implementation.
Datasets
The paper uses the RCV1 dataset for experimental evaluation. This is a standard benchmark for L2-regularized logistic regression.
Key Insights and Ideas
- Mini-batching for Variance Reduction: The paper demonstrates that using mini-batches for gradient estimation in S2GD not only reduces variance more effectively than single-sample SGD but also leads to better theoretical convergence rates.
- Twofold Speedup: mS2GD offers a dual benefit:
- Theoretical Speedup: For a given accuracy, mS2GD can achieve it with fewer total gradient evaluations compared to non-mini-batched methods, up to a certain batch size.
- Practical Speedup: The mini-batch approach is inherently parallelizable, allowing for significant speedups on multi-core processors or distributed systems.
- Proximal Setting Advantage: The method is designed for composite optimization problems, which are common in machine learning (e.g., with L1 or L2 regularization), making it broadly applicable.
- No Averaging of Iterates: Unlike some previous methods, mS2GD continues from the last iterate of the inner loop, simplifying the implementation and avoiding the need to average multiple points.
Key Results
The paper presents a theoretical complexity result (Theorem 1) showing that mS2GD achieves linear convergence in expectation. Theorem 2 quantifies the speedup achievable by mini-batching, indicating that the number of gradient evaluations required to reach a target accuracy decreases as the mini-batch size $b$ increases, up to a certain point. Experiments on the RCV1 dataset (Figure 1) show that mS2GD can achieve the same accuracy as S2GD with significantly less work (fewer passes through the data), even without parallelism. Figure 2 illustrates the speedup from parallelism, showing that mS2GD can approach ideal parallel speedup.
Limitations and Future Work
- Threshold for Mini-batch Size: The theoretical analysis suggests that the benefits of mini-batching diminish or even reverse if the batch size $b$ becomes too large. The paper provides guidance on choosing an optimal $b$.
- Parameter Tuning: The performance of mS2GD, like many optimization algorithms, depends on the choice of parameters such as stepsize ($h$) and the number of inner loop iterations ($m$). The paper offers theoretical insights into optimal parameter choices.
- Future Work: The authors mention that the mini-batching scheme is suitable for further acceleration by parallelization, implying that exploring distributed implementations is a natural next step. They also suggest that the theoretical analysis could be extended to more general settings.
Summary updated