- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper develop a framework to reconstruct the objective smoothed function optimized by a given zeroth-order gradient estimate.
The method consists in identifying the sampling distribution of the perturbations and the weighting function , and integrate the reconstruction equation given by the authors to obtain the smoothing distribution .
The introduced "reconstruction" methodology unifies several zeroth-order gradient estimators (Gaussian ES, randomized/fixed-denominator perturbations or deterministic finite differences) estimators and allows their comparison in Table 1.
The authors also illustrate the obtained "reconstructed" smoothing kernels in Figure 1 and their implication on the minimized fonction.
Critical strengths
The paper proposes an elegant unification of several zeroth-order gradient estimators under the lens of the objective they minimize.
The paper is clearly written and develops the reconstruction strategy very pedagogically.
Critical weaknesses
Despite the quality of the unified framework, the papers does not leads to any important knowledge breakthrough. No general property emerge from this unification, no innovative kernel is introduced, and the method is mainly applied to known smoothing kernels. The traditional "target-first" construction of gradient estimates is a way to discover new potential zeroth-order gradient estimators, but the impact of the presented "update-first" reconstruction is less clear (see Figure 1).
Moreover, the main point of these ZO gradient estimator is to be used to minimize a given objective function . The optimization aspect is almost absent of the paper (beside being evoked in the Discussion section).
Questions for authors
- Q1) Could this paper be useful to cite and to rely on to refer to existing known bounds of the DFO different estimators? Beharas et al, 2022 "A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization"
- Q2) Could you be more precise in line 161?
- Q3) Line 192. Isn't this comment (about the unbiasedness of the gradient estimate relative to the smoothed objective) also true for the estimates of equation (5), cf Nesterov & Spokiony 2017 equation (31).
- Q4) Line 282. Maybe it's trivial, but could you explain why requires the weights function to be centered under ?
- Q5) Out of curiosity, how are the kernels for fixed denominator Gaussian and uniform zeroth order estimators compare with those in Figure 2 (a)?
Comments/Suggestions:
- It is known from experts of the domain that one must be careful with the rescaling factor when it comes to ZO gradient estimate with perturbations sampled uniformly over the (unit) sphere (or one has to sample over the sphere of radius . I would encourage the authors to precise this once in their article around Section 2.2
- Maybe it could be good to add explicitly in Table 1 the gradient estimates corresponding to each pair of sampling and weight function.
- Line 346,. "these full candidates" are the individual coordinate-wise candidates given in 344?
2 comments
Response to Reviewer oG68 (2/2)
Q1. Existing bounds for derivative-free estimators
Could this paper be useful to cite and to rely on to refer to existing known bounds of the DFO different estimators? Beharas et al, 2022 "A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization"
Thank you for pointing us to this paper. The results of Berahas et al. (2022) could help connect the smoothing bias discussed in Appendix F to the accuracy of gradient estimates obtained from finitely many function evaluations and to convergence conditions for optimization.
Q2. Line 161
Could you be more precise in line 161?
Assume that the Hessian of is -Lipschitz in operator norm and that . The estimator in Eq. (5) then satisfies
\le (L_H/6)\sigma^2\mathbb E\|Z\|^4.$$ In the second-order Taylor expansions of $f(\mu+\sigma Z)$ and $f(\mu-\sigma Z)$ about $\mu$, the constant and quadratic terms cancel upon subtraction. Each remainder is at most $(L_H/6)\sigma^3\|Z\|^3$ in absolute value. After dividing by $2\sigma$ and multiplying by $Z$, the remainder has norm at most $(L_H/6)\sigma^2\|Z\|^4$. The leading term is $ZZ^\top\nabla f(\mu)$, whose expectation is $\nabla f(\mu)$ because $\mathbb E[ZZ^\top]=I_d$ as assumed in Eq. (5). If the paper is accepted, we will replace “sufficiently smooth” with “the Hessian of $f$ is Lipschitz continuous in operator norm.” ## Q3. Does line 192 also apply to Eq. (5)? > Line 192. Isn't this comment (about the unbiasedness of the gradient estimate relative to the smoothed objective) also true for the estimates of equation (5), cf Nesterov & Spokiony 2017 equation (31). Thank you for pointing this out. Yes, this also holds for Eq. (5) with Gaussian perturbations. Nesterov and Spokoiny (2017) give the corresponding finite-scale identity and estimator. We will make the connection to Eq. (5) explicit at line 192 and cite them. ## Q4. Why must the weights be centered under the sampler? > Line 282. Maybe it's trivial, but could you explain why $\partial_{\theta_j} p_\theta (x) = q_\theta (x) \psi_{\theta_j} (x)$ requires the weights function to be centered under $q_\theta$? Since $p_\theta$ is a probability density, its total mass is $1$ for every $\theta$. Integrating the reconstruction equation over $x$ therefore gives $\mathbb E_{X\sim q_\theta}[\psi_\theta(X)]=\partial_\theta\int p_\theta(x)\,dx=0$, provided differentiation can be interchanged with integration. ## Q5. Fixed-denominator kernels in Fig. 2(a) > Line 282. Maybe it's trivial, but could you explain why $\partial_{\theta_j} p_\theta (x) = q_\theta (x) \psi_{\theta_j} (x)$ requires the weights function to be centered under $q_\theta$? Both fixed-denominator estimators are shown in Fig. 2(a). The Gaussian version corresponds to “Gaussian ES” and has a Gaussian smoothing kernel. The version with perturbations sampled uniformly from an interval corresponds to “Uniform numerator” and has an Epanechnikov smoothing kernel. ## Comments/Suggestions > It is known from experts of the domain that one must be careful with the rescaling factor $d$ when it comes to ZO gradient estimate with perturbations sampled uniformly over the (unit) sphere (or one has to sample over the sphere of radius $\sqrt{d}$. I would encourage the authors to precise this once in their article around Section 2.2 > Maybe it could be good to add explicitly in Table 1 the gradient estimates corresponding to each pair of sampling and weight function. >Line 346,. "these full candidates" are the individual coordinate-wise candidates given in 344? Thank you for your comments. The phrase "these full candidates" in line 346 refers to the individual coordinate-wise candidates introduced in line 344. If the paper is accepted, we will make this reference explicit.
Response to Reviewer oG68 (1/2)
Thank you for your careful review and constructive questions.
W1. What the framework reveals
Our contribution is to identify the objective function that an implemented sampler and set of update weights implicitly differentiate, thereby providing an intuitive interpretation of existing algorithms. The kernel shapes in Fig. 2(a) help explain how these estimators behave.
The reconstructed kernels also provide new insights. Section 5.3 identifies the objectives implicitly differentiated by existing random-denominator estimators. Uniform perturbations yield a logarithmic kernel, and Gaussian perturbations yield a kernel involving the exponential integral. Fig. 2(a) also shows that, even when evaluation points are sampled from the same uniform distribution on an interval, different update weights yield logarithmic and Epanechnikov kernels.
Proposition F.1 further illustrates the value of kernel reconstruction. For a function f with an L-Lipschitz gradient, it uses the mean perturbation norm aj=E[∥U(j)∥] under the reconstructed kernel. The bias b(μ)=E[gμ]−∇f(μ) satisfies
∥b(μ)∥≤ζrec:=L(∑j=1daj2)1/2.
W2. Connection to optimization
The appendix discusses the connection to optimization performance. If the paper is accepted, we will also include this discussion in the main text. For example, under the assumptions of Proposition F.1, if the original objective f is λ-strongly convex, Appendix F shows that the distance from any point μ^ at which the expected update is zero to the minimizer μ⋆ of f satisfies
∥μ^−μ⋆∥≤λζrec.