Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

While this manuscript has many strengths, there are several issues that need to be clarified before it can be accepted for publication. 

Pros:
- This work offers a simple solution. 

- Also, the authors offer guarantees for this solution under several sets of assumptions on the functions. 

Cons:
- 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. 

- 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.

- 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. 


-----
Update after rebuttal:

I 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.

After addressing these issues, I think this work would warrant acceptance to ICLR. For now, however, I am not changing my score.
review_title: Recommendation to reject

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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
$$\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.

The 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.  

The 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.

The 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.

I look forward to the authors' answers. My recommendation will be amended after their rebuttal.



Pros:

The paper is technically sound and well written.

The regret bounds derived in the non-convex online optimization framework are of particular interest.

Since the proposed algorithm does not depend on the function levels, it may perform better than the basic 'one-point' methods in practice.



Concerns and questions:

The 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.

I 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.

In 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?

Another 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].



Typos :
p.2 such an one-point derivative-free setting => such a
p.7 nonstatinoary => nonstationary

[1] Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, 2017.

[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.

[3] https://arxiv.org/abs/1603.04350

[4] Francis Bach and Vianney Perchet. Highly-smooth zero-th order online optimization. In Conference on Learning Theory, pp. 257–283, 2016.

[5] https://arxiv.org/abs/1607.03084

[6] https://arxiv.org/abs/2006.05445


__________



Update after the discussions:

I 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:  

$\ \ \ $ 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.  

$\ \ \ $ 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) ?

-------

That being said, the following issues remain in this submission:

$\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.

$\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.

$\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.

$\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. 

All 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.

I 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.
review_title: Replacing one of the two function samples in zeroth-order online learning algorithms with an old sample collected at a previous iteration: potential and limitations of the technique.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary:
The 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.   

Evaluation:
I 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.

Pros:
1. New theoretical results which are significant for optimization and learning literature, as well as for applications. 
2. Numerical results support theoretical findings.
3. The paper is overall clearly written and motivated.

Cons:
1. There are several minor comments mainly on the clarity of presentation. See below.


Minor comments
1. Some related work seems to be missing
http://proceedings.mlr.press/v48/hazanb16.pdf (non-convex optimization with one-point feedback)
https://link.springer.com/article/10.1007%2Fs10107-014-0846-1 (non-convex stochastic optimization)
http://papers.nips.cc/paper/5377-bandit-convex-optimization-towards-tight-bounds.pdf
http://papers.nips.cc/paper/4475-stochastic-convex-optimization-with-bandit-feedback.pdf 
2. 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?
3. 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.
4. 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.


review_title: A good paper with new theoretical results and empirical evidence

final_score: rating: 4: Ok but not good enough - rejection
review_content: 1. Paper contribution summary
    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. 

2. Strong and weak points of the paper
    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. 

    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. 

3. My recommendation
    I would suggest a rejection due to the problematic update rule in Eq.(4) and the constant order improvement.

4. Supporting arguments for my recommendation.
    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.

5. Questions 
    1) Can the author/s confirm if the update in Eq.(4) is problematic? 
    2) Why using two different regret metric in non-convex problems? 
    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?


review_title: The zeroth-order algorithm in constrained case is problematic

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