Improving optimization when only limited function samples are accessible
Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator
Machine Learning
Summary
Some optimization problems need to calculate many related functions at once, but only a few can be checked at each step. The authors address this by making a new method to estimate and update these multiple function values more efficiently. This helps solve complex problems where functions are combined in layers and only partial data is available each time. They show their approach improves speed and accuracy in training models that handle multiple tasks simultaneously.
What this means in practice
- •For machine learning engineers: Train multi-task models more efficiently by improving estimation of layered function values when only few samples are available each iteration.
- •For data scientists: Optimize metrics that depend on several nested functions of data, such as AUC in multi-task settings, with better sample usage and convergence.
Authors
Wei Jiang, Sifan Yang, Yibo Wang, Lijun Zhang, Zechao Li
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 $\mathcal{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 $\frac{1}{m}\sum_{i=1}^m f_i(g_i(\mathbf{w}))$, where each $g_i$ is accessible only through a stochastic oracle. The key challenge is to track $\mathbf g(\mathbf{w})=(g_1(\mathbf{w}), \ldots, g_m(\mathbf{w}))$ over time, where $\mathbf g(\mathbf{w})$ has $m$ blocks but only $\mathcal{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(\mathbf{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 $\nabla f_i$ are linear. Empirical studies on multi-task deep AUC maximization further demonstrate the superior performance of the proposed estimators.