Multistage Conditional Compositional Optimization

Buse Şen; Yifan Hu; Daniel Kuhn

math.OCApr 15, 2026

Multistage Conditional Compositional Optimization

Authors: Buse Şen, Yifan Hu, Daniel Kuhn

Organizations: EPFL, Switzerland · Rutgers University, USA

Abstract

We introduce Multistage Conditional Compositional Optimization (MCCO) as a new paradigm for decision-making under uncertainty that combines aspects of multistage stochastic programming and conditional stochastic optimization. MCCO minimizes a nest of conditional expectations and nonlinear cost functions. It has numerous applications and arises, for example, in optimal stopping, linear-quadratic regulator problems, distributionally robust contextual bandits, as well as in problems involving dynamic risk measures. The naïve nested sampling approach for MCCO suffers from the curse of dimensionality familiar from scenario tree-based multistage stochastic programming, that is, its scenario complexity grows exponentially with the number of nests. We develop new multilevel Monte Carlo techniques for MCCO whose scenario complexity grows only polynomially with the desired accuracy.

Figures & tables

Panel of Figure 1 — Figure 1: Visualization of the $i_{1}$ -th scenario tree underlying the SAA estimator when $T=3$ .

Panel of Figure 2 — Figure 2: Left panel: dependence of the untruncated and truncated MLMC estimators on $n_{1}$ . Right panel: trade-off between the mean squared error and the total sampling cost of all MLMC and SAA estimators. Each marker corresponds to an average of $10$ independent estimators of the same type for a fixed $n_{1}$ .

$M_{t}$	$r_{t}$	Cost per tree	Estimate (se)	Confidence interval
9	0.5900	$22.6084$	$2.1684(0.0076)$	$[2.1536,2.1832]$
10	0.5800	$29.5795$	$2.1562(0.0072)$	$[2.1421,2.1703]$
11	0.5900	$26.3283$	$2.1641(0.0080)$	$[2.1485,2.1797]$
$\infty$	0.5001	$1.5634\times 10^{10}$	$2.1547(0.0073)$	$[2.1403,2.1690]$
$\infty$	0.6000	$27.0000$	$2.1589(-)$	$-$

Table 1: MLMC estimators for pricing Bermudan basket options: expected costs per tree, estimated option prices with standard errors (se) and

95\%

confidence intervals for different truncation points and rates.

Figure 3: Convergence of the decision variables $\lambda$ (left), $\theta_{1}$ (middle), and $\theta_{2}$ (right) generated by Adam. Results show mean trajectories with 95% confidence intervals based on 20 independent simulation runs.

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 210 papers

Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization
Jul 28, 2026Zhaojun PengStochastic Optimization Nonconvex Stochastic Optimization
School of Computer Science Nanjing University of Information Science and Technology
Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization
Oct 1, 2026Wei Jiang, Rui Yan, Sifan Yang +3Stochastic Optimization Momentum Methods
School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China · School of Software Technology, Zhejiang University, Ningbo, China
Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator
Sep 14, 2026Wei Jiang, Sifan Yang, Yibo Wang +2Stochastic Optimization Variance Reduction
School of Computer Science and Engineering, Nanjing University of Science and Technology, China · 2State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

Jul 28, 2026J/K move · Enter open · S save

Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

Zhaojun Peng

School of Computer Science Nanjing University of Information Science and Technology

Stochastic Optimization Nonconvex Stochastic Optimization Nonconvex Optimization Stochastic Optimization Convergence Variance Reduction

Open paper AskPDF arXiv

We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias

O(τ_{\mathrm{mix}}/T)

uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under

σ^2\mapsto 2ΛG_σ^2

and

L^2\mapsto 2ΛL^2

, where

Λ=O(τ_{\mathrm{mix}}\log T)

. For positive centered noise, the tuned method achieves expected sample complexity

\widetilde{O}((τ_{\mathrm{mix}}^2G_σ+τ_{\mathrm{mix}}^{5/2}G_σ^2)\varepsilon^{-3}+τ_{\mathrm{mix}}^5\varepsilon^{-2})

. The exactly noiseless specialization achieves

\widetilde{O}(\varepsilon^{-2})

with mixing-time-free constants, while a mixing-time-oblivious variant achieves

\widetilde{O}(τ_{\mathrm{mix}}^6\varepsilon^{-3}+τ_{\mathrm{mix}}^3\varepsilon^{-2})

. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.

Abstract

Stochastic Optimization

Explore similar work

Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization

Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator