Debiasing Conditional Stochastic Optimization

Summary

This paper considers CSO problems and its finite-sum variant FCCO, and proposed new algorithms incorporating extrapolation and variance reduction. The proposed algorithms are shown to enjoy a better sample size in the inner layer which induces an improved sample complexity compared to existing CSO literature. The authors also furthered their study in the FCCO regime, the proposed algorithm enjoys a better complexity in moderately large $n$ regime.

Strengths

1. Improved sample complexities for CSO and FCCO problems 2. The algorithm design incorporates extrapolation which is new to the CSO literature I think, and it brings an improvement in the sample complexity in the inner layer, which reveals some innovation.

Weaknesses

1. The additional regularity assumption (compared to [15]) on the bounded higher-order gradients/moments, even though authors tried to rationalize it, reduces the significance of the result. 2. You mentioned "... $\Omega(\epsilon^{-3})$ is a sample complexity lower bound for standard stochastic nonconvex optimization [2]..." in Table 1, but as far as I can see, with your higher-order Lipschitz condition, the statement may not hold. Your function class is more restricted compared to the setting in [2]. I think authors may refer to Could you please comment more on it? - Carmon, Yair, et al. "Lower bounds for finding stationary points ii: first-order methods." Mathematical Programming 185.1-2 (2021): 315-355. - Arjevani, Yossi, et al. "Second-order information in non-convex stochastic optimization: Power and limitations." Conference on Learning Theory. PMLR, 2020. 3. Some writing issues, I believe the paper's writing style could benefit from a few adjustments to enhance its readability, there . - Line 141, $T_m$ (vs. $T_{D_m}$) - Line 148, "lesser" - Line 173, "to (be) $\nabla$..." - Line 224, "... some time $t$...", I think such statements can be further revised and formalized. With that, I think the paper provides some interesting results, especially in terms of the algorithm design, but I am not that convinced on the significance of the results (regarding the a bit unfair comparison) and feel that the writing can be further revised for a better flow.

Questions

1. For clarification, with the extrapolation framework you need the constant term $s$, but when applied to CSO, you just set $s=0$, I am not sure why it is important to include the $s$ into your framework if there is no nontrivial instantiation. Could you please comment more on it? 2. For clarification, in Theorem 3, you set $m=O(\epsilon^{-0.5})$, but in Line 247, you mentioned the straightforward extension of E-BSpiderBoost requires a different $m$ by taking a maximum, I am wondering why the setting of $m$ in Theorem 3 does not directly apply here.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

N/A.

Summary

This paper presents a stochastic extrapolation technique with variance reduction to obtain improved sample complexity bounds for conditional stochastic optimization problem. Numerical study also support the effectiveness of the proposed algorithm.

Strengths

- The stochastic extrapolation is a useful tool for CSO problem. The technique is new for solving the CSO problem, though it requires higher-order smoothness assumption of the loss function. I think it could be potentially useful for other stochastic optimization formulations. I am also curious about how the authors come up with this approach? Do authors inspired from any existing literature? - The overall presentation is very clear and the theoretical results with technique assumptions are presented in detail. - Numerical study is very strong to support the effectiveness of the algorithm.

Weaknesses

- From my perspective, some notations could be confusing. For example, in Theorem 2 the authors use $\Omega(\cdot)$ notation for batch size $m$ and number of iterations $T$, but in line 235 the authors use $\mathcal{O}$ instead. I would encourage the authors check those notations throughout the paper to make it consistent. - Please check and revise the first sentence in line 287. - In the theoretical analysis, the authors present iteration complexity together with sample compelxity per-iteration. However, in related work comparison, the authors only compare the overall total sample complexity of baseline methods. I encourage the authors also check and compare iteration complexity together with sample compelxity per-iteration. - In Table 1, I think the authors should also add V-MLMC method (from [16]) for comparison. Also, in numerical study, I am confusing why the authors do not compare with RT-MLMC method but only V-MLMC method?

Questions

N/A

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

The paper highlights that optimizing conditional stochastic optimization problems is challenging as the sample-averaged gradient is biased. The biased gradient increases the sample complexity needed to achieve convergence. To account for the bias, the paper proposes stochastic extrapolation. The method shows that the bias can be expressed as a sum of Taylor series expansion terms and the bias can be estimated by constructing estimates for each of the terms in the expansion. The key insight is that the size of the $k^{th}$ order term of the series is of size $O(1/m^k)$ where $m$ is the batch size. They propose the $k^{th}$ order extrapolation operator which computes up to the $k^{th}$ order term in the Taylor series and uses the terms to correct for the bias. The paper then uses the the stochastic extrapolation technique to bias correct the gradients for the conditional stochastic optimization problem and finite-sum coupled compositional optimization problem. They then prove convergence guarantees for optimization algorithms applied on the two problem types, showing stochastic extrapolation improves the sample complexity of the algorithms. Finally, they perform a numeric experiment on invariant logistic regression and show the extrapolated version of the algorithms achieves lower sub-optimality.

Strengths

The paper proposes a fairly novel approach to address the issue of biased sub-gradients. The problem and approach are described clearly and intuitively. The paper is also able to highlight some important optimization problems that satisfy the regularity conditions leveraged by the paper. The paper’s significance is being able to leverage these regularity assumptions in order to prove stronger sample complexity bounds.

Weaknesses

The paper is hard to read since authors i) often reference the appendix with limited context, ii) do not point out if the reference is in the appendix or not, and iii) do not define notation. - As an example for the first point, Lemma 1, Lemma 2, and Theorem 7 are all in the appendix but it is not noted. - For the second point, Lemma 2 also is referenced in line 155 to quantify the variance of the operator applied to the function, but it’s unclear what Lemma 2 shows precisely. In most cases, it seems that the authors are trying to make a statement and reference the proof, however, the language is not clear that is the case. As evidence, when referencing Lemma 2, the authors state “a consequence of Lemma 2 is that” when it could be more clear by stating “Lemma 2 (in Appendix Section B) proves”. -For the third point, it is hard to find a definition for V in Lemma 2. The above three points make reading and verifying the statements in the paper challenging. The paper has minimal numeric studies. For example, it would be interesting to see how the approach performs for problems that do not satisfy the regularity conditions. It may also be interesting to see the improvement as the level of bias varies due to underlying problem parameters.

Questions

1. The paper mentions a burn-in rate for higher order extrapolation. Is there any intuition of controls the burn-in rate or if the burn-in rate is theoretically quantifiable? 2. Does the stochastic extrapolation perform better or worse when the number of samples is small? The numerics seem to indicate the performance is the same for BSGD and BSpiderBoost when the # of samples is small.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

From a technical perspective, the authors do note that their proposed approach requires the target optimization problem to satisfy certain regularity conditions. However, it is unclear what is the cost of applying the stochastic extrapolation and if there is any trade-offs.

Summary

The authors study stochastic optimization problems with nested conditional expectations, with access to first-order samples from the involved functions. With such an oracle access, it is non-trivial to build unbiased estimates of the gradient, hence normal stochastic optimization methods don't work. They authors show that under a third-order differentiability assumption, which they argue to be "mild", one could adapt existing extrapolation techniques to this problem and obtain an estimate of the gradient with a reduced bias. This in turn results in substantial improvement in the convergence rate of algorithm fed with this bias-reduced estimate. The authors demonstrate this using state-of-the-art algorithms, both with and without finite-sum variance reduction.

Strengths

The claimed improvements are substantial. The paper is modular, in the sense that there is one clear goal: reducing the bias of the gradient estimate, and that is carried out separately. Then, the result is fed into existing best algorithms. This makes the contribution very clear.

Weaknesses

There seems to be some issue in the last term of Eq (2): since $\phi_\delta$ depends on $\delta$, we cannot take it outside expectation, neither can we decompose the resulting expectation in such a way that $E[(\delta - h)^{2k-1}]$ comes out and multiplies the expectation of the term involving $\phi_\delta$. I am not sure if this will have a major adverse effect on the rest of the results in this section, but I will keep looking deeper in the proofs. In terms of related work, I am surprised that the use of extrapolation for bias reduction in Stochastic Composite Optimization is missed. The central work here is: M. Wang and J. Liu. Accelerating Stochastic Composition Optimization. 2016 The authors need to discuss the relationship between the techniques. I also find it problematic that the authors call the assumption of third-order differentiability a "mild assumption". Whether this is mild or not has to be left to the reader to decide. Currently, the introduction and Table 1 give an incorrect impression. This needs to be made clear way earlier in the introduction, and also laid out clearly in the caption of Table 1. Also, the assumption $n = O(\epsilon^{-2})$ is certainly worth more explanation that the footnote given.

Questions

Please add any comments you may have about the points raised under "Weaknesses", including the relationship to the work on accelerated stochastic composition optimization, as well as the issue with Eq (2).

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The paper can be improved in terms of clarifying the limitations of its results, as explained under "Weaknesses" above. This is a theoretical paper. As such, greater societal impact is not addressable at this level.

Summary

The paper addresses the conditional stochastic optimization (CSO) problem. A noted drawback in CSO is the bias in its sample-averaged gradient, an offshoot of its nested structure, which necessitates an extensive sample complexity to achieve convergence. The authors introduces a new stochastic extrapolation technique address this bias effectively. They propose that by merging this extrapolation with variance reduction techniques, improvements in sample complexity can be realized compared to existing results for non-convex smooth objectives. The authors claim that the proposed methods improve the sample complexities for both the CSO and FCCO under some reguarlity.

Strengths

- Overall writing is clear, and organization is well-structured. - The paper introduces an extrapolation-based scheme to alleviate bias in gradient estimations. The proposed method is used for gradient estimations for CSO and FCCO problems. - For CSO problem, the authors claim that the proposed methods, E-BSGD and E-BSpiderBoost, achieve an improved sample complexity compared to the existing bounds under some additional reguarlity. For FCCO problem, the authors proposed an algorithm, E-NestedVR, combining the extrapolation-based scheme with a multi-level variance reduction which achieves an improved (or at least matching) sample complexity compared to the existing results.
 - The techniques of the anlysis are interesting, and worth credit.

Weaknesses

- While the new bounds show improved rates, the results are based on additional regularity assumptions. The authors acknowledge the discrepancy in the set of assumptions used in the current paper and those in the existing results. They state that "the bounds derived from previous studies do not improve when incorporating this additional regularity assumption" of the 3rd-order differentiability, and hence argue that their results present an improved bound. However, I am not sure whether such an assertion is valid. The new regularity condition imposed by this paper is used for the authors' technical convenience, not required by the existing methods. Hence, it is very possible and often obvious that the existing methods do not improve even with the new additional regularity assumption because these methods did not even need such regularity. - So I am not sure whether the claim of the "improved" rate is valid. Aren't they rather apples and oranges? For example, can you precisely pinpoint where Assumtpino 6 is needed? What rate (just a ballpark) would you get if you do not have this assumption?

Questions

Please see the comment in the weakness section.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

Please see the comment in the weakness section.

Thank you for your response

Thank you for your response. I have read the other reviews and the rebuttals. The response addresses my question about the work of Wang and Liu [2016]. I am still assessing the paper in terms of the proof and in light of the other reviews. I will post any concerns here.

Thanks for the responses.

I have read the authors' responses and other reviews. I think I have a better understanding of the paper. Thanks for the responses.

After reading rebuttal

Thank you for your reply. I will raise my score to 6 because of the efforts made in rebuttal

Thank you for your response

I appreciate the response and additional experimental results. I will keep my score as I think it definitely falls within an acceptance category.