A smoothing stochastic gradient method for composite optimization

Qihang Lin, Xi Chen, Javier Peña

TL;DR

This paper introduces two novel stochastic gradient descent (SGD) algorithms for composite optimization problems, which are common in machine learning. The first algorithm, SG, handles smooth and non-smooth components efficiently. The second, SSG, further improves performance by incorporating a smoothing technique, particularly beneficial when the non-smooth part lacks a simple closed-form solution for projection.

What Problem Does This Paper Address?

Many machine learning problems, such as regularized linear regression and logistic regression, can be formulated as minimizing a composite objective function: $min f(x) + h(x)$. Here, $f(x)$ is a smooth, convex function (often an expectation over data), and $h(x)$ is a convex but non-smooth function. Traditional methods like interior-point methods struggle with large datasets. While first-order methods (like gradient descent) are more scalable, they often require solving a projection subproblem at each step. This projection can be computationally expensive or even intractable if $h(x)$ has a complex structure (e.g., overlapped group lasso). Furthermore, when $f(x)$ is an expectation, computing its exact gradient is often infeasible, necessitating the use of stochastic gradients. This paper addresses the challenge of efficiently solving such composite optimization problems in a stochastic setting, especially when the projection step is problematic.

Methods

The paper proposes two main algorithms:

  • Stochastic Gradient Descent (SG) Algorithm: This algorithm is designed to tackle the composite optimization problem $min f(x) + h(x)$ where $f(x)$ is a smooth function whose gradient is approximated stochastically (i.e., $G(x, \xi)$ is an unbiased estimate of $\nabla f(x)$). It adapts existing accelerated gradient methods by replacing exact gradients with stochastic ones. A key assumption is that the projection step required for the non-smooth part $h(x)$ has a closed-form solution.
  • Smoothing Stochastic Gradient Descent (SSG) Algorithm: This algorithm builds upon SG by addressing the scenario where the projection step for $h(x)$ does not have a closed-form solution. It leverages Nesterov's smoothing technique to approximate the non-smooth function $h(x)$ with a smooth lower approximation $h_\mu(x)$. This transforms the problem into minimizing a smooth function $f(x) + h_\mu(x)$, for which the projection step (now unconstrained) has a closed-form solution. The parameter $\mu$ controls the trade-off between the accuracy of the approximation and the smoothness of the objective.

Both algorithms are shown to achieve an $O(1/N)$ convergence rate, which is competitive with existing methods.

Datasets

The paper uses synthetic datasets for evaluating the proposed algorithms. These datasets are generated for:

  • Regularized Linear Regression:
    • With $l_1$-norm regularization (Lasso) on small and large datasets.
  • With hierarchical norm regularization on small and large datasets.
  • With $l_1$-norm regularization under a continuous probability distribution.
  • Regularized Logistic Regression:
    • With $l_1$-norm regularization.
  • With hierarchical norm regularization.

The authors do not introduce new benchmark datasets but rather use standard problem formulations for evaluation.

Key Insights and Ideas

  • Stochastic Gradients for Composite Optimization: The paper demonstrates that existing accelerated gradient methods can be effectively adapted to the stochastic setting for composite optimization, maintaining good convergence rates.
  • Smoothing as a Solution for Intractable Projections: The core innovation of SSG is using Nesterov's smoothing technique to convert a problem with a difficult projection step into one with an easily solvable unconstrained quadratic subproblem. This is crucial for problems like overlapped group lasso.
  • Negligible Price for Smoothing in Stochastic Setting: While smoothing typically increases the Lipschitz constant and can degrade convergence rates in deterministic settings, the paper shows that in the stochastic setting, this degradation is often non-dominant, and the $O(1/N)$ convergence rate is preserved.
  • SSG's Advantage with Complex Regularizers: Numerical results highlight that SSG significantly outperforms SG and AC-SA when the non-smooth component ($h(x)$) leads to projection mappings that are difficult to solve analytically (e.g., hierarchical norm).

Key Results

  • Theoretical Guarantees: Both SG and SSG algorithms are proven to achieve an $O(1/N)$ convergence rate for composite optimization problems with smooth and non-smooth convex functions, even without assuming strong convexity.
  • Numerical Performance:
    • In many cases, SG and SSG are more efficient than the AC-SA algorithm, especially when the stochastic gradient is a good approximation of the true gradient.
  • SSG significantly outperforms SG and AC-SA when the non-smooth term requires a complex projection mapping (e.g., hierarchical norm regularization), as SSG's smoothing approach provides a closed-form solution for its subproblem.
  • The numerical results generally align with the theoretical convergence rates, demonstrating the practical efficiency and scalability of the proposed algorithms.

Limitations and Future Work

  • Parameter Tuning: While the theoretical convergence rates are established, the practical performance of the algorithms can be sensitive to parameter choices (e.g., step lengths, smoothing parameter $\mu$). The paper does not delve deeply into adaptive parameter selection strategies.
  • Strongly Convex Case: The paper focuses on convex objective functions. The authors mention that similar smoothing techniques can be applied to strongly convex objectives, potentially achieving $O(1/N^2)$ rates, which is a direction for future work.
  • Specific Non-Smooth Structures: While the paper addresses general composite optimization and demonstrates SSG's utility for specific structures like hierarchical norms, exploring its effectiveness on a wider range of non-smooth functions and their associated projection complexities could be beneficial.

Summary updated

BibTeX
@article{lin2014smoothing,
  author = {Qihang Lin and Xi Chen and Javier Peña},
  title = {{A smoothing stochastic gradient method for composite optimization}},
  journal = {Optim. Methods Softw.},
  year = {2014},
  doi = {10.1080/10556788.2014.891592},
}
Figure