Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator
Abstract
Traditional variance reduction methods (e.g., SPIDER, SARAH, STORM) have been extensively investigated for improving the convergence rates of stochastic optimization. These techniques typically maintain a sequence of estimators for a single function (or gradient) across iterations. However, what if we need to track multiple functions, but can only access stochastic samples of 𝒪(1) functions at each iteration? This scenario arises in an important emerging family of finite-sum coupled compositional optimization (FCCO) problems of the form 1/m∑i=1m fi(gi(w)), where each gi is accessible only through a stochastic oracle. The key challenge is to track g(w)=(g1(w), …, gm(w)) over time, where g(w) has m blocks but only 𝒪(1) blocks can be probed for their stochastic values at each step. To address this challenge, we propose a novel Multi-block-Single-probe Variance Reduction (MSVR) estimator to efficiently trace g(w) under partial block sampling. Building on the MSVR estimator, we develop several algorithms for FCCO problems, achieving improved sample complexities for non-convex, convex, strongly convex, and Polyak-Łojasiewicz (PL) objectives. We further obtain an improved dependence on m when the outer function gradients ∇ fi are linear. Empirical studies on multi-task deep AUC maximization further demonstrate the superior performance of the proposed estimators.
Related
- Nonparametric Correlation Estimator via Solving Cubic Equations and its Application to Brain Functional Connectivity Analysis
- Finite sample behavior of the maximum likelihood estimator in the Poisson model under Gaussian design
- Development of an efficient neutrosophic estimator for finite population mean using Monte Carlo simulation and multi-domain data
- Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe
- Solving polynomials in large pseudo-finite sets
BibTeX
@misc{jiang2026solving,
title = {{Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator}},
author = {Wei Jiang and Sifan Yang and Yibo Wang and Lijun Zhang and Zechao Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15723},
eprint = {2609.15723},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15723},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator
AU - Wei Jiang
AU - Sifan Yang
AU - Yibo Wang
AU - Lijun Zhang
AU - Zechao Li
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15723
UR - https://arxiv.org/abs/2609.15723
AB - Traditional variance reduction methods (e.g., SPIDER, SARAH, STORM) have been extensively investigated for improving the convergence rates of stochastic optimization. These techniques typically maintain a sequence of estimators for a single function (or gradient) across iterations. However, what if we need to track multiple functions, but can only access stochastic samples of 𝒪(1) functions at each iteration? This scenario arises in an important emerging family of finite-sum coupled compositional optimization (FCCO) problems of the form 1/m∑_i=1^m f_i(g_i(w)), where each g_i is accessible only through a stochastic oracle. The key challenge is to track g(w)=(g_1(w), …, g_m(w)) over time, where g(w) has m blocks but only 𝒪(1) blocks can be probed for their stochastic values at each step. To address this challenge, we propose a novel Multi-block-Single-probe Variance Reduction (MSVR) estimator to efficiently trace g(w) under partial block sampling. Building on the MSVR estimator, we develop several algorithms for FCCO problems, achieving improved sample complexities for non-convex, convex, strongly convex, and Polyak-Łojasiewicz (PL) objectives. We further obtain an improved dependence on m when the outer function gradients ∇ f_i are linear. Empirical studies on multi-task deep AUC maximization further demonstrate the superior performance of the proposed estimators.
ER -