Abstract
Three Operator Splitting (TOS) is a versatile framework for minimizing the sum of multiple convex functions. However, its standard formulation requires full gradients for smooth terms and proximal operators for nonsmooth terms—requirements that are often impractical in large-scale machine learning. This paper introduces three extensions to TOS: Nonsmooth TOS, Stochastic TOS, and AdapTOS. These extensions allow for the use of subgradients and stochastic gradients while maintaining a $\mathcal{O}(1/\sqrt{t})$ convergence rate. Notably, AdapTOS incorporates adaptive step-sizes to achieve universal convergence, automatically accelerating to $\mathcal{O}(1/t)$ for smooth objectives without prior knowledge of the smoothness parameters. Empirical results across image recovery, portfolio optimization, and sparse neural network training demonstrate the robustness and efficiency of these methods.
Introduction
Optimization problems in modern machine learning frequently involve the minimization of a composite objective function, typically expressed as the sum of a loss function and multiple regularization terms. The Three Operator Splitting (TOS) algorithm, introduced by Davis & Yin (2017), provides a powerful mechanism for solving such problems when each term can be handled via a gradient oracle or a proximal operator.
Despite its theoretical elegance, standard TOS faces significant hurdles in practice. First, computing proximal operators for complex constraints can be as difficult as the original optimization problem. Second, in high-dimensional settings, calculating full gradients is often computationally prohibitive, necessitating the use of stochastic mini-batches. Finally, the performance of TOS is highly sensitive to the choice of step-size, which usually requires knowledge of the Lipschitz constant—a value rarely known in advance. This work addresses these gaps by extending TOS to accommodate subgradients, stochastic gradients, and adaptive learning rates.
Methodology
1. Nonsmooth and Stochastic TOS
The first two extensions relax the requirement for a smooth gradient.
- Nonsmooth TOS: By replacing the traditional gradient step with a subgradient step, the authors enable the algorithm to handle functions where the proximal operator is unavailable but a subgradient is easily computed (e.g., the maximum eigenvalue of a matrix). The authors prove that even without the "averagedness" property typically required for TOS convergence, the iterates remain bounded, ensuring a convergence rate of $\mathcal{O}(1/\sqrt{t})$.
- Stochastic TOS: This version adapts the framework for unbiased stochastic gradients with bounded variance. This is critical for scaling TOS to large datasets where only mini-batch gradients are accessible. It maintains the same $\mathcal{O}(1/\sqrt{t})$ convergence guarantee as the nonsmooth variant.
2. AdapTOS: Adaptive Step-Sizes
The most significant contribution is AdapTOS, which integrates an AdaGrad-inspired adaptive step-size rule: $$\gamma_t = \frac{\alpha}{\sqrt{\beta + \sum_{\tau=1}^t \|u_\tau\|^2}}$$ This mechanism allows the algorithm to be "universal." If the objective is nonsmooth, AdapTOS converges at the standard $\mathcal{O}(1/\sqrt{t})$ rate. However, if the problem is smooth and the solution is well-behaved (specifically, if it lies in the relative interior of the feasible set), the algorithm automatically accelerates to a $\mathcal{O}(1/t)$ rate. This eliminates the need for manual hyperparameter tuning of the learning rate based on unknown smoothness constants.
Empirical Evaluation
The proposed methods were evaluated against a variety of benchmarks and real-world datasets:
- High-Dimensional Regression: Using Real-sim and RCV1 datasets, the authors demonstrated the efficiency of stochastic variants in logistic regression tasks.
- Image and Matrix Recovery: Using the COPT library, the researchers showed that Nonsmooth TOS could natively handle $L_1$ loss functions for image denoising. This approach proved significantly more robust to "salt and pepper" noise compared to standard $L_2$-based methods.
- Sparse Neural Networks: On the MNIST dataset, AdapTOS was used to train neural networks with group lasso regularization. Unlike standard subgradient methods (like SGD or Adam) that produce only approximately sparse weights, the proximal nature of AdapTOS yielded precisely sparse models. The resulting networks achieved over 93% weight sparsity and 68% neuron inactivity while maintaining higher accuracy than state-of-the-art optimizers.
- Financial Engineering: The methods were also validated on portfolio optimization tasks using data from the DJIA, NYSE, S&P 500, and TSE.
Key Insights
- Computational Efficiency: For many complex penalty functions, computing a subgradient is significantly cheaper than computing a proximal operator. By supporting subgradients, TOS becomes applicable to a much wider class of problems.
- Theoretical Robustness: A key theoretical breakthrough in this work is the proof of iterate boundedness in the absence of averagedness, which provides the foundation for the nonsmooth convergence analysis.
- Precision in Sparsity: The hybrid nature of TOS—combining gradient-like steps with proximal steps—allows it to find exact zeros in regularized problems, a feat that purely gradient-based methods struggle to achieve without post-processing.
Conclusion and Future Work
This work significantly expands the applicability of Three Operator Splitting to the "messy" realities of machine learning. AdapTOS, in particular, offers a robust, parameter-free approach to complex convex optimization.
Future research directions include extending the theoretical analysis to strongly convex nonsmooth functions to potentially achieve faster rates. Additionally, while AdapTOS showed empirical success in training neural networks, a rigorous theoretical framework for its performance in nonconvex settings remains an open challenge. Finally, the authors aim to investigate whether the requirement for the solution to lie in the relative interior for acceleration can be relaxed through more advanced proof techniques.
Summary updated