Zeroth-Order Optimization Finds Flat Minima
Authors: Liang Zhang
Bingcong Li
Kiran Koshy Thekumparampil
Sewoong Oh
Michael Muehlebach
Niao He
Venue: NeurIPS 2025 poster ()
Keywords: Zeroth-order optimization
Convex optimization
Implicit regularization
Flat minima
Primary area: optimization

Abstract: Zeroth-order methods are extensively used in machine learning applications where gradients are infeasible or expensive to compute, such as black-box attacks, reinforcement learning, and language model fine-tuning. Existing optimization theory focuses on convergence to an arbitrary stationary point, but less is known on the implicit regularization that provides a fine-grained characterization on which particular solutions are finally reached. We show that zeroth-order optimization with the standard two-point estimator favors solutions with small trace of Hessian, which is widely used in previous work to distinguish between sharp and flat minima. We further provide convergence rates of zeroth-order optimization to approximate flat minima for convex and sufficiently smooth functions, where flat minima are defined as the minimizers that achieve the smallest trace of Hessian among all optimal solutions. Experiments on binary classification tasks with convex losses and language model fine-tuning support our theoretical findings.

Zeroth-Order Optimization Finds Flat Minima
Liang Zhang
Bingcong Li ETH Zurich bingcong. li@inf ethz.. ch
ETH Zurich Max Planck Institute liang. zhang@inf....mmm ethz.cl ch
Kiran Koshy Thekumparampil
Sewoong Oh University of Washington sewoongccs washington. edu
Amazon kkt@amazon com
Michael Muchlebach Max Planck Institute
Niao He
ETH Zurich niao haaone ethz.
mi micchelm@tuebbnneen.c mpp.:e..iiinnn..............
Abstract
Zeroth-order methods are extensively used in machine learning applications where gradients are infeasible expensive to compute, such black-box attacks, rein- forcement learning, and language model fine-tuning. Existing optimization theory focuses convergence to arbitrary stationary point, but less is known the implicit regularization that provides fine-grained characterization on which partic- ular solutions are finally reached. We show that zeroth-order optimization with the standard two-point estimator favors solutions with small trace of Hessian, which is widely used in previous work to distinguish between sharp and flat minima. We further provide convergence rates of zeroth-order optimization to approximate flat minima for convex and sufficiently smooth functions, where flat minima are defined as the minimizers that achieve the smallest trace of Hessian among all optimal solutions. Experiments binary classification tasks with convex losses and language model fine-tuning support our theoretical findings.
Introduction
There are many emerging machine learning problems where gradients are not accessible or expensive to compute. hindering the application of gradient-based optimization algorithms. For example, fine-tuning large language models (LLMs). particularly at the scale of billions of parameters, faces significant memory bottlenecks, primarily because the memory-intensive nature of backpropagation. Zeroth-order optimization offers compelling alternative as it permits gradient estimation via finite differences of loss values. Malladi et al. [69] reported that zeroth-order methods are capable of fine-tuning ee-billioo-paramette model using single A100 GPU with 80 GiB memory, whereas gradient-based methods require A100s. zeroth-order methods have also found numerous applications in black-box settings [17, 18, 6) and nonsmooth optimization [74, 57, 47] where gradient computation often infeasible. They have further proven effective in reinforcement learning [80, 68, 39] and distributed learning [31, 93, 77] to reduce computation and communication costs.
addition to recent advances fine-tuning LLMs,
To be more specific, for the optimization problem minge f(z) with parameters E Rd and a loss function f Rdd + R, zeroth-order optimization with the standard two-point gradient estimator [74]
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(Algorithm 1) iteratively updates x by substituting the computationally intractable gradient with
() f( + Au) f(x Au) u,
2X
where u. ~ (N0,, Ia) is a standard Gaussian random vector and À E IR is smoothing parameter. It convenient to understand zeroth-order methods through surrogate smoothed function defined as (a) := E (() [f + Xu)] [27, 74J. Since Eq. (I) unbiasedly estimates the gradient of fx(z) [74], i.e., (z u)] = V [xxx,,, standard convergence analyses directly indicate that fx fx) minimized. Further noting that (Ir) is close to ((x) when À is small, the convergence of zeroth- order optimization can be established on the original loss ((r). For example, when [(x) is smooth and convex, zeroth-order methods guarantee that the average of the iterates, Tr, after T iterations satisfy (āT) - minzeRd [(x) & Odd/T); see e.g. [74].
However, in the presence of multiple solutions, it remains unclear from the above arguments whether zeroth-order methods prefer certain minima. Our intuition to this question comes from revisiting the underexplored role of fx (z)). Using Taylor's theorem (with details in Eq. (2)), one can find that
(x) = f(x) + 22 Tr (+² + +(2))
2
This implies that zeroth-order optimization implicitly encodes an additive regularizer using the trace of Hessian, which is a widely adopted metric in the literature [89, 88, 58, 34, 24, 3] to differentiate sharp and flat minima [40, 46, 29, 75, 25, 38]. Existing works studying flat minima mostly centered around first-order methods. The work of [75, 105, 85] empirically demonstrated that stochastic gradient descent (SGD) converges to solutions with small expected sharpness FV [f + Xu)] f(x) on a variety of vision tasks, which also implies small trace of Hessian according to Eq. (2). It was also shown that SGD with label noise provably decreases trace of Hessian regularization term for overparameterized models [12, 22, 55]. Wen et al. [89] proved that sharpness-awaa minimization (SAM) [33], method specifically designed for finding flat minima, minimizes trace of Hessian when the batch size is one. Further discussions on the relevance of flat minima, as well as the role of the trace of Hessian can be found in the recent work [3].
This work formalizes the intuition above and initiates the study of the implicit regularization of zeroth-order optimization with the standard two-point estimator. Despite relying only on function evaluations of (xx) we show that zeroth-order optimization converges to flat minima, which are typically characterized using second-order information such the Hessian matrix (2)( In particular, our contributions are summarized below.
We define flat minima the minimizers that achieve the smallest trace of Hessian over the set of all minimizers; see Definition 3.1. Assuming the function convex and three times continuously differentiable with Lipschitz--contnnoon gradient, Hessian, and third derivatives (Assumptions 3.3 and 3.4), we prove that zeroth-order optimization with the standard two-point estimator (Algorithm 1) converges to (O(e/d), e) aaappoxiimtee flat minima, defined in Definition 3.2, after T = O(d'/e" /e2 iterations; see Corollary 2. While standard convergence analysis directly treats X² (x)) as a bias term and controls it by choosing a sufficiently small X, we provide a tighter and novel characterization in Section 3.1 of zeroth-order update dynamics to analyze convergence of F(x)= := f() + (X² (X2 f(x)). This result of independent and broader interest for advancing the understanding of zeroth-order optimization and naturally extends to analyzing convergence rates of first-order methods such as SAM and SGD on the smoothed loss towards flat minima (Remark 3.4).
We provide empirical evaluations to examine the behavior of the trace of Hessian under zeroth- order optimization across three settings: a test function (Figure 1), binary classification tasks using overparameterized SVMs and logistic regression (Figure 2), and language model fine-tuning tasks with RoBERTa [61] (Figure 3). Consistent with our theoretical predictions, we observe that the trace of Hessian decreases when using zeroth-ore -odder optimization across all these settings. Note that we adopt an estimation of the trace of Hessian on language models for scalability purposes.
To the best of our knowledge, this is the first work to prove that zeroth-order optimization converges to flat minima. Note that results provided in this paper can be readily extended to zeroth-order optimization with other unbiased estimators of V/x(z) (x) satisfying E E[uu = L2 such that Eq. (2) holds, including the one-point estimator suggested in [32, 74], as well as gradient estimation using random vectors uniformly distributed on the Euclidean sphere [81, 99].

---

Algorithm 1 Zeroth-Order Optimization with the Two-Point Estimator
Input:
Initialization 2y E IRd, number of iterations T, stepsize > 0, smoothing parameter À > O.
I: for = 0, 1.... T - do
2: Sample ut uniformly from the standard multivariate Gaussian distribution (N (V, Ta).
3: Construct the two-point gradient estimator
gx (Te, ud) f(x= Xua) f(x+ Aete) Us
2\
4: Update the parameter
F++1 + It 17 (21, we).
Output: 2, for 7 sampled uniformly at random from {0, . 17.
Notation. We use ||-|| for the Fuclidean norm of vectors and [m] for the set 21, ,m). The trace of square matrix / denoted by Tr(J). A standard Gaussian random vector in IR is written as ~~N -0, Ia) and satisfies E[vv Ia. A function p: R - R is convex if a p(x) + a) p(y) 2 plaar + (1 o)y)), Ve, y E Rd and o E (0. A function
Rd + R is rth-order smooth with L, > if it is r times differentiable and || (2)) - V [v)] < L yll. where [V)* := max,eRd, || VV (x))s"])] and [== := Ci.."..e (0 qxx)/Oz, )s,, .. S, We
say for brevity that q(x) is L1 -moshh if 1.
1.1 Related Works
Zeroth-Order Optimization. Existing works primarily focused on convergence to a stationary point, while we prove the first result on convergence to flat minima. The development and early advances of zeroth-order optimization can be found in [70, 21J. Nesterov and Spokoiny [74] provided convergence analysis of zeroth-order optimization across various settings. Their results for nonsmooth convex functions were refined by [81], while improvements for nonsmooth nonconvex functions were made by [57, 16, 47]. Extensions to the stochastic setting were considered in [36]. Lower bounds were also provided in [90, 28]. showing that the dimension dependence in the convergence guarantees of zeroth-order optimization is unavoidable without additional assumptions. Several recent works [96, 69, 99] proved that such dimension dependence to the trace of Hessian. Zeroth-order optimization has been extended to minimax optimization [86], bilevel optimization [1], constrained optimization [10, 64], and Riemannian optimization [52, 53]. has also been integrated with coordinate descent [56], conditional gradient descent [9]. SignSGD [60], and variance reduction techniques [59, 30, 43). A line of work [83, 66, 10, 98, 79] established convergence to second-order stationary points, demonstrating that zeroth- order methods can also escape saddle points. The noisy function evaluation setting was studied in [8. 65, 4]. where higher- order smoothness assumptions were used to reduce bias in gradient estimates. The capability of zeroth-order methods for fine-tuning LLMs was first demonstrated by Malladi al. [69]. Following this work, several recent studies have introduced various improvements aimed at enhancing runtime efficiency and performance, including momentum [102, 44], variance reduction [35], sparsification [37, 63), use of Hessian information [103], and better sampling strategies [19].
be relaxed quantity related
Sharpness-Aware Minimization. Prior studies of flat minima have mostly centered on first-order methods. Algorithms designed to find flat minima have achieved strong empirical success, including Entropy-SGD [15], stochastic weight averaging [42, 45), and sharpness-aware minimization (SAM) [33]. Similar methods to SAM were proposed in [92, 104], and their efficiency and performance were further enhanced in e.g., [49, 62, 26, 106, 5, 50]. Also inspired by the insights in Eq. (2), Zhang et al. [97] proposed a gradient-based method that effectively minimizes the smoothed loss. Several recent studies [95, 78, 94] proposed modifying zeroth-order optimization and combining it with principles from SAM to explicitly promote flat minima. In contrast, our work focuses on understanding the implicit regularization effects inherent within the standard zeroth-orde optimization. In addition to the trace Hessian used in this work, other notions of sharpness have also been studied in the literature. One such example is the largest eigenvalue of the Hessian matrix, which has been shown to be implicitly penalized by (S)GD with large learning rates [20, 7, 87, 67, 23, 2] and SAM [89, 11]. Li et al. [51] proved that SAM implicitly promotes balanced solutions scale-invariant problems. A
3

---

sharpness measure based on the largest gradient norm in a local neighborhood was proposed in [101]. Recently, Ahn al. [3] provided a formal definition of flat minima and studied the convergence complexity of finding them. A local concept of flat minima was used, defining them as local minima that are also stationary points of the trace of Hessian evaluated at limit points under gradient flow. Two gradient-hasee hased algorithms were proposed with convergence guarantees to flat local minima under the assumptions that the loss function is four times continuously differentiable, satisfies the local PL condition, and has twice Lipschitz limit map under gradient flow. In this work, we adopt global notion of flat minima and assume convexity of the function to show that zeroth-order optimization with the -wo-point estimator converges to flat global minima.
2 Warm-up: Sharpness as Implicit Regularization
Throughout this paper, zeroth-order optimization refers specifically to the method described in Algorithm 1. As the two-point estimator in Eq. (1) is an unbiased gradient estimator for the smoothed function fx(r)) = (f Xu]] [74], zeroth-order optimization directly minimizes fx(x).
Let fx) be twice continuously differentiable. By Taylor's theorem, we have that
X2 f(x + Au) = f(x) - Au T vf(x) + 2"
T V f(x)x + o(2²).
Taking expectation w.r.t. a ~ (N, Ia), we obtain that
X²
fx(x) f(x) + Eu Tr (wn [2](x)]] + o(2
2
(2)
x
f(x) + Tr (==))))++(() o(²))
2
The results suggest that the smoothed function introduces trace of Hessian as additional regular- ization term. In the literature for sharpness-awe aware minimization. the trace of Hessian is often used to measure the sharpness of the solution [89, 88, 3]. Recall that E[gx(z, u)] = (zxx and thus zeroth-order optimization implicitly minimizes sharpness:
Eu [1++1 - 24 = [V)(() nd?
2 VTT + o(
(3)
This holds for any twice continuously differentiable function without further assumptions. It can be readily deduced from Eq. (3) that when 2; close to optimal, i.e., with small gradient, the iterates move in expectation towards a direction that reduces trace of Hessian. Before formally establishing that Eq. (3) leads to flat minima, we first illustrate this intuition through a concrete example.
Example 2.1. Consider the function h(x)) = (y) 1) where x = TTT E R2d for y.2 E IRd. The optimal value is achieved when y z = 1, and the trace of Hessian is ||v|| + ||
Among all optimal solutions, the smallest trace of Hessian is achieved when y = z and ||>||
Figure plots the values of the loss function and the trace of Hessian when applying gradient descent and zeroth-order optimization on Example 1. Gradient descent and zeroth-order optimization with + 0 leave the trace of Hessian almost unchanged throughout. The smoothing parameter controls the trade-offs between regularization this additional bias term. Despite the large oscillation in loss values from zeroth-order methods due to random search directions, the trajectory of the trace of Hessian decreases noticeably smoother. Example 2.1 belongs to a class of iaale-invrriant problems studied in Li et al. [51]. It was proved that SAM promotes balanced solutions on these problems where B, (Ilev. 1| - [|=.|(2)// converges to 0 in the limit, while B, remains Bo for gradient descent [51]. Note that only flat minima are perfectly balanced with || = ||=|| among all optimal solutions of Example 2.1. We show in the following that zeroth-order optimization favors balanced solutions as well. A proof is provided in Appendix A. Proposition 2.2. When applying zeroth-order optimization (Algorithm 1) on Example 2. I, the limiting flow with - 0 satisfies that d E. /dt = -2X E Br). In other words, [B] + 0 when 1. + co.
the trace of Hessian and the optimization error induced by
The smoothing parameter À plays critical role in driving B[B,] towards zero and determines the rate. When x~ = 0, the regularization effect disappears, and zeroth-order optimization behaves like gradient descent to maintain E. B.) as a constant. These theoretical findings align with Eq. (3) and Figure 1. However, the qualitative discussion of implicit regularization in this section does not offer insights on the complexity reach flat minima, which will be the subject of the next section.

---

Trace of Hessian Loss
10-9.
Loss
10:3
10-20
10-13
Trace of Hessian
150
150
GD
70 0.01)
100
100
20 (2 = 0.05)
Zo
20 (2 0.13
10"
10'
10
10
10*
10
10a
10'
10 10
10
10
Number of Iterations
Number of Iterations
(a) Comparison of GD and ZO.
(b) Effect of X.
Figure 1: Loss and trace of Hessian Example 2.1 with d 100. (a) Comparisons among gradient descent (GD), zeroth-order (ZO) optimization (Algorithm 1) with = 0.1, and ZO with À - (directional derivatives). (b) Comparisons different À used in ZO. GD and ZO with - 0 fail to decrease the trace of Hessian. Larger À in 70 leads to larger errors the loss but brings more regularization effect minimizing the trace of Hessian.
3 Complexity for Finding Flat Minima
To formally study the convergence complexity of zeroth-order optimization with the two-point estimator towards flat minima, we first defin the notion of flat minima that we are interested in.
Definition 3.1 (Flat Minima), Suppose that f() is twice differentiable with a well-defined Hessian matrix. Let X arg min (ax denote the of minimizers of f()) We say xx is flat minimum of (x) x E arg xin Tr(V2 f(x)). That is, x² minimizer f(x) that achieves the smallest trace of Hessian among the of minimizers.
The above definition of flat minima implicitly encodes a constrained optimization problem
min aERd
Trx)) s.t. f(x) min f(x) - =ERd
This functional constraint is equivalent to requiring x E X", since it always holds that f(x) 2 minzer fz) In the literature on functional constrained optimization problems min (2) with the constrained set := (x E Rd ti (x) < 0}. a common objective to find e-approximate solutions satisfying ( mingec (o(x) < and t ( < e [71, 13, 100J. Motivated from this connection constrained optimization, we define approximate flat minima in the following.
Definition 3.2 (Approximate Flat Minima), Suppose that f(x) is twice differentiable with well- defined Hessian matrix. Let X := arg min fx) denote the set of minimizers of f(æ). For é1, f1 O, we say is an (E1, 62) apprrxxmmte flat minimum of f f(x) if
f(+) min f(x) 61, Tr(V² f(+) min Tr(V f(x)) S =EX*
ZER
Ahn al. [3] defined flat minima as local minima that are also stationary points of the trace Hessian evaluated at limit points under gradient flow. Since the trace of Hessian is highly nonconvex, such local definition does not necessarily correspond to minima with the lowest trace of Hessian. this work, we adopt global notion of flat minima and prove that zeroth-order optimization converges to them. The following assumptions are required to guarantee convergence to approximate flat minima.
Assumption 3.3 (Smoothness). We assume the function fxx is three times continuously differen- tiable and satisfies that (a) f(x is L1 -smooth; (b) f(x) second-order smooth with L2 > O, which implies that all third-order partial derivatives are bounded: |03 fz) /ar,,rr,,za. & L2, Vi, j. k E [d]
and Va Rd; and, (c) f(z) is third-order smooth with L3 O, which implies that Vz. y E Rd
((0) - f(x) (x (y 2) (-- TV==))>>(<>>00 x)
(' - =03/ - Ly
|xr v11
where v'f(z)ly - z/3 Eig.eela (0))l))0z,,z, 22)(1, 2,) Iz).
5

---

Since the characterization of flat minima already involves second-orde information of fz), it is natural to require assumptions on higher-order information establish convergence guarantees. Higher-order smoothness assumptions have been widely used to establish fast convergence rates [8, 721, guarantee convergence to second-order stationary points [30, 79], analyze implicit regularization [7, 89], and study the complexity of finding flat minima [3]. We emphasize that these assumptions on higher-order information are used solely for convergence analysis; Algorithm requires only zeroth-order information. In order to prove global convergence,
also need the following convexity assumption, Although f((:) is convex, Tr Tr(V fx))) in general nonconvex. Seeking flat minima with lowest Tr(V2 fxx) in the set of minimizers X is therefore a challenging task.
Assumption 3.4 (Convexity). The function f(x is convex on R and thus Tr(V? f(x)) 0.
3.1 Convergence Analysis
We start with a brief recap of standard convergence analysis for zeroth-order optimization. We then explain the major theoretical contribution in this paper that leads to convergence towards flat minima. By the zeroth-order updates in Algorithm 1, we have that Vo Rd
Ellat+11 - 21|2 c - x - 2np Rlga (Ie, u. ] (xt - x) + B1 ut)l
(4)
E c - =1 (x - (x(1) + Bllaa u)ll
Here, we use Elgx (z,, 4)] = V (xz) and the property that fx(x) is convex when f(x) is convex [74]. Standard analysis considers optimizing f(r) When f(x) is smooth, the second term fx(x)) fx(x) = (xx) - f(x) + O(²)), and the third term can be bounded as
E ( u.) u1)1 s 2(d + ()) ((2)).
Since f(x) is L-smoothh we also have that [[V < 2L, min [(x).. By selecting x as one minimizer from the set X' and setting 1) = O(1/d), we can rearrange Eq. (4) to obtain
E f(x))
min f(x) S (El x=|² El E| =²1²) + 0(2)).
=ER2
Summing up from / = t 1 - 1 and averaging by T give B[f(TT) min f(x)) - O(d/T)
with small enough where Fr is the average of iterates [74].
Going beyond the classical analysis and targeting at flat minima, we take inspiration from Eq. (2)
and instead focus on the regularized loss
2 1
F(x): :
Tr TT(()
(5)
In this way, do not treat Tr Tr(V2f(>))
bias be controlled but instead view the term as objective to be optimized. Indeed, the ()²) error term in the standard analysis mostly comes from bounding T fx))) from above by >² when f(x) is smoohh. To proceed, we need to control the difference between F(x) and fx(x), as well as to bound (l]gx(<,, ut)l by the term [x=)( to establish convergence on F(x).
Lemma 3.5. Let Assumption 3.3 be satisfied. For F(z) defined in Eq. (5), it holds that
La xd
[fa(z) F(x)
Va Rd
24
The second moments of the two-point estimator gx(x,, u) defined in Eq. (1) can be bounded
L2 x x² + 6)*
L3
El u))1 2(d (VF()))
x add+100)
3
288
Note that the result above is non-trivial extension of classical analysis. Particularly for EE|gx w)ll? Isserlis' theorem [41, 91] required to compute an 8th-order moment -1 wi,] where each i, [d] and ui is a standard Gaussian (see Lemma B.)), while standard theory only needs to compute 4th-order moment. By a combinatorial computation, there are in total 105 terms to be considered for 8th-order moments, but only three terms for 4th-order moments. We also need smoothness of F(x) for relating [FF()) to F(x) min F(x).

---

Lemma 3.6. Let Assumption 3.3 be satisfied. Then F(x) is (2Lo)smmothh if S /2L1/
Proofs of Lemmas 3.5 and 3.6 can be found in Appendix B.2. Following the one-step analysis in Eq. (4) and using the above lemmas, the theorem below establishes convergence guarantees of Algorithm to minima of F(x:). A proof is provided in Appendix B.3.
Theorem 1. Under Assumptions 3.3 and 3.4, Algoritimm I with stepsize 1/(8(d+ 6) and
smoothing parameter X² S / ((8//Ls)) satisfies that
F(x+) min F(O) S 8(d (od+6)44 6, 100 x711? DER
E
T
La + +
L +d++6*
L3
2 + 10)*,
24L1
115211
where Do R is the initialization, Fe arg yes F(x), and the expectation is taken w.E.f. the randomness in all search directions and the selection of xr.
Following the standard gradient-based method to minimize F(x) via VF(x), third-order derivatives of f()) are required due to the computation of VTr(V=((z)). Here, we prove that Algorithm 1 that uses only zeroth-order information of f(x) converges to minimizers of F(z). Although F F(x) is nonconvex, the difference between F(z) and a convex function, fx(x). can be made small, and thus convergence to global minima is still guaranteed. The corollary below transfers convergence guarantee towards minima of F(z) to convergence guarantees towards flat minima of f fx) The proof of it can be found in Appendix B.3.
Corollary 2 (Iteration Complexity for Finding Flat Minima). Let Assumptions 3.3 and 3.4 4 be satisfied. For > 0, Algorithm 1 with stepsize 1j 1/(8(d + 6) satisfies that
E
f(x+)
min f(x) *ERU
- 2L3 6)2
3T.e
(1+
1n(d+6)
6
E
Tr(V
min Tr Tr(V"S())) =EX*
Se.
when setting the smoothing parameter and the number of iterations T such that
x2 min { V2T 12/T.16
3L16
L3/2 Lz(d + 10)2² (d 4) (3 6)3 J'
T 64(d + L1 -00 1
2 La(d 10)² 4La(d 4)²
L3(d+ 6)3
max
V2L
12vT.T
3c
31,6
Recall X = arg min f(x). According to Defimition 3.2, this means that (O(e/d), approxi- mate flat minima can be guaranteed with T = Odd"/(dd""") and X = /d/12)
Remark 3.1. Our convergence guarantees require that f(x) is three times continuously differentiable and satisfies first-, second-, and third-order smoothness assumptions. Appendix C. explain how the first- and third-order smoothness assumptions can be relaxed, at the cost of slower convergence rates; see Table for a summary.
Remark 3.2. We discuss here how the parameters and are selected and compare with the standard analysis [74]. Let [x)(x,) mingged F(x)] < Emr(A, T),, where Err( X, T) Odd/T) + (d)
is given by Theorem 1. In the proof of Corollary 2, we show that (if(x, - min f(=)] <
Em,(A, T) + (()dd) and E[Tr( ( f
mingex- Tr 2 f(x)) < 2 Em(A, /22 The guar-
antees on E(f(=,) min f(x)] S Od/TT) + (()d) share the same dependence on the leading error terms the standard analysis [74], but we additionally ensure ( fx.,
minzex (()2((x) < (
(X We choose X2 = O and T
such that E 2 [(x+) x- Tr Tr(V2(()) S c, which results in Bf (-i==--mnneeee (()) S
((> d)) (Ee/e Standard analysis [74] set T' = Odde)) and X² = (Eedd) such that only
E[f(x+) ed f(x) < holds.

---

70
GD
700
a5a
w5a
a5a
w5a
Train Loss
Train Loss
4.0
2.0
2.0
0
0.0
x10
x10
x10
x10
Train Hess
Train Hess
1.0
1.0
Test Ace
0.8
Test Acc
0.8
0.8
0.8
0.6
0.6
0.6
0.6
10
10a
10
10²
101
10
10
10²
Number of Iterations
Number of Iterations
(a) SVMs.
(b) Logistic Regression.
Figure 2: Training loss trace of Hessian the training data (Train Hess in the plot), and test accuracy on (a) SVMs and (b) Logistic regression. Zeroth-order (ZO) optimization slower than gradient descent (GD) for minimizing the loss and maximizing the accuracy, but there is clear trend of decreasing trace of Hessian for ZO.
Remark 3.3. We focus on the convex setting in this work, but the analysis extends to cases where the objective locally convex neighborhood. When initialized in this region, zeroth-order optimization identifies local minima with the smallest trace of Hessian among all local minimizers in the neighborhood. When f() is generally nonconvex, the current definition of flat minima is not theoretically tractable without additional assumptions. We leave for future work a detailed study on the definition of computationally feasible flat minima and the assumptions required to understand the complexity of finding them in the nonconvex setting [2].
Remark 3.4. Our proof framework can be extended to understand the complexity of first-order methods towards flat minima. For example, gradient-based method, xz+11 <- I, 1 V Aua) with यę ~ (0, Ia), that uses gradient evaluated at the perturbed point as the descent direction also minimizes the smoothed loss (xx)) in the expectation. By upper bounding E CIVí(2= + Au)ll with the term F=)))]?? convergence guarantees on F(x) and thus to flat minima can be established. The same framework provides new insights how SAM can be analyzed as well. Our primary focus is on zeroth-orue order methods, and extensions to first-order methods are deferred to future.
4 Experiments
We provide empirical results binary classification tasks with convex losses and language model fine-tuning tasks. Our code is available at https://gittiii com/Liang137/ httta//mcmmmmmmmm33////////e /Ft.13/////aaaae.o.o.o
Binary Classification with SVMs and Logistic Regression. We start empirical evaluations using support vector machines (SVMs) and logistic regression. Given a training dataset {a,, b with feature vectors a; E Rd and binary labels b, we consider an overparameterized regime where each E Rd is mapped to Φ(a;) ) Wa, E R. via random matrix W E RR Dxd with W ~ (0, 1) and > We use two standard binary classification benchmarks from the LIBSVM library [14]: a5a (N = 6, 614, d 123) and w5a (N 9, 888, d 300) [76]. and set D = 10, 000 to overparameterize. This ensures higher-dimensional solution set with increased diversity, enabling a meaningful study of implicit regularization to investigate the solutions selected by the algorithm. We

---

GD
Z0
GD
Z0
K
32
K = 236
SST-5
TREC
Train Loss
Train Loss
10c
10
10m2
10m3
10-3
10
Train Hess
10r
Train Hess
10*
101
10'
Test Ace
0.50-
Test Ace
0.5
0.9
0.85
0.85
0.4
10'
10
10
107
10
102
16'
30'
102
Number of Iterations
Number of Iterations
(a) SST-2.
(b) SST-5 and TREC.
Figure 3: Training loss, trace of Hessian on the training data (Train Hess in the plot). and test accuracy on (a) SST-2 with K = 32 and 256, and (b) SST-5 and TREC with K = 32. Both gradient descent (GD) and zeroth-order (ZO) optimization reduce the trace of Hessian during training. In most cases, GD achieves lower training loss, smaller trace of Hessian, and higher test accuracy.
consider SVMs with the squared hinge loss and b, E (-11, that is,
N
min ZERD
f(x) = min ZERO N
Σ
(max(0, - b;o((a;) xx)))
For ((2) = 1/(1 exp(-2)) and b {0, 13. logistic regression minimizes the loss
min f(x) = min ZERO
(-b, logo x) (1 - log(1 (o(aa) Tx)).
ZERO N
These two models be viewed as linear probing [48] two-layer neural network with frozen first layer and an identity activation. the SVMs case, the second layer uses an identity activation and is trained with the squared hinge loss, while logistic regression applies sigmoid activation and minimizes the cross-entropy loss. Both SVMs and logistic regression have convex objective functions, and the trace of Hessian can be efficiently computed. Figure 2 shows the optimization trajectories of gradient descent and zeroth-order optimization. In all cases, gradient descent and zeroth-order -oddrr optimization achieve comparable training loss and test accuracy; however, zeroth-order optimization consistently reduces the trace of Hessian and converges to flatter solutions. Detailed experimental setups and additional results can be found in Appendix D.2.
Fine- Fine-Tuning Language Models on Text Classification Tasks. We also evaluate the behaviors of zeroth-order optimization on nonconvex language model fine-tuning tasks. Following Malladi et al. [69], we consider few-shot fine-tuning on RoBERTa-Large (355M parameters) [61] with = 32 and K 256 examples per class three sentence classification datasets: SST-2 and SST-5 [82] for sentiment classification, and TREC [84] for topic classification. All experiments are tested on single NVIDIA H100 GPU with 80 GBB memory. To mitigate the effect of mini-batch noise reducing the trace of Hessian, we use full-batch training for both gradient descent and zeroth-order optimization, which is feasible in the few-shot setting. As the exact computation of the trace of Hessian is intractable due to the large model size, we adopt the widely-used expected sharpness By- [f 5u)] [x) as approximation [75, 105, 85), where f(): denotes the
(2 training loss evaluated model weights x E Rdd We set J = 10-4 and estimate the expectation by averaging over 100 samples. The performance of gradient descent and zeroth-order optimization is presented in Figure In this setting, both methods are observed to decrease the trace of Hessian. is conjectured that the behavior in gradient descent results from the implicit regularization associated

---

with large learning rates [20, 7]. Meanwhile, the observed decrease in zeroth -roder optimization matches our theoretical insights. Detailed setups and additional results are deferred to Appendix D.3.
In classical optimization theory [74, 28), the convergence rates of zeroth-order methods scale with the dimension d, limiting their applicability to problems with large d such language model fine-tuning. Previous work [69, 99] explaining why zeroth-order methods still achieve reasonable performance on language model fine-tuning tasks has relaxed the dependence on d to a term related to the trace of Hessian, Tr(V (x)). Assuming fx)) < dLp when f(x) is Ls-moooth, zeroth-order optimization achieves dimension-indepee
rates and remains effective even in high-diment -inensninnii
settings. Our experimental results show that the trace of Hessian decreases and attains values much smaller than the actual dimension, thereby supporting the assumption made in prior work to explain
the empirical success of zeroth-order optimization.
Conclusion
Motivated by the observation that zeroth-ordes optimization with the two-point estimator (Algo- rithm 1) inherently minimizes (x)), we initiate a formal study of this implicit regularization. Specifically, we analyze its convergence to flat minima, defined as the ones with the lowest trace of Hessian among all minimizers. For convex and sufficiently smooth (Assumptions 3.3) functions, we prove that Algorithm guarantees (O(e/d), (O(e/").ee-apppel -ppaprooxee flat minima (Definition 3.2) after T = (dt /² iterations. This is the first work showing that zeroth-order optimization converges to flat minima. Experiments on binary classification tasks using SVMs and logistic regression, as well language model fine-tuning tasks on RoBERTa support our theoretical findings.
Theoretical and empirical performance of zeroth-order methods often limited by the high variance in gradient estimation. A promising direction is to combine zeroth-order and first-order methods to leverage the strengths of both [69, 102, 54J. We only examine zeroth-order optimization using the standard two-point estimator. Exploring whether the convergence complexity can be further improved with possible modifications and additional algorithmic designs remains an interesting line of work. The current theoretical results require convexity and higher-order smoothness assumptions of the function. Investigation into nonconvex functions with relaxed assumptions is left for future work.
Acknowledgments and Disclosure of Funding
We thank all anonymous reviewers for their valuable suggestions. L.Z. gratefully acknowledges funding by the Max Planck ETH Center for Learning Systems. B.L. is supported by Swiss National This work does not relate to the current
Science Foundation Project Funding No. position of K.T. at Amazon. S.O. is supported in part by the National Science Foundation under grant no. 2112471, 2229876, and 2505865 supported in part by funds provided by the National Science Foundation, by the Department of Homeland Security, and by IBM. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or its federal agency and industry partners. M.M. is supported by the German Research Foundation. N.H. is supported by ETH research grant funded through ETH Zurich Foundations and Swiss National Science Foundation Project Funding No. 200021-207343.
References
[1] Alireza Aghasi and Saeed Ghadimi. Fully zeroth-order bilevel programming via Gaussian smoothing. Journal of Optimization Theory and Applications, 205(2))31, 2025.
[2] Kwangjun Ahn, Sébastien Bubeck, Sinho Chewi, Yin Tat Lee, Felipe Suarez, and Yi Zhang Learning threshold neurons via edge of stability, Advances Neural Information Processing Systems, 36: 0199500-95699 2023.
[3] Kwangjun Ahn, Ali Jadbabaie, and Suvrit Sra. How to escape sharp minima with random perturbations. In International Conference on Machine Learning, pages 597-618. PMLR, 2024.
10

---

[4] Arya Akhavan, Evgenii Chzhen, Massimiliano Pontil, and Alexandre B Tsybakov. Gradient- free optimization of highly smooth functions: Improved analysis and a new algorithm. Journal of Machine Learning Research, 25(370):1-50, 2024.
[5] Maksym Andriushchenko and Nicolas Flammarion. Towards understanding sharpness-awas aware minimization. In International Conference Machine Learning, pages 639-668. PMLR, 2022.
[6] Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square Attack: query-efficient black-box adversarial attack via random search. In European Conference on Computer Vision, pages 484-501. Springer, 2020.
[7] Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on the edge of stability in deep learning. In International Conference on Machine Learning, pages 9024. PMLR, 2022.
[8] Francis Bach and Vianney Perchet. Highly-smooth zero-th order online optimization. In Conference on Learning Theory, pages 257-283. PMLR, 2016.
[9] Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates. Advances in Neural Information Processing Systems, 31, 2018.
[10] Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order nonconvex stochastic optimization: Handling constraints, high dimensionality, and saddle points. Foundations of Computational Mathematics, 22(1):35-77 76, 2022.
[11] Peter L. Bartlett, Philip M Long, and Olivier Bousquet. The dynamics of sharpness-awan minimization: Bouncing across ravines and drifting towards wide minima. Journal of Machine Learning Research, 24(316):1-36, 2023.
[12] Guy Blane, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an -hheebbe like process. In Conference on Learning Theory, pages 483-513. PMLR, 2020.
[13] Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic first-order methods for convex and nonconvex functional constrained optimization. Mathematical Programming, 197(1):215-277 2023.
[14] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):1-27, 2011.
[15] Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy SGD: Biasing gradient descent into wide valleys. International Conference on Learning Representations, 2017.
[16] Lesi Chen, Jing Xu, and Luo Luo. Faster gradient-fred free algorithms for nonsmooth nonconvex stochastic optimization. In International Conference on Machine Learning, pages 5219 5233. PMLR, 2023.
[17] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the ACM Workshop on Artificial Intelligence and Security pages 15-26. 2017.
[18] Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. 70-AdaMM: Zeroth-order adaptive momentum method for black-box optimization. Advances Neural Information Processing Systems, 32, 2019.
[19] Yiming Chen, Yuan Zhang, Liyuan Cao, Kun Yuan, and Zaiwen Wen. Enhancing zeroth-order fine-tuning for language models with low-rank structures. International Conference on Learning Representations, 2025.
11

---

[20] Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations, 2021.
[21] Andrew R Conn, Katya Scheinberg, and Luis N Vicente. Introduction to Derivative-Frree Optimization. SIAM, 2009.
[22] Alex Damian, Tengyu Ma, and Jason D Lee. Label noise SGD provably prefers flat global minimizers. Advances in Neural Information Processing Systems, 34:27449-27461, 2021.
[23] Alex Damian, Eshaan Nichani, and Jason D. Lee. Self-stabilization: The implicit bias of gradi- ent descent at the edge of stability. In International Conference on Learning Representations, 2023.
[24] Lijun Ding, Dmitriy Drusvyatskiy, Maryam Fazel, and Zaid Harchaoui. Flat minima generalize for low-rank matrix recovery. Information and Inference: A Journal of the IMA, 13(2)iaaae09, 2024.
[25] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference Machine Learning, pages 1019-1028. PMLR, 2017.
[26] Jiawei Du, Daquan Zhou, Jiashi Feng, Vincent Tan, and Joey Tianyi Zhou. Sharpness-aware training for free. Advances in Neural Information Processing Systems, 35:23439-23451, 2022.
[27] John C Duchi, Peter L Bartlett, and Martin Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
[28] John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5))2788-286 2806, 2015.
[29] Gintare K Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Uncertainty in Artificial Intelligence, 2017.
[30] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non- convex optimization via stochastic path- sut--integrated differential estimator. Advances Neural Information Processing Systems, 31, 2018
[31] Wenzhi Fang. Ziyi Yu, Yuning Jiang, Yuanming Shi. Colin N Jones, and Yong Zhou. communication-effiicee stochastic zeroth-ordes optimization for federated learning. IEEE Transactions on Signal Processing, 70:5058-555 -5758, 2022.
[32] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: Gradient descent without a gradient. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 385-394, 2005.
[33] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations, 2021.
[34] Khashayar Gatmiry, Zhiyuan Li. Tengyu Ma. Sashank Reddi, Stefanie Jegelka, and Ching- Yao Chuang. What is the inductive bias of flatness regularization? A study of deep matrix factorization models. Advances in Neural Information Processing Systems, 36:28040-28052. 2023.
[35] Tanmay Gautam, Youngsuk Park, Hao Zhou, Parameswaran Raman, and Wooseok Ha. Variance-reduced veroth-order methods for fine-tuning language models. In International Conference on Machine Learning, pages 15200. PMLR, 2024.
[36] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, 23(4):23412266) 2013.
12

---

[37] Wentao Guo, Jikai Long, Yimeng Zeng, Zirui Liu, Xinyu Yang, Yide Ran, Jacob R Gardner, Osbert Bastani, Christopher De Sa, Xiaodong Yu, Beidi Chen, and Zhaozhuo Xu. Zeroth-order fine-tuning of LLMS with extreme sparsity. arXiv preprint wrXiv:2406.0291.1 2024.
[38] Haowei He, Gao Huang, and Yang Yuan. Asymmetric valleys: Beyond sharp and flat local minima. Advances in Neural Information Processing Systems, 32, 2019.
[39] Zhiyu He, Saverio Bolognani, Michael Muchlebach, and Florian Dörfeer. Gray-box nonlinear feedback optimization. arXiv preprint arXiv:2404.00435: 2024.
[40] Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9()::144, 1997.
[41] Leon Isserlis. On a formula for the product-moment coefficient of any order of normal frequency distribution in any number of variables. Biometrika, ((1-2):134-1399 1918.
[42] Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson. Averaging weights leads to wider optima and better generalization. In Uncertainty in Artificial Intelligence, pages 375,885,77 2018.
[43] Kaiyi Ji, Zhe Wang, Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In International Conference on Machine Learning, pages 3100-3109 109. PMLR, 2019.
[44] Shuoran Jiang, Qingeai Chen, Youcheng Pan, Yang Xiang, Yukang Lin, Xiangping Wu, Chuanyi Liu, and Xiaobao Song. ZO-AdaMU optimizer: Adapting perturbation by the mo- mentum and uncertainty in zeroth-order optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 18363-18371, 2024.
[45] Jean Kaddour, Linqing Liu, Ricardo Silva, and Matt Kusner. When do flat minima optimizers work? Advances in Neural Information Processing Systems, 35:16577-16555, 2022.
[46] Nitish Shirish Keskar, Dheevatsa Mudigere, Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
[47] Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension dependence for zero-order nonsmooth nonconvex stochastic optimization. Journal of Machine Learning Research, 25(122):1 2024.
[48] Ananya Kumar, Aditi Raghunathan, Robbie Matthew Jones, Tengyu Ma, and Perey Liang, Fine- tuning can distort pretrained features and underperform out-of -isttrribution. In International Conference on Learning Representations, 2022.
[49] Jungmin Kwon, Jeongseop Kim, Hyunseo Park, and In Kwon Choi. ASAM: Adaptive sharpness-aware minimization for scale-invariant learning of deep neural networks. In Interna- tional Conference on Machine Learning, pages 5905-5914. PMLR, 2021.
[50] Bingcong Li and Georgios Giannakis. Enhancing sharpness-awart optimization through variance suppression. Advances in Neural Information Processing Systems, 36:70861-70879, 2023.
[51] Bingcong Li, Liang Zhang, and Niao He. Implicit regularization of sharpness -wrppe aware minimiza- tion for scale-invarians problems. Advances in Neural Information Processing Systems, 37: 44444 44478, 2024.
[52] Jiaxiang Li, Krishnakumar Balasubramanian, and Shiqian Ma. Stochastic zeroth-order Rie- mannian derivative estimation and optimization. Mathematics of Operations Research, 48(2): 118--1211, 2023.
[53] Jiaxiang Li, Krishnakumar Balasubramanian, and Shiqian Ma. Zeroth-order Riemannian averaging stochastic approximation algorithms. SIAM Journal on Optimization, 34(4):3314- 3341, 2024.
13

---

[54] Zeman Li, Xinwei Zhang, Peilin Zhong, Yuan Deng, Meisam Razaviyayn, and Vahab Mirrokni. Addax: Utilizing zeroth-order gradients improve memory efficiency and performance of SGD for fine-tuning language models. In International Conference on Learning Representa- tions, 2025.
[55] Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after SGD reaches zero loss? mathematical framework. In International Conference on Learning Representations, 2022.
[56] Xiangru Lian, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, and Ji Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order. Advances in Neural Information Processing Systems, 29, 2016.
[57] Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient- free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160-26175, 2022.
[58] Hong Liu, Sang Michael Xie, Zhiyuan Li, and Tengyu Ma. Same pre-training loss, better downstream: Implicit bias matters for language models. In International Conference on Machine Learning, pages 22188-22214 14. PMLR, 2023.
[59] Sijia Liu, Bhavya Kailkhura, Pin- Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018
[60] Sijia Liu, Pin- Yu Chen, Xiangyi Chen, and Mingyi Hong. SignSGD via zeroth-order oracle. In International Conference on Learning Representations, 2019.
[61] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pretraining approach. arXiv preprint arXiv: 1692, 2019.
[62] Yong Liu, Siqi Mai, Xiangning Chen, Cho-Jui Hsieh, and Yang You. Towards efficient and scalable tharpness-aware minimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12360-12370, 2022.
[63] Yong Liu, Zirui Zhu, Chaoyu Gong, Minhao Cheng, Cho-Jui Hsich, and Yang You. Sparse MeZO: Less parameters for better performance in zeroth-order LLM fine-tuning. arXiv preprint arXiv:2402.1575// 2024.
[64] Zhuanghua Liu, Cheng Chen, Luo Luo, and Bryan Kian Hsiang Low. Zeroth-order methods for constrained nonconvex nonsmooth stochastic optimization. In International Conference Machine Learning, pages 20842. PMLR, 2024.
[65] Aleksandr Lobanov, Alexander Gasnikov, and Fedor Stonyakin. Highly smooth zeroth- order methods for solving optimization problems under the PL condition. Computational Mathematics and Mathematical Physics, 64(():739-770, 2024.
[66] Aurelien Lucchi, Antonio Orvieto, and Adamos Solomou. On the second-order convergence properties of random search methods. Advances in Neural Information Processing Systems, 34:25633-25645, 2021.
[67] Kaifeng Lyu, Zhiyuan Li, and Sanjeev Arora. Understanding the generalization benefit of normalization layers: Sharpness reduction. Advances in Neural Information Processing Systems, 35:34689 34480889-34788, 2022.
[68] Hao Ma, Melanie Zeilinger, and Michael Muehlebach. Stochastic online optimization for cyber-physical and robotic systems. arXiv preprint arXiv:2404.053118, 2024.
[69] Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D) Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038-53075, 2023.
[70] J Matyas. Random optimization. Automation and Remote Control, 26(2):246-255 1965.
14

---

[71] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer Science & Business Media, 2013.
[72] Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathe- matical Programming, 186:157-1888 2021.
[73] Yurii Nesterov and Arkadii Nemirovskii. Interior-Poing Polynomial Algorithms in Convex Programming. SIAM, 1994.
[74] Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex func- tions. Foundations of Computational Mathematics, 17:527-566, 2017.
[75] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. Advances in Neural Information Processing Systems, 30, 2017.
[76] John C Platt. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods: Support Vector Learning, pages 185-208. MIT Press, 1998.
[77] Zhen Qin, Daoyuan Chen, Bingchen Qian, Bolin Ding, Yaliang Li, and Shuiguang Deng. Federated full-pan full-parameter tuning of billion-sized language models with communication cost under 18 kilobytes. In International Conference on Machine Learning, pages 41473-41497. PMLR, 2024.
[78] Yehonathan Refael, Iftach Arbel, Ofir Lindenbaum, and Tom Tirer. LORENZA: Enhancing generalization in low-rank gradient LLM training via efficient zeroth-order adaptive SAM. arXiv preprint arXiv:2502.1957 19571, 2025.
[79] Zhaolin Ren, Yujie Tang, and Na Li. Escaping saddle points in zeroth-order optimization: the power of two woo-point estimators. In International Conference on Machine Learning, pages 28914-28975. PMLR, 2023.
[80] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and lly Sutskever. Evolution strategies as scalable alternative to reinforcement learning. arXiv preprint arXiv: 170::03034444 2017.
[81] Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research, 18(1):1703-1713. 2017.
[82] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng. and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 1631-1642 2013.
[83] Emmanouil-Vasile Vlatakis- Siaakks-Gkaragkounii, Lampros Flokas, and Georgios Piliouras. Effi- ciently avoiding saddle points with zero order methods: No gradients required. Advances in Neural Information Processing Systems, 32, 2019.
[84] Ellen M Voorhees and Dawn M Tice. Building a question answering test collection. In Proceedings the Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 200-207, 2000.
[85] Xingyu Wang, Sewoong Oh, and Chang-Han Han Rhee. Eliminating sharp minima from SGD with truncated heavy-tailed noise. In International Conference on Learning Representations, 2022.
[86] Zhongruo Wang, Krishnakumar Balasubramaniann Shiqian Ma, and Meisam Razaviyayn. Zeroth-order algorithms for nonconnee--ttrongyy-comm
minimax problems with improved complexities. Journal of Global Optimization, pages 1-32, 2022.
[87] Zixuan Wang. Zhouzi Li, and Jian Li. Analyzing sharpness along gd trajectory: Progressive sharpening and edge of stability. Advances in Neural Information Processing Systems, 35: 9983-9994, 2022.
[88] Kaiyue Wen, Zhiyuan Li, and Tengyu Ma. Sharpness minimization algorithms do not only min- imize sharpness to achieve better generalization. Advances Neural Information Processing Systems, 36:1024-1035, 2023.
15

---

[89] Kaiyue Wen, Tengyu Ma, and Zhiyuan Li. How sharpness aware minimization minimizes sharpness? International Conference on Learning Representations, 2023.
[90] Andre Wibisono, Martin Wainwright, Michael Jordan, and John C Duchi. Finite sample con- vergence rates of zero-order stochastic optimization methods. Advances in Neural Information Processing Systems, 25, 2012.
[91] Gian Carlo Wick. The evaluation of the collision matrix. Physical Review, 80(2)266--772, 1950.
[92] Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust generalization. Advances in Neural Information Processing Systems, 33:2958-2969 2020.
[93] Mengwei Xu, Dongqi Cai, Yaozong Wu, Xiang Li, and Shangguang Wang. FwdLLM: Efficient federated finetuning of large language models with perturbed inferences. In USENIX Anmual Technical Conference, pages 379-596, 2024.
[94] Yifan Yang, Zhen Zhang, Rupak Vignesh Swaminathan, Jing Liu, Nathan Susanj, and Zheng Zhang. SharpZO: Hybrid sharpness-aware vision language model prompt tuning via forward- only passes, arXiv preprint arXiv:2506.20900 2025.
[95] Feiyang Ye, Yueming Lyu, Xuehao Wang. Masashi Sugiyama, Yu Zhang, and Ivor Tsang. Sharpness-awee aware black-box optimization. In International Conference on Learning Represen- tations, 2025.
[96] Pengyun Yue, Long Yang, Cong Fang, and Zhouchen Lin. Zeroth-order optimization with weak dimension dependency. In Conference on Learning Theory, pages 4429-4472. PMLR, 2023.
[97] Hongyang R Zhang, Dongyue Li, and Haotian Ju. Noise stability optimization for finding flat minima: A Hessian- regularization approach. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
[98] Hualin Zhang, Huan Xiong, and Bin Gu. Zeroth-order negative curvature finding: Escaping saddle points without gradients. Advances in Neural Information Processing Systems, 35: 38332-38344, 2022.
[99] Liang Zhang, Bingcong Li, Kiran Koshy Thekumparampil, Sewoong Oh, and Niao He. DPZero: Private fine-tuning of language models without backpropagation. In International Conference on Machine Learning, pages 59210-59246. PMLR, 2024.
[100] Liang Zhang, Niao He, and Michael Muchlebach. Primal methods for variational inequality problems with functional constraints. Mathematical Programming, 2025.
[101] Xingxuan Zhang, Renzhe Xu, Han Yu, Hao Zou, and Peng Cui. Gradient norm aware minimization seeks first-order flatness and improves generalization. In Proceedings of the IEEE/CVE Conference on Computer Vision and Puttern Recognition, pages 20247-20257, 2023.
[102] Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin- Yu Chen, Jason D Lee, Wotao Yin, Mingyi Hong. Zhangyang Wang, Sijia Liu, and Tianlong Chen. Revisiting zeroth- order optimization for memory-efficient LLM fine-tuning: A benchmark. In International Conference on Machine Learning, pages 59173-5915 PMLR, 2024.
[103] Yanjun Zhao, Sizhe Dang, Haishan Ye, Guang Dai, Yi Qian, and Ivor Tsang. Second-order fine- tuning without pain for LLMs: A Hessian informed zeroth-order optimizer. In International Conference on Learning Representations, 2025.
[104] Yaowei Zheng, Richong Zhang, and Yongyi Mao. Regularizing neural networks via adversarial model perturbation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8156-811 8165, 2021.
[105] Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In International Conference on Machine Learning, pages 7654-7663. PMLR, 2019.
16

---

[106] Juntang Zhuang, Boqing Gong, Liangzhe Yuan. Yin Cui, Hartwig Adam, Nicha C Dvorekk Sekhar Tatikonda, James S Duncan, and Ting Liu. Surrogate gap minimization improves sharpness-aware training. In International Conference on Learning Representations, 2022.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our theoretical claims are justified in Corollary 2, with proofs in Appendix B.3. Our empirical results are provided Section 4, with details in Appendix D.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the paper are discussed in Section 5,
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
18

---

Justification: We use Assumptions 3.3 and 3.4. Proofs of the theoretical results are provided in Appendix B.2 and B.3.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The detailed experimental setups and configuration of hyperparameters are discussed in Appendix D. The supplementary material provides all codes to reproduce the experiment results.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
19

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification; All codes provided in the supplementary material. All datasets common benchmarks with open access.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
Sholic//giides/odeeeee
wwwasssssollliiees imPllccy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / wttpp.ccppppllippppppppppppppppp wwtpccccpccccceeccccccccccccttlt wwtpc//ggg/eeeeeeeeeeeeee
ceabbbmmsssoonPo. ssiiisolicyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experiment settings are presented in Section 4, with details Appendix D. Codes are provided in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: In Appendix D, we provide additional experiment results using different random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
20

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the hardware, memory, and runtime in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https htt///neuripppp/ cc cc/public/ Caublic/Ethicseee wtw.chhhciiceieeeeee...
Answer: [Yes]
Justification: We have reviewed the guidelines. The research this paper conforms every respect with the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This study is primarily theoretical, with experiments conducted on standard open-acces benchmarks. does not raise any foreseeable and immediate societal concerns.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
21

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is primarily thcoretical and has such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Information of all the data and codes use is provided in Section 4 and Appendix D.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
22

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasttssss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide documentation for codes in the README file from the supplementary material.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not involve such research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not involve such research.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
23

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We use LLM only for writing, editing, or formatting purposes.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //turr/ps...... /ww.neeernnnee/22//1111// for what should or should be described.
24

---

A
Missing Proofs from Section
Proof of Proposition 2.2. Algorithm 1 applied to Example 2.1 gives
T++1 zt h(æz + Xua) - h(ær - Aue) U4
2X
where dt ~ NN(0, I2d) the search direction. Let u4 (wr w()T. The dynamics can be written as
((ve + )wxe [(+ + =ww))= - -1)² ((y+ - -ox) (#e - -Awe)) - -1)² Ute
1/++1
Ut
"
41
((y6 \ve) (2x + Awi)) - -1)² ((ye - -xe)) (2e Aww) - -1)² W/-
2++1
2t
17
41
Let A, = ((ye + \ux) (#+ + Xwo)) - 1)3 ((y: \w4) (2+ - xxx))) - -1)2. As it holds that
A. = 42 (v 2 - 1 + x20, we) we + 2 ve),
the dynamics can be simplified as
36+1 V/1
E[(y 24 1 2211 we (v) we 24 v() Ue arl
Zt
(ue 2t 1) Izc A2 wew
(ul 2t 1)zr - X2ye.
and the same reasoning applies
Zt+1
Zt
E11 2t - 1 + 22, we (e) we + [TTe)oy xzl
24
7
(vi 1)ye X220 22.
Here, we use that W/, are independent, and that Bw = Bluivd = La. For B, = (11vel) (zel12)/2, we then have that
B Be
yc+1
1/1
2441 - 24
Vl41
3t
2
17
21+1 22
Vs
26
+
17
2
Since it holds that
y/
E
Ut+1
y/
11.
E
21+1 Zt
(1
-1lwal1
17
= -22
conclude that
Bi+1 B,
IE
-2X + O()).
1)
Therefore, by taking the limit 7 + O, we have that dBEiBi/dt== -21² E
B Missing Proofs from Section 3
We Isserlis' theorem [41, 91] frequently in this section and restate it below for clarity. Fact B.1 (Isserlis' theorem). Let -N Ia) be standard Gaussian random vector in Rd The i-th coordinate of u is denoted by u4- For E [d] with j E [N], it holds that
N
E
I /=1
u
=
Σ
II Sighe
PEP
(K.1)E
where P3 is the set of all distinet ways of partitioning [N] into pairs, and digq, is the Kronecker delta, equal to if is i,, and 0 otherwise.
25

---

For example, when N = 4, there are in total (2) /21 = 3 distinct ways, and we have that
P = (((1,2), (3,4)) ((1,3) (2. (1.44))))))
Applying Isserlis' theorem gives that
4
E
Si + Oesig + d Oizis
In general, there is such partitions and the expectation is 0 when N is odd. For the case, the number distinct partitions is
= (N 1)(N - -3) ...3.
(N/2)!
which results (N 1)!! terms in the summation.
B.1 Supporting Lemmas
Let f() he three times continuously differentiable and u ~ WOO,, Ia) be standard Gaussian random vector in Rd. To simplify notation in this section, we denote
Go(æ, (u fx())) u,
Ho(x, u) = (u T v(u v2f(x))) u.
Since E[uuT] = Ia, we have that
Vf())u]= = E|wu fV)(x) -a(x).
This shows that the directional derivative Go(a, u) when taking X the two-point estimator (see Eq. (1)) is an unbiased estimator of Vf(x). For Ho(x, u), it holds that
d
Ho( u) = 2
(u
22 f(x)u)
k=1
d
d
d
82 fx))
26
Dz,, dz,0rz Ugugg
dzk
d
fz)(z)
0x, 0xx u
1=1
Let by be the I-th coordinate of Ho(a, u) for 1 E [d]. Applying Isserlis' theorem, have that
d
f(zzz)
E[hy]
E [uuu,mmu
0x,0x, ,x
83 fx))
(dejou + S5p2 + 8ạ05k)
dz, 20,
a
f2
dz
dx?
This means that (z w) 3V (x)))) and that Go(a, u) + (22/6) Ho(æ, u) is an unbi- ased gradient estimator for F(x) defined in Eq. (5).
26

---

Lemma B.1. Let f() be three times continuously differentiable and u ~ (O, Ia) be a standard Gaussian random vector in TRe independent of x E TR. It holds that
(a) Go 4)1l 2d))
(6) B[Go(a, u) Ho(z,u) 3(d + 4) V VTH(V
80
(c) Ho,, w)]l 9(d + 66 V]] 6 6(d 6) 0x,
This enables the computation of an upper bound on El]Go(a, u) (2/6)) Ho(,, w)ll Proof. For (a), we have that
0f(z)
E Hll'V((aa ((x)ul E
Oec
Of(z) Of(z) Eluzujufl
8x; dx,
(f()) 0f(z)
(dej + 26=
0x; dz,
k=1
Of(x))
(d +
0r.
(d + v())
Similarly for (b), we have that
E[Go (2,, u)" T Ho u)] E [(u" f
V(u V2 (()))))))111
E
u4 0f(x)
ΣΣΣ
uu dx,
0²
Σ
u
Oz,
8 {(x)) 0f(x)
ΣΣΣΣΣ
umm
,x, Oxm
By Isserlis' theorem (see Fact B) when N to compute Elu,u,ugu 2 there are in total x
3 = 15 terms in the summation, and the problem reduces to how we partition the set {ú, j. k, m, n.
into three pairs. Let us consider the following two cases.
(1) We pair n with n and partition {i,j. ki m) into two pairs. This gives terms in the summation.
ōimōxm + 8. + 6im = Ai.
Here, we use 6nn = 1 and let A, denote the summation of terms considered in case (1), and then
d d d ΣΣΣΣΣ 11
fzx(z) 0f(z) 0x drm
03 fz)()) Of(z)
A 3d
dr drk
(2) We select two ordered indices in {i, k. m), pair the first one with the first n, and pair the second one with the second n. The remaining two indices form the third pair. This gives 3 12 terms in the summation. To further simplify notation, we divide case (2) into two subgroups, each with 6 terms, and denote the summation of considered terms by Az-1. A2-2. 2. respectively.
In A2-1, 1. we consider the case where both selected indices come from {i.j.k) k3 involved in third-order derivatives. It contains 6 terms and thus
0f(z) Ōx,ūx,,0r Fam Az
f²
f() 0f(z)
dx7Oan Oxy
n=
27

---

In A2-2, we consider the case where one index in the selected two indices is m. This also gives 6 terms, and we have that
d ΣΣΣΣΣ
8 fx)) 0f(x) A2-2
8 f(x) 0f(²) dx dry
0r, Day 0xm
Considering the above cases (1) and (2), we conclude the proof of (b).
i= ΣΣΣΣ f2x()) 0f(x) ulu Rnl
E|Gu (2x u) Ho(x, u)]
Ox, dmm
0 f(x) 0f(x)
(A1 + A2-1 + A2-2)
:= j=1 1mm m= 0x, dum
f(z) 0f(x)
= =(d++4) 4)
dz Drk dsk
VTr(V> 3(d 4) V VT+> ((x))
Finally for (c). we have that
El Ho, w)ll = E [[u"
Vu
T V2 [ [1
2
d
d
8 f(x)
Σ ut
E
dz. 0x,0x,0m uuuuuk
d
83 f(x)
8 f(x)
Blu,, ui Uk, Mia M3a Wk2 uf],
au dcr, Srk Dr Jr Ourka
high Au
12 A2, m 1 Im
where Σ Linhh.h means Ei= E₁ Σ Ek,=1- By Isserlis' theorem (see Fact B.1), we need to consider all distinct ways of partitioning the set (i1.1, kı i2, 1,1 into four pairs, which has 7 x 5 x 3 = 105 terms in the summation. We consider the following two cases.
(1) We pair / with and partition fi1, k1, 12, k2 into three pairs. This gives 5 x 3 = 15 terms in the summation. We further divide case (1) into two subgroups and denote the summation of considered terms by A1-1, A1-2, respectiell..
A1-1 has x 3 9 terms, where the first pair formed with one index from (11. J1, k1 and the other index from remaining indices (22, k2) give the third pair. By symmetry of the summation, we have that
the remaining indices in {ir,J1, ki} yield the second pair, and the
fz)() f1:1, 11 j2.1,,k011 dr, ju,, Son, j Oxr
ΣEΣ
d Σ Σ
fz)(x)
d d d 0 f(x) f(x)
AI- 9d
ΣEΣ
duz duz
==1
1=1=1
The rest terms of cases (1) are collected in A1-2, where all three pairs consist of one index from f2, k.). Therefore, we have that
fir,1, } and the other index from f22.j2,
f(x)) dz, Oxz, Org, ox, Or,,Ox,, Oxks A1 6d ΣΣΣ
f(x)
f8x)
Σ
Σ
0r,0x,0xx
(2) We select two ordered indices (ir, ji, ki, f2, f2, h2). pair the first one with the first I, and pair the second one with the second I. The remaining four indices form the last two pairs. This gives (6 x 5) x = 90 terms in the summation. We further divide case (2) into two subgroups and denote the summation of considered terms by A2-1. A2-2, respectively.
In A2-1, i. the selected two indices come from the same (ir, ki, k1) or (22.j2, k2). There are in total 3 x 2 x = 36 terms involved. By symmetry of the summation, we have that
Σ
Σ
Σ
f(x))
0d
A 36
f(x) 8 f(x) du Outaus
Dx,, Dzy, Oxy, dxi, Ox 0zks
h kg=
28

---

In A2-2, the selected two indices consist of one from (é1.ji.k) k1 and the other from f2: k2) to pair with I. To simplify computation, Ag-2 is further split into 22-2-1 and 22-2-22 according to how the remaining two pairs are constructed.
For case 22-2-1, after having the pairs with I, the remaining indices in {ii: .1, ka) } yield the third pair, and the remaining indices in fi2.J2, k2} give the fourth pair. One example of such partition {(11, 1), (iz, 1), (i,, k1), k2)). There are total 3 2 18 terms in the summation, and
d
8 fxx) dx,, or Uxv, Or, 0rka
f(x(
8 f(x) 8 f(x). Ox7 dx²
A2-2-1 18
A1 k2.
For case A2-2-2, after having the two pairs with I, the remaining two pairs are composed of one index from (ii: k1) and the other index from k2. There are 3 x x 2 x = 36 terms, and thus we have that
d
d
(2{()) dæs, Jz,j doe, dzi, jr Orkg
8 (x))
01(()) 2
Σ
Σ
A2-2-2 36 2
Ji 12.22.2=1111 1=1
sanity check ensures all terms are considered to compute Elu;, Us, uk, Us, U/ Uk, "f]. Therefore, considering all cases above, we have that
36- makes sure that all terms are included in case (2), and 15+ 90 105
f())
0 f(x)
B| (o(,,
Σ
E
Blu,, Uj Uka Uea U3 uka uf]
ox, or dag Or, 0r 0rke
iidi S2 1=1
f(x)
8 f(x)
03 (z)(z) 0z,0z,00x
9dd
6(d 6) Σ
dataay 0zzōrz
d
02,0x,0ru )
8 f(x())
= 9(d VVV+VVVVVVVVVVVVV 6(d + 6)
This proves (c) and concludes the proof of Lemma B.I.
B.2 Proofs of Lemmas 3.5 and 3.6
Proof of Lemma 3.5. Recall that fx(z) = E[f(x + Xu)] and F(x) = f(x) + (A22)) The first part follows from the third-order smoothness of f(x) in Assumption 3.3. To simplify notation, we let
A
Dx (z + Au) f(x) +VV((x) a+ 2 VZz( + v fx))33
(6)
6
where V {')(') - Eig. (0 fxx)/Ox,0z, (aaddt,,0xxuua) uuuuu un and N/ La) standard Gaus- sian random vector. Taking expectation w.r.t. u, have that
X2
Eg P_ + Au)] = f(x)+ + Elu ())))
2
= F()).
As result, obtain
[fx()) - F(x)) [ (z + Aw)] EE (x Xu)]
< E [(x BB
+ Xu) - (x (x + Xu)
< La xa E||
24
where we use Assumption 3.3 (c). The proof is complete applying Lemma I in Nesterov and Spokoiny [74] such that [E|lu|" < (d + 1/2 if 2.
29

---

We now show the second part using Lemma B. Similarly to Eq. (6), we define
X² (z Au)= = - -VF(z)) u+ V f(z)
Xa v [z)|[//3
2
6
By Assumption 3.3 (c), we have that
[f(z + Au) - f(x -Auul S [f + Au) - 1x + Au)l + 12 - Xu) - [(x - Au)
+ 11 + Xu) 2x Xu)]
(x) Tu + x v fz))
La
+
12
For the two-point estimator in Eq. (1), it holds that
| 2)1²= (f(x + Au) f(x Au))2
|/21|2
412
X2
L3 ||u|2
2 (f(l)) uut +
V {())()))
6
288
Recall Go(z, u) = wu u fzz)) and u) uu Ju v (z))))) ft) Therefore, we have that [1] u)ll
2x²
X1
T.
$2E u)]l2+ +
E[Go(r, u) Ho(a, w]]+ +
E Ho( u)]l
E| u|l 10
3
18
288
=2(d+ 2) (x)) 2 + 2(d + 4) (TT(V> f(x)) + (d + 6)A1
2
(d (d+ 6)
d d
(f(())
L
ΣΣΣ
+
El|u||
3
dx,0x,ddr
288
k=1
S 2[ + T2 (d - 6) +
6 + 10)3.
3
288
Here, we plug in Lemma B.I, apply Assumption 3.3 (b), and use Lemma I in [74].
For completeness, we also show here that second-order smoothness implies the boundedness of third-order derivatives. Recall the second-order smoothness in Assumption 3.3 (b).
| s(=)l < L22y =|I, Vy.eRR R
where the matrix norm is defined as
- =
w -
max VER!!||!!
For simplicity of the notation, we let Vi, E [4].
(1,(,,)):= 0² fl) dr,0o, Or,0x,
82 (())
Let eq E Bd denote the unit vector whose i-th coordinate is and all other coordinates are 0. Since
|es|| || = 1, we have that Vi E [d],
[D =) =
=l. -e (())e
< [
-
I Lelly- - z||.
We define w == (ei +ei+ and - = (e: e / for any i,j E [d] and i + j. It holds that
(w (w+)T((²(()) (2())))) (wx))( / (Du(v,2) + +D 2) + D3g (v. z)), 2) + D39 (v. 2)).
(w (w>)T(v²f()) (z=))( = 2
2) - -
30

---

Since ||w*1 || = || ||
1, we have that
[D,(
2 (v -w
(w (w>))(v2f()))
(w)
- 1 -
$ L =||1
This means that the function 0² /(rr)/0r00 is Le-Lipschitz for all i,j E [d] and implies that its gradient norm is upper bounded by L2. As a result, we have that Vi, J, k E [d].
0 f(z) 0x,0x,00 Ozr
2
0 f(x))
- V
dx,dr,
s L2.
This concludes the proof that 10
& L2 Vi,j, k E [d].
Proof of Lemma 3.6. Recall the third-order smoothness in Assumption 3.3 (c).
|[v) - L Ls ly =|I,
Vy, Rd
where the tensor norm is defined as
[(0) - [3)(l
V -
V {=)][(]))
max WER
and [y)((\] = Eijkeld (8 (0r///,,,,,,,))ee (1.1)(1155) of Nesterov [72] and Appendix I of Nesterov and Nemirovskii [73]. For simplicity of notation, let Vi, k E [d].
More details can be found in Eq.
f
f²f(2)
Disk(y, 2) 0r,0x,00x dz,0x,0xx
Let C2 E Rd denote the unit vector whose i-th coordinate is and all other coordinates are 0. Since |e:| 1, we have that Vi [d].
(Die(,,))
["yl]e -- {()()e)
< [(²)(() f')(2))
< Lally-211
We define w = (e: ex)/v2 and w- (e: ex // /2 for any i [d] and i of k. It holds that
V2
4 (Dis (y, 2) 3D (y, 2) 3D DDRa 2) + DRuK(y =)),
V')(y)[u {²) V2 -/2 (Din),22) - +D. 2) - DERK(Y, 2))
Since ||w+|| = [||[[] 1, we have that
Din(U,))
2
V2
(V (2f())(ut13 -/rla//p--///////>>>>>>>>>"
"-
D DunA(U,2)
3
2
2v2
$
/|v) v2
DuAK(V. 2)
<
/2Lally -zll-
31

---

As result, we obtain
à d
82 f(y)
0
d
0 f(z)
2
-
duk
dxp
k=1
i=1
2
Disk (ys z)
k=
1=1
2
Σ
D Den 2)1
k=1
< 2d Li - 211
By Assumption 3.3 (a), we have that Vy, 2 R2
[VF(()) - VF())]] (VV(()) vs(=)]I + 1² VVVVV>/))-- (=)))
2
L1+ L2 11y - z||.
V2
This means that F(x) is (2L1) -smoohh when X2 /2L1 (dd322 (1) Therefore, we have that
1 v((() F(x)
1
1 VF(x)
[F(2))1 L,
2h
2T,1
2T.1
= F(x)
|FF(2)1
4L1
Rearranging terms, we obtain that Vo E RR.
|VF())] < 4L,
F(x) F
F(()))
2L,
< 4h
F(x)
min
F(x)
=ERd
This property of smooth functions is used in the proof of Theorem below.
B.3 Proofs of Theorem and Corollary 2
Proof of Theorem 1. By Assumption 3.4, f(x is convex, which suggests that the smoothed function
fx(x) is also convex [74]. Let ui be one minimizer of F(x) = (xx + (F//)T(((V"((x))) By the zeroth-order update rule in Algorithm 1, we have that
Eu, |,141
1
|| 2 2 2n Elga (2,, uI) [2; (0,-xx)) + n/² Bllga (z,, ut)l
= || / 2 2 (x;) (xt - -+²)+++++ + g u4) )|
[x(x)) (ll 4x) 1| < || 2r 112 (n(F(()) - F(z))) + 71²
< ||<re x 1|2 2n)(S2
+ 2m (2x) - fA (x:)) 2nl.f -(x)))
< ||,, x 212 - 2n F(*))) + Ellgx( 12)l
La
(d 4)2,
6
where we apply Lemma 3.5 in the last step. Using the same lemma, we also have that
BlIga( u. 2(d ()) + L3 xd)
L3
10)
288
L3 x + 6) +
L3
{(d+))) F(z))) +
x ( + 10)5,
3
288
32

---

where we apply Lemma 3.6 with 32 /2L1/(dd/2 L3) and use Eq. (7) when F(x) is (2L1) smooth. As result, we obtain that
En, F1 =x>p1? -
[1 - 1 2n(11 4n(d + ())) F(
+ La n n
(d + 4)²
L -d+ 6)
L3 n" x 10)s.
3
288
We choose 1/ = 1/(8(d + 11) such that 4n(d + 11 = 1/2. Rearranging terms, we have
B(F(zz) - F(x})]
E| - x3,112 - B1| - x71
+ La 22x4 +
L2 nd 6)+ +
LE n (d 10)
4)3
3
288
$ 8(d+ + 6) (B) b4 - 1/ -
E E11 - -1)11²)
+ La xd 4)² +
L3
L3
x+ ( 6)h² + 1152L,
x (d + 10)*
24L1
Summing up from to
and dividing both sides by T. we have that
E
F(x+)
min F(z) sERd
T-1
B - F(x7]]
T
1=U
8(d + 61111 - x3?
La x 4)²+
L3 24T,
L3 1152T,
(d + 6)
A + 10)4.
T
6
The proof is thus complete.
Proof of Corollary 2. First, we show the guarantee the function f(x). Assumption 3.4 implies that Tr(V2 f()) 2 0, Vz E Rd, and thus f(z) F(z), Rd. Since f(x) is -smoohhh by Assumption 3.3, we also have that
X² Tr Tr(V² f(x))
min F(x)= = min zERd
f(x) +
wERd
2
X2
< min
f(x) + Lıd
2
X²
min zERd
[(x) + 2 L,d.
As a result, we obtain that
[(xx)) min f(x)) seRd
Li x2d
S E F(x-)
min F(x)
+
sCRd
2
8(d L) |00
xx
L x2d
+
T
2
La
L3
L3
xd + 4)²
+
( + 6)3 +
1
6
24L
1152L
Next, we prove the guarantee on the trace of Hessian. Since X = arg min f(x), we have that
X2 Tr Tr(V' f(x))
min F(z) min #ERd
f(x) +
zERd
2
X²
min x
(f(z)
Tr Tr f(z))
X2
min zERd
f(x)
min Tr 2 fx)) xEx
33

---

As result, we obtain that
E
Tr(V2
min Tr(V² fx))
=Ex*
2 B[F(x+) - [(x+)]
2
min F(x)
min f(x)
X²
ZER
=ERd
(8)
2
B F(xx)= - min F(xx)
X2
=ER
16(d
6)7₁ |1:0 21212
La xd
L3 _ (d 6)$ +
L3 57641
4)2
x 10)
X²T
12L1
Given > 0, choosing À and ' such that
V2L d3/2 La(d + 10)2 4La(d + 4)2 L3 + 6)3
12
3e
3L,c
2² min
(4 + 6, 11=0 - 13 max
1 Lg(d 10)2
4T.g(d+ + 442
I2 6)$
T2
c
V2h 12vLie
3c
3L1c
to make sure that each term in the right-hand side of Eq. (8) is most c/4, have that
min Tr(v2 Se. E f(x)))
TEX*
This also ensures that E[f(x,) min P(x)] e2e/2, and thus
+ L1 x2d
E
f(x+)
min f(x) zERd
S F(x,) min F(Ø)
=ER
2
X²
s (e + Lid)
2
< 3
(1+ Li(d+6))
1+
c
The proof is thus complete.
C Alternative Proof of the Main Result
In Section 3.1, we provide a convergence analysis by relating gA (I,, u. 2 to |VF Here, show that it is also possible to first bound Ellgx 12 by f>
Lemma C.1. Let Assumption 3.3 be satisfied. The second moments of gx (z, u) can be bounded as
Bllga( w)l < 4(d+ + L3 (x)+88))
Proof. The proof mostly follows from Lemma and Theorem 4 in Nesterov and Spokoiny [74] and is similar to that of Lemma 3.5. With a slight abuse of notation, we define
X²
Φ (x + Au) f(x) (V)(x)
+
22 TT2 f(x)u,
X2
T (x Au) = f(x) - (Vf(x) u +
2 4
(2
Assumption 3.3 (b) implies that
La
(f Aw) 2x 12 xu)
6
34

---

and the same holds for If - Au) - 22 - xu)l. Therefore, we have that
(f Au)- f(z -uu)] - [f + Au) 2x Au)l + 22 Au) - f(x Xu)
+ (2 + Au) 2x Aw)l
2XV (x) Tul + L2 x 1|ul1
For the two-point estimator (x, u), it holds that
(1 u)|l= (f(z + Au) - f(x Au))²
|u||
412
L2
S 2(u 2 ||||2
18
Recall Go(z, u) = un [ in Lemma B.1. By Lemma in [74], we obtain that
L3
Elgg (z. w)ll s 2E/|Go(z, u)] +
2
18
L
$ 2 2) v
+
A (d + 8)
18
Then upper bound the difference
[V/(x) v/((=)]
Vf(r)u f(x + Au)
f(x A2))
[V(x)) - vf(+)]==
E
u
11
21
(2 Au) 2x Aee) - -f(x + Au) + f(x Au))ull
21
La 1u112
6
La x2 4
6
As result, this gives that
L3 Eliga 1)1l < 4(d 2 4(d - ()() VA(*) xd + 8)
18
LA L2 xd
4(d ((d+2)) 4[d+2)]V\\()
The error term O()d55) has worse dependence d compared to Lemma 3.5.
Theorem 3. Under Assumptions 3.3 and 3.4, Algorithm 1 with stepsize n = 1/(8(d (idd++2)). 2)) satisfies
8(d + [| xx
L
La xd + 4)2.
F(ir) min
F(x))
S
x x2 8)
ZERd
T
12L
12
where zo E Rd is the initialization, 23, E arg min fx(x). कт = (1/T) Et 2, the average of iterates, and the expectation is taken w.r.t. the randomness in all search directions. This implies
E [(xr)
min )()) < L2(d+ + 8)3 ZERd
T.fe
1+ LTdd+8))
E Tr(V)f(Er))
min Tr(V2f(x)) ZEX
Se.
when setting the smoothing parameter X and the number of iterations T such that
2e
2L1E
x min
Lg(d + 472' T 8)1
T> 48(d + L1 Io
x11?
[a(d+ 4)2
L2(d 88
max
2e
2L16
According to Definition 3.2, this means that (O(e/d8), approximate flat minima can be guaranteed with T O /e2) and (
35

---

Table 1: Summary of convergence rates to approximate flat minima with different set of assumptions. Convexity is required for all cases and is thus omitted in the table. Lg means f(x) is Lo-Lipschitz, and L, denotes that (x) is rth-order smooth for r = 2.3. Under the smssoohtsssss assumption, (O()9d), c) approximate flat minima are attained; without this assumption, zeroth-order optimization converges to (O(Ad ()) approximate flat minima.
Assumptions
Reference
Smoothing
Stepsize 1)
Iteration Complexity
L1, L2, La Li, La
Corollary 2
O(e (d8/2) (min 2/2 /dd, e/d9/2)) (min c 122 //,//d, (1////111)))))
((1dd)
(62
Remark C.2
(11dd)
( (d (P/ (23)))
Los L2z La
Remark C,3
((A/d)
O(max (d /é, f. (6/22) Od
Lo, L2
Remark C.3
((e/d5/2)
((/d))
Remark C.I. Compared to Corollary 2, Theorem 3 has similar dependence on but worse dependence on d in number of iterations T. This comes from the worse dependence O(A &d5) in Lemma C.I.
Remark C.2. In this framework, the only place that uses the third-order smoothness assumption is to upper bound the difference [x(x) fx(r)] With second-order smoothness, an alternative result [xxx) [x(x) S
(L2/6)A² + 3)5/2 has worse dependence on A; see Theorem in [74]. ( + ddd + Ad9/2) and thus T = (maxx /e dd /e")). Relaxing the third-order smoothness assumption gives strictly worse convergence rates. The detailed derivations are similar to the proof below and are thus omitted.
This leads to E [ 2 ((Tr) min [r(V) &
Remark C.3. We also briefly discuss how the L1 Li-smoothness assumption on f(x) can be relaxed to the function being differentiable and Ln-Lipschitz, i.e., [ S Lo, Va E Rd. By Lemma This
E.3 in [27], when (Ix is convex and La-Lipschitz, f' (x) is convex and (Zo/A)-smootie means all dependence on L1 can be replaced by Lo/X x in the analysis below. With both second-order and third-order smoothness assumptions, and setting v - O(/d)), this gives B[Tr( ( ((T)) - minzexx- Tr fr(V) s ((d/()*))+
and thus T = (mmax(dP/e / 5/2/1)) With only second-order smoothness assumption, this gives E[Tr(V²((Tr) (d)())T + da + Xd2/2) and thus T = (d /ct. (c11///c) Table summarizes the complexity under different set of assumptions on the function (x).
minzex
f())) <
Proof. When f(r is L1 -moothh and convex, fx() is also L1 Lm-shooth and convex [74]. Let x² be one minimizer of fx) The same the proof of Theorem 1, we obtain that
Eu, 11.111111- - =² = || == 2n7 1lgg (2t, ut)] (a. - = + r7² (lgg u)l1 = || x²|1² - 2 T (z. (000-25) - = (o 12
< || xx11 - (n((((==)) - Axx2)) + Ell w))1
By Lemma C.I. we have that
L3
E gl 5 = ((dd)))[///())))) 6
xd(++8))
L3
< 8(dd 2) fx(1))) + (d+
As result, we obtain that
L3 _2, , 2 + 8)3. BRg ||ae+] - x312 & |1,, xx1²² 21y(1 - 4n(d 2)(+) - Aa())) +
6
We choose 17 1/(8(d + 2)) such that 4n + 2)T, -1/2. Rearranging terms, have
E J++ x 1|2 El|22+1 - xx12
13
(x:) - fx(xa)) <
+
(d + 8)²
6
13
s 8(dd 2)4, x312
Ell - x}(1²)
Xt 8)1.
12L
36

---

Summing up from = to = T - and dividing both sides by T, we have that
1
E
fa(oT)
min fx(z) FER
(z) fx(2]]]
8(d 2) I1 - +X11
L
xd
T
12h,
where ëт - (1/T) T-1
iy is the average of iterates. By Lemma 3.5, have that
min zE
fa(x)
min (F(x) + [a(=) F()))
< min (F(x)) + (1(x) F())I)
=ER
LB (d 4)2. min F(z)
As result, obtain that
E
F F(Tr)
min F(z) #E
S E (ZT)
min fx(z)
+ (fx( F(Tr)) + min fx(x) ZER"
min F(x) ZER4
SER
8(d + 2)||||10 211?
L3 xd+
La (d 4)
12L
12
According to the proof of Corollary 2 (see Eq. (8)), this implies that
2 X
(T(V3S(ET) min Tr ( ((x))
E
[(TT)
min F(x))
#EX*
xER
16(d + 2) - xx
L3
8) + La
(2
2 4)2.
XrT
671
6
Given 0, choosing À and T such that
2c
2T
x² = min
Ly(d+ 4)22
L3(d + 8)4
48(d + 2) Ix0 xx1?
L3(d + 4)2 L3(d + 8)
T
max
2e
2L18
guarantee that E (VT minzex Tr(V² s and that
E
[(TT)
min ZERd
(x)
SE F(TT)
min F(x) zERd
+
41 x2d
L1
2
X²
S (e + Lid)
2
TifE
(1 11 ()d+8))
< L + 8)3
The proof is thus complete.
D Additional Experiments
D.1 Test Function
In Figures and 4, we plot the values of the loss function and the trace of Hessian when applying gradient descent and zeroth-order optimization on Example 2.1. We the example with dimension d = 100 and run the algorithms for T = 100, 000 iterations. Gradient descent uses stepsize of 0.01, and zeroth-order optimization uses 0.001. In Figures 1 (a) and (a), zeroth-order optimization is run with a smoothing parameter À = 0.1. The initialization is sampled from the standard Gaussian distribution (O. I24). Randomness arises from both the initialization and random search directions in zeroth-order optimization. Figure/ uses random seed 13, and Figure reports results for additional seeds 17 and 73. The results are consistent across all seeds. Each run executed on a CPU and takes approximately 1 second.
37

---

GD
22 +)
À 0.1
À = 0.05
... = 0.1
Seed 17
Seed 73
Seed 17
Seed = 73
Loss
10.3
Loss
10
200
Hess
Hess
10
10
10a 105
10a
10
10a
10
Number of Iterations
Number of Iterations
(a) Comparison GD and ZO.
(b) Effect of X.
Figure 4: Loss and trace of Hessian (Hess in the plot) on Example 2.1 using different random seeds. The observation aligns with Figure (random seed 13). Zeroth-order optimization (ZO) decreases the trace Hessian, and controls the trade-offs between regularization on the trace of Hessian and the optimization error induced by additional bias terms.
GD
Z0
a5a
w5a
a5a
w55
Train Loss
Train Loss
2
0-
x10
Train Hess
Train Hess
10a
10:
10a
10
6-
10a
1.0
1.0
Test Ace
Test Ace
0.8
0.8
0.6
0.6
0.6
0.6
10
10
10
10'
10
10a
10
10
Number Iterations
Number Iterations
(a) SVMs with Seed 13.
(b) Logistic Regression with Seed 83.
Figure 5: Training loss, trace of Hessian on the training data (Train Hess in the plot), and test accuracy on (a) SVMs and (b) Logistic regression using different random seeds. The observation is consistent with Figure 2 (random seed 29), where zeroth-order optimization (ZO) reduces the trace of Hessian.
D.2 Binary Classification with SvMs and Logistic Regression
The datasets "a5a" and "w5a" used in both the SVMs and logistic regression experiments standard binary classification benchmarks from the LIBSVM library'. LIBSVM [14] is released under the BSD 3-Clause "New" or "Revised" License The a5a dataset contains N 6, 414 training and 26, 147 test samples with d = 123 features, and the w5a dataset contains N = 9, 888 training and 300 features. We algorithms for T 10, 000 iterations. To mitigate the effect of mini-batch noise, we use full-batch gradient descent and zeroth-order optimization in the experiments. The stepsize and smoothing
39, 861 test samples with
10, 000 overparameterize and run all
www..ntu.ce.ee.e.mmmmmmm atu..eu.... http::/www...a.aacoooooooocattta html
38

---

GD
Z0
GD
Z0
K
32
K = 226
SST-5
TREC
Train Loss
Train Loss
10-2
10-2
10-3
10
Train Hess
10P
101
Train Hess
10r
10F
10-1-
10
10¹
0.5
Test Ace
Test Ace
0.50-
0.35
0.85
0.5
10'
10
10
107
10
16'
10'
102
Number of Iterations
Number of Iterations
(a) SST-2 with Seed 21.
(b) SST-5 and TREC with Seed 87.
Figure 6: Training loss, trace of Hessian on the training data (Train Hess in the plot), and test accuracy on (a) SST-2 with K = 32 and K 256, and (b) SST-5 and TREC with K 32 using different random seeds. The observation consistent with Figure (random seed 42).
parameter À searched from the grid {0.5, 0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001, 0.00005). Gradient descent uses stepsize of 0.001 for SVMs and 0.01 for logistic regression. For zeroth-order optimization, the selected hyperparameters
listed below.
For SVMs, the stepsize is 0.0001, and the smoothing parameter 0.05.
For logistic regression a5a, the stepsize 0.01, and the smoothing parameter À 0.1.
For logistic regression on w5a, the stepsize is 0.005, and the smoothing parameter À 0.05.
The initialization is drawn from the Gaussian distribution (0, (0.1)=Ip). Randomness arises from the initialization, the random matrix W used in ②(a,) = W ag. and the random search directions in zeroth-order optimization. Figure 2 uses random seed 29, and Figure reports results for additional seeds 13 and 83. The results are consistent across all 3 seeds. Each run is executed on a CPU and takes approximately 3.5 hours.
D.3 Fine-Tuning Language Models on Text Classification Tasks
We follow experiment settings in Malladi et al. [69] and consider few-shot fine-tuning on RoBERTa- Large* (355M parameters) [61] with K = 32 and K 256 examples per class on 3 text classification tasks: SST-2* and SST-5$ [82] for sentiment classification, and TREC [84] for topic classification. RoBERTa is available under the MIT License?. The datasets commonly-used benchmarks that publicly available for research purposes. Our implementation based on the codebase provided by Malladi al. [69] and uses the same prompts. Their code is released under the MIT' License The SST-2, SST-5, and TREC datasets contain 2, 5, and classes, respectively. We consider К = 256 only for the SST-2 dataset, and K 32 for all datasets. The training set constructed by sampling K examples per class from the original dataset, and the test set is built by randomly selecting 1, 000 examples from the original test dataset.
We fix the number of iterations to 100, 000 for K 32 and 50, 000 for = 256. The trace Hessian evaluated every 100 steps using the expected sharpness (2/5²) (m ( ōu)] f())
39

---

Table 2: Total runtime (hours) and memory consumption (MiB) when fine-tuning RoBERTa using gradient descent (GD) and zeroth-order (ZO) optimization. We report both mean and standard error of the runtime across three random seeds {42, 21, 87)) Due to additional forward passes required to approximate the trace of Hessian, the reported runtime is longer than standard training. GD consumes less memory than the default first-order optimizer, Adam W, which stores additional optimizer states.
SST-2
SST-5
TREC
Task
K 256
32
K 32
Batch Size
512
64
160
192 100, 000
Number of Iterations
50, 000
100, 000
100, 000
GD
29.47 = 0.93
7.38
0.33
21.64 + 1.18
14.79 = 0.56
Runtime
Zo
25.13 = 0.94
7.34 + 0.22
18.91 + 0.52
13.37 + 0.47
GD
54, 214
7,986
18, 826
14, 258
Memory
ZO
5, 038
3, 074
3, 4,4
3, 274
approximation, where 5 10-4 and the expectation is estimated by averaging over 100 samples. To reduce the impact of mini-batch noise, we use full-batch gradient descent and zeroth- order optimization in all experiments, both without learning rate scheduling. This leads to batch sizes of 512 (SST-2 with K = 256), 64 (SST-2 with K 32), 160 (SST-5 with K = 32), and 192 (TREC with K 32). The stepsize for gradient descent is set x 10-5 for all cases. Zeroth-order optimization uses stepsize of 10-5 for SST-2, and 5 x 10-6 for SST-5 and TREC. The smoothing parameter À in zeroth-order optimization set to 10 for SST-2 and TREC, and 10 for SST-5, Randomness arises from the selection of datasets, the initialization, and the random search directions zeroth-order optimization. Figure seeds 21 and 87. The results are consistent across all 3 seeds. All experiments are tested on single NVIDIA H100 GPU with 80 GiB memory. The runtime and memory are summarized in Table 2.
random seed 42, and Figure reports results for additional
40


Reviews:
[{"review_id": "UxvtLtN6en", "reviewer": "Reviewer_WS1L", "summary": "This paper presents a theoretical analysis of zeroth-order (ZO) optimization, revealing its implicit regularization effect towards finding flat minima. \n\nThe authors provide a theoretical framework to explain this phenomenon\nThe core idea—that the smoothing inherent in ZO methods acts as a regularizer minimizing the trace of the Hessian—is both insightful and elegant. \n\nThe theoretical contributions are well-supported by proofs.\nWhile the experiments provide corroborating evidence, there are some questions regarding the practical implications in highly non-convex settings. \nOverall, this is a paper that makes contribution to our understanding of zeroth-order methods", "questions": "This raises the question of the practical utility of using ZO for this task. \n\nIf 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? \nThe 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.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nNovelty and Conceptual Contribution: The primary strength of this work lies in its novel perspective. While the analysis of ZO methods via smoothed functions is standard, this paper is the first to re-interpret the Hessian trace term not as a bias to be suppressed, but as a desirable regularization term to be embraced. This leap, connecting a classic optimization technique to the modern pursuit of flat minima for better generalization, is a fundamental contribution.\n\nTheoretical Rigor: The paper's claims are backed by solid theoretical work. The authors formally define flat minima in a global context, construct a novel proof strategy around a regularized objective function F(x), and provide a full convergence complexity analysis (T = O(d⁴/ε²)) for finding approximate flat minima. The technical depth required for the proofs, such as handling 8th-order moments of Gaussian variables, demonstrates the non-triviality of the theoretical analysis.\n\nPoints for improvement\n\nWhile the theoretical contributions are clear, I have some questions regarding the experimental section, particularly concerning the practical implications of the findings in the non-convex LLM fine-tuning setting.\n\nOn the Practical Significance in the Non-Convex Setting: The authors are commended for extending their investigation to the challenging setting of fine-tuning a 355M parameter RoBERTa model. However, 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.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the contribution of our work. We address the reviewer's concern regarding practical implications in the following.\n\n1. **Practical significance.**\n\n> 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.\n\nThanks 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.\nIn 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.\nFor the trace of Hessian, we provide the first evidence that zeroth-order optimization has implicit regularization to reduce the trace of Hessian.\nDespite this gap in performance, there are scenarios where first-order optimization cannot be applied, and we **have to** use zeroth-order optimization instead.\nFor example, LLMs fine-tuning tasks where gradients are expensive to compute [69] and black-box settings where gradients are not accessible [17].\nWe provide more clarification in the following reply.\n\n\n2. **When to use ZO.**\n\n> 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.\n\nZeroth-order optimization is often preferred over first-order optimization when gradients are not accessible or expensive to compute.\nIn LLMs fine-tuning tasks, first-order optimization achieves better performance but has significantly larger memory consumption.\nFor 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.\nIn 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**.\nFor 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]."}, {"review_id": "tSDmJxgAR5", "reviewer": "Reviewer_2MGS", "summary": "This paper demonstrates an implicit bias in two-point zeroth-order optimization of $C^3$ functions towards flatter minima, as measured by the Hessian trace, and provides convergence analysis. This is done via a smoothed surrogate, which is shown to implicitly encode a regularizer term containing the Hessian trace. The smoothing parameter is framed as a trade-off between this regularization and the optimization error induced by a bias term. Experiments on binary classification problems in the overparameterized setting, and fine-tuning language models are shown.", "questions": "1. Could you clarify the $2/\\delta^2$ constant in the sharpness estimation equation, via a simple derivation, for instance?\n2. Do the results of your experiments change when the grid search is used to prioritize both validation loss and Hessian norm? If not, 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?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n* This paper has very clear writing and proofs are relatively easy to follow. The paper also clearly distinguishes its analysis from that provided by Nesterov.\n* The paper addresses an important problem of explicitly connecting zeroth-order optimization to the research on flat minima.\n\n## Weaknesses\n\n* In Appendix D.2, the authors state that they chose the learning rate and smoothing parameter via grid search. What metric was used to perform this? 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. Therefore, 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).\n* On L297 (page 9), can you expand on the $2/\\delta^2$ constant in your estimation of sharpness? I could not find that leading constant in either Neyshabur et al. (ref. 75) or Zhu et al. (ref. 103). In the former, the closest equation is (5), which uses $\\mathbb{E}\\_{u \\sim \\mathcal{N}(0, \\sigma I)} [f(x + u)] - f(x)$, and Zhu et al. use (from their Supplementary), $\\mathbb{E}_{u \\sim \\mathcal{N}(0, \\delta^2 I)} [f(x + u)] - f(x)$.\n* 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 moreso for a cursory confirmation of the established theory.\n\n[1] Beneventano, P., & Woodworth, B. (2025). Gradient Descent Converges Linearly to Flatter Minima than Gradient Flow in Shallow Linear Networks. arXiv preprint arXiv:2501.09137.", "was_revised": true, "final_justification": "All of my concerns have been addressed, and the paper makes interesting and novel contributions to the field. I recommend acceptance.", "rebuttal": "We thank the reviewer for the positive feedback and insightful questions. Here are our clarifications.\n\n1. **Metric used for model selection.**\n\n> 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?\n\nWe 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\n\n* 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.\n\n* 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.\n\nAlthough 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.\n\n\n2. **Compare to batch GD.**\n\n> 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?\n\nThanks for bringing this interesting paper into our attention. We will include it in the reference of our paper.\nThe 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.\nIn 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.\n**We believe this depends crucially on the loss landscape, the initialization point, and the learning rate**.\nWe leave a detailed study to future work.\n\n\n3. **Constant in the expected sharpness.**\n\n> Could you clarify the $2/\\delta^2$ constant in the sharpness estimation equation, via a simple derivation, for instance?\n\nThis follows from similar reasons as Eq.(2):\n\\begin{equation*}\n    \\mathbb{E}_{u\\sim \\mathcal{N}(0, \\delta^2 I)}[f(x+u)] - f(x)\n    =\n    f\\_\\delta(x) - f(x)\n    =\n    \\frac{\\delta^2}{2} \\text{Tr}(\\nabla^2 f(x)) + o(\\delta^2).\n\\end{equation*}\nTherefore, we add this $2/\\delta^2$ constant to directly estimate the trace of Hessian.\n\n\n4. **Relatively few experiments.**\n\n> 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.\n\nThanks 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."}, {"review_id": "mHfru9Apaz", "reviewer": "Reviewer_9wKN", "summary": "This paper studies the convergence of zeroth-order algorithms toward flat minima. Specifically, the authors analyze the convergence rate of a zeroth-order algorithm employing the standard two-point estimator, to solutions with minimal Hessian trace within the optimal solution set for smooth convex functions.\n Experiments on SVM, logistic regression, and language model fine-tuning validate the theoretical findings.", "questions": "1. Can the results in this paper be extended to non-convex settings? Since the derivation of implicit regularization (Eq.(3)) does not require convexity assumptions.\n\n2. 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?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. This paper is well written and easy to follow. The derivation of implicit regularization and flat minima (Sections 2 and 3) are clear and easy to understand.\n\n2. The derivation of implicit regularization on Hessian trace in zeroth-order algorithms is both novel and theoretically interesting.\n\n3. The convergence analysis in Section 3.1 is clearly presented, offering valuable theoretical insights.\n\n\nWeaknesses\n\n1.  This paper primarily focuses on the convex setting, where the Hessian matrix is positive semi-definite, making the trace of the Hessian an appropriate measure of sharpness. However, 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.", "was_revised": true, "final_justification": "For the extension to the nonconvex setting, the authors have outlined the current challenges as well as potential solutions. Regarding the experimental behavior of GD, the authors also provided references that offer explanations. Since these issues are not the main focus of this work, and given that this paper is the first to study the implicit regularization of sharpness by zeroth-order algorithms, I recommend accepting this paper.", "rebuttal": "We appreciate the reviewer for highlighting the strengths of our work. We address additional concerns in the following.\n\n1. **Extension to nonconvex functions.**\n\n> 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?\n\nAlthough 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.\nWe 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.\nFor 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.\nNonetheless, we want to emphasize that convergence guarantees to our definition of flat **global** minima remain unknown before this work in the existing literature.\nWe believe our results provide new insights and present a first step towards more challenging settings, including nonconvex problems.\n\n\n2. **Explanation for GD.**\n\n> 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?\n\nGD 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.\nThe 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**."}, {"review_id": "UlhFjKN2lt", "reviewer": "Reviewer_erZq", "summary": "The paper shows that a smoothed function based on a two-point zeroth-order gradient estimator incorporates the trace of the Hessian matrix implicitly as a regularization term. Zeroth-order minimization thus implicitly favors small eigenvalues of the Hessian. A small trace of the Hessian matrix has been shown to correlate with flat minima. The authors give a proof of convergence of zeroth-order optimization to flat minima, and show experimentally that the trace of the Hessian is smaller for zeroth-order than for first-order optimization methods.", "questions": "1. 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?\n2. Why is it that 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?\n3. 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?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- Nice use of Taylor's theorem to show the connection of two-point gradient approximation and Hessian matrix (eq.2)\n- Rigorous mathematical proof of convergence\n\nWeaknesses:\n- Very strong assumptions of function to be optimized being twice continuously differentiable and convex\n- Experimental results consistent with the theory are only found for convex losses (SVM, logistic regression), but not for non-convex losses (LLMs)\n- No attempt to link flat minima to improved generalization", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful questions. Here are our detailed clarifications.\n\n1. **Strong assumptions.**\n\n> 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?\n\nZeroth-order optimization is previously popular for optimizing nonsmooth functions where gradients do not always exist.\nHowever, 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.\nFor 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.\nTherefore, 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.\nExtension 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.\n\nWe 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.\nWe believe our results open up promising directions in the study of flat minima, including a better understanding for nonsmooth and nonconvex functions. \n\n\n2. **Experiments seem not consistent.**\n\n> 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?\n\nOur 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.\nFor 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**.\nNote 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**.\n\nThe 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.\nThe 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.\n\n\n3. **Flat minima and generalization.**\n\n> 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?\n\nWe explicitly avoid claiming that zeroth-order optimization generalizes better as it finds flat minima.\n\n* 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].\nIn 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.\n\n* 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.\n\nGiven 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."}, {"review_id": "3eITePnzd6", "reviewer": "Reviewer_79de", "summary": "This paper investigates the implicit regularization properties of zeroth-order (ZO) optimization methods, specifically focusing on the behavior of the standard two-point gradient estimator. The central claim of the paper is that ZO optimization with the two-point estimator implicitly favors and converges to \"flat minima\". The authors provide the theoretical analysis to support their method. Also, authors provide empirical validation across several settings to support their theoretical findings.", "questions": "See the weaknesses part.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1.  Rigorous Theoretical Analysis for Convex Case.\n2. The paper is generally well-written and logically structured.\n3. The experimental results provide support for the theoretical claims, especially in convex settings.\n\nWeaknesses:\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. In Figure 3, it appears that the methods have not fully converged.", "was_revised": true, "final_justification": "My concerns have been addressed.", "rebuttal": "Many thanks for the detailed review and instructive feedback. We provide clarifications below.\n\n1. **Challenging to evaluate due to smoothness and convexity assumptions.**\n\n> 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.\n\nThanks 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.\n\n* **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.\nSecond, 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.\n\n* **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).\n[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$.\n[3] considered **smooth functions locally satisfying the PL condition**. Convergence to **stationary points** of the trace of Hessian\nevaluated at limit points under gradient flow was established.\nCompared 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.\n\n* **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.\nLogistic 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.\nNesterov 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.\nAmong 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.\n\nWe 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.\n\n**References**\n\n(COLT, 2019) The Implicit Bias of Gradient Descent on Nonseparable Data.\n\n(ICML, 2025) Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression.\n\n\n2. **It is surprising that ZO achieves good performance.**\n\n> 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.\n\nThe 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.\n\nAlthough 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.\nWe 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.\nThe 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.\n\nFollowing 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.\nOn the Levy, Ackley, and Rastrigin functions, behaviors of algorithms crucially depend on the initialization rather than implicit regularization.\nOn the test function in Figure 1, there are infinitely many global minimizers, and implicit regularization selects which minima to converge to.\nTherefore, 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.\n\"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}$.\n\n| Function | Initial Loss |  | Final Loss | | No. of Steps To Converge | |\n| -- | -- | -- | -- | -- | -- | -- |\n| | ZO | GD | ZO | GD | ZO | GD |\n| Levy | 0.622 | 0.622 | 8e-4 | 0 | Not Converged at 10,000 | 7605 |\n| | 12.39 | 12.39 | 0.903 | 0.991 | Not Converged at 10,000 | 8085 |\n| Ackley | 0.967 | 0.967 | 4e-15 | 8e-3 | 9167 | 2333 |\n| | 3.958 | 3.958 | 1.605 | 1.646 | Not Converged at 10,000 | 2393 |\n| Rastrigin | 214.29 | 214.29 | 0 | 0 | 5578 | 37 |\n|  | 1147.7 | 1147.7 | 36.81 | 35.82 | 6537 | 54 |\n\n\n3. **Compare with baseline methods.**\n\n> 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.\n\nIt seems there might be a misunderstanding.\nOur paper mainly studies implicit regularization of zeroth-order optimization with the standard two-point estimator. \nEvaluating 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.\nThe goal of our empirical experiments is only to evaluate whether zeroth-order optimization with the two-point estimator decreases the trace of Hessian.\nIn this regard, we believe our current experiment results suffice to support the theoretical findings.\n\n\n4. **Not fully converge on LLMs.**\n\n> In Figure 3, it appears that the methods have not fully converged.\n\nLLMs 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.\nEven 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."}]

Author rebuttal:

Meta-review: This paper studies the implicit regularization of zeroth-order optimization with the two-point estimator, showing that it favors flat minima characterized by small Hessian trace. The authors also provide convergence rates in convex settings and validate the theory with experiments.

All reviewers are positive and agree that this paper is novel and interesting. The theoretical guarantees and supporting experiments are convincing, and initial concerns have been addressed in the rebuttal. I recommend acceptance. However, the authors are encouraged to further refine the final version by clarifying differences with related work and ensuring fair comparisons in the experiments.
Decision: Accept (poster)