Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations

We sincerely thank you for the thorough and constructive feedback. Below we respond to the comments in Weaknesses (W) and Questions (Q). We have also uploaded a Paper Revision with modified content in red.

• W1: Unspecified criterion for the word "optimal".

  A: We thank the reviewer for highlighting this ambiguity. We acknowledge that our use of the term "optimal" was imprecise in this context. We have revised the manuscript to replace "optimal perturbation" with a more specific description: achieving minimum asymptotic variance as the perturbation step $\mu\to 0$. This is also what our work aims to convey: The widely used fixed length random perturbation is not the only distribution that achieves such minimum variance; the DAP presents an alternative approach to achieve the same criterion.

• W2: Experiment Validation.

  A: We appreciate the reviewer's valuable feedback. To address this concern, we have conducted an additional experiment focusing on mesh optimization—a crucial component in numerical PDE solving. This experiment aims to optimize vertex positions in pre-defined meshes to enhance PDE solver performance by minimizing numerical errors and improving solution accuracy.

  The results, detailed in Appendix E (Additional Experiments), demonstrate that DAP significantly outperforms both uniform and Gaussian perturbation methods (Figure 7). This experiment serves two purposes: it not only showcases DAP's superior performance over classical random perturbations but also illustrates the anisotropic behavior in gradient estimation in a practical application—a key distinguishing feature of DAP compared to conventional random perturbation methods.

  In Appendix E.2, Figure 6 compares numerical PDE solutions between coarse and fine meshes, revealing that mesh corners require denser vertex positioning for improved accuracy. Furthermore, Figure 8 visualizes the gradient estimation norms using uniform distribution versus DAP, demonstrating that DAP's gradient estimator structure more closely aligns with the ground truth and appropriately emphasizes the mesh corners.

• W3 & Q1: Impact of Taylor approximation in the theoretical analysis.

  A: We thank the reviewer for pointing out this critical point. In our revised version, we have added an additional remark and an appendix section to discuss the error caused by the Taylor approximation. We shortly summarize it as follows: We use the bounded Hessian assumption to upper bound the residual term of the Taylor series. When the perturbation step $\mu$ is sufficiently small, we will be able to control the error of this error term.

  We note that although we didn't explicitly state this error term in our main text, we have already considered its impact in our original convergence analysis (Lemma C.8). We have further discussed its influence in the final upper bound in Appendix G Discussions on the Accumulative Errors.

• W4: Discussions on the limitation.

  A: We appreciate the reviewer's suggestion. We have added the limitation section in the revised paper. Shortly speaking, we have emphasis the following three points: (1) The projection step requires to store the whole gradient estimation, which may cost too much memory. (2) The additional estimation step in Algorithm 2 introduces additional error in the gradient estimation, which potentially makes the DAP underperform standard methods in traditional tasks. (3) More experiments could be needed to clearly verify when the DAP method is better and when the DAP method is not.

Dear Reviewer aCKy,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors with whether they have addressed your concern and whether you will keep or modify your assessment on this submission?

Thanks.

Area Chair

Dear author(s), thank you for your detailed response. I have waited for further engagement by the other authors because I thought I had nothing to add. On my side, it looks like you have sufficiently addressed my comments.

I will raise the score, and vouch for acceptance. Please note that since there is no "7" and "6" is a marginal grade (which I want to avoid), my score is 8 on this scale.

Good luck.

We sincerely thank your careful reading and constructive feedback. Below we respond to the comments in two Weaknesses (W). We have also uploaded a Paper Revision with modified content in red.

• W1: Regarding the "only if" part of Theorem 2.2.

  A: We appreciate this insightful question. While we establish a sufficient condition for achieving minimum variance, we acknowledge that this condition is not necessary. Finding the necessary condition (of achieving the minimum variance) is much harder than finding the sufficient condition. We can easily construct a mixed distribution that is neither the DAP nor the constant magnitude perturbation by taking the probability $p$ to be the DAP and the probability $1-p$ to be the constant magnitude perturbation.

  We believe it is possible to obtain the necessary and sufficient condition by further restricting the distribution class of the random perturbations. However, we still choose to present our current version due to the following reasons: (1) Our chosen distribution class (i.e. all distribution $V$ such that $E_{v\sim V} vv^\top = \delta I_d$) aligns with standard frameworks in the field, such as [Kozak2023] and [Rando2024]. While restricting this class might yield necessary and sufficient conditions, it would deviate from established conventions. (2) The directional alignment condition we present introduces a novel class of random perturbations with compelling anisotropic properties. We believe this discovery makes a meaningful contribution to the optimization community, even without characterizing the complete set of minimum-variance distributions.

  [Kozak2023] Kozak, David, et al. "Zeroth-order optimization with orthogonal random directions." Mathematical Programming 199.1 (2023): 1179-1219.

  [Rando2024] Rando, Marco, et al. "Stochastic zeroth order descent with structured directions." Computational Optimization and Applications (2024): 1-37.

• W2: Experiments.

  • Other practical application.
  • Comparison with other constant magnitude perturbations.
  • Explain why DAP is better (even they have the same variance).

  A: Thank you for these constructive suggestions. We have expanded our experimental section in Appendix E with two key additions: (1) A new practical application involving mesh optimization for PDE solvers, where we optimize mesh configurations to enhance numerical accuracy. (2) The comparison among other constant-magnitude perturbation in the language model fine-tuning experiment.

  The reason why the DAP achieves better performance on the certain application is that the DAP will automatically detect which direction is more important; therefore, it provides more accurate estimation on these directions. We have illustrated this phenomenon in the Figure 2.

  To explain this phenomenon in a more practical example, we further illustrate it in the mesh optimization problem. In Appendix E.2, Figure 6 compares numerical PDE solutions between coarse and fine meshes, revealing that mesh corners require denser vertex positioning for improved accuracy. Furthermore, Figure 8 visualizes the gradient estimation norms using uniform distribution versus DAP, demonstrating that DAP's gradient estimator structure more closely aligns with the ground truth and appropriately emphasizes the mesh corners. As the result, higher accuracy on these corner vertices improve the performance of the DAP.

Dear Reviewer gWHS,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors with whether they have addressed your concern and whether you will keep or modify your assessment on this submission?

Thanks.

Area Chair

We sincerely thank you for the comment. Below we respond to the comments in two Weaknesses (W). We have also uploaded a Paper Revision with modified content in red.

• W1 (Dimension-Free Rate): I don't think the study over problem Eq. (3) is meaningful. Under the theory of this paper, the random coordinate is better than Gaussian random vector. However, just as pointed out in Theorem 1 of "Fine-tuning language models with just forward passes'', the Gaussian random vector can provide a "Dimension-Free Rate''. Unfortunately, the random coordinate can not guarantee this ``Dimension-Free Rate'' even it is good under the theory of this paper.

  A: We politely disagree with this point. We would like to highlight that the dimension-free rate in the paper "Fine-tuning language models with just forward passes" requires the Local $r$-Effective Rank assumption (the Assumption 1 in their paper). The dimension-free rate in that paper is not because the Gaussian perturbation is used; instead, it is because the local $r$-effective rank assumption is made. Without adding additional assumption, the dependence on the dimension $d$ is not avoidable (see [Duchi2015]).

  [Duchi2015] Duchi, John C., et al. "Optimal rates for zero-order convex optimization: The power of two function evaluations." IEEE Transactions on Information Theory 61.5 (2015): 2788-2806.

• W2 (No significant advantages of DAP): The experiments in this paper do not show significant advantages of DAP over other estimations.

  A: We appreciate the reviewer's comments and would like to highlight: First, Figure 3 demonstrates that the DAP achieves significant improvements in estimating the gradient of the product function with respect to the $\tau$-effective MSE. Furthermore, as shown in Figure 4, the convergence performance using DAPs is substantially faster compared to both other methods.

  To directly address the reviewer's concerns, we have conducted an additional experiment on the mesh optimization problem. The results, presented in Figure 7, further validate that DAP outperforms the other two random perturbations in this context as well.

  We would like to clarify that we have not claimed our method universally outperforms traditional approaches across all scenarios, nor was this our research objective. Instead, our primary contribution lies in identifying and characterizing a novel type of random perturbation. The anisotropic nature of DAP is significantly different from existing random perturbation methods, marking it possible to achieve particular advancement in specific fields. We respectfully ask the reviewer to consider this novel finding and the important theoretical contribution when evaluating our work.

We sincerely thank the reviewer for their thorough and constructive feedback. We appreciate the positive assessment of our work. Below we respond to the comments in Weaknesses (W) and Questions (Q). We have also uploaded a Paper Revision with modified content in red.

• W1.1: Is the converse of Theorem 2.2 also true? & Q2: Is (a) and (b) in Theorem 2.2 sufficient conditions for achieving the minimum variance, or are they also necessary conditions?

  A: We appreciate this insightful question raised by the reviewer. The converse is unfortunately not true and we only derive the sufficient condition for achieving the minimum variance. Finding the necessary condition (of achieving the minimum variance) is much harder than finding the sufficient condition. We can easily construct a mixed distribution that is neither the DAP nor the constant magnitude perturbation by taking the probability $p$ to be the DAP and the probability $1-p$ to be the constant magnitude perturbation. We believe it is possible to obtain the necessary and sufficient condition by further restricting the distribution class of the random perturbations. However, we still choose to present our current version due to the following reasons: (1) We prefer to consider the current distribution class (i.e. all distribution $V$ such that $E_{v\sim V} vv^\top = \delta I_d$) instead of further restricting it to obtain the necessary and sufficient condition because the current setting is more standard. The similar distribution class can be found in [Kozak2023] and [Rando2024]. (2) The directional alignment condition has already revealed a new class of random perturbations which presents an attractive anisotropic behavior; we truly believe it is an interesting and impactful result to share with the optimization community.

  [Kozak2023] Kozak, David, et al. "Zeroth-order optimization with orthogonal random directions." Mathematical Programming 199.1 (2023): 1179-1219.

  [Rando2024] Rando, Marco, et al. "Stochastic zeroth order descent with structured directions." Computational Optimization and Applications (2024): 1-37.

• W1.2: How to elaborate the finite fourth-order moment condition in the upper bound? Is it the necessary condition?

  A: We appreciate this insightful question raised by the reviewer. The fourth-order moment condition $E_{v\sim V} \| v\|^4 = \delta^2 d^2$ can be treated as another sufficient condition, which we didn't consider in our paper. It is weaker than the fixed-length perturbation (because $\|v\|^2=\delta d$​​ implies this fourth-moment condition); however, it remains unclear if this condition could be the necessary condition. We believe it could be an interesting topic to be further explored in the future.

• W2 & W3 : What is the contribution of convergence analysis in Section 3? What is the role of Theorem 3.1 in the overall context of the paper?

  A: We appreciate the reviewer's constructive suggestion. We have added an overview paragraph at the beginning of the Section 3.

  In existing literature, the approximation error of the gradient estimation $E_{v\sim V}\\| \hat{\nabla} f(x;v) - \nabla f(x) \\|^2$ is commonly tailored to a specific type of random perturbation. For example, [Nesterov2017] only considers the Gaussian random perturbation; the explicit Gaussian density allows the tight characterization of the dependence on the parameter dimension $d$. By applying the upper bound obtained from Theorem 2.2, we are able to build a much more general upper bound with such optimal dependence.

  [Nesterov2017] Nesterov, Yurii, and Vladimir Spokoiny. "Random gradient-free minimization of convex functions." Foundations of Computational Mathematics 17.2 (2017): 527-566.

• Q3: Theorem 3.1 only provides an upper bound result, which doesn't support the claim made in the remark of Theorem 3.1.

  A: We appreciate the reviewer point out this crucial point. We agree that the upper bound result doesn't support the claim that a small $\delta$ leads to more gradient updates. Here, we intended to state the reason why we only consider the case $\delta=1$ in our worst-case complexity analysis. We have revised the comment (a) to reflect our purpose more clearly.

Minor questions: Thanks for pointing out these issues. We have removed the redundant definition of parameters in Theorem 3.1 and fixed the typo in line 215 in our revised paper.

We sincerely thank the reviewer for their thorough and constructive feedback. We appreciate the positive assessment of our work. Below we respond to the comments in Weaknesses (W) and Questions (Q). We have also uploaded a Paper Revision with modified content in red.

• W1: The stochastic optimization setting is not needed in the first part of the paper but only for SGD (Section 3), and it creates confusion.

  A: We appreciate the reviewer's suggestion. We have added additional subsection (Section 1.1 Paper Structure) in the introduction to describe the structure of our paper, which we hope could improve the overall clarity.

• W2: How to deduce the result of Theorem 2.2:

  • Q1: Is $\rho_V=0$ a sufficient condition?
  • Q2: $\rho_V \neq 0$ doesn't imply Gaussian smoothing is not optimal.

  A: We appreciate the your insightful comments. We acknowledge that our statement regarding the Gaussian smoothing is not accurate. As the reviewer point out, our proposed conditions including ($\rho_V=0$) are only the sufficient condition; it is easy to construct a perturbation that is neither the fixed length and the DAP: We can sample a perturbation from the uniform smoothing with the probability $p$, then sample from the DAP with the probability $1-p$. This construction doesn't change the variance but doesn't satisfy either condition.

  Therefore, from our statement, we cannot conclude that the Gaussian smoothing fails to achieve the minimum variance as claimed by simply evaluating the fourth-order moment $E\\| v\\|^4$. Fortunately, our statement is still correct: the matrix $E (vv^\top)^2$ can be explicitly solved when the distribution $v$ is known as $N(0, I_d)$; it is a diagonal matrix with $E[(vv^\top)^2_{i,j}]=0$ for $i\neq j$ and $E[(vv^\top)^2_{i,j}]=E[v_i^4] + (d-1)=d+2$ for $i=j$. It concludes that asymptotic variance of $\hat{\nabla} f(x;v)$ as $\mu \to 0$ is $(d+1)\| \nabla f(x)\|^2$ which is larger than the minimum asymptotic variance $(d-1)\| \nabla f(x)\|^2$ achieved by the uniform distribution over the sphere $\\|v\\|^2=d$. To avoid the confusion, we have removed our inaccurate statement regarding the Gaussian smoothing in our text.

• Q2: With which distribution do you sample for the estimator of the gradient used in DAP?

  A: We simply use the uniform distribution over sphere to obtain the gradient estimation. The choice of this distribution can be set as a hyper-parameter, while it is not a crucial factor in the final performance.

Bibliography: We appreciate the reviewer providing these highly relevant references. We have updated the bibliography and revised the introduction section to include these results.

Minor comments: Thanks for the careful reading. We have thoroughly revised the paper to fix typos, clarified the needs of requiring $\mu \to 0$ for obtaining the unbiasedness, added discussion on the error caused by the Taylor formula approximation, highlighted that the DAP is not directly available, and improved the overall clarity.