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