Variance-Reduced Normalized Zeroth Order Method for Generalized-Smooth Non-Convex Optimization

1. There are so many typos and grammar issues in the paper. This was really annoying when I was reading the paper. I am not sure whether this comes from that this paper was written in a rush or are there any other reasons? If the paper was written in a rush, then I would reasonably question the correctness of the theoretical proofs. Here are some issues (I could not list all of them as there are so many). line21 in the abstract: complexes; line86-93: what do you mean by "we both analyze, we both use"; line98: can as effective as; line123 in table 2: estimator denotes represent the number; line194, 239: can't access to; line265: should be introduced; line308 in Algo. 1: defied in (5) and (4); line364: constans; line376: itration; line382, 408, 420: funtion; line408, 420: number of e function query; line 524: coordand rand. Some weird spacing: line40, distribution.In; line 42; line 162. Grammar: You cannot just list a sequence of sentences in English, e.g., "sentence A, sentence B, sentence C". They should be connected using conjunctions (and, but), relative clauses (which, where, that), or transitional words or phrases (however, moreover). This happens several times in the paper, e.g., line 76-79, 187-199, 202-203, 284-286, 347-354, 364-376. I completely understand the strict timeline for submission, where typos and grammar problems are unavoidable. However, such many issues are unaccepted. It disrupts readability and affects clarity of the paper. This is also unfair for other submissions where the authors spend lots of time on polishing the paper. As a reviewer, it is also frustrating to evalute papers that are far from publication standard.

2. Some classical results on zeroth-order methods are missing. $\mathbb{E}\bar \nabla f=\nabla_\mu f$ was first proved in [1] as far as I know. Classical analysis of zeorth-order methods were provided in [2] and [3]. [4] also studied variance reduced zeroth-order method, and [5] discussed the lower-bound.

[1] Online convex optimization in the bandit setting: Gradient descent without a gradient. SODA 2005.

[2] Random gradient-free minimization of convex functions. Nesterov and Spokoiny.

[3] An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. JMLR, 2017.

[4] Zeroth-order stochastic variance reduction for nonconvex optimization. NeurIPS, 2018.

[5] Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE, 2015.

3. The authors claim their complexity on $\epsilon$ and $d$ is optimal. However, there is no discussion on the lower-bound in the paper under Assumptions 1-3 for zeroth-order methods. Usually, the complexity of zeroth-order methods is $d$-times worse compared to first-order methods (see lower-bounds in [5] above), but that is for $L$-smoothess setting. The author should discuss why the same lower-bound applies to the generalized smoothness setting. Before that, it is only valid to claim the complexity being best-known upper-bound instead of the optimal.

4. Another option for Coord estimator is to only sample a subset of all $d$ coordinates instead of computing every coordinate, as the current one is computational challenge for problem with large dimensions.

5. Although the paper is indeed the first one on zeroth-order optimization with generalized smoothness condition, I am not surprised by any of its results. All the proof techniques exist before, and there are no fundamental difference by combining all related works. First, existing work already show $\epsilon^{-3}$ rate using SPIDER under the generalized smoothness condition. Second, extensive literature provides examples how to extend from first-order methods to zeroth-order methods. The computation involved in Lemmas 1-3 is also standard, and there is nothing special. I can only rate the novelty as marginal.

6. It is unclear why the current experiments verify the effectiveness of the proposed method. I am not sure why one has to apply zeroth-order methods on applications (10) and (9), where gradients are accessible and not hard to compute. These might be good examples for $(L_0, L_1)$-smoothness, but not for why zeroth-order methods should be applied. Why not just use first-order methods on the two applications? Zeroth-order methods are useful when gradient is not possible or hard to obtain, and the current experiments do not belong to this class.

7. In the theoretical results, the complexity of the proposed zeroth-order method is $d\epsilon^{-3}$, while that of first-order methods is $\epsilon^{-3}$. This means zeroth-order method is $d$-times worse compared to first-order methods. Then why is it the case that in Figures 1(c) and 1(d), there is not much difference between zeroth- and first-order methods? What is the sample complexity here in the figure? Is it queries on $f$, or queries on $|S|$ number of $f$?

• The paper is poorly written; there are many typos, and some sentences are confusing and unfinished. The manuscript should be polished and revisited.
• Assumption A2(3) is a strong assumption that requires the $(L_0, L_1)$-smooth property to be satisfied for every sample.
• The paper does not present and compare with the results on convergence of the SPIDER method for $\alpha$-symmetric functions provided in Chen et al 2023; they also used normalization, and the analysis in their work has the same challenges and tricks used in this paper. ZO-normalized-SPIDER is exactly Algorithm 2 (Spider). In Technical Novelty paragraph in Chen et al 2023, the same problem of bounding $\mathbb{E}[\|v_k - \nabla f(x_k, \xi)\|^2]$ is solved.

Please address the following concerns:

• line 048: A key observation where? This sentence is not complete.
• lines 194-195 the sentence there is incomplete.
• the error bound in Lemmas 1, 4 holds only for $\mu$ is bounded by some constant, perhaps $\frac{1}{L_1}$.
• sentence on lines 392-393 is not clear. Typos:
• line 041, these problems
• line 042, space between notable.
• lines 047-048, critical applications such as LSTM. Perhaps you want to say critical application such as training of LSTM models.
• line 098, it should be zeroth-order methods
• line 10,1 it should be convergence instead of converge
• lines 123-124,

denotes represent

perhaps one of these is a typo.

• lines 1628-1629 dut should be due
• line 230, approximate should be approximation

1. rand estimator seems to be not optimal one, e.g. see Shamir's (O. Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(1):1703–1713, 2017.) or Polyak-Tsybakov ones (if you have high-order smoothness) https://arxiv.org/pdf/2306.02159
2. I don't understand how $L_0$ and $L_1$ could be compared in $\max\{\cdot\}$ in formulas. They have principally different physical dimension.
3. There are no high-probability deviations bounds in the paper
4. The only improvement from my point of view is gradient-free generalization of full (stochastic gradient procedures), but nowadays this is quite a routine procedure.

My primary concern is the significance of the technical contribution. The analysis of gradient estimators (Lemma 1, 2 and 4) is almost identical to Lemma 1 and 3 from Liu et al. (2018), with smoothness replaced by generalized smoothness assumption. Consequently, I do not see substantial technical novelty as claimed after Lemma 3, though it is understandable that leading lemmas might not be novel. I also urge the authors to add relevant citations, such as counterparts of lemmas that hold for $L$-smooth or first-order strategies, for better reference.

The writing of the manuscript should be carefully checked, as the current version contains much ambiguity and is error-prone. See the Questions section for details.

Reference:

Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems 31, 2018.