Source-linked AI summary
Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions
Mengdi Wang, Ethan X. Fang, Han Liu
TL;DR
The paper addresses stochastic optimization of compositions of expected-value functions, for which classical SGD does not directly apply. It develops two-timescale SCGD algorithms using noisy inner and outer evaluations, with convergence guarantees and improved smooth-case rates. The resulting benchmarks suggest sub-quadratic sample requirements despite nested expectations.
Problem
Classical SGD does not directly apply when the objective is nonlinear in sampling probabilities, including compositions of two expected-value functions.
Method
SCGD combines noisy gradient evaluations with an auxiliary running estimate of the inner expected value through two iterations on different timescales.
Results
SCGD converges almost surely to an optimum for convex problems, reaches improved rates in smooth settings, and yields sub-quadratic sample-complexity benchmarks.
Takeaways & Limitations
The proposed methods extend stochastic gradient-like optimization to compositional problems arising in learning, dynamic programming, risk management, and related applications.
Takeaways & Limitations
The analysis assumes an existing optimum and a convex closed feasible set; the main convex results require a convex composition, although the component functions need not be convex or monotone.
Abstract
from arXiv · showhide
Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., problems of the form $\min_x \mathbf{E}_v [f_v\big(\mathbf{E}_w [g_w(x)]\big)]$. In order to solve this stochastic composition problem, we propose a class of stochastic compositional gradient descent (SCGD) algorithms that can be viewed as stochastic versions of quasi-gradient method. SCGD update the solutions based on noisy sample gradients of $f_v,g_{w}$ and use an auxiliary variable to track the unknown quantity $\mathbf{E}_w[g_w(x)]$. We prove that the SCGD converge almost surely to an optimal solution for convex optimization problems, as long as such a solution exists. The convergence involves the interplay of two iterations with different time scales. For nonsmooth convex problems, the SCGD achieve a convergence rate of $O(k^{-1/4})$ in the general case and $O(k^{-2/3})$ in the strongly convex case, after taking $k$ samples. For smooth convex problems, the SCGD can be accelerated to converge at a rate of $O(k^{-2/7})$ in the general case and $O(k^{-4/5})$ in the strongly convex case. For nonconvex problems, we prove that any limit point generated by SCGD is a stationary point, for which we also provide the convergence rate analysis. Indeed, the stochastic setting where one wants to optimize compositions of expected-value functions is very common in practice. The proposed SCGD methods find wide applications in learning, estimation, dynamic programming, etc.
1 Introduction
The paper studies stochastic optimization of compositions of expected-value functions, where classical SGD is hindered by nonlinear sampling dependence and unavailable composition gradients. It proposes SCGD methods with two-timescale updates and analyzes their convergence, sample complexity, and applications.
- Problem: Classical SGD relies on unbiased sampled gradients and does not directly address objectives that are nonlinear in sampling probabilities.The paper identifies loss of linearity in sampling probabilities as the central difficulty for compositional stochastic optimization.
- Setting: The paper assumes a convex closed feasible set and an existing optimum, while requiring only continuous differentiability of the outer function and allowing a nonsmooth inner function.Neither the outer nor inner function must be convex or monotone, although the composition is mainly analyzed when convex.
- Motivation: The composition problem is ubiquitous in risk management, two-stage optimization, statistical learning, dynamic programming, and estimation.Examples include risk-averse optimization with expected payoff and deviation risk, and two-stage decisions under random information.
- Results: The sample-complexity benchmarks suggest that sufficiently small optimization error requires only a sub-quadratic number of samples despite two nested expectation levels.The analysis is presented as an initial benchmark for the stochastic composition problem and is compared with expectation minimization.
- Method: SCGD uses noisy queries and two iterations: one updates the solution and the other maintains a running estimate of the inner expected value.This quasi-gradient design targets low computational cost, small memory overhead, and online execution without storing past query responses.
- Theory: The basic SCGD receives convergence and rate analyses for convex, strongly convex, and nonconvex problems, while accelerated SCGD improves rates for smooth optimization.The accelerated method adds an extrapolation step before noisy function evaluation to reduce estimation bias using gradient continuity.
A Basic Algorithm
Basic SCGD alternates stochastic quasi-gradient updates with iterative tracking of the unknown inner expectation, using two coupled stepsizes. Under the stated assumptions, it converges almost surely to optimal solutions in convex settings and to stationary points in smooth nonconvex settings, with rates depending on curvature.
- Algorithm: Basic SCGD alternates stochastic quasi-gradient updates for x_k with iterative weighted averaging to estimate g(x_k).The method uses noisy samples of g and its generalized gradient, together with noisy outer-function gradients.
- Assumptions: The analysis allows F = f ◦ g to be convex without requiring f or g individually to be convex or monotone, while permitting g to be nonsmooth.It assumes f is continuously differentiable and imposes continuity, Lipschitz, sampling, and moment conditions on the functions and samples.
- Algorithm: Two different stepsizes control the coupled processes estimating x* and g(x*), enabling almost-sure convergence at favorable rates.The tracking variable and solution iterate are analyzed as entangled stochastic processes.
- Convergence: Under convexity and an existing optimum, basic SCGD converges almost surely to an optimal solution; with Lipschitz gradient, every limit point is stationary in the nonconvex setting.The convex guarantee is stated for the constrained problem, while the stationary-point guarantee assumes X = ℜn.
- Rates: O(k^-1/4) is the convex error rate, while O(k^-2/3) is the strongly convex rate after k queries to the stochastic oracle.The rates concern averaged iterates and show faster convergence in the strongly convex case.
- Rates: For nonconvex objectives, basic SCGD is not guaranteed to find a global optimum but drives the nonstationary metric toward zero and yields stationary limit points.The rate analysis uses a gradient-based stationarity measure.
3 Acceleration for Smooth Convex Optimization
Accelerated SCGD targets smooth stochastic compositions by extrapolating query points so an auxiliary estimate tracks the unknown inner expectation more accurately. Under stated assumptions, it converges almost surely for convex problems and improves convergence rates over basic SCGD.
- Accelerated SCGD is designed for differentiable compositions of expected-value functions, where smoothness can improve the basic method’s rates.The accelerated method is contrasted with basic SCGD, which permits nondifferentiable inner samples.
- The algorithm queries noisy gradients at xk and yk, then evaluates g at the extrapolated point zk+1.The variables xk and zk lie in the decision space, while yk tracks the inner expected value.
- Extrapolation makes xk+1 an interpolated point and reduces bias in the auxiliary estimate by exploiting gradient continuity.The accelerated estimate uses weighted samples evaluated at extrapolated points.
- The auxiliary estimate yk tracks g(xk) at a faster rate, producing accelerated error complexities for general and strongly convex problems.The supplied theorem passages state these rates symbolically but do not include the exponent values in the extracted text.
- The accelerated method improves on the basic SCGD’s O(k^-1/4) error bound for general convex problems.The paper attributes acceleration to the extrapolation step rather than deterministic accelerated stochastic approximation.
Remarks on Sample Error Complexity
The paper leaves open whether SCGD’s sample error complexities can be improved. Its rates remain below the optimal known rates for classical expectation minimization, although the composition problem is more general.
- Whether SCGD’s sample error complexity for compositions of expected-value functions is improvable remains an open issue.The authors identify lower-bound analysis as an important direction for future work.
- The composition problem contains classical expectation minimization as a special case and is conjectured to be intrinsically harder.The paper proposes sample-complexity lower bounds to test whether current rates are non-improvable.
4 Applications and Extensions
SCGD is presented as a general approach for stochastic compositions, with applications spanning learning, minimax optimization, dynamic programming, tail-probability estimation, and derivative-free optimization.
- Optimization of expected-value compositions is framed as a generic model of real-world decision-making problems.The paper collects multiple application instances to demonstrate SCGD’s potential scope.
- Statistical learning: In sparse additive modeling, SCGD estimates nonlinear feature functions for SpAM, addressing the lack of a provably convergent stochastic algorithm for its convex formulation.SpAM imposes sparsity by assuming most feature functions are zero.
- Minimax optimization: SCGD can solve smoothed stochastic minimax problems by treating the max operator as the outer function after differentiable approximation.The underlying minimax formulation may involve two stages of stochasticity.
- Dynamic programming: For dynamic programming, SCGD updates Bellman residual minimization online from simulated state transitions without knowing transition probabilities.The method can operate directly on simulation trajectories and produce estimates of optimal policies.
- Rate-function estimation: SCGD can estimate a random variable’s rate function from random realizations because the resulting optimization is nonlinear in an expected-value function.The paper suggests combining the algorithm with adaptive Monte Carlo sampling to sharpen estimator sample complexity.
- Derivative-free optimization: Derivative-free SCGD replaces unavailable inner gradients with Kiefer–Wolfowitz-style approximations, but introduces bias and stepsize-coupling requirements.The paper identifies complexity analysis and applications of these variants as open questions.
5 Numerical Results
Numerical experiments apply SCGD to sparse additive modeling and stochastic shortest paths. The reported figures compare estimates with true or optimal solutions and show faster convergence for accelerated SCGD.
- The experiments evaluate SCGD on two problems: sparse additive modeling and stochastic shortest paths.The methods are tested using basic and accelerated variants.
- Sparse additive model: Figure 1 compares the four estimated SpAM feature functions with their true counterparts using random input-response samples.Computed functions are shown as purple solid lines and true functions as blue dotted lines.
- Sparse additive model: Figure 2 plots empirical convergence rates against iteration count and reports faster convergence for accelerated SCGD than basic SCGD.The plotted error uses the distance between ηk and the estimated optimal solution η∗.
- Stochastic shortest path: In the shortest-path experiment, actions a1 and a2 induce different random movements among adjacent nodes with associated transition costs.The objective is to minimize expected path length from node A to node B.
- Stochastic shortest path: Figure 4 encodes the SCGD decision rule with white nodes selecting a1, grey nodes selecting a2, and colored arcs representing action-specific transitions.The reported decision rule coincides with the optimal cost vector obtained by value iteration.
- Stochastic shortest path: Figure 5 shows both basic and accelerated SCGD converging to the optimal solution, with accelerated SCGD converging faster.It plots log(∥Jk − J∗∥2) against log(k).
6 Conclusions
The paper develops stochastic compositional gradient methods for minimizing compositions of two expected-value functions, where classical stochastic gradients do not apply. It analyzes their convergence and sample complexity while identifying open directions for improving complexity and extending beyond two stochastic compositions.
- SCGD methods address optimization problems with two levels of stochasticity, where classical stochastic gradients no longer apply.The methods use random gradient evaluations of the inner and outer functions.
- The paper provides comprehensive convergence and convergence-rate analyses for the proposed SCGD algorithms.Table 1 summarizes the convergence rate and sample error complexity results.
- Future work includes determining whether current sample complexity can be improved and extending the approach to more than two stochastic functions.