Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization
Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization
复制标题
DOI：
10.48550/arxiv.2207.08540
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Wei Jiang;Gang Li;Yibo Wang-;Lijun Zhang;Tianbao Yang
中科院分区：
文献类型：
--
作者：
Wei Jiang;Gang Li;Yibo Wang-;Lijun Zhang;Tianbao Yang
诸如 SPIDER/SARAH/STORM 之类的方差减少技术已被广泛研究，以提高随机非凸优化的收敛速度，这些优化通常在迭代中维护和更新单个函数的估计器序列。如果我们需要跨迭代跟踪多个函数映射，但只能在每次迭代时访问 $\mathcal{O}(1)$ 函数映射的随机样本，该怎么办？在解决 $\sum_{i=1}^m f_i(g_i(\mathbf{w}))$ 形式的新兴耦合组合优化问题方面有一个重要的应用，其中 $g_i$ 可以通过随机预言机访问。关键问题是在迭代中跟踪和估计 $\mathbf g(\mathbf{w})=(g_1(\mathbf{w}), \ldots, g_m(\mathbf{w}))$ 的序列，其中 $\mathbf g(\mathbf{w})$ 有 $m$ 个块，并且只允许探测 $\mathcal{O}(1)$ 块以获得它们的值随机值和雅可比行列式。为了提高解决这些问题的复杂性，我们提出了一种名为多块单探针方差减少（MSVR）估计器的新颖随机方法来跟踪 $\mathbf g(\mathbf{w})$ 的序列。它受到 STORM 的启发，但引入了定制的纠错项，不仅可以减轻所选块的随机样本中的噪声，还可以减轻那些未采样的块中的噪声。在 MSVR 估计器的帮助下，我们开发了几种算法来解决上述组合问题，并在具有非凸/凸/强凸/Polyak-{\L}ojasiewicz (PL) 目标的一系列设置中提高了复杂性。我们的结果在几个方面优于先前的结果，包括样本复杂性的顺序和对强凸性参数的依赖性。对多任务深度 AUC 最大化的实证研究证明了使用新估计器的更好性能。
Variance reduction techniques such as SPIDER/SARAH/STORM have been extensively studied to improve the convergence rates of stochastic non-convex optimization, which usually maintain and update a sequence of estimators for a single function across iterations. What if we need to track multiple functional mappings across iterations but only with access to stochastic samples of $\mathcal{O}(1)$ functional mappings at each iteration? There is an important application in solving an emerging family of coupled compositional optimization problems in the form of $\sum_{i=1}^m f_i(g_i(\mathbf{w}))$, where $g_i$ is accessible through a stochastic oracle. The key issue is to track and estimate a sequence of $\mathbf g(\mathbf{w})=(g_1(\mathbf{w}), \ldots, g_m(\mathbf{w}))$ across iterations, where $\mathbf g(\mathbf{w})$ has $m$ blocks and it is only allowed to probe $\mathcal{O}(1)$ blocks to attain their stochastic values and Jacobians. To improve the complexity for solving these problems, we propose a novel stochastic method named Multi-block-Single-probe Variance Reduced (MSVR) estimator to track the sequence of $\mathbf g(\mathbf{w})$. It is inspired by STORM but introduces a customized error correction term to alleviate the noise not only in stochastic samples for the selected blocks but also in those blocks that are not sampled. With the help of the MSVR estimator, we develop several algorithms for solving the aforementioned compositional problems with improved complexities across a spectrum of settings with non-convex/convex/strongly convex/Polyak-{\L}ojasiewicz (PL) objectives. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on the strong convexity parameter. Empirical studies on multi-task deep AUC maximization demonstrate the better performance of using the new estimator.