A Smoothing Stochastic Gradient Method for Composite Optimization

Qihang Lin

Introduction

In modern machine learning and statistics, optimization problems often involve minimizing a composite objective function consisting of a smooth loss component and a non-smooth penalty term. While stochastic gradient descent (SGD) is the standard approach for large-scale data, its efficiency is often hampered when the non-smooth penalty (such as the overlapped group lasso) lacks a closed-form proximal operator. This paper introduces a novel Smoothing Stochastic Gradient (SSG) framework that addresses this bottleneck by integrating Nesterov’s smoothing technique into a stochastic optimization setting.

Problem Formulation

The research focuses on the optimization problem: $$\min_{x \in X} \{ \phi(x) := f(x) + h(x) \}$$

Where:

  • $f(x)$ is a smooth function represented as an expectation ($E[F(x, \xi)]$), typically a loss function like least squares or logistic regression.
  • $h(x)$ is a non-smooth regularizer, such as the $\ell_1$-norm or more complex structures like fused lasso.

Two primary challenges exist: the stochastic nature of $f(x)$ requires relying on noisy gradient estimates, and complex regularizers $h(x)$ often require expensive inner-loop sub-routines to compute projection mappings, significantly slowing down convergence in high-dimensional settings.

The Smoothing Stochastic Gradient (SSG) Framework

The authors propose two algorithms to tackle these challenges:

  1. Stochastic Gradient (SG): A stochastic adaptation of Tseng’s accelerated gradient method. It utilizes two distinct step-length sequences to maintain convergence despite gradient noise.
  2. Smoothing Stochastic Gradient (SSG): This is the core contribution. For complex $h(x)$, the algorithm replaces the non-smooth term with a smooth approximation $h_\mu(x)$ using Nesterov’s smoothing. This transformation converts a difficult projection step into a simple, unconstrained quadratic problem with a closed-form solution, eliminating the need for costly inner-loop solvers.

Key Insights: Smoothing is "Free" in Stochastic Land

A significant theoretical finding of this work is that while smoothing typically degrades the convergence rate of deterministic algorithms (e.g., from $O(1/N^2)$ to $O(1/N)$), it does not penalize the rate in a stochastic setting. In stochastic optimization, the primary bottleneck is the variance of the gradient estimates rather than the lack of smoothness. The authors prove that the error introduced by smoothing is dominated by the stochastic variance, allowing SSG to maintain the optimal $O(1/\sqrt{N})$ convergence rate while gaining substantial computational efficiency.

Experimental Results

The algorithms were evaluated using synthetic datasets mimicking high-dimensional regression and classification (up to 100,000 samples and various feature counts). The experiments focused on the Hierarchical/Overlapped Group Lasso, where traditional proximal methods are computationally expensive.

Key findings include:

  • Computational Speedup: On hierarchical group lasso problems, SSG significantly outperformed standard SG and Accelerated Stochastic Approximation (AC-SA). While SG required hundreds of seconds due to internal coordinate descent solvers, SSG reached lower objective values in a fraction of the time because each iteration was computationally inexpensive.
  • Aggressive Step Sizes: The proposed algorithms use more aggressive step-size policies than existing methods, leading to faster empirical convergence when stochastic gradients are relatively accurate.
  • Robustness: The method performed consistently across both finite (discrete) datasets and infinite (continuous) probability distributions.

Conclusion and Future Work

The SSG framework provides a theoretically sound and practically efficient way to handle complex non-smooth regularizers in large-scale stochastic optimization. By showing that smoothing is essentially "free" in terms of convergence rates, the authors enable the use of direct updates for problems that previously required slow, nested algorithms. Future research may focus on extending this technique to regularizers that do not fit the "max-structure" required for Nesterov's smoothing and validating the approach on non-normal, real-world datasets in fields like genomics or finance.

Summary updated

BibTeX
@article{lin2014smoothing,
  author = {Qihang Lin},
  title = {{A Smoothing Stochastic Gradient Method for Composite Optimization}},
  journal = {Optim. Methods Softw.},
  year = {2014},
  doi = {10.1080/10556788.2014.891592},
}
Figure