On the Hardness of Online Nonconvex Optimization with Single Oracle Feedback

We thank the reviewer for the careful reading and thoughtful comments. We addressed the reviewer's questions in the following and revised the paper accordingly. The changes are marked in blue color in our revision. We hope the responses below and the changes in the paper address the reviewer's concerns.

Q1: Concretely, I think some statements of the optimality of the results are a little over-claimed. Note that the lower bounds (Theorem 1 and Theorem 3) do not hold for any possible algorithm but only for a specific class called linear-span algorithms. When talking about optimality, it is correct to say that 'our algorithm is optimal inside the class of linear-span algorithms', but not just 'our algorithm is optimal', as the authors have claimed in the current version. This is a serious issue, and I suggest that the authors could revise the corresponding statements to avoid unnecessary misunderstandings of the paper's contributions. By the way, I think the contributions of this paper are still adequate for acceptance, even if the authors use the correct descriptions of optimality. As a result, there is no need for over-claiming, which will only give readers and reviewers (at least for me) a bad impression.

A1: Many thanks for pointing this out! We agree with the reviewer that our claims of optimality should be more precise and restricted to the class of linear-span algorithms. Following the reviewer's suggestion, we have updated all these claims in the revision. Thanks again for the suggestion, and we agree that it is important to clarify our contribution.

Q2: Can I conclude that after this work, the methods using the smoothed function $F_{t,w}$ can be abandoned? Or equivalently, does this work offer a strictly superior methodology compared with Hazan's work? If not, what is the disadvantages of measuring local regret defined on the original functions?

A2: We think that the previous studies (e.g., Hazan et al., 2017) investigated a complimentary regret metric based on the window-smoothed $F_{t,w}$, which is also valuable, particularly for studying slowly changing environments. In the future, it is also interesting to continue their line of work and obtain refined problem-dependent bounds relating to function variation $V_T$.

Q3: Is the one-point running difference gradient estimator strictly superior to the standard FKM one-gradient estimator? I think this only holds in the problem of online nonconvex optimization, but not in bandit convex optimization (BCO)? As the authors have stated, the variance of the one-point running difference estimator is a constant, which is also the case for the standard two-point estimator, and thus the guarantee of this work is as good as that using a two-point estimator. However, is the variance of the running difference estimator still a constant in the BCO setup? If so, it seems that an $\mathcal{O}(\sqrt{T})$ regret can be achieved in the BCO setup, which is definitely the most exciting progress in the BCO research (which is too simple to be true). If not, what is the difference between using this estimator in the nonconvex setup and in the convex setup? Will using the running difference estimator in the method of Flaxman (SODA'05) improve their $\mathcal{O}(T^{3/4})$ regret? If not, what is the key difficulty?

A3: Many thanks for the insightful questions! Yes, the one-point running difference gradient estimator is strictly better than FKM in our setting (i.e., online nonconvex optimization). But this may not generally hold, e.g., for online BCO. In particular, for BCO, the variance of the running difference estimator may not be a constant if there is no assumption on the function variation $V_T$. Hence, $\mathcal{O}(\sqrt{T})$ may not be achieved without function variation $V_T$ being present in the upper bound.

We also point out that (Flaxman et al., SODA'2005) considered BCO for static global regret and did not introduce function variation $V_T$ in their static setting. Hence, our analysis of the running difference estimator for dynamic regret does not apply to their setting directly. However, if we consider BCO under dynamic regret, our method will be applicable, and the bound will involve the function variation $V_T$.

Finally, we thank the reviewer again for the helpful comments and suggestions for our work. The reviewer's main concern is our claim of the optimality of algorithms, which we have revised our statement throughout the paper. Since the reviewer commented that "I think the contributions of this paper are still adequate for acceptance", we kindly ask the reviewer to consider raising the rating of our work to be aligned with your comment. Certainly, we are more than happy to address any further questions that you may have during the discussion period.

We thank the reviewer for the careful reading and thoughtful comments. We addressed the reviewer's questions in the following and revised the paper accordingly. The changes are marked in blue color in our revision. We hope the responses below and the changes in the paper address the reviewer's concerns.

Q1: I would like to see more comparisons and discussions on three variants, specifically when we need to consider SGO/SSGO/SVO.

A1: Thanks for pointing this out. In the revision, we added the discussion in Section 1.1 (see the blue-colored texts). We also provide the discussion below for your convenience. The three settings correspond to three different application scenarios. The SGO setting applies to white-box systems with known objective functions whose exact gradients can be calculated. However, many systems can have various uncertainties, e.g., loss functions depending on random samples or systems with intrinsic noise. In such a case, even if the system objective function is known, the calculation of their gradients can still be stochastic, leading to the SSGO setting. Moreover, the SVO setting is suitable to model black-box systems, where objective functions are unknown but only function values can be queried. For example, the recommendation system can provide users' ratings (i.e., reward values), but the reward function following which users provide ratings is typically unknown.

Q2: There is no matching lower bound for the SVO problem.

A2: Yes, it is still an open problem. We anticipate the lower bound for SVO to be $\mathcal{O}(d\sqrt{(1+V_T)T})$, but this seems to need non-trivial techniques to prove. Here are some initial thoughts. Inspired by (Besbes et al., 2015) on the lower bound for online convex optimization with function value feedback, we will need to construct several special nonconvex functions as candidates for $f_t$'s and then reformulate the problem on $f_t$ as a non-parametric estimation problem, aiming to identify which function is used from the candidate list at each time step. We note that constructing nonconvex candidate functions and reformulating the problem will require considerable effort, and we leave this as an interesting future problem.

Q3: Can the lower bound analysis extend to the general setting of sliding windows? E.g., for a fixed window length $w$, $V_T$ is still appear in the regret bound?

A3: Good question. We expect that our lower bound analysis can be extended to the setting of sliding windows, but may not be in a straightforward way. In our lower bound proof, we construct functions in different blocks to be orthogonal with each other. After sliding window average, functions may not satisfy such a requirement anymore. To address this issue, setting a window of initial and ending functions to be zero in each block can potentially avoid such a problem. It may be possible to design better schemes, but will take more effort. We will continue to explore this problem in the future.

(Besbes et.al., 2015): Besbes, Omar, Yonatan Gur, and Assaf Zeevi. "Non-stationary stochastic optimization." Operations research 63, no. 5 (2015): 1227-1244.

We thank the reviewer for the careful reading and thoughtful comments. We addressed the reviewer's questions in the following and revised the paper accordingly. The changes are marked in blue color in our revision. We hope the responses below and the changes in the paper address the reviewer's concerns.

Q1: The lower bounds for SGO and SSGO models are restricted to a relatively small family of algorithms such that $x_{t+1} = x_t+ \sum_{i=1}^t\alpha_{t,i}g_i$. This family does not include popular algorithms like online mirror descent and FTRL.

A1: Thanks for the great comment! Our current technique can extend to the larger family of algorithms of the zero-respecting set (as discussed in A3). To develop lower bounds for the larger algorithm class that includes mirror descent and FTRL, the general idea for online convex optimization counterpart may be useful. But the construction of specific hard-to-learn nonconvex functions will take more effort. We will pursue this direction as an interesting future work.

Q2: For the lower bounds, I assume there is an implicit assumption on function dimension $d$ (where $f_t:\mathbb{R}^d \to \mathbb{R}$), e.g. $d\ge \Omega(1+V_T)$ to guarantee there are $\Omega(1+V_T)$ orthogonal gradients?

A2: We agree with the reviewer and made this assumption explicit in the revision of the paper.

Q3: The lower bound construction in Carmon et al. 2021 and Arjevani et al. 2022 can be applied to a larger family of algorithms besides algorithms of form $x_{t+1} = x_t+ \sum_{i=1}^t\alpha_{t,i}g_i$. I am curious if the lower bounds for ONO can also be extended beyond the current family? If not, what is the main difficulty in ONO compared to offline nonconvex optimization?

A3: Great question! We expect our proof of lower bound can be extended to the suggested larger family of algorithms, i.e., all zero-respecting algorithms (Carmon et al., 2021; Arjevani et al., 2022). Specifically, to make the current proof still hold for the zero-respecting algorithm class, the gradients in the previous blocks should be orthogonal to the present gradients. Our current design of online functions already satisfies such a requirement. Hence, our lower bound will still hold. We will carefully go over the proof and ensure that all steps are mathematically rigorous.

Q4: Proof of Lemma 2 first two equalities: where does $d$ outside $\\|\mathbb{E}\ldots\\|$ come from? is it a typo?

A4: Thanks for pointing it out. It is a typo, and $d$ should come out later. We corrected the steps in the proof of Lemma 2 in the revised paper (see the highlighted steps in the proof of Lemma 2).

We thank the reviewer for the careful reading and thoughtful comments. We addressed the reviewer's questions in the following and revised the paper accordingly. The changes are marked in blue color in our revision. We hope the responses below and the changes in the paper address the reviewer's concerns.

Q1: There is a long line of research in online learning that studies dynamic regret, which also have function variation bounds. After reading the proof, I found that the many parts of proof for obtaining the upper bound are very similar to this line of research. I recommend the authors review these papers and add a discussion.

A1: Thanks for the suggestion. In the revision, we have added the suggested discussion to Section 1.2 Related Work. Please feel free to check.

Q2: In online optimization, apart from function variation bound, there are also other measures for function changes, such as the gradient variation bound. Is it possible to consider this or other adaptive bounds (in future work)? Similar to function variation, the gradient variation bound is defined as $V_T = \sum_{t=1}^T \sup_{x} ||\nabla f_t(x) - \nabla f_{t-1}(x)||^2$. See, e.g., (1) of (Chiang et al., 2012), for more information.

A2: We appreciate your insightful inclusion of the $L_p$-deviation concept (Chiang et al., 2012) into this discussion. It is possible to derive upper bounds based on other types of function variation. Consider the example of the gradient variation suggested by the reviewer. Here are our preliminary thoughts. We can use a specific $f_t$ as the reference function, and then the updates at other time steps can be viewed as gradient descents of the reference function with a bias error, where the gradient variation determines the bias error. Such an idea may lead to a gradient variation-dependent dynamic regret upper bound. We will continue to work out the rigorous proof, which we expect to be promising.

Q3: I don't understand this discussion (quoted texts in the introduction). Regret is a performance metric, and people do not really compute regret when implementing the algorithm. So why "accessing the global minimum of nonconvex functions is typically infeasible"?

A3: Great question. Typically, the comparison metric in the regret serves as a baseline to measure how well-designed algorithms perform. Since the global minimum of nonconvex functions is generally infeasible to obtain in a computationally efficient manner, using such a point as the comparison baseline might be an unrealistic standard for computationally feasible algorithms to try to achieve.