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

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 O(1) functions at each iteration? This scenario arises in an important emerging family of finite-sum coupled compositional optimization (FCCO) problems of the form frac1msumi=1m fi(gi(w)), where each gi is accessible only through a stochastic oracle. The key challenge is to track mathbf g(w)=(g1(w), ldots, gm(w)) over time, where mathbf g(w) has m blocks but only O(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 mathbf 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-Lojasiewicz (PL) objectives. We further obtain an improved dependence on m when the outer function gradients nabla fi are linear. Empirical studies on multi-task deep AUC maximization further demonstrate the superior performance of the proposed estimators.