Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a novel stochastic method named Multi-block-Single-probe Variance Reduced (MSVR) estimator to track multiple functional mappings across iterations. Based on MSVR, the authors develop several algorithms for solving the finite-sum coupled compositional optimization (FCCO) problem. Theoretical analysis shows that the proposed algorithms obtain optimal complexities across a spectrum of settings.  Experiment results on multi-task deep AUC maximization to demonstrate the advantage of the proposed algorithms.
strengths_and_weaknesses: Strengths:

1. The FCCO problem has a broad spectrum of applications in machine learning and may have a high impact in this area. The proposed algorithms have a major improvement in complexities.  

2. The proposed MSVR estimator is novel and quite efficient. It successfully reduces the tracking error with only a constant number of stochastic accesses to functional mappings at each iteration. 

3. The sample complexities are much better than existing works, and optimal in many cases. The experimental results are also convincing.

Weaknesses:
1. Besides multi-task deep AUC maximization, more experiments on others problems could be added to evaluate the proposed algorithms.

2. The MSVR estimator seems incremental with respect to STORM, although the parameter is set in a different way.

questions: 1. In Theorem 3, the authors obtain better sample complexities under the $\mu$-PL condition. When considering the $\mu$-PL condition, do we need the convexity condition?

2. There seems an inconsistency in the writing. The authors introduce the concept of PL condition on Page 7, but use strong convexity in other places.

2. The sample complexities in Table 1 increase with $B_2$. It seems that we should use a small value of $B_2$. Is there any benefit of using a large $B_2$? 

limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers a scheme in coupled compositional optimization where oracles of inner functions are only available at $\mathcal{O}(1)$ blocks of functions each time. The paper proposes a new estimator called MSVR for inner function values leveraging the idea of variance reduction techniques such as STORM and SVRG. The authors establish the convergence rates of proposed algorithms in the (non)-convex and PL setting. Experimental results on the multi-task deep AUC maximization demonstrate their effectiveness and superiority over SOX - the algorithm proposed previously for solving this problem.

strengths_and_weaknesses: **Strength**: The paper is well-organized and well-written. They leverage the idea of the STORM estimator [1] to obtain better convergence rates compared to [2]. All the results are clearly stated and the proof (although I didn’t check carefully for convex and PL objectives) is sound and consistent with existing literature.

**Weaknesses**: On the theoretical side, the considered problem and proposed algorithms in this paper can be viewed as variance-reduced block coordinate update methods in stochastic compositional optimation. I partially doubt the novelty of this paper though I did not find any related work in this regime. From the practical point of view, the paper needs more experimental results to support the effectiveness and superiority of the proposed algorithm; see comments below.

Reference:

[1] A. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems 32, pages 15210–15219, 2019.

[2] B. Wang and T. Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. ArXiv e-prints, arXiv:2202.12396, 2022.

questions: As stated above I have two **major** questions for this paper: 

1. For the Coupled Compositional Optimization (CCO) problem considered, one can treat it as a general compositional optimization problem where a unified outer function $f$ can be defined to operate on $[g_1, g_2, \dots, g_m]$. Moreover, since the outer function considered $f$ is deterministic, one can think of this problem from the perspective of block coordinate updates. It would be much more clear if the authors can elaborate more on their contributions and distinguish them from other existing works on variance reduction and block coordinate updates.

2. The experiments results presented fail to capture the differences between sample complexities of SOX ($\mathcal{O}(\epsilon^{-4})$) and MSVR ($\mathcal{O}(\epsilon^{-2})$) in the finite-sum non-convex setting. The paper should include more experimental results to demonstrate the dependency of $\epsilon, n, B_1, B_2$ instead of simply presenting results when fixing $B_1, B_2$.

In addition, I have a few **minor** comments for this paper:

1. Line 30: Eq. (2) is valid only if each $\xi_{i}$ **uniformly** distributed over a finite support.
2. Line 31: As demonstrated above, I don’t think these problems are different from classical stochastic compositional optimization problems.
3. Table 1: Please indentify $B_1 = |\mathcal{B}_1^t|$ 
4. Section 2: Please add related works on the variance-reduced block coordinate updates.
5. Line 182: How to ensure that the linearized update in Eq. (6) can obtain an $\mathbf{u}_t^i$ within the range of $g_i$? For example, if $g_i$ is nonnegative given its structure, the linearized update may obtain a negative $\mathbf{u}_t^i$. Would this be a significant issue?
6. Theorem 3: The authors should at least mention the stage-wise design and refer readers to Reference.
7. Line 254: Please cite reference papers discussing the convergence rate under the PL condition.
8. Section 5: It would be more convincing if the authors can further motivate their presented examples. I didn’t see any merit in probing only one task in CIFAR-10 and MNIST datasets.

limitations: The theoretical and experimental limitations are clearly stated in the previous section.

The paper doesn’t have any potential negative societal impact due to the theoretical nature of the work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors study the problem of finite-sum coupled compositional optimization (FCCO), in which the inner function may depend on the outer function. When designing stochastic algorithms for FCCO, the main challenge is how to keep track of multiple (inner) functions efficiently. To solve this, the authors propose a new stochastic method named Multi-block-Single-probe Variance Reduced (MSVR) estimator, which could track a sequence of multiple blocks of functions by only probing $O(1)$ blocks. Based on the MSVR estimator, they develop three stochastic algorithms for FCCO, and establish improved complexities for non-convex, convex and strongly convex objectives. Experiments on the multi-task deep AUC maximization show the effectiveness of the proposed methods.
strengths_and_weaknesses: Strengths:
1.  In the design of MSVR, the authors propose a customized error correction term, which is novel and powerful. Moreover, based on the MSVR, the authors develop three stochastic algorithms and establish optimal sample complexities.
2.  The paper is generally well-written. In particular, the motivation in Section 3.2 is convincing.


Weaknesses:
1. In the experiments, the authors only compare with SOX. I think it is better to add more baselines.
2. Experiments are conducted on only one network (ResNet-18), it is expected to provide more experiments with different models. Moreover,  the parameter analysis and ablation study are required to show the effectiveness of the proposed method. 
questions: 1. In line 55, the authors claim that “However, this simple change does not improve the complexities over that obtained by Wang and Yang [2022]”. Do you mean that with Eq.4 the complexity is the same complexities as Wang and Yang [2022]?

2. I am confused with the last column of Table 1. Does it denote the ratio between $B_1$ and $B_2$? For BSGD and BSpiderBoost, there are two Big O notations, but for other methods, there is only one Big O notation. What is the exact meaning?

3. After presenting the main theorems, the authors should discuss how to set the values of $B_1$ and $B_2$.

limitations: Since this paper study an optimization problem, I think that there is no potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers a general problem: tracking multiple mappings with only O(1) mappings available. An important application investigated in the paper is the Finite-sum Coupled Compositional Optimization (FCCO) problem. By using the proposed Multi-block-Single-probe Variance Reduced (MSVR) estimator, the authors obtain improved complexities for the FCCO problem under different settings. The proposed methods also enjoy better performance in experiments.
strengths_and_weaknesses: Overall, the paper is well-written and the contribution is solid.
Strengths: 
1. The proposed algorithms have better complexities than the previous best-known method for the FCCO problem, which covers wide applications in ML. The authors investigate the complexities under different settings, i.e., non-convex/convex/strongly-convex/finite-sum. Their theoretical guarantees match the lower bound in terms of $\epsilon$ and $\mu$ in many settings.
2. The authors clearly show the intuition of the proposed method and how to determine the value of the parameter $\gamma_t$. The proposed MSVR estimator is of interest and may inspire the algorithm design for other ML problems.
3. The writing and explanations are clear. The algorithm is simple and the theoretical analysis looks sound to me.

Weakness:
1. The proofs in the supplementary are not very clear-written and more explanations about each lemma are recommended.

questions: 1. Could the analysis also be used in contrastive learning, whose loss function can also be written in the form of FCCO? 
2. For the inequality in Lemma1 on page 5 line 174, should it be $\beta_{t+1}$ rather than $\beta_{t}$ ?

limitations: No problems here.
review_title: null

Meta-review: metareview: The paper makes a nice contribution to the growing field of stochastic compositional optimization. In particular, it considers the case of coupled compositional problems and provides an algorithm that tracks all the inner-level objective information required in an efficient manner. Sample complexities (which are intuitively, optimal) are established. 

The authors **must**  emphasize that they work under the stronger Assumption 3 in the revision. 
confidence: Certain
Decision: Accept