Abstract
We consider the stochastic composition optimization problem, which has applications ranging from estimation to statistical and machine learning. We propose the first ADMM-based algorithm named com-SVR-ADMM, and show that com-SVR-ADMM converges linearly for strongly convex and Lipschitz smooth objectives, and has a convergence rate of $O( \log S/S)$, which improves upon the $O(S^{-4/9})$ rate in previous work when the objective is convex and Lipschitz smooth. Moreover, com-SVR-ADMM possesses a rate of $O(1/\sqrt{S})$ when the objective is convex but without Lipschitz smoothness. We also conduct experiments and show that it outperforms existing algorithms.
Introduction
Stochastic composition optimization addresses problems where the objective function is a composition of two expected values: $\min_x \mathbb{E}[f(\mathbb{E}[g(x)])]$. This formulation is critical for various applications, including risk-averse learning—where one minimizes both the mean and variance of a loss—and reinforcement learning, specifically in minimizing Bellman residuals.
Despite its utility, existing algorithms often struggle with complex linear constraints or non-smooth regularizers, such as the L1 penalty for sparsity. While the Alternating Direction Method of Multipliers (ADMM) is a standard tool for constrained optimization, its integration with variance-reduced stochastic composition methods has remained unexplored until now.
The com-SVR-ADMM Algorithm
We introduce com-SVR-ADMM (Compositional Stochastic Variance Reduced ADMM), the first algorithm to combine ADMM with variance reduction for stochastic composition problems. The algorithm leverages two core components:
- ADMM: To decompose constrained optimization into manageable sub-problems.
- SVRG (Stochastic Variance Reduced Gradient): To mitigate the noise of stochastic gradients by periodically computing full gradients.
A significant challenge in this setting is the bias introduced by the composite nature of the objective function. Standard SVRG cannot be directly applied. Our approach utilizes a novel gradient estimator designed to correct this bias. The algorithm employs a double-loop structure: the outer loop computes a snapshot of the inner function $g(x)$, while the inner loop performs computationally efficient stochastic updates and adjusts ADMM dual variables to satisfy constraints.
Theoretical Contributions
The paper provides rigorous convergence guarantees for com-SVR-ADMM across different objective types:
- Strongly Convex and Lipschitz Smooth: Achieves a linear convergence rate.
- Convex and Lipschitz Smooth: Achieves a rate of $O(\log S / S)$, significantly improving upon the previous state-of-the-art $O(S^{-4/9})$.
- General Convex (Non-Smooth): Provides the first-ever convergence guarantee of $O(1/\sqrt{S})$ for stochastic composition optimization without assuming Lipschitz smoothness. This is particularly relevant for problems employing sharp regularizers.
Experimental Evaluation
We evaluated com-SVR-ADMM against standard Stochastic Gradient Descent (SGD) and two recent benchmarks, com-SVRG-1 and com-SVRG-2, using simulated datasets for portfolio management and reinforcement learning.
Portfolio Management
The portfolio management task involved mean-variance optimization for $N=200$ assets over $n=2000$ time slots. As shown in Figure 1, com-SVR-ADMM demonstrates superior efficiency, reaching the optimal objective value with fewer oracle calls and less CPU time than competing methods.
Reinforcement Learning
In on-policy learning experiments using a simulated Markov Decision Process (MDP) with $S=200$ states, com-SVR-ADMM consistently outperformed benchmarks across different feature dimensions ($d=100$ and $d=200$), confirming its robustness and speed.
Conclusion
com-SVR-ADMM represents a significant advancement in stochastic composition optimization, offering the first ADMM-based framework with variance reduction. By taming composition bias and providing superior convergence rates for both smooth and non-smooth convex problems, it sets a new standard for constrained stochastic optimization. Future work may explore extending these guarantees to non-convex objectives common in deep learning.
Summary updated