- Rating
- 4(+1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper analyzes standard two-point Gaussian zeroth-order optimization under a uniform pointwise bound on the Hessian trace norm. It establishes nonconvex stationarity and PL convergence guarantees without requiring a common Hessian envelope, with explicit smoothing and noise terms. A Twisted Valley construction demonstrates a separation between the proposed condition and global envelope assumptions. Synthetic and neural-adaptation experiments illustrate how Gaussian probing behaves as the parameter dimension increases.
Critical strengths
-
The paper provides a nontrivial extension of effective-dimension analysis beyond common Hessian envelopes. It clarifies that pointwise concentration of curvature can support favorable convergence guarantees even when the dominant curvature directions vary with location.
-
The Twisted Valley construction makes the theoretical contribution concrete: its trace-norm and PL constants remain independent of dimension, while any global Hessian envelope must have a trace that grows with dimension.
Critical weaknesses
-
The practical importance of the assumption relaxation could be explained more clearly. The paper would benefit from identifying realistic optimization problems where the uniform trace-norm condition is plausible and a common low-trace envelope is substantially more restrictive.
-
The neural experiments provide limited validation of this practical connection. The head-only control achieves similar performance, and the selected step sizes exceed the theoretically guaranteed range. Although these limitations are acknowledged, the experiments do not clearly establish the relevance of the newly covered regime to practical training.
-
The theoretical novelty is relatively focused: the estimator and effective-dimension measure are established, and the PL result follows from a standard argument. The significance of removing the common-envelope requirement could be clearer.
Questions for authors
-
Clarification of the theoretical comparison: In Section 5.2, the local-envelope trace bound depends on a neighborhood radius that itself depends on the step size and iterate. Under precisely which conditions does the claimed linear growth with dimension hold? How does the comparison change when the step size depends on dimension?
-
Additional evidence relevant to the empirical assessment: Can the authors provide trajectory-level diagnostics showing that successful ZO runs encounter substantial changes in dominant curvature directions while maintaining controlled Hessian trace norms? The existing nonrotating and head-only controls are useful, but such diagnostics would more directly connect the observed optimization behavior to the distinctive setting covered by the analysis.
2 comments
Response to reviewer xguL (2/2)
Q1: Clarification of the theoretical comparison in Section 5.2
We thank the reviewer for this question. Following it, we revised Section 5.2 in two respects.
First, we corrected the description of the envelope conditions. The submitted version described both DPZero and MeZO by a one-sided bound and stated that our condition is implied by both, which holds for DPZero but not for MeZO. The revised Section 5.2 distinguishes the two. DPZero requires a global two-sided envelope, for every . MeZO requires a local one-sided envelope, on a ball around of radius at least . Proposition 5.2(i) now requires only a symmetric , instead of , and applies to both.
Second, we added to Section 5.2 the step-size regime in which the linear growth holds. It holds at a step size independent of , as in the analysis of MeZO. The radius then grows linearly in , and by Proposition 5.2(i), the trace of the envelope grows linearly as well. If the step size depends on , keeping the radius bounded requires . This reduces the decrease per iteration by a factor of . In both regimes, the envelope analysis pays a factor of on the Twisted Valley, whereas our guarantee holds at with independent of .
Response to reviewer xguL (1/2)
We address your concerns below.
W1 and Q2: Practical relevance and trajectory-level diagnostics
Thank you for raising this important issue. As you pointed out, the submitted version compared the leading eigenspaces only at two nearby points of one run and did not follow their change along the trajectory. To address this, we conducted an additional experiment that computes the exact Hessian every 500 queries along one ZO-Gauss run on the adapted CNN and ViT.
For each iterate z, the table below reports the overlap ∥Uz⊤Ux∥F2/k between the leading k-dimensional eigenspaces of the Hessian at z and at the final iterate x after 4000 queries, where Uz and Ux are their orthonormal bases.
These results show that successful ZO-Gauss runs encounter substantial changes in the dominant curvature directions while the trace norm of the Hessian stays bounded. This is precisely the regime that our pointwise condition covers. A common envelope, in contrast, would have to dominate all the directions met along the run. We added these results to Appendix E (Figure 8) and refer to them in Section 6.2.
W2: Head-only control and step sizes in the neural experiments
Head-only control. We agree that the validation in the submitted version was limited. The width sweep shows that the added dimensions do not slow ZO-Gauss but slow ZO-Coord. Since ZO-Gauss reaches within the budget the same loss as without the adapter (r=0), however, the sweep does not show whether ZO-Gauss uses these dimensions.
To test this, we added a sweep that starts the head at the optimum of the head-only model, whose training loss we denote by fLP (Appendix F.4, Figure 11). Since fLP is the minimum over the head alone, the loss goes below it only through the adapter. The table below reports the decrease fLP−f of the training loss after 40000 queries (median over five seeds), with gradient descent (GD) at the same step size as ZO-Gauss.
ZO-Gauss lowers the loss below fLP for every d, by about as much as GD with the same step size, whereas ZO-Coord hardly lowers it for large d.
Step sizes. We agree that the selected step sizes exceed 1/(100H). As we remark after the proof of Proposition A.8, the constant 100 is not optimized and may leave room for improvement. The theory predicts that the step size depends on d only through H, and the selected step sizes agree with this. On the Twisted Valley, the tuned step size of ZO-Gauss in Appendix D is 0.3 for every d from 50 to 50000. In the width sweep of Table 1, d grows thirteenfold from 647 to 8645, and the classical step size 1/(dL) would decrease by more than an order of magnitude. The selected step size of ZO-Gauss decreases by at most a factor of three, from 3×10−3 to 10−3 on the CNN, and does not change on the ViT.
W3: Theoretical novelty and significance
Thank you for helping us clarify our theoretical contribution. We revised Section 2 and Remark 4.6 to explain the technical contribution of removing the curvature envelope. Beyond quadratics, the Hessian enters the descent inequality at points that depend on the random direction, and bounding it there by its operator norm costs a factor of d. We explain the two tools by which we avoid this factor, an averaging over the rotations that fix the gradient and a bound along rays based on the Gaussian Poincaré inequality and an integrated Bochner identity.