On the Hardness of Online Nonconvex Optimization with Single Oracle Feedback
Authors: Ziwei Guan
Yi Zhou
Yingbin Liang
Venue: ICLR 2024 poster (2024)
Keywords: online nonconvex optimization
local regret
optimal rate analysis
Primary area: optimization
TL;DR: We consider online nonconvex optimization with single oracle feedback, and provide matching lower and upper bounds on the local regret.

Abstract: Online nonconvex optimization has been an active area of research recently. Previous studies either considered the global regret with full information about the objective functions, or studied the local regret with window-smoothed objective functions, which required access to unlimited number of gradient oracles per time step. In this paper, we focus on the more challenging and practical setting, where access to only a single oracle is allowed per time step, and take the local regret of the original (i.e., unsmoothed) objective functions as the performance metric. Specifically, for both settings respectively with a single exact and stochastic gradient oracle feedback, we derive lower bounds on the local regret and show that the classical online (stochastic) gradient descent algorithms are optimal. Moreover, for the more challenging setting with a single function value oracle feedback, we develop an online algorithm based on a one-point running difference gradient estimator, and show that such an algorithm achieves a local regret that a generic stochastic gradient oracle can best achieve.

objective Published as a conference paper at ICLR 2024
ON THE HARDNESS OF ONLINE NONCONVEX OPTIMIZATION WITH SINGLE ORACLE FEEDBACK
Ziwei Guan Yi Zhou & Yingbin Liang
Department of Electrical and Computer Engineering, Ohio State University Department of Electrical and Computer Engineering, University of Utah {guan. 283, liang. 809) edu, yi. ri.zhou@utah.eo edu
ABSTRACT
Online nonconvex optimization has been active area of research recently. Pre- vious studies either considered the global regret with full information about the objective functions, or studied the local regret with window-smoote functions, which required access to unlimited number of gradient oracles per time step. In this paper, we focus on the more challenging and practical setting, where access to only a single oracle is allowed per time step, and take the local regret of the original (i.e., unsmoothed) objective functions the performance metric. Specifically, for both settings respectively with a single exact and stochastic gra- dient oracle feedback, we derive lower bounds on the local regret and show that the classical online (stochastic) gradient descent algorithms are optimal in the class of linear-span algorithms. Moreover, for the more challenging setting with a single function value oracle feedback, we develop online algorithm based on a one-point running difference gradient estimator, and show that such an algorithm achieves local regret that generic stochastic gradient oracle can best achieve.
INTRODUCTION
Online optimization is a popular learning framework that models sequential decision-making in non-stationary environment, and it has attracted a lot of attention in the past decade (Hazan et al. 2016; Orabonal 2019). In online optimization, an agent interacts with the environment by selecting a sequence of control variables .i...... De and receiving information about loss functions fi(:).... fe(-) from the environment. Specifically, at each iteration f, the agent selects control variable x, based on the historical information about fi.... certain feedback about is revealed to the agent, who then selects the next control variable 24+11 based on the updated information. The goal of the agent is to select 2ú sequentially to minimize a certain metric of regret, typically defined as the cumulative difference between the function value the chosen control variable and the minimal function value with hindsight information.
After the selection has been made,
In the existing studics on online optimization, many efficient online algorithms have been proposed to minimize different types of regret for convex objective functions, whose global minimum can be efficiently achieved with gradient oracles (Agarwal et al. 2010; Suggala & Netrapalli 2020 Héloou
et al. 2020 Zinkevich] 2003) Hall & Willett 2013 Jadbabate
al..2015, Mokhtari et al. 2016
Zhang et al. 2018). As a comparison, the more challenging online nonconvex optimization has not been well explored yet. Specifically, the existing studies on online nonconvex optimization have focused on two major settings. One line of work adopted the global regret as the performance metric (Krichene et al. 2013) Agarwal et al., 2019:: Lesage-Lanme
et al.) 2020 Héliou al. 22220), which compares the algorithm output to the global minimum of the nonconvex objective functions. However, accessing the global minimum of nonconvex functions is typically infeasible. Another line of work considered the more feasible local regrer (Hazan et al. 2017, Ayyorr et al. [2019) Hallak et al. [021] Guan et al. 2023), which compares the control variables to the stationary points of corresponding nonconvex functions. Importantly, these nonconvex functions are smoothed versions of the online nonconvex objective functions fe averaged over a sliding window. These studies designed online algorithms that achieve sublinear local regret of the smoothed nonconvex objective functions with sufficiently large window length. However, the local regret of window-smoother functions can be very different from that of the original online objective functions and hence may not accurately reflect

---

Published as a conference paper at ICLR 2024
the actual performance of the system, especially when the functions fi change rapidly. Therefore, are motivated to study the following fundamental problems in this work.
Q1: What are the fundamental lower bounds on the local regret (without function smoothing) for online nonconvex optimization with different types of single oracle feedback, e.g., exact gradient, stochastic gradient, and function value oracles?
Q2: What online learning algorithms can achieve these lower bounds on the local regret using only single oracle feedback of nonconvex functions?
1.1 OUR CONTRIBUTIONS
In this paper, we follow the line of research on the local regret of online nonconvex optimization, and focus on the setting with only single oracle feedback per time step. In particular, we study the local regret of the original online objective functions (i.e., without window-smoothing). Below we discuss the major challenges in each setting and summarize our contributions.
Single Gradient Oracle (SGO) feedback, where only one gradient oracle is available at a time. In this setting, instantiating the existing analysis (Hazan al. 2017 Guan al. 2023) by taking the window size w = provides an (T()) lower bound on the local regret, which ignores the intrinsic function variation over time and can be overly pessimistic when the functions change slowly. We provide a tighter and problem-dependent lower bound on the local regret that captures how the function variation affects the hardness of the problem. Then, we show that the classical online gradient descent algorithm achieves the optimal regret bound for the class of span algorithms.
Single Stochastic Gradient Oracle (SSGO) feedback, where only one stochastic gradient oracle is available at a time and the local regret harder to optimize. In this setting, the existing study (Guan al., 2023) provides Ω (T) lower bound by taking window size w w== 1, but it does not capture the impact of function variation and can be overly pessimistic. We characterize the challenge through establishing another tight lower bound the expected local regret. Then, we show that the online stochastic gradient descent algorithm achieves the optimal regret for the class of linear-span algorithms.
Single function value oracle (SVO) feedback, where only one function value oracle is available at a time. In this setting, the challenge lies in constructing a good gradient estimator with only one function value oracle. We found that online gradient descent with the classical one-point gradient estimator has poor performance due to large variance. To address this, we developed one-point rumning difference gradient estimator. We show that such a zeroth-orde gradient estimator, when applied to the online gradient descent algorithm, achieves an optimal local regret for the class of linear-span algorithms with generic stochastic gradient oracle.
The above three settings capture different application scenarios. The SGO setting applies to white-box systems with known objective functions, where 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. 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.c., reward values), but the reward function following which users provide ratings typically unknown.
1.2 RELATED WORK
Online convex optimization: Online convex optimization has been extensively studied in the past. and we refer the readers to the standard textbooks (Hazan et al., 2016 Orabona 2019 Shalev-Shwar 2012) and recent survey (Hoi al.) 2021) to obtain a comprehensive understanding. Below we summarize a few main directions the topic.
Studies on online convex optimization can be generally divided into three categories based on which notion of regret they are interested in and what feedback information a learner has for the design.
Extensive works such as Agarwal et al. (2010); Suggala & Netrapalli 2020); Héliou et al.) (2020) studied static regret, which is defined as the difference between cumulative losses and the minimum
cumulative losses with hindsight information. Many other works (Zinkevich) 2003 Hall & Willett
2013. Jadbabaie al. 2015 Mokhtari et al. 2016 Zhang et al. 2018 Héliou et al. 2020) studied
2

---

Published as a conference paper at ICLR 2024
the dynamic regret, where the comparison is made to the function value at a given reference point (typically chosen as a global minimum of the instantaneous objective function) at each time step. Among these three lines of research, the studies the dynamic regret (inkevichh 2003 Hall & Willett 2013 Jadbabaie et al., 2013] Mokhtari et al.) 2016 Zhang et al. 2018 Héliou et al. (0200 closest to this paper. Their development of upper bounds on the dynamic regret uses the Lipschitz smoothness, gradient update direction, and the convexity of online functions. In particular, their upper bounds involve various types of function variation such as the path length (defined as the summation of differences between two adjacent global minimal variables) and the gradient variation. In our study of online nonconvex optimization, the development of upper bounds on the dynamic regret also uses the Lipschitz smoothness and the gradient update direction (which are the same as online convex optimization). However, since there is no convexity property we can use here, we leverage the Lipschitz smoothness of each objective function to connect the local regret to the cumulative difference in function values, which lcads to a different function variation we define in eq. 2
Further, number of works such Hazan& & Seshadhri (009); Daniely et al. (2055) Zhang et al. (201)); Garber& Garber & Kretzu (2022) studied the adaptive regret, which is defined as the static regret on the subsets of all iterations, bridging between the dynamic regret and the static regret. Online convex optimization has also been studied under function value feedback, which captures many practical applications. In partieular, |laxman et al.] (2005) and [Saha & Tewari (201T) studied the setting with one-point gradient estimators, and Agarwal et al. (2010) studied the setting with multiple-point estimators. Further, Cao & Liu (2018); Kim & Lee (2023) studied functional constrained online optimization and Yi et al. (2020); Wang et al. (2022) studied distributed online optimization with
both one-point and two-point estimators.
One line of studies on online nonconvex optimization considered the global regret as the performance metric, which is defined as the cumulative discrepancy between the loss of the algorithm output and the lowest possible loss. Particularly, Krichene et al. (2015) extended the Hedge algorithm to the continuum and showed it achieves a sublinear regret. Yang
Online nonconvex optimization:
al. 2018) developed an improved algorithm based on the Hedge algorithm with novel weighting
strategy. Agarwal et al. (2019) extends the bandit algorithm of follow-the-perturber tite-pettrred--eeee leader to the
nonconvex setting, and Suggala & Netrapalli (2020) further showed that such an algorithm achieves the optimal regret. Online nonconvex optimization has also been studied under certain assumptions on nonconvex objective functions, such as the weak pseudo-convex condition (Gao et al., (018)) and the Polyak-Lojasiewicz condition (Mulvaney-Kenn
et al.] (0022). Moreover, the global regret minimization of online nonconvex functions has also been studied under the function value feedback
in Gao et al. 2018); Héliou et al. (2020) 2021): Gao et al. (2018).
Another line of research studied the more feasible local regrer that compares the control variables to the stationary points of hindow-smoothen nonconvex functions. Particularly, Hazan et al. (201)) provided the first analysis, where the objective functions are smoothed via sliding window and developed a lower bound on the local regret. The authors further devised a nested-loop algorithm and showed that it achieves the regret lower bound. |Aydore et al. (2019) adopted the nested-loop type algorithm to dynamic environment application, and Hallak et al. (2021) adopted the same approach and extended it to the setting with nonsmooth functions. Guan et al. (2023) considered the setting with a limited number of feedback concerning the gradient or the function value of the window- smoothed objectives and provided tight lower and upper bounds for linear-span algorithms. Our study follows this line of research with the following main differences. First, we do not take window-smoother objective functions but rather focus on the original functions and their corresponding local regret and provide a problen-dependent analysis based on the function variation. Second, all the algorithms developed in the above studies require multiple feedback oracles concerning fi due to the window- smoothing, whereas we study the settings with only a single oracle feedback of ft. is worth noting that the aforementioned previous studies on the complimentary regret metric based on window- smoothed functions are still valuable, particularly for studying slowly changing environments. In the future, it is interesting to continue their line of work and obtain refined problem-dependent bounds based on function variations.
Gradient estimation with function value oracles: Various gradient estimation methods have been applied to online optimization when there is only function value (i.e., bandit) feedback. The performance of these gradient estimators highly affect the performance of their corresponding online algorithms. Specifically, the conventional one one-point gradient estimator was developed in in/Flaxman et al.) (2005); Dekel et al. (2015); Gasnikov et al. (2077) estimate the gradient of function based only
3

---

Published as a conference paper at ICLR 2024
on one function value. Two-point gradient estimators (Agarwal et al. 2010 Nesterov & Spokoiny 2017: Shamir 2017) are also designed to estimate the gradient based on two function values and can achieve much better performance over the conventional one-point estimator. Recently, Zhang et al.) (2022) proposed a novel one-point estimator which uses an immediate previous function value during iterations serve as the second function value in the gradient estimator reduce the variance. Such an estimator has been shown in Zhang et al. (2022) to achieve a much better performance than the conventional one-point estimator but still performs weaker than the two-point estimator. Inspired by such an estimator, in this paper, we propose a one-point running difference estimator for online nonconvex optimization and show that it enjoys the same regret bound as two-point estimator.
PRELIMINARY
In this paper, we consider the online nonconvex optimization (ONO) problem with a sequence of objective functions fi, : ft..... The objective functions are smooth and bounded on IR and are generally nonconvex. We adopt the following standard assumption that is widely used in the
online optimization literature (Agarwal et al.
2010 Flaxman et al. 2005 Hazan al. 2017 Aydore
ct al. 2019 Zhao et al., 2020 Hallak et al.] 2021).
Assumption 1. For all I. function ft Ed + R satisfies [f(()) S M for some M 2 0 and for all x E IR. Moreover, there exist universal constants Lo, L1 2 0 such that for any x, y E IR [f(x) - f(y)l - Lollæ yl), and [=) f S Lı|læ - yII. where || denotes the lg norm.
At each iteration t. the agent first submits a control variable 2; E R to the system based on the historical feedback. After that, the feedback about objective function fi is revealed from the system, and based on that, the agent further determines the next control variable. For such an ONO problem, we study the following local regret.
(Local regret): R(T Σ [(
Intuitively, the local regret defined in eq. (I) compares the control variables to the stationary points if that satisfies (x²) = O. It can also be interpreted as the dynamic local regret because the comparison baseline is stationary point of the instantaneous objective function ft.
We note that the previous work of online nonconvex optimization (Hazan et al. 2017; Hallak et al. 2021] Guan et al.
2023) studied the local regret with window-smoothing which defined as R. (T) 1= F. (x))ll where Ft, (z) ar
Li=t-wt fa(z) corresponds the smoothed objective function averaged over a sliding window of size w. It reduces to our definition of the local regret in eq. (T) when w 1. In Hazan al. (017): : Hallak et al. (202T); Guan et al.) (003)), the window size w is chosen to be large so that the smoothed functions {Fr,w>> e change slowly over the iterations, making it easier to minimize the local regret. However, the local regret of window- smoothed functions can be very different from that of the original functions and hence may not accurately reflect the actual performance of the system, particularly when functions change rapidly.
E
In this work, we focus on online nonconvex optimization with single oracle feedback about fo per iteration, and our goal is to develop algorithms that minimize the local regret in eq. (T). In particular, consider the following single oracle feedback settings:
Single Gradient Oracle (SGO) feedback: At each time f, one can only access a single exact gradient oracle.
Single Stochastic Gradient Oracle (SSGO) feedback: At each time 4, one can only access a single stochastic gradient oracle.
Single Value Oracle (SVO) feedback: At each time t, one can only access single function value oracle.
We also define the following notion of function variation over time, a fundamental quantity that useful to characterize the local regret in the nonconvex setting.
sup (z- f((x))
2= ZERd
The above function variation intuitively reflects how much the online learning objective functions vary over time. In particular, when Vy = 0, all fi's are the same as f1, and online learning problem
4

---

Published as a conference paper at ICLR 2024
reduces to offline optimization problem. On the other hand, when Vi = cT' for some constant c > O, the number of objective functions ft that are totally different from all previous ones can scale linearly with T. No algorithm can perform well for these rapidly changing functions f. because all received information is about fi up to ft-1, which contains little information about fz-
3 ONLINE NONCONVEX OPTIMIZATION WITH SGO
Previous studies (Hazan al. 2017 Hallak et al. 2021 Guan et al. 2023 of online nonconvex
optimization have been focusing on window-smoothn gradient oracles of ft. this section, we study online nonconvex optimization with SGO, where only single access to the gradient oracle of ft is available at each time L.
functions that require access to multiple
3.1 LOWER BOUND ON LOCAL REGRET UNDER SGO
In order to understand the complexity limit of the problem under SGO, we establish a lower bound on the local regret. We first specify the algorithm class that we consider as follows.
Definition 1 (Linear-span (Nesterov) (003)), The class of online learning algorithms A with SGO feedback at each time generates sequence of variables ) according to
21+1
21
ar Vf(z))) d,, E R, eRi==,,.....
The above class of algorithms queries only a single gradient oracle each time step, and it covers many widely used gradient- algorithms, including gradient descent, accelerated gradient descent, etc.
The following theorem establishes the first lower bound on the local regret in online nonconvex optimization for all linear-span algorithms with SGO feedback defined in Definition!! [
Theorem 1. Consider any algorithm A that satisfies Definition [ and
and has access to a single gradient
oracle fi at each iteration. Then, for problems with the dimension d 2 S2(1 + Vr), there exist
(fr with function variation Vr (defined in eq. (2) and satisfying Assumption 7 for which
R(T) 2 (1++
Theorem shows that the hardness of the problem over any linear-span algorithm is entirely deter- mined by the function variation defined in eq. (2). i.e., the changes of the objective functions. the objective function ft is totally different from the previous functions, then all previous learning history not helpful, and the agent is forced to learn each ft from scratch. In such a case, the local regret must be I(T)). Nonetheless, if the changes of functions are small and scale sublinearly with T, it can be possible to achieve a sublinear regret.
As comparison, although the existing works (Hazan et al. 2017 Guan et al. 2023) provided lower bounds on the local regret that can instantiate to our setting of SGO (Hazan et al. (2017) Theorem 2.7) with bounds do not capture the impact of the function variation Vy. They are vacuous with the order of ((T).. In contrast, lower bound in Theorem 1 is tighter and problem-dependent by capturing how the function variation affects the hardness of the problem.
1 and Guan al. 2023 Theorem 1) with
and 0), their resulting lower
Proof Oulline of Theorem 7 The details of the proof can be found in Appendix A.1 The main idea of the proof is as follows. Given a total budget of Vy on the function variation, the objective function can have 2( + V7) times of rapid change. Thus, we divide the total time steps into 2 Vr) blocks, choose the same objective function within each block and change the objective function across blocks. We then construct series of functions whose gradients are orthogonal to each other and assign them to these blocks, which hinders the agent from constructing fz(zz) based on feedback from previous blocks. This construction of {fr) forces the agent restart the learning process in each block. The agent suffers from high value of [x:))( at the beginning of each restart, and thus the local regret is doom to be 2(1 + VT).
3.2 LOCAL REGRET OF ONLINE GRADIENT DESCENT
Consider the simple online gradient descent (OGD) algorithm described in Algorithm | which clearly belongs to the class of linear-span algorithms defined in Definition 1 At each iteration + 1, the OGD algorithm with constant stepsize > takes the update
Ft+1 Tt 1) V (x())
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 Online Gradient Descent (OGD)
Input: Initial point 21, stepsizes for t 1,.... do
Update J++1 based on eq. end for
Our next result shows that OGD achieves the local regret 0 + Vr)) for online nonconvex optimiza- tion, which matches the lower bound in Theorem I This implies that OGD is optimal in the class of linear-spar algorithms for online nonconvex optimization with SGO.
Theorem 2. Suppose Assumption 7 holds. Consider Algorithm
1 with initial point xı 0, and
1 stepsize yl 1,1 Then, we have (T): I Vr).
The proof of Theorem is included in Appendix A.2 The main idea is to leverage the Lipschitz smoothness of each objective function to connect the local regret to the cumulative difference
E Je+1 (F++1) fe( that is upper-bounded by Vr.
ONLINE NONCONVEX OPTIMIZATION WITH SSGO
In many practical online learning scenarios, the exact gradient feedback may not be available, and one has access to only noisy stochastic gradient oracles. Thus, in this section, we consider the setting where only single stochastic gradient oracle (SSGO) is available at each time step. We adopt the following standard unbiasedness and bounded variance assumptions on the stochastic gradient, which widely adopted in the online optimization literature (Agarwal et al. 2010 Flaxman al., 2005
Hallak et al. 2021 Hazan et al. 2017 Guan et al. 2023).
Assumption 2. For every I, the stochastic gradient ge(x) (as an estimator of the true gradient V (x))) satisfies that for all x E Rdd, E (g) = f+(x)) and [ [a(())) S oz where
o is the variance of the stochastic gradient feedback.
4.1 LOWER BOUND ON LOCAL REGRET WITH SSGO
We first establish a novel lower bound on the local regret of the class of linear-span algorithms defined in Definition in the nonconvex SSGO setting.
Theorem 3. Suppose that an algorithm A satisfies Definition 7 with V fe(zz) replaced by its stochastic version (x2)) Then, for problems with the dimension d 2 Ω VT(++ Vir) there exist {fe with the function variation VT (defined in eq. ②2) and satisfying Assumplion as well as (ge )
satisfying Assumption for which IE [P((T) N (o.VT(1+VVr)
Proof Outline of Theorem The detailed proof is provided in Appendix B.2 Rather than taking the sigmoid function as the basic example function the proof of Theorem [] we adopt the components of hard-to-learn function in offline nonconvex optimization (Carmon et al. 2021 Arjevani et al.
2022 to construct the hard case here, to capture how the randomness of the stochastic gradient can hinder the learning process.
Theorem 3 provides the first meaningful lower bound on the local regret for online nonconvex optimization with SSGO feedback. It captures how the regret scales with the variance of stochastic gradients, the number of iterations, and the function variation. The existing result only provides a vacuous ((()) lower bound by taking
1 in Guan al. 2023 Theorem 1).
Compared to the lower bound in Theorem for the SGO setting, the lower bound in Theorem is larger due to: (a) /T + Vr) 2 2(V)) because VT < O(T') and (b) the positive variance Ty. Hence, stochastic gradients cause the problem to harder than exact gradients.
4.2 LOCAL REGRET OF ONLINE STOCHASTIC GRADIENT DESCENT
In this subsection, we show that the standard online stochastic gradient descent (OSGD) algorithm achieves the lower bound the local regret in the nonconvex setting with SSGO feedback.

---

Published as a conference paper at ICLR 2024
Algorithm 2 Online Stochastic Gradient Descent (OSGD)
Input: Initial point 21, stepsizes for t 1..... do
Update J++1 based on eq. end for
At each 1, the OSGD algorithm (see Algorithm with constant stepsize v) > 0 takes the update 21+1 2; (2)(
where gr is the stochastic gradient that satisfies Assumption 2
Our lower bound in Theorem implies that the lowest possible regret for the class of linear-span algorithms expect is O (o,VT((1 Vr)) The following theorem shows that such an optimal rate for linear-span algorithms is attained by OSGD.
Theorem 4. Suppose Assumptions
7 and hold. Consider Algorithm with initial point æ1 and
stepsize 17 min
Then, we have 1E [P((T) S O (o.v(L+
27.1 4
Proof Outline of Theorem 4 The detailed proof is provided in Appendix B.3 The main step lies in decomposing the regret into the tracking error of the stationary points, which is bounded by O 1+Vr) ). and the variance of the stochastic gradient (by taking the conditional expectation given the history information) which is bounded by ), Then, the final regret bound can be obtained by the best tradeoff between the tracking error and the variance via the stepsize
Theorem 4 provides an upper bound on the expected value of the local regret. Next, we establish more refined characterization of the local regret with high probability guarantee. To this end, we first state the following boundedness assumption the stochastic gradient.
Assumption For any and x Rd, there exists constant G such that the stochastic gradient satisfies [[)]l))) s G almost surely.
Theorem 5. Suppose Assumptions 1
hold. Consider the OSGD Algorithm initial point j. Then, for any 0 < & < 1, with probability at least
J1 = 0 and stepsize min
1
1+Vr T
21a a
1 - we have R(T) < O (1, V-)T) + + (o,TTTloo (1/E).
Theorem 5 shows that the stochastic gradient feedback has a bounded norm, the local regret concentrates around its expected value with high probability.
Proof Outline of Theorem 5 The detailed proof is provided in Appendix B.4 Below we summarize our main proof steps. In the proof of Theorem 4 we have shown that conditioned on the filtration
F, (g1 ... 91-1(xx-1))) (z))]l - ((1((1 + 2(1 L(1-) Based on the (1 Li-n
Livo
above property, we can construct the following super-martingale sequence Zo O, and Z,+1 =
Z. - f(xx(( f((m))-((ee 21-Lım] It can be shown that [., Ze-1l is bounded by (1- (I-Tanly
Li
certain constant. Then by applying the Azuma-Hoeffding inequality to {Zr). we can obtain a high probability upper bound on the local regret.
5 ONLINE NONCONVEX OPTIMIZATION WITH SVO
In this section, we study the online nonconvex optimization problem with the agent having access to only single function value oracle (SVO) feedback each time t.
7

---

Published as a conference paper at ICLR 2024
5.1 ALGORITHM DESIGN
The setting with SVO feedback is much more challenging than the gradient feedback because with only a single function value, the gradient of the function cannot estimated accurately. The conventional one-point gradient estimator (Flaxman et al. 2005) has been used in online optimization and is also widely adopted in offline gradient-free algorithms. The performance of such an estimator is much worse than the standard two-point gradient estimator used previously in online optimization (Agarwal et al. 2010). Albeit the great performance gain, the two-point estimator cannot be used in our setting of S SVO because it requires two function value oracles at each time step.
Hence, our goal here is to design an online algorithm that requires only a single function value oracle, but achieves the same regret that of a two-point estimator. To this end, we design the following one-point gradient estimator based on the running difference of online function values:
(+(x)) = dus o (Je(ae + du)) It-1( + dut-1)),
where uy is drawn from the uniform distribution over unit sphere on Rd independently from history. Such an estimator uses the consecutive value feedback to construct a similar residual structure as the two-point estimator. Our idea is inspired by the one-point residual estimator proposed in Zhang et al. (2022) for offline optimization but has subtle yet critical difference. The one-point residual estimator duc de (fg, (Ia + 8uz) ( + 804-1)) where & and 5t-1 are two samples following the same distribution as the sampling variable Ç. Thus, both unbiased noisy samples of [e[ However, in our one-point running difference
in Zhang et al. (022) is given by V f((z)
fc, and Je. estimator, Jt and ft-1 are two online functions and can be very different. Their relationship is only captured by the function variation over time. This difference causes a significant difference in the theoretical analysis: our analysis relies on the function variation VT to bound the regret in online optimization, whereas the analysis Zhang et al. (2022) exploits the stochastic unbiased property of the two functions in offline optimization. Compared to the one-point estimator used in Guan jtt al.) (2023), our estimator does not skip updates in every other iteration and thus is much more sample efficient, We then propose an OGD-type algorithm (see Algorithm 3 for online nonconvex optimization with SVO feedback, which uses the one-point running difference gradient estimator given in eq. ( to update the variable.
Algorithm 3 OGD with One-point Running Difference Estimation
Input: Initial point 1 stepsizes and parameter 8
for ( = 1,...,7 TT do
Draw u, from the uniform distribution over the unit sphere and observe Se(x, + 8u;)
Let (xx) 1 (fe(r + dua) f + du,-1)) we
Let It+11 It 7/ f((e)
end for
5.2 REGRET ANALYSIS
As aforementioned, the technical analysis of Algorithm 3 online optimization is very different from the one-pont meint gradient residual estimator in offline optimization. In particular, our main technical development lies in providing novel upper bound on the magnitude of the one-point running difference gradient estimator regarding the function variation (see Lemma [T. With such a property, the local regret can be further bounded via the function variation.
Lemma 1. Suppose 17 and 5 are chosen satisfying 8/(4Lgd). For Algorithm 3 have
S - (
+ 4d
(f+(2))- (-lla))/--1(22-)" + 166
Proof Outline of Lemma] 7 The proof of Lemma I jis provided in Appendix C.I It mainly relies on two developments: (a) extracting the function variation from the form of the gradient estimator; and (b) constructing the contraction of gradient norms by selecting sufficiently small stepsize.
Applying Lemma 1
we establish the following upper bound the regret for Algorithm
8

---

Published as a conference paper at ICLR 2024
Theorem 6. Suppose Assumption 7 holds. Consider Algorithm 3 with initial point x1 0. per- turbation å v(1+ VT)/T and stepsize 7 6/(4Lod). Then, the expected local regret satisfies
E [()( & O(d/(1+ (v)))
The result in Theorem 6 indicates that our one-point running difference gradient estimator (when applied to OGD) achieves the regret lower bound that a generic stochastic gradient oracle can best achieve (i.e., Theorem 3), where the variance of our gradient estimator is at the order of (d²). We will also show below that our one-point estimator yields the same regret as the standard two-point estimator. Both of the above facts indicate that Algorithm achieves desirable regret performance.
Proof Outline of Theorem 6 The detailed proof is provided in Appendix C.2 Differently from the proof of Theorem the main technical development here lies in upper-bounding the bias and variance of our one-point running difference gradient estimator. More specially, the bias term satisfies
E V [F)
E fa + )u, [i] V Vets(ate), which can be shown to be bounded by
(0). The variance term has been bounded in Lemma Then, the tradeoff between the bias, the variance, and the tracking error of the stationary points via ò and provides the best regret bound. O
Comparison to standard one-point and two-point estimators: Previous online optimization studies (Flaxman et al. 2005) mainly adopted the conventional one-point gradient estimator, for which can be shown (see Appendix D.I) that the local regret of OSGD with such an estimator in online nonconvex optimization is bounded as E. [9((T) < ((d(1 + TT+) As comparison, Theorem 6 obtained by our one-point running difference estimator achieves much smaller regret (note that Vr scales most with the order of T, and can scale much slower than T). Furthermore, it can be shown that the local regret of OSGD with standard two-point gradient estimator (Agarwal et al. 2010) satisfies E [T) < O(dv(1 VT) (in Appendix D.2). Clearly, Theorem 6 shows that our one- ante-point estimator achieves the same regret as the two-point estimator. This the first result in online nonconvex optimization that establishes that one function value oracle achieves the same regret as two oracles.
Since Lemma 1 has already provided an upper bound on [++)( we can further obtain the following high probability upper bound on the local regret without making further assumption the norm of "gradient" as in Assumption
Theorem 7. Suppose Assumption 7 holds. Consider Algorithm 3 with initial point æ 0, pertur- bation (1 + V/T/ and stepsize n = 5/(4Lgd). Then, for any 0 < < 1, with probability at least 1 { we have RTT S O (d/T(L Vrr log()//))))) (1/E))
Proof Outline of Theorem 7 The detailed proof is provided in Appendix C.3 Below we summarize our main idea of the proof. In the proof of Theorem we have obtained the following bound:
V+)() < f((m)))(( + Lodō + LIEE
[ Fi]
7
Based on the above bound, we construct the following super-martingale: Yo O. and Y++1 + || (2 f((xe=1)- fe(ma) Lodō اسيي V (z We then construct sequence of scalar o such that a 2 |Y4+1 Yel. Finally, we obtain the probability bound on the local regret by applying Azuma- Azuma-Hoeffding Hoeffding inequality and upper-bounding Σ c.
6 CONCLUSION
In this paper, we investigate the online nonconvex optimization with single oracle feedback per time step. We take the local regret of original objective functions as performance metric and study three single oracle settings: with an (exact) gradient oracle, with a stochastic gradient oracle, and with a function value oracle. We provide the first regret lower bound for both the exact and stochastic gradient oracles, and we show that the online (stochastic) gradient descent can achieve the optimal local regret for the class of linear-span algorithms. For the setting with function value oracle, we propose one- noint rumning difference gradient estimator and show that incorporating such estimator into online gradient descent achieves a local regret that a generic stochastic gradient oracle can best achieve for the class of linear-span algorithms.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The work of Z. Guan and Y. Liang was supported in part by the U.S. National Science Foundation under the grants CCF-1900145 and CCF-1761506.
Y. Zhou's work is supported by the National Science Foundation under grants CCF-2106216, DMS- 2134223, ECCS- (CAREER).
REFERENCES
Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-pon point bandit feedback. In Proc. Annual Conference on Learning Theory (COLT), pp. 28-40, 2010.
Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Proc. Annual Conference on Learning Theory (COLT), pp- 18 29. PMLR, 2019.
Yossi Arjevani, Yair Carmon, John C Duchi. Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1-50, 2022.
Sergul Aydore, Tianhao Zhu, and Dean P Foster. Dynamic local regret for non-convex online forecasting. Proc. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
Xuanyu Cao and K. J. Ray Liu. On the time-varying constraints and bandit feedback of online convex optimization. In IEEE International Conference on Communications (ICC), pp. 1-6, 2018. doi: 10.1109/1C 8.4.2425599,,
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184(1):71-120, 2020.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II: first-order methods. Mathematical Programming, 1 185(1-2):315-355, 2021.
Amit Daniely, Alon Gonen, and Shai Shalev-Shwards Strongly adaptive online learning. In Proc. International Conference on Machine Learning (ICML). PMLR, 2015.
Ofer Dekel, Ronen Eldan, and Tomer Koren. Bandit smooth convex optimization: Improving the bari-veri tradeoff. Proc. Advances in Neural Information Processing Systems (NeurIPS), 28, 2015.
Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex optimization in the bandit setting: Gradient descent without gradient. In Proc-ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 385-394, 2005.
Xiand Gao, Xiaobo Li. and Shuzhong Zhang. Online learning with non-convex losses and non- stationary regret. In Proc. International Conference on Artifical Intelligence and Statistics (AIS- TA7S), pp. 235-243. PMLR, 2018
Dan Garber and Ben Kretzu. New projection-free algorithms for online convex optimization with adaptive regret guarantees. In Proc. Annual Conference on Learning Theory (COLT), pp. 2326- 2359. PMLR, 2022.
Alexander Gasnikov, Ekaterina A Krymova, Anastasia A Lagunovskaya, Inura Usmanova, and Fedor A Fedorenko. Stochastic online optimization. single-point and multi-point non-linear multi- armed bandits. convex and strongly-convex case. Automation and remote control, 78:224-234, 2017.
Ziwei Guan, Zhou, and Yingbin Liang. Online nonconvex optimization with limited instantaneous oracle feedback. In The Thirty Sixth Annual Conference Learning Theory, pp. 3328-3355 PMLR, 2023.
Eric Hall and Rebecca Willett. Dynamical models and tracking regret in online convex programming. In Proc. International Conference Machine Learning (ICMI), pp. 579-587. PMLR, 2013.
10

---

Published as a conference paper at ICLR 2024
Nadav Hallak, Panayotis Mertikopoulos, and Volkan Cevher. Regret minimization in stochastic non-convex learning via proximal-grade approach. In Proc. International Conference on Machine Learning (ICML), pp. 1008-4017. PMLR, 2021.
Elad Hazan and Comandur Seshadhri. Efficient learning algorithms for changing environments, In Proc. International Conference on Machine Learning (ICML), pp. 393-400, 2009.
Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization in non-convex games. In Proc. International Conference on Machine Learning (ICML), pp. 1433-1441. PMLR, 2017.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- fion, 2(3-4):157-325, 2016.
Amélic Héliou, Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Online non-convex optimization with imperfect feedback. Proc. Advances in Neural Information Processing Systems (NeurIPS), 33:17224-1777 17235, 2020.
Amélie Héliou, Matthicu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Zeroth-order non- convex learning via hierarchical dual averaging. In Proc. International Conference Machine Learning (ICML), pp. 4192-4202. PMLR, 2021.
Steven CH Hoi, Doyen Sahoo, Jing Lu, and Peilin Zhao. Online learning: A comprehensive survey. Neurocomputing. 459:249-289, 2021.
Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pp. 398-406. PMLR, 2015.
Yeongjong Kim and Dabeen Lee. Online convex optimization with stochastic constraints: Zero constraint violation and bandit feedback. arXiv preprint arXiv:2301.11267, 2023.
Walid Krichene, Maximilian Balandat, Claire Tomlin, and Alexandre Bayen. The hedge algorithm on continuum. In International Conference on Machine Learning, pp. 824-832 PMLR, 2015.
Antoine Lesage-Landry, Joshua A Taylor, and Iman Shames. Second-order online nonconvex optimization. IEEE Transactions on Automatic Control, 66(10):48664477) 2020.
Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 7195-7201. IEEE, 2016.
Julie Mulvaney-Keng SangWoo Park, Ming Jin, and Javad Lavaei. Dynamic regret bounds for con- strained online nonconvex optimization based on polyak-lojasievv regions. IEEE Transactions Control of Network Systems, 2022.
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-fre free minimization of convex functions. Foundations of Computational Mathematics, 17:527-566. 2017.
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv: 1912:119...33213, 2019.
Ankan Saha and Ambuj Tewari. Improved regret guarantees for online smooth convex optimization with bandit feedback. In Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pp. 636-642. JMLR Workshop and Conference Proceedings. 2011.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 107) 2012. ISSN 1935-8237. doi: 10.1561/2200000018 URL
http: /ttp://dx doi, www.oogg///.. 10. 1561 1ttp://001116222200000000000 220000011
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research (JMLR), 18(1):170317733, 2017.
11

---

Published as a conference paper at ICLR 2024
Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Algorithmic Learning Theory, pp. 845- 851. PMLR, 2020.
Cong Wang, Shengyuan Xu, Deming Yuan, Baoyong Zhang, and Zhengqiang Zhang. Distributed online convex optimization with bandit primal-dual mirror descent push-sum algorithm. Neuro- computing, 497:204-215, 2022.
Lin Yang, Lei Deng, Mohammad H Hajiesmaili, Cheng Tan, and Wing Shing Wong. An optimal algorithm for online non-convex learning. Proc. of the ACM on Measurement and Analysis of Computing Systems, 2(2):1-25, 2018.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl Henrik Johansson. Distributed bandit online convex optimization with larying coupled inequality constraints. IEEE Trans- actions Automatic Control, 66(10):4620 463652200466-,, 2020.
Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. Proc. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
Lijun Zhang, Tie-Yan Liu, and Zui-Hua Zhou. Adaptive regret of convex and smooth functions. In
Proc. International Conference on Machine Learning (ICML., pp. 7414-7423. PMLR, 2019.
Yan Zhang, Yi Zhou, Kaiyi Ji, and Michael Zavlanos. new one-point residual-feedbate oracle for black-box learning and control. Automatica, 136: 10006, 2022.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. Proc. Advances in Neural Information Processing Systems (NeurIPS), 33:12510-12520, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proc. International Conference on Machine Learning (ICML), pp. 928-936, 2003.
12

---

Published as a conference paper at ICLR 2024
Supplementary Materials
A PROOFS OF SECTION
In this section, we provide the proof' for Theorems 1 [nd 2 in Section
A.1 PROOF OF THEOREM 1
The main idea of the proof is as follows. Given a total budget of Vi on the function variation, the objective function can have 92(1 + Vr) rapid changes. Thus, we divide the total time steps into (21 VT) blocks, choose the same objective function within each block and change the objective function across blocks. We then construct series of functions whose gradients are orthogonal each other and assign them to these blocks, which hinders the agent from constructing ff(()))) based on feedback from previous blocks. This construction {ft)= forces the agent to restart the learning process in each block. The agent suffers from high value of ft at the beginning of each restart, and thus the local regret is doomed to be 92(1 + Vy))
To present the detailed proof. first specify the objective functions for each block. Define the one-entry sigmoid functions as
cexp([x]))
fu(x) 1 exp((x]&))
where e > O is a constant that will be determined later, and [z] is the k-th entry of the vector Clearly, we have, 0 < [x( S and
cexp ((x)))) (1 + exp ([z)k)) Ck
(f(())=
with ex is the kth basis of the Euclidean space. Then we have, for every and y,
[ia(x)) jx(x)) s sup [f((t))
zERd
and
V3c
[V/((x)- -VA(() <
|| yll-
18
Therefore, by taking
6/33)) each (x) satisfies Assumption
We now divide the total T iterations into 1+Vr 2 blocks, and let B cT each block. Within each block, we fix the objective function, i.c., for all k;
be the length of
1r+1
((=)))++(()) = J(- ((N-1)B42(0)= = fkn(()) = fx(x).
Thus, due construction, have
1+Vr -2
V
sup
- - Σ
sup [fxc4(()) fax(x))
2
ZERd
seRd
Vr -2 S Sv- VT-
Due to our construction, for the k-tth block, the gradients received from the previous block reveal only the first & dimensions. Thus, by Definition [πжB+1]* 0 for all k. And we have
Therefore, we have
14
T
- 2
R(T) = Σ 22))
Σ
=Ω(( + VT).
13

---

Published as a conference paper at ICLR 2024
A.2 PROOF OF THEOREM! 2
The main idea for this proof is to leverage the Lipschitz smoothness of each objective function to connect the local regret to the cumulative difference Σ Sc+ (2++1) f((+++1) that is upper- bounded by Vr. By the -grgddientt Lipshitz condition of ft( we have
L1 | x1ll²
f((x++1) - f((z)) ( 2141
rz) +
@ f((1))
17 L11
[(())) 2L, [[
(8)
where (i) follows from the update rule in eq. and (ii) follows because L.
Rearranging eq. (8 and telescoping, we have
RTT) fx))))l
$ 2L, Σ (fe(xz) - fe(x441))
=f11(1 (r+1(ET+1)) + 2L, - fe(x++1))
4I, M 2r,
where (i) follows from the upper bound of the function value and the definition of Vr.
B PROOFS OF SECTION 4
In this section, we first introduce the hard-to-learn nonconvex function constructed by Carmon et al.) 2020)) This function is utilized next in the proof of Theorem 3 We then provide the proofs of Theorems to
B.1 HARD-TO-LEARN NONCONVEX FUNCTION
In Carmon et al. (202)), the authors constructed a special nonconvex function that is hard for gradient-based algorithm to learn. The function Fx : R + IR is defined as
Fx(x) - ((1))(())))))))
Σ 1=2
( [x]+) ((=))))))(())))
(9)
where K is certain integer, [x:] denotes the ith entry of and the (2) and (22 are defined
1/2
(2)
exp 1 -
1/2
(2z 1)2
and
I exp (-1
t2
((2) = Ve
The hard function satisfies the following properties (Carmon et al. 2020
Fx & 24K
(10)
V Fx (x) < 23V
(11)
Fx FFx(1)) 152 vll-
(12)
14

---

Published as a conference paper at ICLR 2024
B.2 PROOF OF THEOREM! 3
Rather than taking the sigmoid function as the basic example function in the proof of Theorem adopt the components of the aforementioned hard-to-learn function in eq. ( to construct the hard case here, to capture how the randomness of the stochastic gradient can hinder the learning process.
| we
We divide the iterations into blocks with size B, and we set B 2M(T+1)
Denote Ta to be
1+Vr
k-th block containing the iterations (I: 1)B (k + ...., kB. Moreover, the objective functions ft within Tk+1 are fixed to be a same function (x). i.e. for all k
fxB+1(x) fxB+2(x) -.. - fx+1)n(()) fa(x),
where (z) is defined as fx(
[2) ((B+
=C
(1)
K
+ +c
M (-[x (( ((( - [[(==
1=2
(13)
where Li X = VR min 152L.
19M
and K is an integer satisfying
[o]
B.
152
23T,
3
Moreover, [xr]; denotes the i-th entry of xr and [ar] (3.....) denotes the (b - a + 1)-dimensional vector
consisting of the entries [æ]a...., [x]]
We now verify that (x( satisfies Assumption 1 Using eq.
10 we obtain
(1k- ((k
2
Cx² CX²FK
I
cx² < M.
(14)
A
4
Next, by eq.
we have
v Fx
11 kB]
)) =cx VFk
[2){((- ((
A
23cv K2 < Lo.
(15)
which implies the LopLishchitz continuous property.
Moreover, by eq.
12 obtain
[z] ([((K-))B+1....... )) v (cPPFK (11((--1)B4.....B)
v
FX
X
X
[2]] [2k [(k--))++1,......
[u](4-1))++1,...G 1).
cA VFK
VFK
X
X
< 152c|| x yll
< 1.1l= | -|1-
(16)
The eqs. (44) to 16 prove that every ft satisfies Assumption] I
We next show that our choice of the length B of each block ensures that the function variation does exceed Vr. The function variation V of our construction is upper-bounded as follows:
T B
V
Σ sup ()-1(x)) ZeRd
Σ
sup [sK*+( - fax(x)) 2M SERA
where (i) follows from eq. 14 Since set B
2M(T+1)
have Vif Vp. And, the choice
I+V
of K is determined immediately by the relationship
[ B.
15

---

Published as a conference paper at ICLR 2024
Lastly, we let the stochastic gradient oracle gr (2) be
1 (1+1 projy (z) (+t -1)))
[g. = [Vf((z)),
(17)
where proju (2:) == max (iz 0| |<>||| 2 1). and 21 Bernoulli(p) with p min 1,
23 2
of
Clearly (x(x)) is unbiased and, by Arjevani al. 2022 Lemma 3), the variance of (x( is smaller
than og. Hence, the construction of St (z) here satisfies Assumption 2
Based on our designed functions Se and the stochastic gradient oracles gt. we next prove the regret lower bound. At each block k, the stochastic gradient oracle feedback obtained from the previous k 1 blocks all lie in the first (k- 1) dimensions of z. Therefore, due to Definition [ we have 0. And the objective function within the k-th block depends only on the (k: - 1)K + 1-th of x up to its KK-th entry. Thus, the optimization within the k-th block equals the
[ (()) +1, t)..kk
offline optimization with total K iterations of updates. Applying Arjevani et al. (2022) Lemma I),
with probability greater or equal to 1. for all KB + S S kB + min
K (2g
B we have
2p
1
V 2 c² = =
(18)
K
We then conclude from eq.
(8) that
B
- log(2) (llog(()
E
2
min
= 22 (o)
(19)
K
2p
We next derive the following bound on the expected value of the local regret:
T
E [P((T)] = E
[V)(())
B
K
V (x)1
T+1
()2KK)
B
D(O,vT(1++)
(20)
where (i) follows from eq. 19
B.3 PROOF OF THEOREM
The main step lies in decomposing the regret into the tracking error of the stationary points which is bounded by O [+ and the variance of the stochastic gradient (by taking the conditional
expectation given the history information) which is bounded by O (mo))) Then, the final regret bound can be obtained by the best tradeoff between the tracking error and the variance via the stepsize 1/.
To proceed the proof, following from the I I-ggrddient Lipshitz condition of fe(a)), we have
Ta
fe(xe41) S f(())) + (Vf((z)) -x,) +
| - 22112
2
① f(( (V + Lnn
ll0x(x))112
2
- - (V) g.)) (z:)) + L [|g Lnn"ll (x(x)) Lnd' (21)
where (i) follows from the update rule in eq. (4) and (ii) follows from the Young's inequality.
Taking expectation conditioned on 2y on both sides of eq. (1 and applying Assumption we have
F. (f(+ S fe( 1y (1 Tan) [x:(())) + Lunz003
(22)
16

---

Published as a conference paper at ICLR 2024
Taking expectation eq.
rearranging and telescoping, have
IB (T(T))
r
E [ - f((0-11]] 1002T
11
L1n)
Li"I
1=1
E (f+1((144)) s((e241)) + 11o5
E (f(( (T+1(FT-1)) +
1111 - -in))
L1
t=1
- L11) (2M + 2V7) + TooT
1
(23)
Li
where (i) follows from the upper bound of the function value and the definition of Vr. Applying the definition of 17, we complete the proof.
B.4 PROOF THEOREM
Define sequence of random variable {Z, ) as
Zo =0 0 and Ze+1 Zz + f1(1441) fe(et)
+ (1- (() Lino
"
Define F, = 02,... Due to eq.
(22h.
we have
E
| S Zz.
Moreover,
f(( - fe(xt)
Ze+1 Zi|
+1 Ln) Ln) nn
17
(1) < LoG + 1, ag
where (i) follows because
[f(( - fxx)) s Loll=, æ++1l = (a)) S LoGn, and [[((()) s LJ. and 17 S o,"
Therefore, { is super-martingale with a bounded difference. Applying the Azuma-Hoefdding inequality Zr-1, we have
Pr Pr Zo 2 c) 2exp
2T + Li MyL
By taking
/ 2T + L3 M) log ? we have, with probability greater or equal to
1 1-6,
ZTT1 S |2TLLOC+ + L togbMM log
2
Using the definition of Zr+1 and rearranging the terms, we have, with probability great or equal to 1 g
T
R(T) = Σ 2x)111
E
1
1
T
2
<
(2M 2Vr) +
2T Li
o,LIM)22og log
1/(1 Lin)
Lim
Lin
Substituting the definition of y into the above inequality completes the proof.
17

---

Published as a conference paper at ICLR 2024
C PROOFS OF SECTION 5
C.I PROOF OF LEMMA 1
We upper-bound the variance term [0;))1 defined in eq. (5) as follows.
d²
52 (felae + ((4) - (221 + --bu,11)
d² (Jelor + δus) (1( + [((xz) - (c-1(1r) S(-1(1)) - (2-1(10-1)
82
f - 1 (du
4d
(fel1e duL) f1(2)))2 + 4d
4d
(f((21) - - (f- -o-1(
4d
+ 82
1 f1-1(1111 + d1)=1))²
1|
4d
8z (f((z)) fi-1 &d
(24)
82
where (i) follows because Se and fi-1 -op-hipcc continuous, and n.. -c-1 =
5 have 1Lzd2n²
Since 77 TLod
Iteratively applying eq. (44 obtain
1 1 [ S
||
||+
4d
Σ
(f+(x+) J 1 + 16d
(25)
82
2
C.2 PROOF OF THEOREM 6
Differently from the proof of Theorem 4 the main technical development here lies in upper-bounding
the bias and variance of our one-point running difference gradient estimator. More specially, the bias
term satisfies E (..)) = E [ fe( + (ue))uee2 [F:] = fr,((r)), which can be shown to be bounded by (8)). The variance term has been bounded Lemma ! Then, the tradeoff between the bias, the variance, and the tracking error of the stationary points via 8 and provides the best regret bound.
To proceed the proof, following from the Lipschitz-smooth condition, have
L1
f((x++1) fx (Vfi. z1)
|| xell?
2
=f((=))-\\V(( (z,)) + (xx)) 112
(26)
Taking expectation on both sides of eq. 26 conditioned on F, = o (u),... up 1), we obtain
E [f((4())
$ f((( 17 (..(( E (1.))) (V
L1n² E. [[
L17²
-((x)) - V. (z.)) + E {((())) Fi]
v)((za))
V
(xx)))
2
2 f(())) V.A 2 + 70 |E f((())) Fi - ((t(
Lin² E
||
|
fx
2
Fi
2
( ((la)>~\\f[(()))))
&
Loddnn
Lid E
[ F..]
(27)
2
where (i) follows from the Cauchy-Schwartz Schwartz inequality and because follows from the following Lemma
[/ & Lo. and (ii)
18

---

Published as a conference paper at ICLR 2024
Lemma 2. For every t, we have
I,d8
E fe(s))) Fi] Vielaee
2
Proof. Using the definition of V (122), we have
E
f (Ix) F. (.ae(
due
Si J1 dut) Fz (((((e))
5
(
IF
du
(Je( + -w+) -fe 8(,)) -dd dd me) Ft
28
[f((z + due)
ff(ex 8uL). (V.i(
8
Ut
(6))
Ló
2
where (1) follows from Agarwal al. (2010 Lemma 7) and (ti) follows because ( gue)
f((x)) + (Vfe(z)), < 1,5-
[f ou:) f((xx) + (Vii(z,), I 4,0- and 2
2
fe(x + 8we) Se(vz dut) (Vfe(ze)
fe(Ee + 8ue) f((xx)
(((xe-du)) f((())) + (Vr( Sun)
2
2 duc)) [e(exx (dus) fe((xe) + (V (Vle(())
Selate + 8vc) Se(xx) (V
2
2
Rearranging eq. (27 we obtain
T Lod
TA E
(x:))l s 7
(fi(z)) DE (F(
(28)
2
2
Taking expectation on both sides of eq.
28 and telescoping, obtain
LoTTT
L
E (TT)
< 17
(ff( f((
E
V fzo)2
(29)
To upper-bound the last term of eq.
we take a summation of eq.
25 over
1 to T and obtain
T < |
T
4d
T
(F - f--1(xx)))
+ 16d 16TT
2
82
21-7
Am rm1
4d
T Σ
T-t
2 ((((z))
(fe(xe) fr- 1
Σ T=0
27
+ 16d 16d2LL
82
t=1
Sdf T
2
v
fo(o))
(f(()) -f(())))f-(()))) 16d L3T.
(30)
82
Substituting eq.
30 into eq.
29
we obtain
T
E [x())) - f((+++1]] + Lo
E (R(T) <
+ L Linll fo(o)))
2
19

---

Published as a conference paper at ICLR 2024
4Lnnd T
+ 81, LindT
+
-
8
t=1
(11) - (141(2
1
[ - ( [(( LuddT
IF
"
2
t=1
Abind
[oloo\ + 8L, 8L, LLId
+
(z-)))))
82
(
2M
VT
LL
LL 44
SM
+
+
(31)
17
2
82
8²
where (i) follows because
2Md and
T - -
s 2M
Σ
S(- S 2MV..
Substituting the definition of 7 and 8 into eq.
31 we obtain
E E S o o
C.3 PROOF OF THEOREM 7
Define a sequence of random variable {X,)==1 as
V. = and Y4+ = Y + [ f((x+11) - f((xs)
Lod
L
(x))))
2
2
Define the filtrations F. ( vz). By eq. 28 we have (Y,) is super-martingale. Moreover,
we have
M4 Vıl = [V)((=)))1 f((1111) - fe(x))
Lg
Li
"1
2 2
[ Lol Ld(xa)
Lodō
Lnd
( == cc.
+
2
where (i) follows because [[:)((x))] < Lo and
fe(x41) fe(x,) I Tol - xell = Lool V St f((x))ll-
Applying the Azuma Hoefffdig inequality to Yr41, we have, for every e 0,
e²
Pr (Yr+1 5
(32)
Σt=
2
We next provide an upper bound on Σ
1t=1 ct.
Lo
L1 | {((x)))))))
Li Lo (o11
2
(4)
f.((1)) + +1L Lim Σ (16f((x)))P))
< ALAT + 4L3
2
(1) x 4L7T 4L2 Σ
1371 Σ f()())))1
(33)
where (i) follows by applying (a + b+ c + d)2
< 4a + 4b2 + 4c² + 4d to every term in the
summation, and (ii) follows because Σ 1
EE )2 when 's are all positive.
20

---

Published as a conference paper at ICLR 2024
Applying Lemmal] 1 we have
4d
(fr()+) ff-11(z)))
vf(()))] - (i)
+ 16d 16d
21-1
82
20-
1=
d
4d
T
Σ
(
+ +1dd L2gT
82
21-
1=1
4M2
MVT
+ 16d T6TTTT
82
8²
16d (Tu) + M2yT,
(34)
where (i) follows from the facts that 8 = - 1+ and Vr S MT.
Substituting eq. 34 into eq. we obtain
1612
c S(L + 64T + M³)JT 1 VT)) +
d d M3) + Vr).
I
Therefore, there exist constant C' such that
Σ cdcCPT(+Vs))
(35)
Substituting eq. (35) into eq. (32) and taking v CCPT(11 + Vr) log (2) we have, with probabil- ity greater or equal to E
YT+ S CT(1 VT) log
2
(36)
Substituting the definition of Y into eq. (36) and rearranging, we obtain, with probability greater or equal to 1 -
R(T)
t=1
2M
VT
4T,d2
8M
+
+ 8L, Innd
n
82
82
2
d
CT(1 Vir) log
=o =0(0 dg T(1 + Vog
log
(37)
D CONVENTIONAL ONE-POINT AND TWO-POINT GRADIENT ESTIMATORS
In this section, we introduce the conventional one-point and two-point gradient estimators, and provide the corresponding regret bounds if these estimators are adopted by OGD. These results serve as comparison to the new running difference gradient estimator that we propose in Section
D.1 REGRET OF CONVENTIONAL ONE-POINT GRADIENT ESTIMATOR
Consider the following one-point gradient estimator (Flxxman al. 2005), which has been used in online convex optimization and is also widely adopted in offline gradient-free algorithms.
d f(())) = z f( + bu.
(38)
21

---

Published as a conference paper at ICLR 2024
where u, is drawn independently from the uniform distribution over the unit sphere in R It has been shown that
V fe(zz) = V1t
where f2, [e 5u)] with be uniformly distributed the unit sphere. Although the expected value of such a one-point gradient estimator is close to the true gradient, i.e.,
[[V\(=)] - (=(())l = ( - (+)()) < 1,5,
its variance explodes in the order of (++)). The trade-off between the bias and variance prohibits show below that the regret of OGD with such one-point
us choose small 8, and hence
gradient estimator can be large.
Consider the OGD algorithm with the above one-point gradient estimator described in Algorithm The regret of such an algorithm is characterized in the following theorem.
Algorithm 4 OGD with Conventional One-point Gradient Estimator
Input: Initial point 21, stepsizes 7) and parameter 8 for t= I,...,7 do
Draw u, from the uniform distribution over the unit sphere
Observe (x+ 5u,) and let fe(x)) % fe(ee + 8u4)
Let F++1 It 7/ fx(ss)
end for
Theorem Suppose Assumption 7 holds. Consider Algorithm with 2o 0, perturbation
8 (= and stepsize 1) = à ( & Then, the expected local regret satisfies
TF (R(T)) & Odd(1 + Vr)
Clearly, the regret of OGD using the conventional one-point gradient estimator much larger than that of OGD using our running difference gradient estimator given in Theorem 6 (note that Vy scales most with the order of T, and can scale much slower than T)). The main reason is because the conventional one-point estimator has a much larger variance and hence the tradeoff between the bias and the variance requires much large perturbation parameter 5 which is chosen to be ( (1+Vr) ) This consequently leads to a worse regret than our one-point estimator.
By the Lipschitz-smooth condition, we have Proof of Theorem g
L
f((x+11) < f((x,) + (V)(())) .xe)
|| sell2
2
Lnd²
=(((x,) - 7/ (z.), (xx))) +
2
S - ([] + n (x)) V/(())) - {(()))) L L
(39)
282
Rearranging and taking expectation on both sides of eq. 39 conditioned on F, = o(u1,..., U we obtain
(6) f((z,) - EE [f(( (V)( Vf((x)) Ve,((1))) Lid2M2
<
11
282
(xx)) IE [
do Lid
(40)
1
252
where (1) follows from the steps similar to those in the proof of Lemma 2 and (ii) follows from the Cauchy-Schwartz inequality, and because [v,)( < Lu. and V Ves(())) < L1ō.
Taking expectation on both sides of eq. 40 and telescoping, we obtain [F())(T))
22

---

Published as a conference paper at ICLR 2024
T
E [(
f1(11) - E (fr+1)
1
T
LoL1doT
M2
([ - fe(xa))
IF.
?
2
28
t=1
2M + VT LaLndöT
17
25
2 O(d(1 + ++))+
D.2 REGRET OF TWO-POINT GRADIENT ESTIMATOR
Although the two-point gradient estimator is not applicable to our setting with only single function value feedback, it serves as a desirable comparison benchmark for our designed one-point estimator: In the literature, the standard two-point gradient estimators have been shown achieve much better performance than the conventional one-point estimator as well as recently developed one-point estimator in Zhang et al. 2022) in both online and offline optimization. In this section, by establishing the regret of OGD with the standard two-point estimator, we will show that our running difference one-point estimator can achieve the same performance as the standard two-point estimator.
Consider the standard two-point gradient estimator (Agarwal et al. 2010 given as follows:
f((x)) = 5 (fe(az + dwe) - fx()))
(41)
Compared eq. (38 the two-point estimator in eq. 41 has the same expected value, but its variance
bounded by LEF which much smaller.
Now consider OGD with the above two-point gradient estimator described in Algorithm The
regret of such an algorithm is characterized in the following theorem.
Algorithm OGD with Standard Two-point Gradient Estimator
Input: Initial point æ1, stepsizes 7 and parameter 8
T fort= = I,...,T do
Draw ue from the uniform distribution over the unit sphere
Observe fi; + du;) and fe(1z)
Let (x.) = du
3 (f( + 5u)) fe(x))
Let Fe+1 He fa
end for
Theorem 9. Suppose Assumption holds. Consider Algorithm with Zo 0, perturbation
5 1tVr and stepsize 1) à VV T
+Vr T Then, the expected local regret satisfies
E (P(T)) S O(dv(1+
Clearly, comparison of Theorem 6 and Theorem shows that our one-point estimator achieves the same regret as the two-point estimator, and they both outperform the conventional one-point estimator. This is the first result in online nonconvex optimization that establishes that one function value oracle achieves the same regret as two oracles.
Proof Theorem By the Lipschitz-smooth condition, we have
I | - 1111
L
[((x++1) f((x)) (V]((z)) x441 xz)
Ln
-f((z) - -((x)))(([(()))) vf(za)) + 2
23

---

Published as a conference paper at ICLR 2024
Vf((a) Vf((z))) + LI
S -
(42)
2
Rearranging and taking expectation on both sides of eq. 42 conditioned on F, = o(u we obtain
[Vf(<>))1? < [t( IF. (F(((())))) (V)((.)), Vfr(()) - V)) + In
2
[x())) - (1 + 2 + Lo
LoLidö
(43)
"
2
where (i) follows from the steps similar to those in the proof of Lemma and Cauchy-Schwand inquality.
Taking expectation on both sides of eq. (43) and telescoping, we obtain
E (())
T
Σ
E [I ff(
f1(21) EE lfr (IT+1)]
Σ E (f+1( - f((x)) + LoL1döT LLLidnII
7
2
2
sO(dvT(L+Vr)) VT)).
24


Reviews:
[{"review_id": "dYZhamMxKU", "reviewer": "Reviewer_xXV1", "summary": "This paper studies minimizing the local regret in online non-convex optimization. Previous work mainly focus on smoothed version of regret, and show the **worst-case** local regret with window size 1 is linear with respect to T. In this paper, the authors reveal that, both upper bound and lower bound in this setting can be better, as they can depend on the total function variation. The authors consider several different settings in ONCO with different oracles, such as sgo and ssgo, and show matching function-variation-dependent lower and upper bounds.", "questions": "In online optimization, apart from function variation bound, there are also other measues for function changes, such as the gradient variation bound. Is it possible to also 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 [1], for more information. \n\n[1] Chiang, C. K., Yang, T., Lee, C. J., Mahdavi, M., Lu, C. J., Jin, R., & Zhu, S.. Online optimization with gradual variations. In Conference on Learning Theory, 2012.\n\n> Introduction: One line of work adopted the global regret as the performance metric (Krichene et al., 2015; Agarwal et al., 2019; Lesage-Landry et al., 2020; Heliou et al., 2020), which compares the algorithm output to the global minimum of the nonconvex objective functions. However, accessing the global minimum of nonconvex functions is typically infeasible.\n\nI don't understand this discussion. 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\"?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Significance and novelty:\n\nThe main idea is quite novel and very interesting. In recent several years, there have been a lot of work on studying the local regret. However, all of these work use smoothed version of the loss function (i.e., the average of a batch of functions in a window) when computing the regret, and people typically believed that using the exact function (that is, with window size 1) will lead to a \\Omega(T) regret. However, these bounds are actually worst-case bound, and do not depend on data of the loss functions themselves. That is to say, there must exist simple cases where the regret is sublinear. In this paper, the authors captures this by showing a data-dependnt lower bound (function variation bound) and matching upper bound. This is the first paper that shows both sublinear lower and upper bounds for online non-convex optimization with local regret with window 1, which is a significant and novel contribution, and may inspire future works. \n\n\nThe proof for the upper bound is relatively straightforward and brings to mind what people do when obtaining the function variation  bound  for dynamic regret. The proof for lower bound is much more challenging and require novel techniques.\n\nPresentation: The paper is in general well-written, and easy to read.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y8mtnxH2hs", "reviewer": "Reviewer_sA6m", "summary": "This paper studies online-nonconvex-optimization (ONO) problem with local regret. Unlike previous works that focused on window-smoothed loss of the form $F_t(x)=\\frac{1}{w}\\sum\\_{i=t-w+1}^t f_i(x)$, this paper directly addresses local regret using the original losses, namely $\\mathrm{Regret}\\_T = \\sum\\_{t=1}^T \\\\|\\nabla f_t(x_t)\\\\|^2$ (which corresponds to setting $w=1$ in the window-smoothed definition). Moreover, the paper focuses on single oracle algorithm where, in each iteration, the algorithm can only request one oracle query. Specifically, three oracle models are analyzed in this work: 1. deterministic gradient oracle (SGO) that returns $\\nabla f_t(x_t)$, 2. stochastic gradient oracle (SSGO) that returns an unbiased estimator of $\\nabla f_t(x_t)$, and 3. function value oracle (SVO) that returns $f_t(x_t)$. For the first two oracle models, the paper presents a tight analysis, providing both upper and lower bounds. For the third model, the paper offers improvements over existing state-of-the-art results.", "questions": "1. 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? \n\n2. 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_1 + \\sum\\_{i=1}^t a_{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?\n\n3. proof of Lemma 2 first two equalities: where does $d$ out side $\\\\|\\mathbb{E}...\\\\|$ come from? is it a typo?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper offers a thorough examination of the ONO using single-oracle algorithms. I'd like to highlight a few standout results:\n\n- While previous results of ONO with local regret consider window-smoothed approximation $F_t(x)=\\frac{1}{w}\\sum\\_{i=t-w+1}^t f_i(x)$, which may vary a lot from the original loss, this paper works directly on original losses and thus providing a more accurate regret bound.\n\n- The algorithms studied in this paper only makes one single oracle query in each iteration, while most algorithms in prior works require multiple oracle queries due to window-smoothing.\n\n- This paper provides comprehensive analysis for 3 different oracle models. Specifically, it provides lower bounds for the gradient oracle models and proves that online subgradient descent achieves the optimal lower bounds in both cases. \n\n  Moreover, for the function value model, this paper proposes a single oracle algorithm, matching the state-of-art regret bound which is previously achieved by an algorithm making two oracle queries per iteration. The idea of one-point estimator using running difference of function values instead of the standard two-point estimator is novel and interesting.\n\n- What stands out to me the most is the notation of \"function variation over time\", namely $V_T = \\sum_{t=2}^T \\sup_x |f_t(x) - f_{t-1}(x)|$. Similar to the notation of path length in dynamic regret, function variation is also an adaptive measure that captures the difficulty of the ONO problem. Therefore, the proposed regret bounds in this paper (namely $O(1+V_T)$ for SGO, $O(\\sqrt{(1+V_T)T})$ for SSGO, and $O(d\\sqrt{(1+V_T)T})$ for SVO) are always tighter than the previous vacuous bounds in the corresponding settings.\n\n  I also find it interesting how $V_T$ naturally follows from $\\sum\\_{t=1}^T f_t(x_t) - f_t(x_{t-1})$ in the smooth loss analysis, and it just happens to be a tighter measure.", "weaknesses": "The lower bounds for SGO and SSGO models are restricted to a relatively small family of algorithms such that $x_{t+1} = x_1 + \\sum\\_{i=1}^t a_{t,i} g_i$. This family does not include popular algorithms like online mirror descent and FTRL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fEMYCQJu9c", "reviewer": "Reviewer_qRqP", "summary": "This paper studies the online nonconvex optimization problem, where access to only a single oracle is allowed per time step. The authors consider three variants: single gradient oracle (SGO) feedback, single stochastic gradient oracle (SSGO) feedback, and single value oracle (SVO) feedback, and take the local regret of the original objective functions as the performance metric. For SGO and SSGO, they derive lower bounds on the local regret and show that the classic online algorithms are already optimal. For SVO, they develop an online algorithm based on a one-point running difference gradient estimator, which achieves a local regret that a generic stochastic gradient oracle can best achieve.", "questions": "- Can the lower bound analysis extend to the general setting of sliding windows? E.g., for a fixed window length $w$, is $V_T$ still appear in the regret bound?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The online nonconvex optimization problem is interesting and relevant.\n- The three proposed variants are practical and meaningful.\n- The theoretical results are standard, specifically, indicating the importance of parameter $V_T$.", "weaknesses": "- I would like to see more comparisons and discussions on three variants, specifically, when we need to consider SGO/SSGO/SVO.\n- There is no matching lower bound for the SVO problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2vHQ3FFNnt", "reviewer": "Reviewer_e2ZJ", "summary": "This work studies the problem of online nonconvex optimization with single oracle feedback. More specifically, the authors consider three setups of the single oracle: single exact gradient feedback, single stochastic gradient feedback, and single function value feedback. The authors choose local regret on the original function, not on the smoothed version of it as previous works, as the performance measure. The key contribution of this work is that the authors find that the problem-dependent quantity of function variation is a fundamental variable in this problem. Specifically, in the first two cases, the authors give two corresponding lower bounds regarding the function variation for the linear-span algorithm family. And they prove that OGD and OSGD are optimal inside the linear-span algorithm family. In the functional value feedback, the authors use a new running difference gradient estimator and obtain an optimal result inside the linear-span algorithm family. Note that the result under the function value feedback with one-point running difference gradient estimator is as good as that using a two-point gradient estimator.", "questions": "1. 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?\n2. 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 $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 $O(T^{3/4})$ regret? If not, what is the key difficulty?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The overall paper is well-written. The problem is well-motivated, and the descriptions of the three cases are well-explained with proof sketches. The observation of the role of function variations in this problem is important and may lead to novel perspectives for this problem for future research.", "weaknesses": "I have only one major concern, which affects my score for this paper.\n\nConcretely, 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 family called linear-span algorithms. Although the family of linear-span algorithms contains many famous and widely used algorithms such as GD, AGD, and so on, as the authors have stated, they cannot represent all algorithms. As a result, the lower bounds are only algorithm-related lower bounds. When talking about optimality, it is correct to say that 'our algorithm is optimal inside the linear-span algorithm', 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)