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
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
m1∑i=1mfi(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
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
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.