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. We show that com-SVR-ADMM converges linearly for strongly convex and Lipschitz smooth objectives, and has a convergence rate of $O(\log S/S)$ when the objective is convex and Lipschitz smooth—improving upon the previous $O(S^{-4/9})$ state-of-the-art rate. Moreover, com-SVR-ADMM possesses a rate of $O(1/\sqrt{S})$ when the objective is convex but without Lipschitz smoothness. Empirical results demonstrate that our method outperforms existing algorithms.
Introduction
Stochastic Composition Optimization (SCO) involves minimizing nested functions of the form $f(g(x))$, where both $f$ and $g$ are expectations over random variables. This structure is prevalent in fields such as portfolio management and reinforcement learning. A significant challenge in SCO is that standard Stochastic Gradient Descent (SGD) produces biased gradient estimates unless the inner function $g(x)$ is computed exactly, which is often computationally prohibitive. Furthermore, many practical problems require handling linear constraints and non-smooth regularizers, which previous SCO solvers did not address efficiently.
Methodology
The proposed com-SVR-ADMM (Compositional Stochastic Variance Reduced ADMM) integrates three key components to overcome these hurdles:
- ADMM Framework: Used to handle linear constraints ($Ax + B\omega = 0$) and non-smooth regularizers by decomposing the problem into smaller, solvable subproblems.
- Stochastic Variance Reduced Gradient (SVRG): A technique that periodically calculates a full gradient at a reference point to reduce the variance of noisy gradients in the inner loops, enabling faster convergence.
- Biased Gradient Estimator: To handle the nested structure, the algorithm uses a specific estimator for the inner function $g(x)$ and its Jacobian, keeping the gradient bias under control without needing full evaluations at every step.
Experimental Evaluation
The authors evaluated com-SVR-ADMM on two standard scenarios: Portfolio Management (mean-variance minimization) and Reinforcement Learning (minimizing Bellman residuals). The algorithm was compared against SGD and existing SVRG-based composition solvers (com-SVRG-1 and com-SVRG-2).
As illustrated in the figures, com-SVR-ADMM reaches the optimal value significantly faster than competing methods in terms of both CPU time and the number of oracle calls. This efficiency is particularly notable in its ability to manage linear constraints while maintaining high convergence speeds.
Key Insights and Conclusion
The primary contribution of this work is the realization that while gradient estimates in SCO are inherently biased, a variance-reduction framework can make that bias vanish fast enough to achieve linear convergence in the strongly convex case. For general convex objectives, the method provides a significant jump in convergence rates over previous benchmarks and offers the first theoretical guarantees for non-smooth stochastic composite optimization.
While the algorithm is robust, future work may focus on mitigating the computational cost of proximal updates involving large matrix inversions and extending these fast rates to non-convex stochastic composition problems.
Summary updated