Introduction
Stochastic optimization is a cornerstone of modern machine learning, yet it faces two persistent challenges: non-smoothness and "variance blindness." Many popular objective functions, such as $L_1$ regularization or hinge loss, are non-differentiable. This lack of smoothness typically prevents the use of accelerated optimization techniques. Furthermore, while increasing the number of gradient samples per iteration ($m$) reduces variance in smooth optimization, standard theory for non-smooth functions suggests that convergence rates depend primarily on the number of updates, not the total number of samples. This paper introduces a framework that bridges this gap by combining randomized smoothing with accelerated gradient methods.
The Problem: Non-Smoothness and Variance
In stochastic optimization, we aim to minimize a function $f(x) = \mathbb{E}[F(x; \xi)]$. When $f$ is non-smooth, two issues arise:
- Lack of Acceleration: Accelerated methods (like Nesterov’s) require a Lipschitz continuous gradient. Without it, we are often stuck with slower subgradient-style convergence.
- Inefficient Parallelism: For non-smooth functions, the standard convergence rate is $O(1/\sqrt{T})$, where $T$ is the number of iterations. Crucially, this rate often does not improve by taking more samples per iteration. This means that in a distributed environment, adding more workers to compute gradients in parallel does not theoretically reduce the number of iterations needed to reach a target accuracy.
Methodology: Randomized Smoothing and Accelerated Dual Averaging
The authors propose a two-pronged approach to overcome these hurdles.
1. Randomized Smoothing
The core idea is to replace the non-smooth function $f$ with a smooth approximation $f_\mu$. This is achieved by convolving $f$ with a probability density $\mu$ (e.g., a Gaussian or uniform distribution): $$f_\mu(x) = \mathbb{E}_{Z \sim \mu} [f(x + Z)]$$ By sampling $m$ points in a neighborhood around the current iterate and averaging their stochastic gradients, the algorithm obtains a gradient estimate for the smoothed function.
2. Accelerated Dual Averaging
The authors adapt Tseng’s accelerated dual averaging framework to handle the smoothed objective. A key innovation is the use of a dynamic smoothing parameter $u_t$. By decreasing the size of the perturbation as the algorithm progresses, the method "sharpens" its approximation, eventually converging to the optimum of the original non-smooth function. This allows the algorithm to benefit from acceleration while maintaining the robustness of smoothing.
Key Insights
Optimal Convergence Rates
The paper proves that this approach achieves a convergence rate of $O(RL_0/\sqrt{Tm})$. This result is significant because the error scales with the total number of samples ($Tm$) rather than just the number of iterations ($T$). This matches the optimal rates known for smooth stochastic optimization and provides a theoretical justification for mini-batching in non-smooth settings.
Amortizing Proximal Costs
In many high-dimensional problems, the "proximal" step (e.g., projecting onto a complex constraint set) is significantly more expensive than computing a gradient. For example, in Metric Learning, the gradient computation is $O(d^2)$, but the projection onto the positive semidefinite (PSD) cone is $O(d^3)$. By using a large number of samples $m$ per iteration, the algorithm performs fewer expensive projections to reach the same level of accuracy, leading to substantial wall-clock time savings.
Empirical Results
The framework was validated on two primary tasks:
- Robust Linear Regression: Using $L_1$ loss on synthetic data, the authors demonstrated that the number of iterations required to reach a target error decreases linearly as the number of samples $m$ increases. This confirms the $1/\sqrt{m}$ variance dependence predicted by their theory.
- Metric Learning: In high-dimensional settings, the smoothed algorithm outperformed standard stochastic gradient descent (SGD). By scaling $m$ to match the problem dimension, the algorithm significantly reduced the total computation time by minimizing the number of costly PSD projections.
Conclusion and Future Work
This work provides a theoretically grounded and practically efficient method for non-smooth stochastic optimization. By enabling linear speedups through parallelism and amortizing expensive proximal operations, it addresses key bottlenecks in large-scale machine learning.
However, some challenges remain. The smoothing technique introduces a dependence on the dimension $d$ in the lower-order terms of the convergence rate. Future research may explore whether dimension-independent smoothing is achievable or if specific smoothing distributions can be tailored to the geometry of different constraint sets. Additionally, while the accelerated dual averaging scheme is powerful, its implementation requires more careful parameter tuning than standard SGD.
Summary updated