Introduction
In mathematical optimization for machine learning, researchers frequently encounter the challenge of minimizing a composite objective function expressed as the sum of three terms: $f(x) + g(x) + h(x)$. Typically, $f$ represents a data-fitting loss, while $g$ and $h$ encode constraints or structural priors, such as sparsity.
The standard algorithmic tool for this problem is Three Operator Splitting (TOS). TOS is highly regarded for its elegance and efficiency, as it only requires evaluating the gradient of $f$ and the proximal operators of $g$ and $h$ once per iteration. However, standard TOS relies on strict assumptions that often fail in modern, "messy" machine learning environments:
- Strict Smoothness: It assumes $f$ is smooth (possesses a continuous gradient). In reality, many loss functions are nonsmooth, meaning only "subgradients" are available.
- Full Gradient Computation: It assumes the ability to compute gradients over the entire dataset, which is computationally prohibitive for large-scale data where stochastic gradients (mini-batches) are necessary.
- Hyperparameter Sensitivity: It requires prior knowledge of the function's "smoothness constant" to set the learning rate. Incorrect guesses can lead to painfully slow convergence or outright failure.
To bridge the gap between theory and practice, recent research extends the TOS framework to handle nonsmooth functions, stochastic gradients, and unknown smoothness, culminating in an adaptive algorithm known as AdapTOS.
Methodological Extensions
The authors propose three critical extensions to the traditional TOS framework to make it viable for real-world applications:
- Nonsmooth TOS: The requirement for a smooth gradient $\nabla f$ is relaxed, allowing the use of subgradients. While this modification breaks the "averaged operator" property usually required for TOS to function, the authors prove that the algorithm still converges at a stable $\mathcal{O}(1/\sqrt{t})$ rate.
- Stochastic TOS: The framework is extended to accommodate noisy, unbiased estimates of the gradient (stochastic gradients). This stochastic variant maintains the same reliable $\mathcal{O}(1/\sqrt{t})$ convergence rate, making it suitable for large-scale machine learning.
- AdapTOS (Adaptive TOS): As the most significant contribution, AdapTOS introduces an adaptive step-size rule inspired by algorithms like AdaGrad. It scales the learning rate based on the history of observed gradients, eliminating the need for manual hyperparameter tuning.
Key Theoretical Insights
The theoretical analysis of these extensions yields several important insights into optimization dynamics:
- Universal Convergence: AdapTOS is "universal" in that it does not need to know a priori whether the optimization problem is smooth or nonsmooth. It automatically achieves an $\mathcal{O}(1/\sqrt{t})$ rate for nonsmooth problems and seamlessly accelerates to a faster $\mathcal{O}(1/t)$ rate if the problem is smooth and the solution is well-behaved.
- Computational Efficiency of Subgradients: For certain complex functions (e.g., the maximum eigenvalue of a matrix), computing a proximal operator requires a full, computationally expensive eigendecomposition. In contrast, computing a subgradient only requires finding the top eigenvector. This work provides the theoretical justification for using cheaper subgradients within the TOS framework.
- Stability in the Wild: Even when the theoretical "niceness" (Fejér monotonicity) of the algorithm is lost due to nonsmoothness, the authors demonstrate that the distance to the optimal solution remains bounded. This critical discovery underpins their new convergence proofs.
Empirical Results
The researchers evaluated their proposed methods across a variety of benchmark problems, including synthetic data (overlapping group lasso, sparse matrix recovery), the Real-sim dataset (large-scale logistic regression), image data (total variation denoising and inpainting), and MNIST (regularized deep neural networks).
Key findings from the experiments include:
- Competitive Performance: In standard convex benchmarks, AdapTOS performed on par with—and sometimes outperformed—variants of TOS and Primal-Dual Hybrid Gradient (PDHG) that rely on expensive "line-search" strategies to find optimal step sizes.
- Superior Sparsity in Neural Networks: When training a neural network with group lasso regularization on MNIST, AdapTOS achieved over 93% weight sparsity and 68% inactive neurons. Standard subgradient methods like Adam or SGD only achieved "approximate" sparsity, demonstrating that the splitting approach is vastly superior at driving redundant parameters exactly to zero.
- Robustness to Noise: In image denoising tasks, the nonsmooth $L_1$-loss version of the algorithm proved significantly more robust to "salt and pepper" noise than the standard $L_2$-loss version, achieving a noticeably higher Peak Signal-to-Noise Ratio (PSNR).
Limitations and Future Directions
While these extensions significantly broaden the applicability of TOS, a few limitations remain for future work:
- The "Interior" Assumption: The accelerated $\mathcal{O}(1/t)$ convergence rate for smooth problems currently requires the optimal solution to lie within the relative interior of the feasible set. The authors suspect this may be an artifact of their proof technique rather than a strict algorithmic limitation.
- Strong Convexity: Although subgradient methods can theoretically achieve an $\mathcal{O}(1/t)$ rate for strongly convex functions, the specific analysis of TOS under strong convexity remains an open problem.
- Generalizing AdapTOS: The current theoretical analysis of AdapTOS focuses on scenarios where $g$ and $h$ act as indicator functions (constraints). Extending this adaptive theory to encompass the most general three-function template is a primary goal for future research.
Summary updated