Zeroth-Order Optimization Finds Flat Minima

Many thanks for the detailed review and instructive feedback. We provide clarifications below.

1. Challenging to evaluate due to smoothness and convexity assumptions.

Previous work on SAM-based models has primarily focused on analyzing their methods in non-convex cases. If the entire region under consideration were convex and smooth, it is likely that many existing methods would demonstrate good properties. Therefore, evaluating the theoretical findings of this paper becomes challenging. I believe the lack of analysis for non-convex cases and the absence of a theoretical comparison with other methods weaken the paper's contribution.

Thanks for this valuable comment. We agree that convergence analysis on nonconvex functions will make our paper even more solid, but we respectfully disagree that only considering smooth and convex functions directly suggests that our results are not significant and challenging to evaluate.

• Significance of our results. First, the implicit regularization of zeroth-order optimization in Eq. (2) and (3) does not require the smoothness and convexity assumptions and holds for any twice continuously differentiable functions. The test function in Figure 1 is nonsmooth and nonconvex, but zeroth-order optimization is capable of decreasing both the objective value and the trace of Hessian. Second, we provide the first convergence guarantees towards flat global minima. This can be extended to the case where the function is only locally convex in a neighborhood; see Remark 3.2.

• Existing theoretical understanding of SAM-based methods. The work [11] mainly focused on convex quadratic functions that are smooth and convex. They also discussed nonconvex functions that are locally quadratic and provided implicit regularization of SAM in the form of Eq. (3). [89] did not assume convexity and considered local convergence behaviors for smooth functions. They instead assumed existence of a low-dimensional solution manifold $\Gamma$ consisting of local minimizers with low-rank Hessian matrix and supposed that gradient flow admits attraction set $U$ on this solution manifold $\Gamma$. When initializing on the attraction set $U$, SAM converges to flat minima with the smallest trace of Hessian on the set $U$. [3] considered smooth functions locally satisfying the PL condition. Convergence to stationary points of the trace of Hessian evaluated at limit points under gradient flow was established. Compared with these methods, $(i)$ we adopt a global definition of flat minima that are more challenging to guarantee; $(ii)$ it is not immediate to conclude that they have weaker assumptions of the objective functions. Therefore, we do not think the fact that these paper studied nonconvex functions weakens our contributions.

• More on smooth and convex functions. It is difficult (and sometimes meaningless) to derive algorithms and theoretical complexities with entire generality, such as problems with arbitrary nonconvexity. That's exactly why the majority of literature associates complexity bounds with problem classes. Smooth and convex functions, as an example, are still general enough to capture interesting problems and provide new insights to guide both the design and analysis of algorithms for general nonconvex functions. Logistic regression, as an example of smooth and convex functions, remains an important problem in learning theory and continually reveals new open directions; see (COLT, 2019) and (ICML, 2025) below. Nesterov momentum [71] achieves accelerated convergence rates only on smooth and convex functions, but this does not affect its significance for understanding momentum-based methods central to the success of modern deep learning. Among the most significant optimization techniques of the last decade, variance reduction methods like SAGA and SVRG were first developed only for smooth and convex objectives.

We consider smooth and convex functions as an initial step to analyze convergence to flat minima for zeroth-order optimization. We believe our results provide new insights in the understanding of zeroth-order optimization and open up promising directions in the study of nonconvex functions.

References

(COLT, 2019) The Implicit Bias of Gradient Descent on Nonseparable Data.

(ICML, 2025) Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression.

2. It is surprising that ZO achieves good performance.

It is surprising that a two-point gradient estimator can achieve good performance in learning tasks. In my opinion, this type of method lacks second-order information and should theoretically struggle or fail in ill-conditioned optimization problems. The authors should provide numerical results on well-known optimization problems, such as the Lévy, Ackley, and Rastrigin functions, to support their method's convergence claims.

The two-point estimator is one of the most popular and standard methods used in zeroth-order optimization. There are extensive evidences that zeroth-order optimization can achieve good performance in learning tasks. We refer the reviewer to the work [74] and subsequent literature citing it. Here, we only mention LLMs fine-tuning as a challenging nonconvex learning task. [69] has already reported that zeroth-order optimization is capable of achieving similar performance as first-order methods on many LLMs fine-tuning tasks. We also provide examples in Figures 1 (nonconvex and nonsmooth test function), 2 (convex learning tasks), and 3 (LLMs fine-tuning) demonstrating that zeroth-order optimization achieves good performance.

Although lacking explicit second-order information, Eq. (2) says that zeroth-order optimization can incorporate trace of Hessian implicitly in its objective function, which is the major intuition motivating this work. We agree that explicit second-order information provides richer information of the loss landscape and that second-order methods converge faster on many objective functions. However, second-order information can be computationally expensive when scaling to large model training. The optimizers behind the success of modern deep learning, such as SGD, SAM, and AdamW, are all first-order methods lacking explicit second-order information. They are powerful enough to achieve nice performance.

Following the reviewer's suggestion, we examine the behaviors of zeroth-order optimization on the Levy, Ackley, and Rastrigin functions. Note that all these functions only have one global minimizer, and local minimizers are isolated from each other, unlike the nonconvex test function $(y^\top z-1)^2/2$ in Figure 1 where all points satisfying $y^\top z=1$ are global minima and form a connected solution manifold. On the Levy, Ackley, and Rastrigin functions, behaviors of algorithms crucially depend on the initialization rather than implicit regularization. On the test function in Figure 1, there are infinitely many global minimizers, and implicit regularization selects which minima to converge to. Therefore, the Levy, Ackley, and Rastrigin functions are not good examples to test implicit regularization, and we only report loss values to show that zeroth-order optimization is capable of minimizing them. We choose the dimension to be 100 for all three functions and run different algorithms for $10^4$ steps. "No. of Steps To Converge" is the iteration where the loss stabilizes and the absolute difference between the current loss and the final loss is less than $10^{-15}$.

3. Compare with baseline methods.

The paper lacks a sufficient comparison with baseline methods. I believe there are more than ten relevant zeroth-order (and potentially simple first-order) methods, but the authors choose not to compare their approach against any of them.

It seems there might be a misunderstanding. Our paper mainly studies implicit regularization of zeroth-order optimization with the standard two-point estimator. Evaluating the implicit regularization of additional benchmarks, as well as faster-converging algorithms, lies beyond the scope of this work as we make no claims about them. The goal of our empirical experiments is only to evaluate whether zeroth-order optimization with the two-point estimator decreases the trace of Hessian. In this regard, we believe our current experiment results suffice to support the theoretical findings.

4. Not fully converge on LLMs.

In Figure 3, it appears that the methods have not fully converged.

LLMs fine-tuning is a challenging task. Depending on the dataset, it is often not possible or takes extremely long time to achieve full convergence. The runtime of Figure 3 can be found in Table 2 in the appendix. The current results already take 7 - 30 hours for a single run. Even though the loss might continue to decrease with more iterations, the trend of decreasing trace of Hessian for zeroth-order optimization is already clear and thus suffices to support our claims.

We thank the reviewer for the insightful questions. Here are our detailed clarifications.

1. Strong assumptions.

Very strong assumptions of function to be optimized being twice continuously differentiable and convex. Zeroth-order optimization is particularly interesting if it enables optimization of non-differentiable functions by Gaussian smoothing. However, your work depends on twice continuously differentiable objective functions (eq.2). Do you have an idea if your work could be extended to non-smooth $C^{0,0}$ functions?

Zeroth-order optimization is previously popular for optimizing nonsmooth functions where gradients do not always exist. However, even when gradients can be computed, there are scenarios where zeroth-order optimization still offer clear advantage over gradient-based methods in terms of memory consumption, i.e., LLMs fine-tuning tasks. For example, [69] reported that 8 A100 GPUs, each with 80 GiB of memory, are required for gradient-based methods to fine-tune a 30-billion-parameter model, whereas a single GPU is enough for zeroth-order optimization. Therefore, we focus on the case when the function is differentiable. Note that our current definition of flat minima requires Hessian information, and thus we assume the function to be twice differentiable such that the trace of Hessian is well-defined. Extension to nonsmooth functions requires a different measure of sharpness. A promising alternative is to define flat minima as minima with the smallest $f_\lambda(x) - f(x)$. Detailed study is left for future work.

We consider smooth and convex functions as an initial study of convergence to flat global minima for zeroth-order optimization. We want to emphasize that such guarantees remain unknown before our work in the existing literature. We believe our results open up promising directions in the study of flat minima, including a better understanding for nonsmooth and nonconvex functions.

2. Experiments seem not consistent.

Experimental results consistent with the theory are only found for convex losses (SVM, logistic regression), but not for non-convex losses (LLMs). Is the convexity assumption perhaps more that a theoretical tool to prove convergence?

Our theoretical results only consider zeroth-order optimization, with implicit regularization towards small trace of Hessian for any twice continuously differentiable function in Eq. (2) and (3), and convergence rates to flat minima for convex functions in Corollary 2. We do not argue and claim any behaviors of first-order optimization for general functions. For LLMs fine-tuning tasks, it can be observed that the estimated trace of Hessian decreases for zeroth-order optimization. Therefore, the experiment results are also consistent. Note that the test function in Figure 1 is also nonconvex, and the trace of Hessian also decreases for zeroth-order optimization. This aligns with the implicit regularization in Eq. (2) and (3) that does not require the convexity assumption.

The reason why GD also decreases the trace of Hessian in some settings is that GD also has implicit regularization. For example, GD with large learning rates penalizes the largest eigenvalue of Hessian [20, 7]; Reviewer 2MGS also points out a recent paper showing that full-batch GD converges to flat minima in shallow linear networks. The study of implicit regularization of first-order optimization is not the primary focus of our paper. It still remains an interesting question when and why such implicit regularization happens. We believe this depends crucially on the loss landscape, the initialization point, and the learning rate. A more detailed study on this topic will be valuable to the community.

3. Flat minima and generalization.

No attempt to link flat minima to improved generalization. Isn't the main claim of convergence to flat minima the fact that such methods show improved generalization? Is this the case in your experiments?

We explicitly avoid claiming that zeroth-order optimization generalizes better as it finds flat minima.

• The link between flat minima and improved generalization is still an ongoing research direction. Although there are evidences that flat minima generalize better and methods designed for finding flat minima have better empirical performance, there are also cases where sharp minima can generalize [25] and flat minima do not generalize [88]. In our experiments, we find that GD often converges to flatter minima and has better test accuracy on LLMs fine-tuning tasks, but it is not the case for binary classification tasks.

• The measure of sharpness and definition of flat minima are also undergoing research in the community. In addition to the trace of Hessian used in this work, there are also other widely-adopted notions such as the largest eigenvalue of the Hessian. There are still no agreement on which is the most precise measure that corresponds to generalization performance.

Given these arguments, we only claim in the paper that zeroth-order optimization has implicit regularization towards flat minima, where we adopt the trace of Hessian to measure sharpness. Such implicit regularization is an interesting algorithmic property to explore, as in first-order methods [103, 12, 11], and improves our understanding of zeroth-order optimization. The link between flat minima and improved generalization is not the main focus of the work.

We appreciate the reviewer for highlighting the strengths of our work. We address additional concerns in the following.

1. Extension to nonconvex functions.

It remains unclear whether the conclusions in this paper hold in non-convex scenarios, although the derivation of implicit regularization on the Hessian trace does not require convexity assumptions. Can the results in this paper be extended to non-convex settings?

Although the implicit regularization in Eq. (3) also holds for nonconvex functions, the precise convergence analysis to flat minima requires convexity assumption in the current work. We briefly discuss extensions to the nonconvex setting in Remark 3.2, where the current results can be directly extended to the case where the function is only locally convex in a neighborhood. For general nonconvex functions, convergence analysis to flat minima requires both different definitions of flat minima and novel analysis techniques with additional assumptions. A detailed study is left for future. Nonetheless, we want to emphasize that convergence guarantees to our definition of flat global minima remain unknown before this work in the existing literature. We believe our results provide new insights and present a first step towards more challenging settings, including nonconvex problems.

2. Explanation for GD.

In Figure 3, it seems that GD is more effective than ZO in reducing the Hessian trace. Could the authors provide further explanation for this phenomenon?

GD also has implicit regularization. For example, GD with large learning rates penalizes the largest eigenvalue of Hessian [20, 7]; Reviewer 2MGS also points out a recent paper showing that full-batch GD converges to flat minima in shallow linear networks. The study of implicit regularization of first-order optimization is not the primary focus of our paper. It still remains an interesting question when and why such implicit regularization happens. We believe this depends crucially on the loss landscape, the initialization point, and the learning rate.

We thank the reviewer for the positive feedback and insightful questions. Here are our clarifications.

1. Metric used for model selection.

The authors state that they chose the learning rate and smoothing parameter via grid search. What metric was used to perform this? This paper's evidence may be stronger if the metric used to compare also takes into account the sharpness (via the Hessian norm, for example) of the solutions, rather than just a validation loss (which I assume was used here). Do the results of your experiments change when the grid search is used to prioritize both validation loss and Hessian norm?

We follow standard procedure in machine learning and only use the accuracy as the metric to select the best learning rate and smoothing parameter. We do not directly take into account the sharpness as metric since

• This introduces bias into model selection and affects our evaluation of implicit regularization, since parameters that lead to decreased trace of Hessian are always selected.

• The link between sharpness and model performance is an ongoing research direction. The claim that sharp minima always lead to worse model performance is still debatable [25]. Therefore, we directly use model performance as the metric.

Although the experiment results depend on the hyperparameters, we find that the trend of decreasing trace of Hessian is consistent across choices of learning rates and smoothing parameters such that the two-point estimator results in good model performance.

2. Compare to batch GD.

In [1], the authors show the batch GD (which is used in this paper) can also converge to flatter minima (compared to gradient flow) and establish a linear convergence rate under the edge of stability regime. Can you comment on why your experiments show such a strong bias (as a trade-off for convergence rate) for low Hessian trace compared to batch GD?

Thanks for bringing this interesting paper into our attention. We will include it in the reference of our paper. The study of implicit regularization of first-order optimization is not the primary focus of our paper. It still remains an interesting question when and why such implicit regularization happens. In our experiments, although the behavior of zeroth-order optimization is consistent across all three settings we consider, the behavior of GD varies; the trace of Hessian decreases for LLMs fine-tuning tasks but not for the test function and the binary classification tasks. We believe this depends crucially on the loss landscape, the initialization point, and the learning rate. We leave a detailed study to future work.

3. Constant in the expected sharpness.

Could you clarify the $2/\delta^2$ constant in the sharpness estimation equation, via a simple derivation, for instance?

This follows from similar reasons as Eq.(2):

$

\mathbb{E}_{u\sim \mathcal{N}(0, \delta^2 I)}[f(x+u)] - f(x)
=
f\_\delta(x) - f(x)
=
\frac{\delta^2}{2} \text{Tr}(\nabla^2 f(x)) + o(\delta^2).

$

Therefore, we add this $2/\delta^2$ constant to directly estimate the trace of Hessian.

4. Relatively few experiments.

There are relatively few experiments, and these do not account for the stochastic nature of the methods (caused, e.g., by random initialization). That said, I do not think empirical analysis is the point of this paper, and that the experiments are more for a cursory confirmation of the established theory.

Thanks for this comment. In Appendix D, we provide more experiments using different random seeds to measure the effect of random initialization and random search directions in zeroth-order optimization. The results are consistent in all our settings. The main focus of the paper is on the theoretical properties of zeroth-order optimization, and current experiments suffice to act as confirmation of our theory. We leave a more extensive empirical study to future work.

Thank you for your rebuttal. My primary concerns have been addressed, and I maintain my original recommendation of acceptance.

We thank the reviewer for acknowledging the contribution of our work. We address the reviewer's concern regarding practical implications in the following.

1. Practical significance.

The practical significance of the findings is not entirely clear from the results presented. As shown in Figure 2 and 3, standard gradient descent (GD) often achieves a lower training loss, a smaller Hessian trace (i.e., finds an even "flatter" solution), and higher test accuracy.

Thanks for raising this point. The aim of the experiments is not to claim that zeroth-order optimization is better than first-order optimization, but only to provide examples to support our theoretical findings that the trace of Hessian decreases. In terms of training loss and test accuracy, there is still a gap between the performance of zeroth and first-order optimization, which is known in the literature [69, 100] and is supported by classical theoretical understandings that the convergence rates of zeroth-order optimization depend on the dimension. For the trace of Hessian, we provide the first evidence that zeroth-order optimization has implicit regularization to reduce the trace of Hessian. Despite this gap in performance, there are scenarios where first-order optimization cannot be applied, and we have to use zeroth-order optimization instead. For example, LLMs fine-tuning tasks where gradients are expensive to compute [69] and black-box settings where gradients are not accessible [17]. We provide more clarification in the following reply.

2. When to use ZO.

If ZO does not offer a clear advantage in either final performance or the "flatness" of the solution compared to a well-tuned first-order method, what is the key takeaway for a practitioner? The paper convincingly shows that ZO also seeks flat minima, but it does not make a strong case for why one would prefer it over GD in this realistic, non-convex scenario.

Zeroth-order optimization is often preferred over first-order optimization when gradients are not accessible or expensive to compute. In LLMs fine-tuning tasks, first-order optimization achieves better performance but has significantly larger memory consumption. For example, [69] reported that first-order optimization requires 8 A100 GPUs to fine-tune a 30-billion-parameter model, each with 80 GiB memory, whereas a single GPU is enough for zeroth-order optimization. In the case when resources are not sufficient, e.g., only one GPU is available, zeroth-order optimization still provides a promising alternative and democratizes the use of LLMs to users with limited resources. For practitioners, the major advantage of zeroth-order optimization is still on its memory efficiency, but we provide a new theoretical understanding on its implicit regularization towards flat minima, which is previously observed only for some first-order methods such as SAM [89, 11].