Boosting One-Point Derivative-Free Online Optimization via Residual Feedback
Authors: Yan Zhang
Yi Zhou
Kaiyi Ji
Michael Zavlanos
Venue:  (2021)
Keywords: zeroth-order optimization
online learning

Abstract: Zeroth-order optimization (ZO) typically relies on two-point feedback to estimate the unknown gradient of the objective function, which queries the objective function value twice at each time instant. However, if the objective function is time-varying, as in online optimization, two-point feedback can not be used. In this case, the gradient can be estimated using one-point feedback that queries a single function value at each time instant, although at the expense of producing gradient estimates with large variance. In this work, we propose a new one-point feedback method for online optimization that estimates the objective function gradient using the residual between two feedback points at consecutive time instants. We study the regret bound of ZO with residual feedback for both convex and nonconvex online optimization problems. Specifically, for both Lipschitz and smooth functions, we show that using residual feedback produces gradient estimates with much smaller variance compared to conventional one-point feedback methods, which improves the learning rate. Our regret bound for ZO with residual feedback is tighter than the existing regret bound for ZO with conventional one-point feedback and relies on weaker assumptions, which suggests that ZO with our proposed residual feedback can better track the optimizer of online optimization problems. We provide numerical experiments that demonstrate that ZO with residual feedback significantly outperforms existing one-point feedback methods in practice.

Under review as a conference paper at ICLR 2021
BOOSTING ONE-POINT DERIVATIVE-FREE ONLINE OPTIMIZATION VIA RESIDUAL FEEDBACK
Anonymous authors Paper under double-blind review
ABSTRACT
Zeroth-order optimization (ZO) typically relies on two-point feedback to estimate the unknown gradient of the objective function, which queries the objective function value twice at each time instant. However, if the objective function is varying, as in online optimization, two-point feedback can not be used. In this case, the gradient can be estimated using one-point feedback that queries a single function value at each time instant, although at the expense of producing gradient estimates with large variance. In this work, we propose a new one- one-point feedback method for online optimization that estimates the objective function gradient using the residual between two feedback points at consecutive time instants. We study the regret bound of ZO with residual feedback for both convex and nonconvex online optimization problems. Specifically, for both Lipschitz and smooth functions, we show that using residual feedback produces gradient estimates with much smaller variance compared to conventional one-point feedback methods, which improves the learning rate. Our regret bound for ZO with residual feedback is tighter than the existing regret bound for ZO with conventional one-point feedback and relies on weaker assumptions, which suggests that 70 with our proposed residual feedback can better track the optimizer of online optimization problems. We provide numerical experiments that demonstrate that 70 with residual feedhack significantly outperforms existing one-point feedback methods in practice.
INTRODUCTION
Zeroth-order optimization (ZO) algorithms have been widely used to solve online optimization problems where first or second order information (i.e., gradient or Hessian information) is unavailable at each time instant. Such problems arise, e.g., in online learning and involve adversarial training Chen et al. (2017) and reinforcement learning Fazel et al. (2018); Malik et al. (2018) among others. The goal in online optimization to minimize a sequence of time-varying objective functions {f((z) ht=::, where the value fI;) is revealed to the agent after an action is selected and is used adapt the agent's future strategy. Since the future objective functions are not known a priori, the performance of the online decision process can be measured using notions of regret, generally defined as the difference between the total cost incurred by the decision selected by the agent online and the cost of the fixed or varying optimal decision that clairvoyant agent could select.
Perhaps the most popular zeroth-order gradient estimator the two-point estimator that has been extensively studied in Agarwal et al. (2010); Ghadimi & Lan (2013); Duchi et al. (2015); Ghadimi et al. (2016); Bach Perchet (2016); Nesterov & Spokoiny (2017); Gao et al. (2018); Roy et al. (2019). Specifically, the two-point estimator queries the function value fi (2:) for twice, for two different realizations of the decision variables, and uses the difference in these function values to estimate the desired gradient, illustrated by the equation
(Two-point feedback): 9i (x) (I(r- Bu) - M(()))
where 5 > 0 is a parameter and (0, 1). However, the two-point gradient estimator not be used for the solution of non-stationary online optimization problems that arise frequently, e.g., in online learning. The reason is that in these non-stationary online optimization problems, the objective

---

Under review as a conference paper at ICLR 2021
function being queried is time-varying and hence only single function value can be sampled at given time instant. In this case, the following one- mee-ponnt feedback can be used
u (One-point feedback); gr (z) = g fr(z + &u),
(2)
which queries the objective function (1(2) only once at each time instant. One-point feedhack was first proposed and analyzed in Flaxman al. (2005) for the solution of online convex optimization problems. Saha & Tewari (2011); 1); Hazan & Levy (2014); Dekel et al. (2015) showed that the regret of convex online optimization methods using one-point gradient estimation can be improved assuming smoothness or strong convexity of the objective functions and using self-concordant regularization. More recently, Gasnikov et al. (2017) developed such regret bounds for stochastic convex problems. On the other hand, Hazan et al. (2016) characterized the convergence of one-point zeroth-ordes methods for static stochastic non-convex optimization problems. However, as shown in these studies, limitation of one-point feedback is that the resulting gradient estimator has large variance and, therefore, induces large regret. In addition, the regret analysis for ZO with one-point feedback usually requires the strong assumption that the function value is uniformly upper bounded over time, this method can not be used for practical non-stationary optimization problems.
Contributions: In this paper, propose novel one-point gradient estimator for zeroth-order online optimization and develop new regret bounds to study its performance. Specifically, our contributions as follows. We propose new one-point feedback scheme which requires single function evaluation at each time instant. This feedback scheme estimates the gradient using the residual between two consecutive feedback points and we refer to it as residual feedback. We show that our residual feedback induces a smaller gradient estimation variance than the conventional one-point feedback scheme in Flaxman et al. (2005); Gasnikov et al. (2017). Furthermore, we provide regret bounds for online convex optimization with our proposed residual feedback estimator. Our analysis relies on a weaker assumption than the one needed in the case of the conventional one-point estimator, and our proposed regret bounds are tighter especially when the value of the objective function is large. In addition, we provide regret bounds for online non-convex optimization with residual feedback. Finally, present numerical experiments that demonstrate that the proposed residual-feedbace estimator significantly outperforms the conventional one-point method in its ability to track the time-varying optimizers of online learning problems. To the best of our knowledge, this is the first time a one-point zeroth-order method is theoretically studied for online non-convex optimization problems. is also the first time that a one-point gradient estimator demonstrates comparable empirical performance to that of the two-point method. We note that two-point estimators can only be used solve online non-stationary learning problems in simulations, where the system can be hard coded to be fixed during two queries of the objective function values at two different decision variables.
Related work: Zeroth-order methods have been used to solve many different types of optimization problems. For example, Balasubramanian & Ghadimi (2018) apply ZO to solve a set-constrained optimization problem where the projection onto the constraint set is non-trivial. Gorbunov al. (2018); et al. (2019) apply a variance-reduced technique and acceleration schemes to achieve better convergence speed in ZO. Wang et al. (2018) improve the dependence of the iteration complexity on the dimension of the problem under an additional sparsity assumption on the gradient of the objective function. And Hajinezhad & Zavlanos (2018): Tang & Li (2019) apply zeroth-order oracles to distributed optimization problems when only bandit feedbacks are available at each local agents. Our proposed residual feedhack oracle can be used to solve such online optimization problems well. Also related is work by Zhang et al. (2015) that considers non-convex online bandit optimization problems with single query at each time step. However, this method employs the exploration and exploitation bandit learning framework and the proposed analysis is restricted to a special class of non-convex objective functions. Finally, Agarwal et al. (2011); Hazan & Li (2016); Bubeck al. (2017) study online bandit algorithms using ellipsoid methods. In particular, these methods induce heavy computation per step and achieve regret bounds that have bad dependence on the problem dimension. As comparison, our one- one-point method is computation light and achieves regret bounds that have better dependence on the problem dimension.
2 PRELIMINARIES AND RESIDUAL FEEDBACK
We first introduce the classes of Lipschitz and smooth functions.
2

---

Under review as a conference paper at ICLR 2021
Definition 2.1 (Lipschitz functions). The class of Lipschtii-coontiuuuss functions C satisfies: for any f E C [f(z) f(y) < Lollz-yll, Vx, E R., where Lo > is the Lipschitaparameter parameter. The
class of smooth functions C satisfies: for any f E (VV[.I(V(()) VV f(y)ll S 1 yll, Vz, Rd, where I > O is the smoothness parameter.
In ZO, the objective is to estimate the first-order gradient of function using zeroth-order oracles. Necessarily, we need to perturb the function around the current point along all the directions uniformly in order estimate the gradient. This motivates us to consider the Gaussian-smon -mootheed version of the function f as introduced in Nesterov & Spokoiny (2017), fx(x) == (u--(o,1)) [f(x + òu)]. where the coordinates of the vector u are i.i.d standard Gaussian random variables. The following bounds on the approximation error of the function (s(z) have been developed in Nesterov & Spokoiny (2017).
Lemma 2.2. Consider a funcciion f and its smoothed version fa. It holds that
(oLovd, if Co.0 Ld, i C and [V - fx()) s 5l if E Ct.1.
[f(()) f(x)) S
The smoothed function fa(x) satisfies the following amenable property Nesterov & Spokoiny (2017).
Lemma 2.3. If f E C is Ly LipLicschit, then fa E C with Lipschitz constant L1 = Vd8-1
Consider the following online bandit optimization problem.
min t=
Sı(r),
where X' C Cd is convex set and {fe) is random sequence of objective functions. In this setting, the objective functions h are unknown a priori and their derivatives are unavailable. At time a new objective function fe is randomly generated independent of an agent's decisions, and then the agent queries the objective function value at certain perturbed points and use them to update the current policy parameters. The goal of the agent is minimize a certain regret function.
Such an online setting often occurs in non-stationary learning scenarios where either the system is time-varying on its own or single query of the function fr changes the system state (i.e., fr changes to fe+1). In this non-stationary setting, the conventional two-point feedback scheme is known to be impractical as requires to evaluate ft at two different points at the same time t. Instead, is natural to use the one- me-poonnt feedback scheme (2) in Gasnikov et al. (2017). However, the gradient estimate based on the above one-point feedback induces a large variance that leads to a large regret. In this paper, we focus on such one-point derivative-free setting and propose the following novel one-point residual feedback scheme for estimating the gradient with reduced variance.
(Residual feedback): (o( 5 (Je(zr + ōu.) fe-1 + du:-1)),
where 14-1; 14 No0 7) independent random vectors. To elaborate, the residual feedback in (3) queries fe at a single perturhed point x; + ou, and then subtracts it by fe-1( + +84-1) obtained from the previous iteration. We name such scheme as one-point residual feedback. Next, we explore some basic properties of the residual feedback. We first show that this estimator is an unbiased gradient estimate of the smoothed function fa.t-
Lemma 2.4. The residual feedbbuc satisfies E (a.)] Js,((zs)) all az E X and t.
Proof. By the fact that u, has zero mean and is independent from u4-1 and 21-1-
We consider the following Zo algorithm with residual feedback
(Z.O with residual feedhack): F++1 = (xx - nx:)))
where 17 is the learning rate and IIx is the projection operator onto the set X. The update (4) can be implemented assuming that the objective function can be queried at points outside the feasible set X', similar to the methods considered in Duchi et al. (2015); Bach & Perchet (2016); Gasnikov et al. (2017). Note that it is possible to modify the update (4) so that the iterates are guaranteed to be within the feasible set X. This modification and related analysis can be found in Section H in the
3

---

Under review as a conference paper at ICLR 2021
supplementary material. The requirement that the objective function is evaluated at feasible points in derivative-free optimization algorithms has also been considered in Bubeck et al. (2017); Bilenne al. (2020). Specifically, Bubeck et al. (2017) develop the so called ellipsoid method, which requires computation of an ellipsoid containing the optimizer at each time step. On the other hand, almost concurrently with this work, Bilenne al. (2020) proposed similar oracle in (3) for static convex optimization problem with specific objective and constraint functions. Next, we bound the second moment of the gradient estimate based on the residual feedback.
Lemma 2.5 (Second moment). Assume that fr C with Lipschitz constant Lo for all time t. Then, under the Zo update rule in (4), the second moment of the residual feedback satisfies: for all t,
4d
(
Bll (10- Dr.
(5)
82
2d
where := 16 + 4) + 82
[[ee[tr- + 114-1) 11 fi ft-1 + -di--1)) 1)
The above lemma shows that the second moment of the residual feedback be bounded by a perturbed contraction, provided that we choose 77 and such that the contracting rate 4dL2//28-2 1. As we show later in the analysis, such contraction property leads small variance of the residual feedback that helps reduce the regret of the online 70 algorithm.
3 ZO WITH RESIDUAL FEEDBACK FOR ONLINE CONVEX OPTIMIZATION
In this section, we consider the online bandit problem (P) where the sequence of functions {f t=::T-1 are all convex. In particular, we are interested in analyzing the following static regret of the algorithm.
T Σ f().)
RT E
min E(la))
(6)
t=
We make the following assumption on the non-stationary of the online learning problem.
Assumption 3.1 (Bounded variation). There exists Vf such that for all 1,
B[[f((T=-1 + du;-1) - ( + Sw, 1) s V7,
where the expectation is taken over xz-1, the random vector u and the random functions fi
Intuitively, we assume the squared variation of the objective function between two consecutive time instants is uniformly bounded over time. We note that this assumption is much weaker than the uniformly bounded function value assumption, i.e., E [f(((]]]] < B², Vt, x X. which is used in the analysis of ZO with the conventional one-point feedback Gasnikov et al. (2017). In particular, under Assumption 3.1, the perturbation term in Lemma 2.5 can be bounded as D, I 16L + 4)² + 2dV26 - Then, by telescoping the contraction inequality, we obtain the following bound for the second moment of the residual-feddbal gradient estimate,
E El (x.) max [lllū((z))] 11 1 (16L3(d + 4)2
2d 82 v2)}
(8)
In practice, 8 is usually chosen to be sufficiently small, and the above bound is dominated by (d5 (db-2177) VV7), which is much smaller than the second moment bound of the conventional one-point feedback (dd- 22) (B2 is the uniform bound of the second moment of f, over time). For example, consider the time-varying objective functions, fo(a)) = 1 1/2x² and f+(x)
( + My where n, is Gaussian noise with zero mean time t. Then, it can be verified that Assumption 3.1 holds
with finite Vy whereas the second moment of ft(z) is unbounded over time. This suggests that the variance of the residual feedback can be significantly smaller than that of the conventional one-point feedback.
Next, we first consider the case where the objective function is convex and Lipschitz. Based the above characterization of the second moment of residual feedback, we obtain the following regret bound for 7. with residual feedback.
4

---

Under review as a conference paper at ICLR 2021
Theorem 3.2 (Regret for Convex Lipschitz ft). Let Assumption 3.1 hold. Assume that fo C is convex with Lipschitz constant Lo for all and [|z - x=1 - R. Run ZO with residual feedback for T > R² iterations with 1 = R (2v 20 /dr )-1 and å = VRT- h, Then, we have that
EE (10 | R
+ 8V2 (d + 4)2
RT S V2LOVRRT
vd Lo R8T
2d/ o T
2T 2LoVaRT? + 22dRV La -1r
Asymptotically, we have RT O(LLo + Lo -Vo==VVVVVVV
To the best of our knowledge, the best known regret for ZO with the conventional one-point feedback is of the order D(VdLgRBT's Gasnikov et al. (2017). Therefore, our regret bound is tighter if the function variation satisfies V² S O L8). Essentially, using the proposed residual feedback gradient estimator, the regret of ZO no longer depends the uniform bound of the function value, which can be huge in practice. Instead, our regret only relies on how fast the function varies over time.
Remark 3.3. We note that the complexity bound in Theorem 3.2 generally depends on the values of the Lipschitz parameters Lg, Lı and the constant V7. Specifically, choose r R (2v2Lo
and 8 RR - with >> 0 as tuning parameter, and we obtain that Rr (( + Ta- 1-9 2 V22 VdR)) when T L R2. If Lo < 1, we can choose q On the other hand, if Lo 2 1, we can choose q 0 to achieve the bound RT = ((Lo + Lo VV We note that the dependence of the bounds in Theorems 3.4, 4.2 and 4.3 on Lo, L1 can also be optimized in a similar way by properly choosing
achieve the bound
Rr = O(Lo +
Next, we present the regret of ZO with residual feedback for convex smooth objective functions. Theorem 3.4 (Regret for Convex Smooth fi). Let Assumption 3.1 hold. Assume that f((x) nC 1 is convex with Lipschitz constant Lo and smoothness constant for all t, and assume that I1 - x= S R. Run 70 with residual feedback for T > R2 iterations with R$ (2 T
and 8 = R - J. Then, we have that
(Z)) 12 R
(d 4)2 8V2LD
Rr V2Lod3 R3
R
2 d T
dš
+ 2 R3T3
-2T R V?T3.
(10)
Asymptotically, the above regret bound is in the order of O ((To + I1 + Lo (URT)))
To the best of our knowledge, the best known regret for Z0 with the conventional one-point feedback in the convex smooth case is of the order O (dRBT)3) Gasnikov al. (2017). Therefore, regret bound is tighter if the function variation satisfies V? < O(B T. T.))- Our numerical experiments show that ZO with residual feedback always outperforms ZO with the conventional one-point feedback in practice.
ZO WITH RESIDUAL FEEDBACK FOR ONLINE NONCONVEX OPTIMIZATION
In this section, we analyze the regret of ZO with residual feedback in solving the unconstrained online bandit problem (P) with nonconvex functions. Throughout this section, we make the following assumption regarding the objective functions.
Assumption 4.1. There exist WT, WT >> 0 such that the following conditions hold all t.
1. Σi (lf - fa.1-1(1))1 S Wz, where the expectation is taken with respect to xt and the random smoothed objective functions f61-11 sb.t-
2. Σr= (x du;-1) ft-1(x1- + -54-1))1 < Wr, where the expectation is taken with respect to Ft-1, the random vector u and the random objective functions ft-1s fy-
5

---

Under review as a conference paper at ICLR 2021
The above two conditions measure the accumulated first-order and second-orde function variations, as also adopted by Roy et al. (2019).
Next, we consider the where ( are nonconvex and Lipschitz continuous functions. Since the objective function ft is not necessarily differentiable, i.c., ft) is not well defined, we define the regret as the accumulated gradient of the smoothed function, i.e., Ry : T-1 fa, (z;) In addition, it is often required that the smoothed function fö, is close to the original function fr such that (z) fz)x S e for all L. To satisfy this condition, we need to choose ò < (vdLo))'e according to Lemma 2.2. We obtain the following regret bound for ZO with residual feedback.
Theorem 4.2 (Nonconvex Lipschitz fi). Let Assumptions 4.1 hold. Assume that ft C with Lipschitz constant Lo and that Jt is bounded below by Sł for all L. Run ZO with residuul feedback for T > (de,) iterations with 1 = Ej (2V2LBd3T and ā = ey(d' Lo) Then, we have that
of 1150 ([)00(=0))0)
Ryo S 2
-6rr + WT Wr)dde -3 3T
2v2dT
+ 4v (d + 4)2
L3 d WT
T +
(11)
d3
V2 T
Asymptotically, we have 2 O(d Lije (Wr + WT'- +d Loe
Based on Theorem 4.2, we observe that the regret bound satisfies R - 0 whenever W7- a( and Wr T $ )) In particular, if the bounded variation Assumption 3.1 holds, then have Wr s O(TV)), and it suffices to let 2 = o(1).
Next, we consider the nonconvex and smooth problem and study the regret Ry EO (( We obtain the following regret for ZO with residuul-feedback.
Theorem 4.3 (Nonconvex smooth ft). Let Assumptions 4. hold. Assume that fe E C nC.. with Lipschitz constant Lo and smoothness constant I, and that fe bounded below by fe for all t. Run ZO with residual feedback feedback for T iterations with 17 = (2v (2
and ō (d&T+)-1 Then,
LE [1
R < 4022L(EEEaaa (Bifa,((zo)] fār WT d WWr)d
V2LodiTz
(d 4)+ T + Lo
d d W + 21? v2L,
(d + +3)3 T
+ LV
(12)
d3
d
Asymptotically, the above regret bound is in the order of (d L. W + d L, Lo Wr).
Based on Theorem 4.3, we observe that the regret bound satisfies R. /T + whenever Wf = ((T)) and WT o(T). We note that these requirements of Wr, WT more relaxed than those in the nonsmooth case, as they do not rely on the small parameter Ey.
5 ZO WITH RESIDUAL FEEDBACK FOR STOCHASTIC ONLINE OPTIMIZATION
In this section, we generalize the residual feedback to solve stochastic online bandit problems. Since its regret analysis follows the same proof logic that ZO with residual feedback, we only introduce the key technical lemmas and comment on the proof difference. The stochastic online bandit problems are formulated as follows.
min XEX
Σ &1)
where E[F ft(x),
(R)
where & denotes a certain noise that is independent of x. Different from the previous deterministic online setting, the agent in the stochastic setting can only query noisy evaluations of the function.

---

Under review as a conference paper at ICLR 2021
This covers the scenarios where the agent does not have access to the underlying data distribution. To solve the above stochastic online problem, we propose the following stochastic residual feedback
Ge (2)) = (Fr(1r + ous; Ex) Pi- (are-1 + dua- Prue-1ff-1 (t-)))
(13)
where f--1 and & are independent random samples that are sampled in the iterations / - and 4, respectively. Since the noisy function value F(x; E+) an unbiased estimate of the objective function fe(a)), it is straightforward to show that (13) is an unbiased gradient estimate of the function (x))
To analyze the regret of ZO with stochastic residual feedback, we first consider the convex setting and make the following assumption that bounds the variation of the stochastic functions.
Assumption 5.1. (Bounded stochastic variation) There exists Vr.5 >> 0 such that for all t,
(Fi + 6, Fi-1(04-1 + pu Et- -)) Vi.
where the expectation is taken with respect to Tt-1. the random vector U and the random objective functions Fi-1(t, &t).
The above assumption generalizes Assumption 3.1 to the stochastic setting. The bound f.g controls both the variation of function over time and the variation due to stochastic sampling.
The following lemma characterizes the second moment of the stochastic residual feedback.
Lemma 5.2. Assume F(x, {) E C0.0 with Lipschitz constant Lo all &. Then, under the ZO update rule, we have that
4dL23n2 82
Ellgg (x:- De.5.
where Dr, == 1d 4)²
2d (F,
F, (I + Su, 1, Ex-1))
Observe that the above second moment bound very similar to that in Lemma 2.5, and the only difference is the perturbation term. In particular, the perturbation term Di,c can be further bounded by leveraging Assumption 5.1, and the resulting second moment bound is almost the same as that in eq. (8) for the deterministic case (simply replace Vy in eq. (8) by Vy.s). Therefore, the regret analysis of ZO with stochastic residual feedback the same as that of 70 with residual feedback in the deterministic online setting. Consequently, ZO with stochastic residual feedback achieves almost the same regret bounds as those in Theorems 3.2 and 3.4, and one simply needs to replace Vy by Vr.s-
For the nonconvex setting, we adopt the following assumption that generalizes Assumption 4.1. Assumption 5.3. There exists Wr, Wr. such that the following two conditions hold for all
- f8,1-1(1) < Wr, where the expectation is taken with respect to I and the random smoothed objective functions f6,--1, f8.--
Ex= (()
2. Ein EE[F((x,-11 + -- F + 8ut-1iEt-1) < WT.S, where the expectation taken with respect to F1-1, the random vector uh-1 and the random objective functions
Fi-1(;;E-1). E.):
Then, following the same proof logic as that Theorems 4.2 and 4.3, on can obtain similar regret bounds for ZO with stochastic residual feedback (simply replace Wr, Wr in Theorems 4.2 and 4.3 by Wr.g, Wr.g. respectively).
6 NUMERICAL EXPERIMENTS
In this section, we compare the performance of 70 with one-point, two-point and residual feedback in solving two non-stationary reinforcement learning problems, i.e., LQR control and resource allocation, in which either the reward or transition functions are varying over episodes.
6.1 NONSTATINOARY LQR CONTROL
We consider an LQR problem with noisy system dynamics. The static version of this problem is considered in Fazel et al. (2018); Malik et al. (2018). Specifically, consider system whose state
7

---

Under review as a conference paper at ICLR 2021
10a
10a
(Vi(K) - V((K)))
107
10a
Varlğ.(Ki)
10c
10a
10a
10a
10a
One seint Residual Feedback
One-polnn Residual Feedback
Two-point Feedback (Impractical)
10a
Two-point Feedback (Impractical)
Conventional One-point Feedback
Conventional One Oneitpoint Feedback
10
10a
0
2000
4000
6000
8000
10000
0
2000
4000
6000
8000
10000
Episode
Episode
(a)
(b)
The regrets of applying the proposed residual one-point feedback (3) (blue), the two-point oracle in Bach & Perchet (2016) (orange) and the conventional one-point oracle in Gasnikov et al. (2017) (green) to online policy optimization for the nonstationary LQR problem. In (a), the regrets Ei= (V(K)) - V(K*) [ of three methods are presented. In (b), the variance of the gradient estimates given by three methods are presented. The two point method (orange) is infeasible benchmark.
Figure I:
in practice and is presented here
the simulating
Th E Rt at step k is subject to a transition function Tk-1= A,Tx + Bru + wk, where Wa E I the action step k, and A, E R===x== and B, E x are dynamical matrices in episode t. These matrices are unknown and changing over episodes. The vector wy is the noise on the state transition. Specifically, the entries of the dynamical matrices Ag and Bo at episode are randomly generated from a Gaussian distribution .V (0, 2.1 Then, we generate the time-varying dynamical matrices as A4+1= A₁ + 0.01 and B = B, + 0.01N,, where Mj and N₂ are random matrices whose entries are uniformly sampled from [0.1]. Moreover, consider state feedback policy UR = KYTY, where K, E RT, Xnz is the policy parameter that is fixed within episode t. Within each episode, there exists optimal policy Kद so that the discounted accumulated cost function VV(K) E - (Ix Quy + uy Rux)] episode is minimized, where ? S is the discount factor and H is the horizon. The goal is to track the time-varying optimal policy parameter K so that (k,) (K²) is small in every episode.
We apply the conventional one-point method in Gasnikov et al. (2017) and the proposed residual- feedback method (13) to solve the above non-stationary LQQ problem. The performance of the two- point method in Bach & Perchet (2016) is also presented as a benchmark, although it is impractical in non-stationary scenarios. This is because the two-point method in Bach & Perchet (2016) requires to evaluate value function V/ for two different policy functions at two consecutive episodes. However, evaluating the value function V2 for given policy during episode t requires to collect samples by executing this policy. Then, during the subsequent episode t + 1, since the problem is non-stationary, the dynamic matrices change to A441, B441 and so does the value function V4+1- Therefore, it is not possible evaluate the same value function V, at different episodes and, as result, the two-point method in Bach & Perchet (2016) is not applicable here. Each algorithm is run for 10 trials, and the stepsizes are optimized respectively. The accumulated regrets Σ (V(,)) V(K*) ) of these algorithms are presented in Figure (aa). We observe that the residual feedback method achieves a much lower regret than the conventional one-point method and has comparable performance to that of the impractical two-point method. Moreover, we present in Figure ((b) the estimated variance of the gradient estimates of these three methods at the policy iterates over episodes. It can be feedbaack is close to the impractical two-point feedback
that the variance of our proposed and is much smaller than that of the conventional one-point feedback. This observation justifies our theoretical characterization of the second moment of the residual feedback.
6.2 NONSTATIONARY RESOURCE ALLOCATION
We consider a multi-stage resource allocation problem with time-varying sensitivity to the lack of resource supply. Specifically, 16 agents are located on 4 x 4 grid. During episode at step k agent i stores m.(k) amount of resources and has a demand for resources in the amount of dk).). Also, agent decides send fraction of resources (ky(k) [0, 1] to its neighbors
8

---

Under review as a conference paper at ICLR 2021
35
10a
wn www.mmmmmm
Vartg.10.)
10a
(,18)
25
10a
20
One point Residual Feedback
10a
One point Residual Feedback
Twe-point feedback limpractical:
Two-point Feedback limpracticall
15
Conventional One-point Feedback
Convertional One One-point Feedback
10a
4000
6000
10000
2000
10000
Episode
Episode
(b)
The costs during each episode by applying the proposed residual one-point feedback (3) (blue), the two-point oracle in Bach & Perchet (2016) (orange) and the conventional one one-point oracle in Gasnikov et (2017) (green) to solve the non-stationary resouree allocation problem are presented. In (a), the varying cost Je(Oe) of three methods are presented. In (b), the variance of the gradient estimates at agent 1 given by three methods are presented. The two point method (orange) is infeasible to use in practice and is presented here to the simulating benchmark.
Figure 2:
j E N₁ on the grid. The local amount of resources and demands of agent i evolve as (k + 1) m, m,(k) (k:) Ejex, aiy (ky(k)),)k) +Eje; (zy(k)) (m,k)))()))) - d, (k) and (k) = 4/s sin(w; + Φz) Wi,k- where Wi,k is the noise in the demand. At each step k. agent i receives a local cost (k)) such (.m,(k)² when m²(k)) < O, where & represents the varying sensitivity of the agents to the lack of supply during episode t. Let agent makes its decisions according a parameterized policy function e,,e 0i.r) O, + [0. 1] NV.l, where 0z,, is the parameter of the policy function Ti, at episode t, E O, denotes agent i's local observation. Specifically, we let o, (k) = (k)) di (k))) Our goal is to track the time-varying optimal policy so that the accumulated cost
that (A:) = 0 when (k) 2 O and (k.)
the grid Je (0 Σ 16 i=1 k== > (k) during each episode is maintained at a low level, where 0₂ = [..., f,.,,... . is the policy parameter, H is the problem horizon at each episode, and y is the discount factor.
In Figure 2(a), we present the costs achieved during each episode J, (e,) with 10 trials using ZO with the residual-feedhack one-point and the impractical two-point feedback. It can be that our proposed feedbbackk achieves a cost ((t) that as low as the cost achieved by the impractical two-point feedback in such non-stationary environment. In particular, both residual and two-point feedback perform much better than the conventional one-point feedback. Moreover, Figure 2(b) compares the estimated variances of these feedback schemes, and one can observe that the variance of the residual feedback is comparable to that of the two-point feedback and is much smaller than that of the conventional one-point feedback.
CONCLUSION
In this paper, we proposed residual one-point feedback oracle for zeroth-order online learning problems, which estimates the gradient of the time-varying objective function using a single query of the function value at each time instant. We showed that the regret bound of the proposed residual feedback estimator can be much lower than that of the conventional one-point method in online convex optimization setting. In addition, we studied the gradient size regret bound the residual- feedback estimator when it is applied to the online non-convex optimization problems. Numerical experiments on two non non-stationary reinforcement learning problems were conducted and the proposed residual-feedback estimator shown to significantly outperform the conventional one-point method in non-stationary online learning problems.
REFERENCES
Alckh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In COLT, pp. 28-40. Citeseer, 2010.

---

Under review as a conference paper at ICLR 2021
Alekh Agarwal, Dean P Foster, Daniel Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. In Advances in Neural Information Processing Systems, pp. 1015-001333 2011.
Francis Bach and Vianney Perchet. Highly-smooth zero-th thrtth order online optimization. In Conference on Learning Theory, pp. 257-283, 2016
Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic optimiza- tion via conditional gradient and gradient updates. In Advances in Neural Information Processing Systems, pp. 3455-3464, 2018.
Olivier Bilenne, Panayotis Mertikopoulos, and Elena- Veronica Belmega. Fast optimization with zeroth-order feedback in distributed, multi-user mimo systems. IEEE Transactions on Signal Processing, 2020.
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimiza- tion. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 72-85, 2017.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26, 2017.
Ofer Dekel, Ronen Eldan, and Tomer Koren. Bandit smooth convex optimization: Improving the bias-variance tradeoff. In Advances Neural Information Processing Systems, pp. 2926-2934, 2015.
John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788-288 2015.
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence policy gradient methods for the linear quadratic regulator. In Proceedings of the 35th International Conference on Machine Learning, volume 80, 2018.
Abraham Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 385-394. Society Industrial and Applied Mathematics, 2005.
Xiand Gao, Xiaobo Li, and Shuzhong Zhang. Online learning with non-convex losses and non- stationary regret. In International Conference Artificial Intelligence and Statistics, pp. 235-243, 2018.
Alexander V Gasnikov, Ekaterina Krymova, Anastasia Lagunovskaya, Ilnura N 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(2): 224-234, 2017.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, 23(4):2341-2363 2013.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini- stochastic approximation methods nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2):26.-355 2016.
Eduard Gorbunov, Pavel Dvurechensky, and Alexander Gasnikov. An accelerated method for derivative-free smooth stochastic convex optimization. arXiv preprint 1802. 2018.
10

---

Under review as a conference paper at ICLR 2021
Davood Hajinezhad and Michael M Zavlanos. Gradient-free multi-agent nonconvex nonsmooth optimization. 2018 IEEE Conference on Decision and Control (CDC), pp. 4939 4939-4944. IEEE, 2018.
Elad Hazan and Kfir Levy. Bandit convex optimization: Towards tight bounds. Advances in Neural Information Processing Systems, pp. 784-792, 2014.
Elad Hazan and Yuanzhi Li. An optimal algorithm for bandit convex optimization. arXiv preprint 1603v 04350, 2016.
Elad Hazan, Kfir Ychuda Levy, and Shai Shalev-Shwarzz. On graduated optimization for stochastic non-convex problems. In International conference on machine learning, pp. 1833-1841 2016.
Kaiyi Ji, Zhe Wang, Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. arXiv preprint arXiv:1910.12166. 2019.
Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter L Bartlett, and Martin J Wainwright. Derivative-free methods for policy optimization: Guarantees for linear quadratic
systems. arXiv preprint arXiv: 882008305, 2018
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Abhishek Roy, Krishnakumar Balasubramanian, Saeed Ghadimi, and Prasant Mohapatra. Multi- point bandit algorithms for nonstationary online nonconvex optimization. arXiv preprint arXiv:1907.13616, 2019.
Ankan Saha and Ambuj Tewari. Improved regret guarantees for online smooth convex optimization with bandit feedback. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statisties, pp. 636-642, 2011.
Yujie Tang and Na Li. Distributed zero-order algorithms for nonconvex multi-agent optimization. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 781-786. IEEE, 2019.
Yining Wang, Simon Du, Sivaraman Balakrishnan, and Aarti Singh. Stochastic zeroth-order opti- mization in high dimensions. International Conference on Artificial Intelligence and Statistics, pp. 1356-1365, 2018
Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou Online bandit learning for special class of non-convex losses. In AAAI, pp. 3158-3164, 2015.


Reviews:
[{"review_id": "cCf24rJSglh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This manuscript considers online zeroth order optimization and it develops a gradient estimator based on one query per function. In particular, the proposed method mimics two-point estimators by evaluating two consecutive functions at perturbations of an iterate, as shown in equation (3). Although one-point gradient estimates are possible, they have impractically large variances. Given this limitation and the wide need of zeroth order optimization (in particular in RL), the study of two-point estimators is important. \n\nWhile this manuscript has many strengths, there are several issues that need to be clarified before it can be accepted for publication. \n\nPros:\n- This work offers a simple solution. \n\n- Also, the authors offer guarantees for this solution under several sets of assumptions on the functions. \n\nCons:\n- The theoretical results can be cleaned to offer better guarantees and make them more interpretable. I think the regret bounds offered in Theorem 3.2, 3.3, 4.2, and 4.3 are difficult to parse, but they can be improved. For example, there shouldn't be a dependence on the inverse of the Lipschitz parameters L_0 and L_1 (it doesn't make sense to get a worse bound when the functions are smoother). The dependence on the inverse arises because the chosen step sizes  go to infinity as the Lipschitz constants go to zero. With a better choice of step sizes the regret bounds would be better. \n\n- Assumptions 3.1 and 4.1 are stated in terms of expectations, but it is not clear what the expectations are over. From the proofs it seems that the expectations are over the perturbation directions u, but these are not introduced in the assumptions. Also, is Assumption 4.1.1 really intended as is? I'm asking because it reduces to E f_T <= W_T + E f_0.\n\n- Finally, it seems like in the LQR example the different functions f_t correspond to different transition parameters (A_t, B_t). How are the parameters A_t, B_t chosen? I think a clear discussion of the choice is important to both understand the difficulty of the problem and to understand whether Assumptions 3.1 and 4.1 hold. \n\n\n-----\nUpdate after rebuttal:\n\nI appreciate the detailed answers to my questions and the authors' revisions. I also read the other reviewers' comments. While the new assumptions address my initial concerns, the new versions depend on the algorithm being implemented. As far as I can tell the assumptions might be satisfied for one choice of step-size while not being satisfied for another. Also, I agree with the other reviewers that generally in OCO one considers a worst case sequence of functions. A discussion of this issue in the main body of the paper seems appropriate.\n\nAfter addressing these issues, I think this work would warrant acceptance to ICLR. For now, however, I am not changing my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WRpG-HhiXXX", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a zeroth-order (derivative-free) algorithm for online stochastic optimization problems. The objective is to find a sequence of actions $x_0,\\dots,x_{T-1}$ minimizing the expected regret\n$$\\mathbb{E} [ \\sum_{t=0}^{T-1} f_t(x_t) - \\min_{x\\in\\mathcal{X}} \\sum_{t=0}^{T-1} f_t(x)],$$ where the (sub-)gradients of unknown cost functions $f_t$ are not available, and only measurements $f_t(x_t)$ of the values of the functions at tests points $x_t$ can be obtained.\n\nThe submission builds on the zeroth-order techniques developed by Nesterov & Spokoiny in [1] for derivative-free, non-smooth, convex and non-convex optimization, where similar gradient estimation techniques based on sampling and Gaussian smoothing are used, with the difference that two values of an identical noisy instance of the cost function are needed in [1] at each iteration. By requiring only one noisy function value per iteration and recalling the function value collected during the previous iteration (in the submission this technique is called \"residual feedback\"), the proposed algorithm extends convergence results of the two-point approach [1] to regret bounds in stochastic/bandit settings where the function is changing after every new value observed, on condition that the differences between two consecutive instances of the cost function are bounded in variance.  \n\nThe regret bounds derived in the paper match those obtained for recent 'one-point' zeroth-order methods for online optimization (e.g. [2]). A specificity of the algorithm proposed in the paper, compared to other 'one-point' methods, is that the algorithm does not depend on the absolute function levels, only on differences between two function instances, which may improve the performance in practice, as shown in the numerical experiments. This property was also shared by the approach of Bach and Perchet [4], which serves as a benchmark algorithm in the numerical experiments of the submission. These experiments are carried out on a nonstationary LQR control algorithm, and on a nonstationary resource allocation problem.\n\nThe paper is technically sound and the developments are clear. The regret bounds derived for online non-convex optimization are interesting. The contributions to the online convex optimization framework are less obvious, due to the abundant literature on the topic. See my concerns below and my questions to the authors.\n\nI look forward to the authors' answers. My recommendation will be amended after their rebuttal.\n\n\n\nPros:\n\nThe paper is technically sound and well written.\n\nThe regret bounds derived in the non-convex online optimization framework are of particular interest.\n\nSince the proposed algorithm does not depend on the function levels, it may perform better than the basic 'one-point' methods in practice.\n\n\n\nConcerns and questions:\n\nThe presentation of the results leaves a mixed impression. I agree that regret bounds in non-convex online learning are a contribution to the field. The claims of novelty made by the authors for the convex case, on the other hand, look somewhat overstated. They write, for instance: \"it is also the first time that a one-point gradient estimator demonstrates comparable performance to that of the two-point method\". This sounds optimistic to me, in the sense that the authors' argument is mostly empirical (numerical experiments for a particular problem), whereas the regret bounds derived in the paper do not compare with the regret bounds that two-point methods would achieve. Moreover, there exist more recent approaches to convex zeroth-order online learning which claim the conjectured $\\Omega(\\sqrt{T})$ regret bound [3,5]. These new trends in zeroth-order online learning are not discussed in the submission.\n\nI don't see a clear distinction between the settings 'online bandit optimization' (Sections 3 and 4) and 'online stochastic optimization' (Section 5), because the regret criterion (6), the assumptions of the cost function sequences (3.1, 4.1 / 5.1, 5.2), the algorithms, and the regret bounds are apparently the same for the two settings. The only specificity of the Section 5 model seems to be the existence of a mean cost function $\\mathbb{E}[f_t]$, if we set $f_t(\\cdot)\\equiv F(\\cdot;\\xi_t)$ — assumption which is not exploited. Also, I found Section 5 slightly redundant. I thought it could easily be replaced by a discussion on all the frameworks covered by Assumptions 3.1 and 4.1 and on the possible interpretations given to the model.\n\nIn the submission, an algorithm developed by Bach and Perchet in [4], was classified by the authors as a two-point zeroth-order optimization algorithm and used in the numerical experiments as a benchmark for comparison. In my recollection of [4], the algorithm relies on a gradient estimator which considers the difference between two noisy functions values affected by two independent noises, with the assumption that the noises are uniformly bounded in variance or satisfy a martingale property. To me, these assumptions are similar (if not identical) to those made in Section 5 and in Sections 3,4,6, respectively. Could the authors clarify the differences between the noise model of [4] and the one they use, and why the algorithm [4] is impractical and cannot be used in online settings? Why was it treated differently in the numerical experiments?\n\nAnother feature that was not discussed in the paper is the feasibility of the algorithm in terms of the availability of the function queries. The problem stated in Equation (P) is a constrained online optimization problem over a convex set. However, since the test points are sampled over the entire state space from Gaussian distributions, the proposed algorithm will query function values outside the feasible set, and these function values are not available in many learning applications. Note that it is possible to combine Gaussian sampling with constrained online optimization [5], and that feasible zeroth-order optimization algorithms based on residual feedback have been developed [6].\n\n\n\nTypos :\np.2 such an one-point derivative-free setting => such a\np.7 nonstatinoary => nonstationary\n\n[1] Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, 2017.\n\n[2] Alexander V Gasnikov, Ekaterina A Krymova, Anastasia A Lagunovskaya, Ilnura N Usmanova, and Fedor A Fedorenko. Stochastic online optimization. single-point and multipoint non-linear multi-armed bandits. convex and strongly-convex case. Automation and remote control, 78(2):224–234, 2017.\n\n[3] https://arxiv.org/abs/1603.04350\n\n[4] Francis Bach and Vianney Perchet. Highly-smooth zero-th order online optimization. In Conference on Learning Theory, pp. 257–283, 2016.\n\n[5] https://arxiv.org/abs/1607.03084\n\n[6] https://arxiv.org/abs/2006.05445\n\n\n__________\n\n\n\nUpdate after the discussions:\n\nI would like to thank the author(s) for all their comments. Although most of my concerns have been addressed, some questions remain topics of contention. Before discussing these topics, I will first append to this review my answer to the author(s)' last comments, as it was their wish to keep hearing from me after closing of the discussions:  \n\n$\\ \\ \\ $ The assumptions (3.1, 4.1, 5.1, 5.3) made on the function sequence $f_t$ for convergence of the proposed algorithm are unconventional as they require that the expected absolute variations of two function values at the points visited by the algorithm be bounded, or that the squared variations of two function values obtained by Gaussian sampling from points visited by the algorithm be bounded. So formulated, the conditions for convergence involve the algorithm's trajectory $x_t$ as much as the function sequence $f_t$, and they are difficult to verify. In an attempt to identify sufficient conditions for these assumptions to hold true, I made three suggestions: (i) and (ii) were concerned with the boundedness of the sequence of points generated by the algorithm, and (iii) was the case of bounded incremental variations of the sequence $f_t$, e.g. martingales. In their reply, the author(s) were right to rule out (i) and (ii), which indeed were unrelated. This leaves us with (iii) as a possible setting for the proposed algorithm.  \n\n$\\ \\ \\ $ In my last comment I argued that the case (iii), where the sequence $f_t$ undergoes incremental variations uniformly bounded in expectation, was covered by the approach taken in Bach & Perchet (2016), where two function queries obtained from perturbations around the same iterate are processed at each step. The Bach/Perchet approach is cited in the paper for comparison, but it is called impractical as it would not apply when $f_t$ varies over time $-$ argument I disagree with and that I attempted to refute in a brief discussion involving martingale-like variations for $f_t$. When the author(s) of the submission object to my regret analysis in the case of martingale-like noise on the basis that the assumptions they make also cover non-zero-mean variations with similar uniform upper bounds on the moments, they do not address the main point of my comment. My intention was to show that it does not take much effort to consider the approach used in Bach & Perchet (2016) in settings where the cost function is changing over time, for as long as the cost variations are incremental with bounded moments. This can be seen by noting that the convergence result derived in the revised version of the supplementary material for the residual-feedback algorithm with unit-sphere sampling can be reproduced for the Bach/Perchet approach under the considered assumptions. I take it that the author(s), who excel at deriving the convergence rates for such algorithms, will not disagree. Although the assumptions used in Bach & Perchet (2016) (uniform zero-mean increments) may look somewhat stricter, they have the merit of being clear and simple, as opposed to Assumptions 3.1, 4.1, 5.1, 5.3, which involve the trajectory of the algorithm and can't be verified easily. They are also sufficient to improve the convergence rates for higher degrees of smoothness compared to the early algorithm by Flaxman et al. (2005), which was the objective of that paper. Higher degrees of smoothness failing which it is difficult to improve the convergence rates, as confirmed by the convergence rates given in the submission. In my sense, one important message conveyed by the submission is that the approaches proposed in the submission and in Bach & Perchet (2016) can both handle bounded additive noise, and both fail in the more general framework of adversarial learning. By calling the Bach/Perchet algorithm impractical for their setting, I believe the author(s) of the submission missed to chance to compare the two approaches from a fair perspective and to answer the simple question that comes to mind when reading their paper: is the residual feedback technique really useful in the stochastic learning framework, or isn't convergence just as fast when the function queries are processed by pairs as in Bach & Perchet (2016), or in the reference paper by Nesterov & Spokoiny (2017) ?\n\n-------\n\nThat being said, the following issues remain in this submission:\n\n$\\bullet$ The assumptions (3.1, 4.1, 5.1, 5.3) made on the function sequence $f_t$ for convergence of the proposed algorithm are unconventional and difficult to verify, because they consist in properties of the iterates of the algorithm.\n\n$\\bullet$ In our discussions, only incremental sequences $f_t$ with variations uniformly bounded in expectation have been identified to meet those assumptions. In my sense, this particular setting is also covered by the approach taken in Bach & Perchet (2016), where the function queries are handled by pairs obtained from perturbations around the same iterate. Also, I still find it unfair to call the latter approach impractical for the considered setting.\n\n$\\bullet$ Since the convergence rates derived in the paper show no clear improvement, compared to the early approach of Flaxman et al. (2005), the arguments of the submission lie in the experimental results, where I don't think the algorithm by Bach & Perchet (2016) is given a fair treatment (for the reason explained in the previous paragraph). Besides, the application considered in Section 6.1 reduces to the unconstrained minimization of a polynomial of high degree that is neither Lipschitz nor smooth, which is a basic requirement for the convergence algorithms. This makes the convergence of the algorithms highly dependent on the initial point, unless optimization is done over a compact set, but I don't think the projection step was implemented for the algorithms.\n\n$\\bullet$ In constrained optimization, the problem that the proposed algorithm samples function values outside the feasible set has been partly addressed by the author(s), who provided a variant of the algorithm based no longer on Gaussian sampling, but on sampling over a sphere. Partly because only one convergence result for a particular setting was derived, and it remains unclear (as pointed out by Reviewer 4) if all the benefits of Gaussian smoothing and all convergence results would also extend to spheric smoothing. This discussion is missing. In my opinion, the extension to settings where the functions can't be sampled outside the feasible set is not absolutely imperative in all frameworks (the author(s) have provided counter-examples), but it would be useful to know the limits of the proposed technique. \n\nAll things considered, I would not recommend the submission for presentation at the conference. Independently of the final decision, I hope the author(s) will make the most from the discussions with all the reviewers.\n\nI would like to make a last comment about the submission and the discussions that followed. It is natural that the author(s) give the best picture of the algorithm they propose. Yet in the paper the contrast is particularly strong between, on the one hand, the haziness surrounding the assumptions made on the function sequence $f_t$, or the negligence with which the algorithms were applied in Section 6.1 to a problem not actually meeting the conditions for convergence, and on the other hand the severity with which the Bach/Perchet approach was disqualified as a possible method of solution. This contrast gives the reader an overall feeling of partiality, which makes the reviewing task an intricate, contradictory, and unappreciative one.", "extra_scores": {}, "extra_text": {}}, {"review_id": "C5_IrhdRS29", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Paper contribution summary\n    This paper proposes a new one-point zeroth-order gradient estimation method for online optimization. Comparing to previous methods in the same scenario, this paper's method is shown to have smaller variance, which can improve the learning rate in certain cases including classes of convex Lipschitz functions, convex smooth functions, non-convex Lipschitz functions, as well as non-convex smooth functions. \n\n2. Strong and weak points of the paper\n    1) Strong points: The paper's focus is on one-point zeroth-order gradient estimate, which is a more realistic setting in non-stationary online optimization problems as compared to most popular two-point estimator due to the queried function is time-varying. The new estimate method is based on residual feedback from previous time's perturbed objective value, which can help improve the regret order when function variation is small. It also extends the finding to online non-convex optimization problems with different regret definitions. And the proposed new one-point zeroth-order gradient estimation method is shown to have smaller variance and improved performance in the two numerical examples. \n\n    2) Weak points: The proposed zeroth-order update rule for constrained convex case in Eq.(4) is problematic. For the constrained case, it uses a projection to make sure x_{t+1} is feasible. However, when doing gradient estimation, it actually uses the perturbed x_{t+1} + \\delta u_{t+1}, which may violate the constraint, making this update rule not feasible sometimes. The claimed improvement for convex cases is only in the constant order instead of the order of T even under this problematic update rule. The regret metrics used in the two online non-convex cases: non-convex Lipschitz, non-convex smooth are different from each other, which is very weird. \n\n3. My recommendation\n    I would suggest a rejection due to the problematic update rule in Eq.(4) and the constant order improvement.\n\n4. Supporting arguments for my recommendation.\n    First, the problematic update rule as discussed above. Second, the only constant order improvement of regret in convex cases. Third, the weird different regret metrics used in non-convex cases.\n\n5. Questions \n    1) Can the author/s confirm if the update in Eq.(4) is problematic? \n    2) Why using two different regret metric in non-convex problems? \n    3) For the example used in the paragraph under Eq.(8) to show that the assumption 3.1 is weaker than previous works' uniform boundedness, i feel that the uniform boundedness assumption in prior works can be improved to have only bounded first or second order expectation. Then the example's statement won't hold anymore. Can the author/s make any comments on this?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6iou19PmKSn", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper considers online optimization with zero-order oracle. Motivated by nonstationarity of the objective function, impracticality is underlined for the two-point feedback approach. Instead, staying in the one-point setting, the proposed approach reuses the objective value from the previous round of observations, which is called as residual feedback. The variance of the corresponding proxy for the subgradient is estimated under more relaxed assumptions than existing in the literature. The proposed approach leads to smaller variance and better regret bounds. Regret bounds are proved for smooth/non-smooth convex/non-convex cases, the non-convex case being analyzed for the first time in the literature. Numerical experiments show that the practical performance of the proposed gradient estimator is better than that of the existing one-point feedback methods and is close to the performance of the one-point approach with two observations per round. The latter approach can be impractical for some applications.   \n\nEvaluation:\nI believe that the paper contains new interesting results on zero-order methods with one-point feedback, which are supported both theoretically and numerically. So, I suggest accepting the paper.\n\nPros:\n1. New theoretical results which are significant for optimization and learning literature, as well as for applications. \n2. Numerical results support theoretical findings.\n3. The paper is overall clearly written and motivated.\n\nCons:\n1. There are several minor comments mainly on the clarity of presentation. See below.\n\n\nMinor comments\n1. Some related work seems to be missing\nhttp://proceedings.mlr.press/v48/hazanb16.pdf (non-convex optimization with one-point feedback)\nhttps://link.springer.com/article/10.1007%2Fs10107-014-0846-1 (non-convex stochastic optimization)\nhttp://papers.nips.cc/paper/5377-bandit-convex-optimization-towards-tight-bounds.pdf\nhttp://papers.nips.cc/paper/4475-stochastic-convex-optimization-with-bandit-feedback.pdf \n2. Please consider writing explicitly on p.7 that Bach & Perchet (2016) use two function evaluations in each round. Also it would be nice to explain in more details, why their approach is impractical. For example, in the considered in Sect. 6.1 example, why one can not observe x_{k+1} two times (with different values w_k), and the evaluate the loss twice?\n3. The proof of Lemma 2.5 does not completely correspond to the statement of the Lemma. In the proof more is derived than stated in the Lemma, but under additional assumptions.\n4. In the first line of Appendix F, did you mean that $f_{\\delta,t} \\in C^{1,1}$? Also here Assumption 3.1 is used, which should be mentioned.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper generated a lot of discussion. After reviewing all of the opinions, and my own reading of the paper, we have concluded that the theoretical innovation is too incremental for ICLR. It is possible that the idea of "residual feedback" could be helpful, but for this to be demonstrated effectively one would need to consider concrete models where the assumptions are verified.
Decision: Reject