Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm
Authors: Amir Ali Farzin
Yuen-Man Pun
Philipp Braun
Antoine Lesage-Landry
Youssef Diouane
Iman Shames
Venue: Accepted by TMLR ()

Abstract: This study explores the performance of the random Gaussian smoothing Zeroth-Order ExtraGradient (ZO-EG) scheme considering deterministic min-max optimisation problems with possibly NonConvex-NonConcave (NC-NC) objective functions. We consider both unconstrained and constrained, differentiable and non-differentiable settings. We discuss the min-max problem from the point of view of variational inequalities. For the unconstrained problem, we establish the convergence of the ZO-EG algorithm to the neighbourhood of an $\epsilon$-stationary point of the NC-NC objective function, whose radius can be controlled under a variance reduction scheme, along with its complexity. For the constrained problem, we introduce the new notion of proximal variational inequalities and give examples of functions satisfying this property. Moreover, we prove analogous results to the unconstrained case for the constrained problem. For the non-differentiable case, we prove the convergence of the ZO-EG algorithm to a neighbourhood of an $\epsilon$-stationary point of the smoothed version of the objective function, where the radius of the neighbourhood can be controlled, which can be related to the ($\delta,\epsilon$)-Goldstein stationary point of the original objective function.

Published in Transactions on Machine Learning Research (09/2025)
Min-Max Optimisation for Nonconvex-Nonconcavv Func- tions Using a Random Zeroth-Order Extragradient Algo- rithm
Amir Ali Farzin
amirrliifarzin edu.
School of Engineering
Australian National University & CHICAAA Lab
Yuen-Man Pun
yuenman.pun@ann..cu
School of Engineering
Australian National University & CHICADA Lab
Philipp Braun
School of Engineering
Australian National University & CIICADA Lab
Antoine Lesage-Landry
Department Electrical Engineering Polytechnique Montréal, GERAD Mila
Youssef Diouane
youssef.choonneeeyyyyym...c
Department of Mathematics and Industrial Engineering Polytechnique Moutréal & GERAD
Iman Shames
mman.shoamess@unimmcil
Department of Electrical and Electronic Engineering
University of Melbourne CHICADA Lab
Reviewed on OpenReview: https: opwwreveew. net/ forun? id- hatp:////uuuykyooote>>-001111111
Abstract
This study explores the performance the random Gaussian smoothing Zeroth-Order Ex- traGradient (ZO-EG) scheme considering deterministic min-max optimisation problems with possibly NonConvex-NonConee strained and constrained, differentiable and non-differentiable settings. We discuss the min- max problem from the point of view of variational inequalities. For the unconstrained problem, establish the convergence of the ZO-EG algorithm to the neighbourhood of an e-stationary point of the NC-NC objective function, whose radius can be controlled under a variance reduction scheme, along with its complexity. For the constrained problem, we introduce the new notion of proximal variational inequalities and give examples functions satisfying this property. Moreover, we prove analogous results the unconstrained case for the constrained problem. For the non-differentiable case, we prove the convergence of the ZO-EG algorithm to neighbourhood of an c-stationary point of the smoothed version of the ovjective fonction, where the radius of the neighbourhood can be controlled, which can be related to the (ō, GooGssttein stationary point of the original objective function.
(NC-NC) objective functions. We consider both uncon-

---

Published in Transactions on Machine Learning Research (09/2025)
1 Introduction
Many min-max problems that arise in modern machine learning are nonconvex- for example, gen- erative adversarial networks (Goodfellow et al. 2014 Gulrajani et al. 2017), robust neural networks (Madry et al. 2018), and sharpness-aware minimisation (Foret et al.; 2021 These min-max problems are gener- ally intractable even for computing an approximate first-order locally optimal solution for smooth objective functions (Diakonikolas et al. 2021p. p. thus structural properties have to be imposed in analyses. The exist- ing literature generally follows two approaches to solving zonconvex-nonconcen min-max optimisation: (i) imposing one-sided or two-sided Polyak-Lojjsiewvin
conditions (Yang et al. 2020) (or Kurdyyka-Tojjsiewve.
for nonsmooth functions (Zheng et al. 2023)) the min-max problem; or (ii) addressing the problem from
the lens of variational inequalities [Diakonikolas et al. 2021 Pethick et al. 2023
Regardless of either approach, most existing works require access to the gradient of the oracle, which prohibits its use for a wide range of applications. For example, one can only access the input and output of a Deep Neural Network (DNN) instead of the internal configurations (e.g., the network structure and weights) in most real-world systems. Hence, it is more practical to design black-box attacks DNNs for robustifying them against adversarial examples (Chen et al. 2017) Another example is Automated Machine Learning tasks, where computing gradients with respect to pipeline configuration parameters is infeasible (Wang et al. 2021
Other applications include hyperparameter tuning (Snoek et al.
2012) reinforcement learning (Salimans
et al.) 2017), robust training (Moosavi-Dezfoool et al. 2019); net work control and management CCen &
Giannakis 2018), and high-dimensional data processing (Liu et al.
2018
In this paper, we solve possibly NonConvex--onnCnncae (NC-NC) min-max problems via Zeroth-Order (ZO) methods from the perspective of Variational Inequalities (VT). Unlike first-order methods, ZO methods only require access to (often noisy) evaluations of the objective function, thus are applicable to problems for which gradients are costly or even impossible to compute (Maass et al.] 2021 Salimans et al. 2017 Bottou et al. 2018); also see (Rios & Sahinidis. 2013; Audet & Hare| 2017) for detailed reviews of these frameworks. As lar as we are concerned, the literature on solving NC-NC min-max optimisation problems via ZO methods is very sparse. The only works we noticed are (Xu et al. 2023) and (Anagnostidis et al., 2021), which study the unconstrained diffcrentiable nonconvex- nonconvex-Polyal-eeee Polyak-Lojjsicwiezz (NC-PL) min-max problem. Our work considers the min-max problem for both the unconstrained and the constrained setting. We assume the existence of solution to the weak Minty Variational Inequality (MVI) (Diakonikolas et al.. 2021) problem and propose Zo extragradient method to solve it. The word "extra' refers to the extra oracle evaluation needed in each iteration compared to ZO gradient descent ascent. It is shown that our analysis is also applicable to non-differentiable min-max problems, with a convergence guarantee to a Goldstein stationary point.
1.1 Contributions
In this paper, we study the possibly nonconvex-nonconne deterministic min-max problem of the form
min max f(x, y), #ex xey
(1)
where f: R" x RT + R is an integrable objective function. The sets X' C R" and y C R" are assumed to be nonemply, closed, and convex. To solve the problem, we propose a 70 extragradient algorithm based on Gaussian smoothing. While it is common in the ZO optimisation literature based on Gaussian smoothing to sample random directions from the standard normal distribution NN I), in this work, we consider a more general setting introduced in (Nesterov & Spokoiny| 2017 Section 1.3) where symmetric and positive definite matrix B = B" > 0 is used to define random directions sampled from \/ B-)). The performance of the algorithm in both the unconstrained and the constrained setting is analysed. For the unconstrained setting, by assuming the existence of a solution satisfying the weak MVI (introduced in Definition 10p. we prove the convergence of the algorithm to a neighbourhood of the e-stationary point of f (whose size depends on the variance), in at most O(e iterations and function evaluations. For the constrained setting, by assuming the existence of solution satisfying the prozimal weak MVI (defined in
In Nesterov & Spokoiny 2017), allowed be complex valued and thus the Hermitian matrix B is used instead of the transpose B Here, we restrict our attention vell-valued matrices.
2

---

Published in Transactions on Machine Learning Research (09/2025)
show that the algorithm converges to neighbourhood of the e-stationary point of (whose size again depends on the variance), in at most ((=-2) iterations and function evaluations. The size of the neighbourhood of convergence in both settings can be controlled using variance-reduucion techniques in the ZO random oracle. In particular, by employing the variance reduction technique described in Algorithm 2 we establish the convergence of the algorithm to an e-stalionary point of f in the unconstrained set ting within O((-2) iterations and requiring ((c-1) function evaluations. For the constrained setting, we demonstrate convergence to an e-stationary point of f in O(e-2) iterations, with O function evaluations.
Definition
While most of the prior works assume the differentiability of the objective function of the min-max problem, we show that the assumption can be removed by considering a Gaussian smoothed objective function instead. Assuming the existence of a weak MVI solution for a Gaussian smoothed function fn of f, we show that the algorithm converges to a variance dependent neighbourhood of the e-stationary point of fo in at most 3 iterations and function evaluations, implying convergence to an e-Goldstein stationary point of f (defined in Definition 7 Gaussian smoothing of a function discussed in (10p. As in the smooth sctting, using the variance reduction technique in Algorithm 2 we show the convergence of the algorithm to an e-stationary point of fu and an e-Goldstein stationary point of f in ())=)) iterations and OEe=t) function evaluations. Note that in our work, across all considered settings, the bounds on the number of itcrations do not explicitly depend on the problem dimension.
1.2 Related work
ZO min-max optimisation: ZO methods provide a key for solving a host of min-max optimisation problems in which gradient information is not accessible; see, c.g., (Chen et al.] 2017 Wang et al. 2021:
Snock al., 2012 Salimans et al. 2017; Moosavi-Dezfooli et al. 2019). A vast majority of existing literature 70 min-max optimisation focuses on solving convex-concave or convex-nonconcave min-max problems. For example, Wang et al. (2023) addresses the deterministic and stochastic nonconvex-strong max optimisation problem with constraints only on the maximiser. The authors solve the deterministic optimisation problem using 70 gradient descent ascent and ZO gradient descent multi-slep ascent mods both sampled from Gaussian random oracles, and in the deterministic case, prove the convergence of their methods to an e-stationary point in (de--)) and in Odd ")) -2) iterations (d is the problem dimension), respectively. Liu al. (2020) considers the constrained nonconvex-strongly concave min-max problem and solves it using 70 projected gradient descent ascent method with uniform sampling vectors. The method is shown to converge to ncighbourhood of an c-stationary point in O(c-²) iterations.
concave min-
ZO methods are also developed for stochastic min-max optimisation problems with similar problem struc- tures. Xu et al. (2020) proposes a Zo variance-reduced gradient descent ascent method based on Gaussian sampling vectors for solving the (deterministic or stochastic) unconstrained differentiable nonconvex-strongly concave min-max optimisation problems. The algorithmi is proved to converge to an e-slationary point. of the objective function in (de--)) iterations. Later, Huang et al. (2022) developed an accelerated ZO momentum descent ascent method based on uniform smoothing estimators for solving stochastic nonconvex-strongly concave min-max optimisation problems, which has been shown to converge to an e-stationary point in O(BMe iterations.
To the best of our knowledge, the only existing works on Zo NC-NC min-max optimisation are (Xu et al., 2023) and (Anagnostidis et al.] 2021]. In (Xu et al.) 2023 the authors study min-max problems for stochastic and deterministic unconstrained differentiable nonconvez- Polyyakkee-PPlaak--- Lajjsiuun- min-max problems using a uniform smoothing random oracle. The authors prove convergence of their approach to an e-stationary point. The authors use ZO alternating gradient descent ascent and ZO variance-reduced alternating gradient descent ascent algorithms and, respectively, in the deterministic case, prove convergence of their approaches to an e-stationary point in (de-2) and O(d2c=2 iterations. The authors in (Anagnostidis et al., (202)) consider stochastic unconstrained differentiable nonconvex- Portooooe-Pooyak---ee use the direct-search method and prove the convergence of their approaches to an e-stationary point in Ollg((-')c itcrations. In this work, we study the class of NC-NC min-max problems for which there exists solution satisfying the weak MVI, which has been shown to be satisfied for large class of functions including all min-max problems with objectives that are bilinear, paeudo-convex-connave, quasi-convex-
min-max problems. They
3

---

Published in Transactions on Machine Learning Research (09/2025)
concave, and star-convex-concave (Diakonikolas et al. 2021p, and all unconstrained variationally coherent
problems studied in, e.g-. Mertikopoulos et. al. (0019) and Zhou et al. (2017).
Variational inequalities: Finding solutions to VIs is equivalent to finding a first-order Nash equilibrium of the min-max problem (Facchinei 2003 Song el al. 2020). In particular, a VT with monotone operator, which has been well investigated, provides a framework in studying convex-concave min-max problems (Ne- mirovski 2004]. Rescarchers have spent efforts in reducing the assumption
the monotonicity of the operator, so to include larger class of applicable functions. Dang & Lan (2015) focuses on class of VT problems, referred to as generalised monotone VI problems, that covers both monotone and pseudo- monotone VI problems. Their work discusses a generalised non-Euclidean extragradient method and proves its convergence in O(e iterations. [Song et al. (2020) uses an optimistic dual extrapolation algorithm and proves its convergence to a strong solution in ( iterations when the existence of a weak solution is assumed.
Diakonikolas et al. (022 introduces class of problems with weak MVI solutions to solve the smooth un- constrained NC-NC min-max problem, which is a weaker assumption than the existence of a weak solution to the VI problem. The assumption is shown to be satisfied by quasiconvex-concavy or starconvex-concav
(x.()
min-max problems, and the problems for which the operator F(x,)) v) = Vy flz.y)
negatively comono-
tone (Bauschke et al.) 2021) or positively colypomonotone (Combettes & Pennanen 2004). The authors proposed an extragradient algorithm in an unconstrained sctup and proved its convergence to an e-stationary point in 3) iterations. Later, Pethick et al. (2023) addresses the constrained NC-NC min-max problem. The paper assumes the existence of solution to the weak MVT with less restricted parameter range and proposes a new extragradient-tyyn algorithm with fixed and adaptive step sizes. The algorithm is proved to converge to a fixed point in Oce-²) iterations.
To our knowledge, no previous work has considered solving the min-max problem that satisfies the weak MVI using ZO random oracles.
Non-differentiable min-max optimisation: Gradient information is needed when studying first-order min-max optimisation problems, hence non-differentiable min-max optimisation has barely been discussed in the literature. However, because a Gaussian smoothed function always has a Lipschitz continuous gradient as long as the function is itself Lipschitz (Nesterov & Spokoiny 2017), it hints that ZO smoothing met may provide a tool to circumvent the computational difficulty caused by the non-differentiabiliy of the objective convex-concawe
function. Indeed, Gu & Xu (2024) considers a non-differentiable convex-concave problem and approximates the gradient by taking the average of finite differences of random points in neighbourhood of the iterate with uniformly sampled vectors. It is proved that the algorithm converges to an 6-optimal point in (de- iterations. Qiu et al. (2023) considers a non-differentiable nonconvex-strongly concave federated optimisation problem. The authors use a ZO federated averaging algorithm based on sampling from a unit. ball and prove the convergence to an e-stationary point of the uniformly smoothed function in Odde iterations.
Goldstein subdifferential in ZO optimisation: The Goldstein subdifferential (defined in Definition G has been used in studying the stationarity of a non-differentiable function (Goldstein 1977) Lin et al 2022 shows that the gradient of a uniformly smoothed function is an clement of the Goldstein subdifferential. The authors then proposed a gradient-free method for solving non-smooth nonconvex minimisation problems and proved its convergence to a (f,e) Golldsteinn stationary point at a rate of (0(3/25-1e- where d is the problem dimension. Similar convergence results of ZO uniform smoothing methods to a Goldstein stationary point can also be found in the non-smooth nonconvex minimisation literature [Kornowski & Shamir, 2024 Rando et al. 2024). Concurrently, Lei et al. (004)) studies the convergence of a Z0 Gaussian smoothing method for class of locally Lipschitz functions called sub-differentially polynomially bounded functions. It is shown that the gradient of the Gaussian smoothed function lies in neighbourhood of Goldstein subdifferential. These results allow us to quantify the stationarity of a solution in non-iifferentiable min-max problem.
Outline:
The paper is organised as follows. Preliminarics and the proposed framework are introduced in Section 2 In Section g the main convergence and complexity results related to the proposed algorithm are presented for different settings. Section offers illustrative examples. Lastly, we conclude our paper and
4

---

Published in Transactions on Machine Learning Research (09/2025)
discuss potential future research directions in Section 5 and complementary material can be found in the appendix.
Auxiliary lemmas, proofs of the main theorems,
Notation: For symmetric positive definite real matrices B = = = > 0, B2 B2 > 0, B1 R=*", B2 E Rmxm and B P B, we define nr, m- and d-dimensional normed spaces
X = (R", | (a,, b,,
Y = (R.", |yll (y, B2y) ), and Z (R. ||=||| = (z, B2)²);
(2)
where d = n m, respectively. The dual spaces of X, Y, and are denoted by X", Y", and Z", respectively, For all 2 Z', the dual norm denoted by || (2, B-1 2)², i... Z (R", -|=||l (z, B 2) Additionally, for the space Z, we use the weighted norm
def |= (z, B=) = (2, =)
which reduces to the standard Euclidean norm in RR" and specialises to the absolute value of a real number in the scalar case.
The smallest eigenvalue, the largest eigenvalue, and the condition number of the positive definite matrix B > 0 are denoted by X, X, and k I respectively, and it holds that
2|=|² < ||=|| s x|=|? X | S || = 11/
(4)
(5)
The ceiling function is denoted by [.1, i.e. for E R, 2 0, [-] min(N N/n 2 x}. The projection operator onto closed convex set Z Z, is defined
(r)jz(3) def
arg mugmin E|| SE2
(6)
The convex hull of set of points S C Z is denoted by cSnv(S). Let Bs(2) be the closed ball in Z with centre and radius 8. The expectation operator with respect to a random variable u is denoted by F.(t). For k E N, E Z, we denote by Ui: = (u1...., mx) a set comprising of independent and identically distributed random vectors. The conditional expectation over Us is denoted by E.,, The identity matrix of appropriate dimension is denoted by The diameter of set Zc Z is denoted by D3 and is equal to sup(lla1 22ll
21, 22 E 2). The Minkowski sum of two sets A, BcZ is denoted by A + (a b b A, be B).
2 Preliminaries, Problem of Interest, and Algorithm
In this section, we provide the preliminaries for different classes of functions used in this paper. Moreover, the definitions for e-stationary points, generalised gradients, and (6, coooddsen stationary points are given. We define different classes of VIs and explain how they are related to min-max problems. Finally, definitions related to Gaussian smoothing ZO oracles are provided, and the main algorithum discussed in this paper is introduced.
2.1 Preliminaries and Problem of Interest
For simplicity of notation, we use the definitions d = n + m E N, 2 X' yC (X C X, ) C Y and Z = X x Y), and = (I,y) to write f(z) = f(z,v) y) in cases where the properties of function f in are important but the individual components x and are not.
Regularity of the objective function in 11 essential for optimisation algorithms to have convergence guarantees (Nestervv al.] 2018). The Lipschitz continuity, defined below, is the first of such conditions. We introduce other necessary properties later in this section.
5

---

Published in Transactions on Machine Learning Research (09/2025)
Definition 1 (Lipschitz continuity). Let f: Z - R be continuous function. Then, f is said to be globally Lipschilz if there evists Lipschitz constant Lo((f) >> O such that
- S Lo(f)]lz1 22
A 21, 22 E Z.
If there erists a positive å where the above inequality is satisfied for any 21 Z and z2 where || - 8, then f is said to be locally Lipschitz.
Moreover, if f is continnoushy differentiable function, then the gradient of is said to be globally Lipschitz if there erists a Lipschitz constant (f() > such that
[V]((z)) - f=2))l - L(flla 22
V 21, 22 Z.
Finding the global minimum of nonconvex optimisation problem, if it exists, is NP-hard Nemirovski & Yudin 1983) and it is known that finding global saddle point (or Nash equilibrium) of an NC-NC function f is in general intractable (Murty & Kabadi 1987p. Thus, in this paper, instead of finding the saddle points of 1 we mainly focus on finding stationary points of f as described in the following problem statement. Problem 1. Consider a function f Z + along with a nonemply closed convex set C X x.. Find the stationary points of f-
In what follows, we discuss various ways of characterising the stationary points of a function under different smoothness conditions.
We start by defining the stationary points of continuously differentiable functions. Definition 2 (Stationary points). For a continuously differentiable function f, 20 E is a stationary point o if (z() = 0.
Similarly, under the same assumptions on f, one define c-stationary points through the condition [[Vf(z))]|- < for e 2 O. A general definition of e-stationary points is presented below.
Definition 3 (e-stationary points (Liu et al. 2024)). Let f X' x y + IR be a continuously differentiable function, where & C X and y C are nonempty closed convex sets and let h and h2 denote positive constants. Then, a point (ro, vo) E X y is an e-slationary point of f if [| vo)ll= S e, where
def hy (#o Proix - hy V V {o)))
TF0, vo)
(yo (vo + h22 V f f {o)))
Recall that the projection operator (-)jx(-) is defined in 6 in the notation section. We can further extend the definition of stationary points for the case where is not necessarily continuously diffcrentiable, termed (6, e)-Goldstein stationary points. To this aim, we first need to define generalised directional derivatives and generalised gradients (Clarke 1975
Definition 4 (Generalised directional derivative). Let f: Z be a locally Lipschitz continuous function. Given a point z e Z and a direction u E Z, the generalised directional derivative of function f is given by lim ? (f(2' + tv) f(z))). The generalised gradient of f defined as the set シー 130
(z) def
af(z) def Eg E Z: () S (2;00) Ve E E).
Rademacher's theorem guarantees that any Lipschitz continuous function is differentiable almost everywhere (that is, non-differentiable points are of Lebesgue measure zero) (Evans) 2018 Hence, for any Lipschitz continuous function f, there is simple way to represent the generalised gradient 0f(=),
0f(z) conv conv (f0E E Z Z:
lim (f(z)) Vf(zz) exists }): 2k
g
which is the convex hull of all limit points of f over all sequences (zR)ReN such that 23 -> for - oc and fz(x)) exists for all & N (Lin al. 2022). Given the definition of generalised gradients, as a next step towards (ō, GGoldsten stationary points, need to consider Clarke stationary points (Clarke) 1990).

---

Published in Transactions on Machine Learning Research (09/2025)
Definition 5 (Clarke stationary point). Given locally Lipschitz continuous function f Z R, Clarke stalionary point of f is point E Z salisfying 0 E 0f(=). A point. E Z is an e-Clarke stalionary point if min : g
0f(z)) e.
In Zhang et al. 20200) it is shown that c-Clarke stationary points of a nonsmooth nonconvex function with fixed E (0, 1] can not be found by any finite-time optimisation algorithm in general. This leads to the definitions of 8- G-Goldstein subdifferentials and (6, e)-Golsstnin stationary points.
Definition 6 (&-Goldstein subdifferential (Ln et al. 2022)): Given a point 2 E Z and ó 2 0, the d-
def
Goldstein subdifferential of Lipschitz continuous function f Z + R at is given by 0sf(z)
conv (UZEBAC)) 0f(z)))
The Goldstein subdifferential of at is the convex hull of the unions of all generalised gradients at points in 5-ball around 2. Accordingly, the (ô,c)-Goldstein stationary points are defined below. Definition ((ô, Goooddtein stationary point). point & E is a (6,c) (ó.e)-Goldstein stationary point of Lipschitz continuous function f Z if min Igll. 9 0zf(=)) c.
Note that (6, Goldsten stationary points c-Clarke stationary point is a (6, -oooosstenn stationary point, but not vice versa. In Zhang et al. (2020), it is shown that the converse holds under the assumption of continuous differentiability and lims fz)(z) = (=). Finding (o.c)-Goldstein stationary point in nonsmooth nonconvex optimisation has been shown to tractable TTan et al. 2022).
weaker notion than e-Clarke stationary points because any
As next step, we introduce variational inequalities. In particular, instead of solving (1) directly, we find points satisfying these variational incqualities for different operators, which under appropriate continuity assumptions, characterise stationary points of f in the presence of Z and consequently solutions to Problem 1
For example, for the case where f is continuously differentiable, the gradient operator of f is defined as
F(z) def V (x, - V (zf(z,))
Then, point 2" satisfying Definition below is stationary point of f.
Definition 8 (Stampacchia variational inequality (Diakonikolas et al. 2021)). ). Consider a closed and conver set C and an operator F: Z z" Then, we say that 2" E satisfies the Stampacchia Variational Inequality (SVI) if
(F(*"), 2²) 0,
holds for all 2.
The SVI is in general difficult to verify. Thus, related and computationally more tractable Minty variational inequality can be used.
Definition 9 (Minty variational inequality (Diakonikolas et al. 2021 ). Consider a closed and conver set C Z and an operator F + Zz Then, we say that x" E satisfies the Minty Variational Inequality (MVI) if
(F(z), =²) 0,
holds for all Z.
If F is monotone, then every solution to SVT is also a solution to MVT, and the two sets of solutions are equivalent. If F' is not monotone, all that can be said is that the set of MVI solutions is a subset of the set of SVI solutions [Kiderrechrer & Stampacchia] 2000). Instead of Definition we will consider a generalisation of MVIs, as discussed in Diakonikolas et al. (2021).
Definition 10 (Weak Minty variational inequality (Diakonikolas et al.
2021 ) Consider a closed and conver
set Z C Z and a Lipschitz operator F Z Z' with Lipschitz constant L 0. Then, say that z E Z satisfies the weak Minty variational inequality if, for some E [0, s
( x3) +
(9)

---

Published in Transactions on Machine Learning Research (09/2025)
holds for all 2, and where denotes the condition number of B defined in
Note that Definition I0 is generalisation of Definition 9 and reduces Definition for p For more details, see (Diakonikolas al. 2021 Section 2.2).
2.2 The Zeroth-Order Extragradient Algorithm & Gaussian Smoothing
In this paper, the objective function in (1) is not necessarily continuously differentiable, or, if f is contin- nously differentiable, its gradient is not necessarily accessible for computations. For this sake, we will use a function approximation known as Gaussian smoothing (Nesterov & Spokoiny 2017). Such approximation is continuously differentiable as long as f is integrable. Namely, for a parameter > 0, the Gaussian smoothed version of an integrable function f: Z + IR, defined as fp Z R,
fz(2) def - [f(( puje +|llll du, where & def f + +|ll du [det. BJ 1
(2T)4/2
(10)
2
Here, E Z is sampled from Gaussian distribution B-1) In Nesterov & Spokoiny 2017 Section 2), it is shown that for all μ 0 and under the assumption that f is integrable, then fp is contimuously differentiable. If is additionally assumed to be globally Lipschitz continuous, then La is globally Lipschitz continuous with the same Lipschitz constant. The same conclusion can be made with respect to the gradient of the functions f and fp.
To approximate the gradient of a function f (for points where the gradient is defined), we define the random oracle 9μ Z + Z" as (Nesterov & Spokoiny 2017 Section 3)
(a(=)= = (u(2; B) def f(z + pm) - f(z) Bu,
(11)
where u E Z and B are as defined in 12 It is shown in Nesterov & Spokoiny (017)) that 9a is an unbiased
estimator of fpp i.e., fz(=)) E. (z)]. The oracle 9μ allows to approximate fz only with function evaluations of the function f-
In our proposed framework, we use the simultaneous smoothing for both x and using a pre-specified smoothing parameter μ > 0, but with independent random vectors U1 ú1 E X and u2 02 E Y sampled from (00 2) and (0, B57). To simplify the notation, we define
21
def û i2
B 0
0 B₂
à
and B
(12)
U2
The common choice of B defined in 12 is the identity matrix B I, but we will state the main results Now that all preliminary definitions have been detailed, we are able state the zeroth-order extragradient algorithm, shown in Algorithm 1
Section 3 for the general choice of = B T >
Algorithm Zeroth-Order Extragradient (70-EG)
Input: 2n (zo. Vo) E N; e N; (h1 (h2, 1N Rypip 0; B, B 0; Bg B
for k == .....,N do
Sample ûτ and fzz from (0, B and NO BT
4: Calculate (= using u = 0x. 14 and 13
5: Compute & = Projz h (z))
6: Sample 41,6 and u2,2 from (0, B and (O, B
7: Calculate (x using u = us. 14 and 13
Compute Ek+1 Projz(2x G2,.).
end for
10: return 21,...;EN

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm |
relies on the evaluation of the oracle
Gz(()) def Ju,z (2)
(13)
where
guæl2) dof f(z pu) f(z)
Blui and guv(z) def f(2 pui) f(z)
Bru2.
(14)
If we define
(=) def V=.n(=)) (zfu(z)
and {(z) def Gn(z) - F2(();
(15)
2017 Section 3), it is known that EulE(=)] 0 for all Z, Gz(2) is unbiased estimator of F F2),), i.c., with only the evaluations of f, we can obtain an unbiased estimation of Fy.- We later use this identity to prove the convergence to a point z for which [F(=) < e satisfied.
then from (Neterrvv & Spokoiny
Algorithm 1 Eo denotes the initial guess of a stationary point of ( p > 0 is the smoothing parameter 14 N E denotes the number of iterations, and h1, and h2 denote positive step sizes for kEW (0, ........ Nj. The projection sleps are only necessary in the constrained case to ensure leasibility, i.e., to ensure that 2 E Z for all & (I.....N..
in 13
Algorithm 1 ensures convergence to variance-dependent neighbourhood of the e-stationary point as shown in the subsequent sections under various assumptions. To reduce the size of the variance-dependent neigh- bourhood, a variance reduction scheme can be used. Here we use the scheme as outlined in Algorithm 2 which can be found in Balasubramanian & Ghadimi (2022), for example. In Algorithm [ each iteration instead of sampling one to calculate the corresponding Gμ, defined in 13
we sample tx directions, then
Algorithm | changes to Algorithm 2
Algorithm 2 Variance-Reduced ZO-EG
1: Input: 2g (00,2/0) E N E N; (h { R / > 0; B BJ > 0; B2 = B > 0:
[tx] C
for k= 0,..., N do
Sample "i...... 0it and 02 "2 dii from NO (T, and (o, B,"
Calculate G (zx), G (zx) using w² it. i == ......4. Lk 14 and
Compute (= ty Ele (*)())
Compute 2 Projz h (k)))())))
Sample u "I' and wy u2, 2 from W0, B and NO0 B,
and Calculate (Ex), ... (2x) using u² ur. i 0, O,.... Lk.
Compute (dx) to 1 (4x)
10:
Compute =++1 = (rojz (3x))
11: end for
12:
return 21,...,
Leveraging this technique the upper bound on the variance of the random oracle will be divided by the number of sampled directions.
Having the stage set up, in the next section, we present the main results. In particular, we analyse the convergence and itcration complexity of Algorithm for three different cases.
3 Main Results
In this section, we analyse the convergence and iteration complexity of Algorithm for nonconcave min-max problems. Specifically, Section 3.1 examines the scenario where f is continuously
for possibly nonconvex-

---

Published in Transactions on Machine Learning Research (09/2025)
differentiable and 2 Z. In Section 3.2 extend the analysis to the case where f is continuously
differentiable but 2 + z in Problem Finally, Section 3.3 focuses the case where 2 = Z and is
non-differentiable. Detailed proofs of the lemmas and theorems are provided in Appendices A and
3.1 Unconstrained Differentiable Problem
In this subsection, we consider the unconstrained version 1 that corresponds to Problem 1 with 2 = Z. Let us start with the following standard assumption on the variance of the 20 random oracle in the literature of Zo and stochastic optimisation; see, e.g., Maass et al. (2021): Liu et al. 2020 Xu et al. (2020).
Assumption 1. For a fixed μ > 0, the variance of the random oracle Gz(z) defined in by d² 0, i.e.
13 is upper bounded
- Fa(2)1 oo V2 E
(16)
We assume that Assumption |
satisfied throughout the paper. Indeed, a simple calculation shows that
- -
E,, F., [| (=) [=)
(=) (=)
= -
- (=)ll,,
(17)
where the first equality follows from expanding the norm, and the second equality holds since E. [x,]
(=). It is shown that (=)III (d 4)² for Lipschitz continuous function f with Lipschitz constant Lo(s) and E. (+)] I & (d + 6)s + 2(d + F)) for a function f with Lipschitz continuous gradient with constant L1(f) (Nesterov & Spokoiny 2017 Theorem 4). Hence, Assumption i not a stringent assumption, particularly when Lipschitz continuous or when f has Lipschitz gradients.
Remark 1. Leveraging the variance reduction techniquee Algorithm 16 of the rondom oracle is
2
the upper bound on the variance in
o²
Fullll,,(ER) FF((x))13]
tx
Thus, by increasing the number of samples tk, the bound variance decreases. Additionally, note that this variance reduction scheme preserves the property (z[Gp(=x)] (z()).
Next, we need to make an assumption about the existence of solution for the weak MVI in Definition Assumption 2. For Problem with Z = Z, there exists z" E Z such that F(z) defined in satissies the weak MVI defined in (9.
Now, we need to analyse the behaviour of F2 defined in 15 when Assumption 2 is satisfied. The following lemma presents the properties of F2, when Assumption 2 is satisfied.
Lemma 1. Let f: Z + R be continuously differentiable with Lipschitz continuous gradient with constant
Li(f) O. Moreover, let Fu be the operotor defined in 15) with smoothing parameter P 0, and let p denote the weak MVI parameter defined in Definition satisfied, then it holds that
10
If there erists 2" Z such that Assumption is
(Fa(z), +²) +1E ( p L(1)(d 33 2 E
(18)
A proof of Lemma I can be found in Appendix Using Lemma can present the main theorem of this subscction. This thcorem introduces an upper bound for the average of the expected value of the square norm of the gradient operator of the sedothed function in the sequence generated by Algorithm [
Theorem 1. Let f: Z + R be continuously differentiable with Lipschitz conlinuous gradients with con- stant
L (f) > Let o² be an upper bound on the variance of the random oracle defined in Assump- N 2 be the number of iterations, Fμ. be defined in (15) with smoothing parameter p. > O, (ug. (uz, (ur.ar)..... âz).... (ug, dz],, le (O.....N) and p denotes the weak MVI parameter in Defini-
tion
U4
tion
10 Moreover, let {zk 3200 and (ix]x20 be the sequences generated by Algorithm 1 lines and 8,
10

---

Published in Transactions on Machine Learning Research (09/2025)
respectively, suppose that Assumption the largest eigenwalue X and the condilion number of the posilive definite matrix B defined in 2 Then, for any iteration N, with
2 is satisfied, and recall the definitions of the smollest eigenvalue À.
1 and 12. = h2 E (V (f)
2p
h1
h1.k = h LT(s)K
(19)
2
we have
1
2 - -2112
2p A1)d
Fan [
+
N +
(AALI (f) - -N (f)xk) - 2p)
(20)
+ 2p (f)
320²
+
(AALI (f) - 2p)
LI(D)(AAAL -2p)
A proof of Theorem can be found in Appendix B Given the upper bound provided by Theorem the
first. right-hand side term of (20) becomes arbitrarily small for N - co. The second term, in turns, can become arbitrarily small if - O. The last term depends on the variance of the random oracle, defined in Assumption which becomes arbitrarily small by using a variance reduction scheme, see Algorithm and
Remark !
In Theorem the positive definite matrix B defines degree of freedom, whose cigenvalues and condition number have significant impact on the step size selection in (19) and on the upper bound in (20). An optimal selection of B in terms of (19 and 20 is out of the scope of this paper. Nevertheless, a discussion based on heuristic arguments is added in Appendix C.1 indicating that an optimal selection of B in Theorem [
implics B to have a condition mumber x = (but does not necessarily need to be the identity matrix). Building on the discussion in Appendix C.T the following corollary restates the result of Theorem | for the special case where B is a scalar multiple of the identity matrix. In this setting, the random directions up and ûz in Algorithm [ are sampled from (0, XI) for some X > 0.
Corollary 1. Let the assumptions of Theorem 1 be satisfied with B = AI for A 0. Then, it holds that
1
2 - 2012
2n²2 {L)dd
Eug (166))) < (A -P)
N
(1)T(())3)) 2p)
k=0
2μ 2 (f
3
(APL)(F)22- 2p))
(f)) 2p)
The proof of Corollary is the same as the proof of Theorem with A X = X and K = 1. The next corollary gives a guideline on how to choose the number of iterations and the smoothing parameter μ4, for a given specific measure of performance and for diagonal matrices B >
Corollary 2. Let the assumptions of Theorem 7 be satésfied with B = AI for X 0 and let ro 1|:0 2*1 For given 0, if
5 (1)1) 2p)) ( (XL7(f)p(d+ + 3)3) ) ) <and and N2
(12228/710 -2p))pp))) )02-)
then,
N Σ Ea (1F (XPIR()) -pTr K=
320²
A proof of Corollary 2 can be found in Appendix B Considering Definition 3 to show that the sequence generated by Algorithm converges to an e-stationary point, [[(())) needs to be bounded, Based on
Theorem annd Corollary the following corollary introduces an upper bound of the average of the expected value of the squared norm of the gradient operator F, defined in 8 over the sequence generated by A Algorithm
11

---

Published in Transactions on Machine Learning Research (09/2025)
Corollary 3. Let the assumptions of Theorem 1 be satisfied with B = AI for A 0 and let
( - 2p
1 } and N2
( c=--1 (XPL1(F)13 -2p)
/ U.min min
(22L 3)
(f) 16AL
Then, it holds that
N N Σ k=0
Gλ s (X1120013322p1(10)
Bu. (P()))
- 2pT,(
The proof of the Corollary can be found in Appendix In light of Corollary can be seen that the soquence generated by Algorithm D guaranteed to converge to neighbourhood of the e-stationary points of f in expectation. Additionally, the size of the neighbourhood can be made arbitrarily small using the variance reduction scheme in Algorithm 2 The next theorem introduces upper bound for the average of the expected value of the square norm of the gradient operator of the smoothed function in the sequence generated by Algorithm 2
Theorem 2. Let f: Z - R be continuously differentiable with Lipschitz continuous gradients with constant (J) > O. Let x² be an upper bound on the variance of the random oracle defined in Assumption 1 N 2 be the number of iterations, tN E N be the number of samples
each iteration of Algorithm 2 Fp be defined in 15 with smoothing porameter μs > 0, U4, [uuo uo), (w1, (l)..... .uu,, ūx)), k E (O....,Ny M,, and p denotes the weak MVI parameter in Defonition 10 Moreover, let {zk [=20 and {āx) be the sequences generaled by
A Algorithm lines 6 and 10, respectively, and suppose that Assumption 2 is satisfied. Then, for any iteration
N, with
(V
2p h1 (I
11,k = h1 S Liff)Te
and h2 = 122 E
2
we have
2T)L - =2012 + 21 2 3)3
Eu, (2W)
N N+1
(fALI(f)nh, +1) (f) - 2p) (f) -2p)
3do²
1
(21)
(F)) 2p) (N+1)
4
k=
A proof of Theorem 2 can be found in Appendix
B As in the case of Theorem 1 a discussion on the selection of B can be found in Appendix C.1 The next corollary gives guideline on how to choose the number of iterations and the smoothing parameter μe, for given specific mcasure of performance to guarantee convergence to an e-stationary point of the objective function.
Corollary 4. Let the assumptions of Theorem 2
be satisfied with B AI for À 0. Moreover, let
4 =t
18
c2
N2
c 2-1 and
(F) - 2p))
(X2L
-2p
(L) - 2p
p. S min
(A +3)
(2ALL p(d 3)3 g
Then, it holds that
N N+1
Σ Eu 12
A proof of the Corollary 1 can be found in Appendix Based on Corollaries and 4 and under appro-
priate parameter selection, we observe the following: employing Algorithm 1 guarantees convergence to
12

---

Published in Transactions on Machine Learning Research (09/2025)
neighbourhood-wee whose size depends the variance of the stochastic oracle- of e-stationary point of the objective function, within O) iterations and () function evaluations. In contrast, utilising Algo- rithm 2 convergence to an actual e-stationary point (rather than a variance-dependent neighbourhood) is guaranteod in O(e-2) iterations and O(e 4) function evaluations.
Remark 2. In Algorithm if we set B = AI (with À > 0) and ts - 1, then from
21 we get
1 N Σ N +
(f) 2012
22Lx pdd 3)3 (f)L) - 2p) n²
(F
(f) - 2PV +1)
(In(N + +1) + 1)320²
(N (f) (f))
Thus, to ohtoin N+I 2k=0 (
(22 (PLL( 2p) +18e
( + c- - ---
11} /
-1 BE - 1n(36~)-11
N M max
is required and where 3 (X6214(1)2 (p and c S Hence, compared to Corollary 4 the dependency
9Aa²
of the number of iterations 6 changes and total of 2(N + 1)NN +22 function evaluations are required.
In cases where specific properties of the objective function (such as Lipschitz constant Li()) of the gradient corresponding to the weak MVT) are unknown or can only be approximated, can be chosen independently of the objective function's propert ies. The following remark provides a guideline for selecting and N to achieve a performance comparable to that of Corollary 2 in the case that j is independent of the function's properties.
Remark 3. Theorem I' 's analysis can be repeated for the case where the smoothing parameter i is iteration- dependent and satisfies μa K+I, for some positive scalar For this cose, under the additional assumption that B I, 200 becomes
1 N+1
-1 =111 L( 120)(d43)))+3 (Ir(f)h² - -2p)(N (L)()) 2p)
1272
Fa Fo (8))133 (a)))
6(N+1 + 1)
K=0
(22)
302
(L(()) 2pL,(f))
Then, for a given tolerance e > 0,
2L((frr (Tr(f) 2p) (T2(T) 2p) 6
+ LI(0d+ +2())++(()(3+3)))) Px2
-1
1.
N>
-2
we have
N N+1 E Fan (BW)I S 5² (RRS) (f),
30
As can be seen, i is selected independently of d, then the number of sterations to achieve tolerance of e is of order Odd'e=)). However, it is possible to reduce the power of d in the complecity order by choosing appropriately. For example, if 3, the number of iterations to achieve a tolerance of E is of order O(de For the sake of comparison, in Anaguostádis et al. (2027), the authors exlended the direct search algorithm of Vicente (2013) and analysed the unconstruined döfferentiable NC-PL mån-max problem and showed that the complerity order of the direct search algorithm for computing an e-slationary point is -f -oog(E -1)).
3.2 Constrained Differentiable Problem
Here, we study the performance of Algorithm for solving the constrained version of Problem | where Z Z is convex compact set with D2 as its diameter. To ensure that the iterates stay in the constraint
13

---

Published in Transactions on Machine Learning Research (09/2025)
set, projection steps needed. In this case, Problem 1 with f as its objective function and Z its constraint set, can be reformulated as an unconstrained problem with T(z) as its objective function, where
I(z) def f(z) +I(=)) and Iz(=) def Ix(x) - II(()) with Iz(z) def 0
2 2, (23)
00 2 2
2.
It is easy to see that r Z we can not use Definitions and 10 with the gradient of r. To proceed and to analyse stationary points of f in the sense of Definition we define operator Qe as follows:
R [o0} is not differentiable and its gradient is not defined everywhere. Thus,
Qr(z,a,F(3) (Poo aF())) =),
1 (Prox((==
E 2.
(24)
Here, a is a positive scalar and (2) def min =||² + {{2)) for a proper and lower semicontinuous
function
For the instances where Ig and Prox, Projz: we recover defined in Definition Next, we define the proximal (weak) Minty variational inequality, analogous to Definitions g and 10 for the analysis of Algorithm I in the constrained case.
Definition 11 (Proximal (weak) Minty variational inequality). Consider a closed and convex set Z C Z, Lipschitz operator F' Z + Z with Lipschitz constant L > 0, and a possibly non-differentiabbe conver function Then z" E Z is said to satisfy the proximal Minty variational inequality if
(Q)(z,,,F())), z²) 20,
(25)
holds for all 2, E E. Moreover, z" E Z is soid to satisfy the prozimal weak Minty variational inequality if
(Qllz,aFF())) - =") ) + (11e((z,a, +"11)))=====+00000
0, De [0, 247.
(26)
holds for all 2,2 E 3, where operator Qe is defined in 24 and denotes the condition number of B.
By comparing Definition I1 with Definitions 9 and 10 it follows that, if function é is constant or 2 = (as
noted in Remark 7 the proximal (weak) MVI simplifies to the (weak) MVI.
We now discuss examples of functions satisfying the proximal MVI defined in 25 Consider f(x,y) v) ry with 2 = (= (x,v) x 2 0, 2 0} and é = Iz, then ʃ satisfies the proximal MVI definition with z¹ = (0, Similarly, the functions v) xny" (n, > 0) with 2 = {= (I, x 2 0, 2 0} and L = Iz satisfy the definition of proximal MVI with 2" = (0,0). More generally, it can be shown that f(x, v) = Ay + cTr + d where I.C E R", y. e R",". A E R"x" with nonnegative A, 2 == (= () 2 0, 2 0} and t= Iz meets the definition of the proximal MVT (25) with = (0,0).
Before proceeding further, we define the following auxiliary function
Pz(2, g())) def Projz(= hg(;))),
(27)
where h is positive scalar. We note that when é is the indicator function, then h2(2,h,9(3) Qe(z, gZ)). Moreover, let F, Gy., and Fa be defined in 18) 13 and (5). Also, let 2h, 2x, hi,k: and 12,4 be adopted from Algorithm I Then we can define below auxiliary variables:
del b1, Gu(zz)),
SR def (zz(z,, 12, Gy((a)).
8k
(28)
Hence, using above auxiliary variables in the constrained case of Problem 5 and 8 in Algorithm [ can be written
1 then the update steps in lines
h2 and - 24 h1,48k-
(29)
To proceed, we need to make an assumption about the existence of solution for the proximal weak MVI in Definition 11
14

---

Published in Transactions on Machine Learning Research (09/2025)
Assumption 3. For Problem 1 with 2 C Z, compact and convex, and Iz defining the indicator function, there cvists z" E 2 such that F(z) defined in (8) salisfies the proximal weak MVI de defined in (66
Next, the main lemma of this subsection is presented. This result is analogous to Lemma I in the un- constrained setting but adapted for the constrained case. The lemma characterises 8n and &% under the assumption that there exists a x* satisfying Assumption 3
Lemma 2. Let f(2) defined in Problem [ be continuously differentiable with Lipschitz continuous gradient with conslant L1 (J) 0. Moreover, let 85 and 8s. be defined in (28). & def Gy(Es) - F2(()), & def - (2)(),, Gμ and Fu be defined in (13) and (15) with smoothing parameter μ > 0, p denote the prozimal weak MVI parameter defined in Definition 14 k denote the condition number of B in ( and DN be the diameter of Z c B If there exists x" E Z such that Assumption S is satisfied, then it holds that
(sk, 2k - --) + pl| l1 + " D2)LL(f)(d++ 3) + D= + 122
2 (()))(( + 2pm 11 2 0, (30)
2
u²
(3s, SK 2²) + ا|| 1 + ト (xxL((f) + 3) f D + pk L(())((++3)))) + 2pm 1 2 0. (31)
2
A proof of Lemma is provided in Appendix A In the sequel, using Lemma 2 we can present the main theorem of this subsection. This theorem introduces an upper bound on the average of the expected value of the Euclidean norm of defined in (28p. Considering the formulation in (29). this theorem is analogous to Theorem in the unconstrained setting but adapted for the constrained case.
Thcorem 3. Let f(2), defined in Problem 1 be continuously differentiable with Lipschitz continuous gra- dient with conslant. [J) > O. Let o² be an upper bound on variance of the random oracle defined in Assumption 1 N 2 0 be the number of iterations, 3% be defined in (28 with smoothing parameter μ >> O, Ux= = [uu, úo ). (u,, ū1),- ..... (ux, úz)], k E NO....,NN, p denotes the prozimal weak MVI porameter defined in Definition 11 and D, be diameter of the compact and conver set Z C R.d. Moreover, let {zx1x20 and {2x) be the sequences generated by Algorithm 7 lines 5 and 8, respectively, suppose that Assumplion 3 is satisfied, and recall the definitions of the smallest eigenvalue 2, the largest eigenvalue X and the condition number k of the positive definite matrix B defined in (2) Then, for any iteration N, with h1 = h22 = h
and h E (V WINCONAA 22.(f)a
Up
1
we have
1
N Ei Eu [1a S
(112AN2 20 2-12
ID DDD. (()(+++)))))
Li +3)
N
(I)()) - (N) +1)
L1 AATx 6p
L2f))PANA -6p
k=
(36pk²> A + L1(5)
42
)0²
2D,AKo
(32)
Li(fb22Ak 6p
Li(f) - 6p
A proof of Theorem 3 is provided in Appendix B Given the upper bound of Theorem 3 the first term on the rinh side of (32h becomes arbitrarily small as N + 20. The second and third terms become arbitrarily small for + O. The last two terms are dependent on the variance of the random oracle, defined in Assumption [| which becomes arbitrarily small by using the variance reduction scheme in Algorithm 2 As in the unconstrained setting, an optimal selection of B is out of the scope of this paper, but a discussion on the selection of B can be found in Appendix C.2 As in Section 3.1 and motivated through the discussion in Appendix C.2 we focus on diagonal matrices B XI, X 0, in the remainder of this section.
Corollary 5. Let the assumptions of Theorem 3 be satisfied with = AI for X >>0 0. Then, we have
N
(f)= - 2012
I L, (f) 333/22 X2 - 6p
+ (1) 3)3
Σ K=
Eus. 19
+
N +1
- (N +1)
X3 L2 6p
(36p + 4 1190)) 220²
2D:20
+
(33)
(f)1 6p
X2Li -6p 6p
15

---

Published in Transactions on Machine Learning Research (09/2025)
The proof of Corollary is the same as the proof of Theorem 8 with A = X and K 1. The next corollary gives guideline how to choose the number of iterations and the smoothing parameter provided specific measure of performance e and for diagonal matrices B > 0.
Corollary 6. Let 8k be defined in 28 with GN defined in 13 and adopt the assumptions of Theorem
(D(433)) LL) 6p and b (d(()) For given 0, XPIa(f)A> 6p
with B AI for A O. Let 200
2n
if
b + 12
2
( )
)==
S
and
N
2a
121,(1)222 - 6p
then,
N
(36p + T(() )oo
4
2D2
Eut
|| 1sxx|1
S
+
N
X² 6p
-fLi
A proof of the Corollary can be found in Appendix variable below:
B To proceed the next result, we need the auxiliary
def Pz(za, h2,6, F(zx))
Pk
(34)
Considering Definition 3 and 27 we observe that Ps can be wrillen as Pk = T yk). To show that the
sequence generated by Algorithm converges to an e-stationary point of f. it is needed to bound [px]. Based on Theorem 3 the next corollary provides an upper bound for the average expected value ps defined in 334.
Corollary 7. Let pk be defined in 34 a def 4
adopt the assumptions of Theorem with B = AI for À and let
(h 6p b def 4AL1(f)D, (d+3)
Xla(f) 6p
bb vb + a
(PLL(f))²² 6p )
16)211(f)10
# S min
and N
2a
V2AL (d)
Then, the following bound holds:
44336p I X2L1(f)22 6p +
8D.N0 22L, (f)) 6p
Fan [IpE 5
2o
N k=0
A proof of the Corollary 7 can be found in Appendix B Taking into account Definition 3 and Corollary 7 the projected Gaussian smoothing 70 estimate generated by Algorithm [ is guaranteed to converge to a neighbourhood of the e-stationary points of f in terms of the expected value. We further note that this neighbourhood can be ensured to be arbitrarily small using the variance reduction technique in Algorithm 2 The next theorem introduces an upper bound for the average the expected value of the Euclidean norm of sę defined in (28 with respoct to the sequence generated by Algorithm 2
Theorem 4. Let f(z), defined in Problem 1 be continuously differentiable with Lipschitz continuous gradient with constant Li(f) > O. Let o² be upper bound on the variance of the random oracle defined in Assump- tion 1 N > 0 be the number of iterations, tx be the number of samples in each iteration of Algorithm 2 be defined in (28) with smoothing parameler μ > 0, Us = [[uo, ûo), (ui, ūi), ...,, (ux, ux)], k E (O....,Ny N denotes the prorimal weak M MI parameter defined in Definition and D be diameter of the compact and conver set 2 C Cdd. Moreover, let (2x)22 and (2xlu20 be the sequences generated by Algorithm 1 lines 5 and 8, respectively, suppose that Assumption is satisfied and recall the definition of the smallest eigenvalue X. the largest eigenwalue X and the condition number of the positive definite matria B defined in Then,
16

---

Published in Transactions on Machine Learning Research (09/2025)
for any iteration N, with h1,e = h2 = and h (V
LI(fNRAA' 2L, (()x
6p
we have
1
2L1(f)ANw(2 - 2-12
+ 3)3/2
p L(f)((d3333
Fau 11
N
(LI())PAAR - (N) +1)
AA 6p
LI(f)R2ANK 66
(36pm2
A+ + Li(l] )02
42
1
N
1
2D2AKo
N
1 Vix
+
(35)
Leff)PAAR 6p
N
tR L(f)) R=
6p N
K=0
A proof of Theorem can be found in Appendix B. A discussion on the step size selection h and the selection of B can be found in Appendix C.2 The next corollary gives guideline on how to choose the number of iterations and the smoothing parameter H4, for a given specific measure of performance to guarantee the convergence to e-stationary point of the objective function.
Corollary 8. Let Pa be defined in 34 adopt the assumptions of Theorem with B XI for X 0.
Moreover, define
a def 4p)L)(F)(d + +3)3 def (fL((f)D,((+3) (2T1(1)2 6p"
def (36p + 1 + +2) I
def 2Dgdo
X3 (f)1² 2 6p
X2 22 - 6p
2 - 6p'
and let
tx = t 2 32 max fee -2 2. +J
-b vb + ac
and N2 (x1110111 -6p
(f)r ) ----
p S min
2a
V2AL (d)
Then, the following bound holds:
N Eu, lppk s 2.
N ++1 k=
A proof of the Corollary X can be found in Appendix B Based on Corollaries and and under appropriate parameter choices, the following conclusions can be drawn: employing Algorithm ensures convergence to a neighbourhood
radius depends on the variance of the stochastic oracle of an e-stationary point of the objective function, within O(e=²) iterations and O(E-2) function evaluations. In contrast, using Algorithm 2 guarantees convergence to an e-stationary point (i.e., not merely a variance-dependent neighbourhood), with the same iteration complexity O(e-)), but at the cost of ((-66) function evaluations.
Remark 4. In Pethick et al. 2023), the authors addressed the NC-NC min-mar problem using a first-order extragradient algorithm with adaplive and constant step sizes. In their approuch, they assume the existence of solution to the weak MVI with respect to the operator v F + A, where F is the gradient operator and A is the sub- nob-differential operator of the indicator function. It is worth noting that both Assumption S and their assumption simplify to the weak MVI with respect to the gradient operator in the unconstruined case. Beyond this, there is no direct. relationship between the assumplions, as each encompasses different classes of problems.
Remark 5. The results presented in Section 3.2 are restricted to conver and compact constraint sels. How- ever, it is well known that if the objective function is coercive, then there exists compact set containing the optimal solution. Consequently, any construined problem with an unbounded conver constraint set and a coercive objective can be equivalently reformalated as a problem with a conver compact constraint sel. We refer the reader to [Calafiore & El Ghaoud, 2014 Lemma 8.5) for additional information on extensions to coercive objectice functions. Extending the current results to seltings with unbounded constraint sets of infinite volume and non-coeren correive objective functions remains an important direction for future research.
17

---

Published in Transactions on Machine Learning Research (09/2025)
3.3 Unconstrained Non-differentiable Problem
The smoothed function fa defined in (10p has several nice properties that can circumvent the difficulties associated with solving non- differentiable problems. Among these the following two play a critical role in one's ability to solve these problems. First, it is known that fu is diffcrentiable regardless of the diffcrentiability of f (Nesterov & Spokoiny 2017] Section 2). Second, if f is Lipschitz continuous, then fu has Lipschitz continuous gradients with its Lipschitz constant explicitly expressed in the following lemma.
Lemma 3 ((Nesterov & Spokoiny
2017 Lemma 2)). Let f Z + R be Lipschitz continuous with constant
Lo(f)> 0 and fyu be defined in 100. Then f 's gradient is Lipschitz continuous with Lı(fu) ///² Lo(f).
Moreover, the existing literature has characterised the relation between the stationary points of smoothed function fn and the Goldstein stationary points of the original function. Specifically, (Lin et al.) 2022, Theorem 3.1) proves that ff(²)) 0af(2) for any 2 E R., where fa(z) = [f + 8u)] is the uniform smoothing with IP being a uniform distribution on a unit ball. Lei et al. (2024) derives similar results for Gaussian smoothing of a class of functions, called Subdifferentially Polynomially Bounded, which includes global Lipschitz continuous functions as a special case.
Lemma (QLei et al. 2024 Theorem 3.6 and Remark 3.7)). Let f Z IR be a Lipschilz continuous function with constant. [o( > O and B = I defined in (2) be the identily. Let. Sn. - be defined according (10p and let Osf be the 6- Goldstein subdifferential defined through Definition For 0 < < and ( )1/4, it holds that
0 0<< Y min (Lo((f)
ffu(z) E (zf(z)+ + (O) Vz E Z.
These results motivate us to study the convergence of ZO-EG in non-differentiable min-max optimisation via the smoothed function fu- Towards that end, in the following we make an assumption on the existence of a solution to the weak MVT with respect to 2 Z and F,, defined in (15)
Assumption 4. Consider Problem | with z Z. Let f - R be a Lipschitz continuous function, Fu(z)
be defined in (5). Lz(fa) be the Lépschitz constant of the gradients of fo defined in (10) and let a denote
the condition number of the matrix B defined in (2) For all = E 2, there erist E such that
(Fa(z), 2*) + (2)1 2 O, PE O, AL 4L1
From Lemina 3. we see that as long f is Lipschitz continuous, (Sr) is well-defined and can be expressed in terms of Lo(f), Hence, Assumption 4 well-defined for studying cinfeifeerett min- max optimisation problems. One simple but non-differentiable example that satisfies Assumption is f(z, v) |x]| lyl, for V. E R and Z = =R.. We leave the proof to Appendix D
Having this set-up, we can discuss the convergence of Algorithm when the objective function is non- differntiable.
Theorem 5. Let f2), defined in Problem ] be Lipschitz continuous with constant Lo(f) > O and recall the defivitions of the smallest eigenvalue X, the largest eigenvalue X and the condition nummer k. of the positive definite matrix B defined in (2). Let o² be an upper bound on variance of the random oracle defined in Assumption 1 N O be the number of iterations, F,, be defined in (15) with smoothing parameter a > 0, Us (wo, ūg), (u1, ..)..... (ux, (x)], k E {O,..., "ig...,N,, NN, denoles the weak MVI parameler defoned in Assumption 4 and Ln (fa) be the Lipschitz constant of the gradient of fu- Moreover, let (zx] Jk20 and (2x]uzz be the sequences generated by Algorithmm 1 (see lines 5 and 8) and suppose Assumption 4 is satisfied. Then, and 122 = =h2 E (v Vn for any number of iterations N, with 41 = h1 S TT
P
we have
2I. (Axslo0 -012 2012 (ANnh) -P)(N +1) ((F.))(L pp) 0².
32
Eua. (8x))
+
=0?
(36)
N+1
0=
18

---

Published in Transactions on Machine Learning Research (09/2025)
A proof of Theorem 5 provided in Appendix B Given the upper bound of Theorem the first term on the right-hand side of (36) becomes arbitrarily small for N + x. The second term is dependent on the variance of the random oracle, defined in Assumption [ which becomes arbitrarily small by using the variance reduction scheme in Algorithm 2 As before, we refer to Appendix C.3 for a discussion on the selection of the matrix and continue with results for the special case B defined as the identity matrix
B =.
Corollary 9. Consider the assumptions of Theorem and let B defined in Then, we have
12 be the identity matric B
N Σ Eu II (24))11)
(fx(ll 11 (LI P)( (1W - 0².
3
(37)
The proof of Corollary is the same as the proof of Theorem 5 with ||=|| = ||=||B || for all Z and À = X = 1. The next corollary provides guideline for choosing the hyperparameters of Theorem 5 given specific measure of performance e.
Corollary 10. Adopt the assumptions of Theorem 5 and let B defined in 12 be the identity matrix B I. Let > 0 be the smoothing parameler, to =|=0- =* and the step sizes to be hi hi S Li(fa)AK
and
h224 122 E (VI.G..AAN
with Li(fu) d Lolf). For a given E 0, if
N
(F (Tn(5 -) c2
(1
then
N (I (L o².
1
Σ
3
A proof of Corollary 10 is given in Appendix B Considering Theorem and Corollary 10 it can be concluded that the sequence generated by Algorithm 1 is guaranteed to converge to a neighbourhood of the estationary points of fa in the expected sense. The size of the neighbourhood can be made arbitrarily small using the variance reduction technique. Morcover, leveraging Lemma f belongs to a neighbourhood of d-Goldstein subdifferential, whose size becomes arbitrarily small by choosing appropriate parameters. Thus, this convergence result means that the point is (old)GGol stationary point of f, defined Definition 7 The result presented in the following corollary.
Corollary 11. Adopt the assumptions of Lemma 4 and Theorem 5 and let B, as defined in be the
idendity matrir B- I. Let < < 1, ro =0= l", and the step sizes to be ha hn Li L.
and
12, =12 E Siee(Viiiia LilsaIAAN 2
For a given e > 0, if
8
1/d
{ 8rgLi(fN) (TT - ) 1
p V dre (Too())
and N
then there ezists 2g E Rd, k NO....,,,, in the sequence generated by Algorithm 1 which is a (old)-Goldstein stationary point of where ē ==c+ L(W.A11))))0000)0 o in the expected sense.
A proof of the Corollary 11 is given in Appendix B Note that in Corollary 11 is the upper bound the variance of the random oracle, defined in Assumption D which becomes arbitrarily small by using the variance reduction scheme in Algorithm 2 The next theorem introduces upper bound for the average of the expected value of the square norm of the gradient operator of the smoothed function in the sequence generated by Algorithm 2
Theorem 6. Let [(z), defined in Problem i be Lipschila continuous with conslant Lo(f) > O and recall the definitions of the smallest eigenvalue X, the largest eigenvalue X and the condition number & of the positive definite matrir B defined in ②.) Let 2² be an upper bound on the variance of the random oracle defined in Assumption 1 N be the number of iterations, tx be the number of samples in each iteration of Algorithmm! Fz. be defined in 155) with smoothing parameter p 0, Ue [[wo, âo), (un; (t)). ... (ux, dx)).
19

---

Published in Transactions on Machine Learning Research (09/2025)
k E [O.....N), P denotes the weak MVI parameter deftned in Assumption and Lı(fu) be the Lipschitz constant. of the gradienl of Jp. Moreover, let {*k 120 and {2x)a20 be the sequences generaled by Algorithm 7 (see lines 5 and 8) and suppose Assumption 4 is satisfied. Then, for any number of iterations N, with
h1.k = h1 S (T and h = h22 E (V (VaathiAAa hy
P
we have
N
3d0 (Li(f))AAh - P) Li P) N +1 k=0
2L1 (f - 2212
N
Fa, (F
+
(38)
N+1
R=0
A proof of Theorem can be found in Appendix B and for the step size selection and selection of the matrix B refer again to Appendix C3 The next corollary gives a guideline how to choose the number of iterations, the smoothing parameter μe, and the number of samples in each iteration of Algorithm 2 for a given specific measure of performance to guarantee the convergence to a (ole)-Goldstein stationary point of the objective function.
Corollary 12. Adopt the assumptions of Lemma 4 and Theorem G and let defined in 12
be the identity and LiffaTT
matrix B I. Let 0
< 6
1, ro || 2 1, and the step sizes to be h1.k h1
h2,2 = h2 (V (1(Ja)TAn"
h (VintGiAAn
For a given e > 0, if
2
1/d
(fr) (In(s - ) and 4x = 1
240² LT p)
1 S Vdree 8Lo(S) N2
then there exists 25 E Rdd k E (O....,N,, in the sequence generated by Algorithm 1 which is (..))-Goldstein stationary point of f in the expected sense.
A proof of the Corollary 12 can be found in Appendix In light of Corollarics 11 and 12 and under appropriate parameter selection, it can be established that employing Algorithum 1 with O iterations and 3) function evaluations ensures convergence to neighbourhood dependent the variance of the random oracle of a (ō, Golldstein stationary point of the objective function. In contrast, utilising Algorithm with (c)²) iterations and O(e=²) function evaluations guarantees convergence to a true (6, e)- Goldstein stationary point, independent. of the oracle variance.
Remark 6. In this puper, we have discussed unconstruined non-differentiable min-mas oplimisalion by assuming the existence of solutions of the weak M based on the smoothed function fa. Similar assumptions can be made via the prozimal weak MVI when constrained non-differentiable min-mar optimisation is studied. For the sake of brevity, omit the detailed discussion here.
In the next section, we provide a general discussion on Algorithm 1 and the main results presented in Sections
3.2 and
3.4 Other oracles, the effect of noisy function evaluation, and the selection of B
In this section, we give some general explanations on Algorithm T the main theorems, and the results of this study. First, we focus on the choice of the random oracle defined in (11). The random Gaussian oracle defined in (11) forward approximation oracle. Other types of random Gaussian oracles, such as the central difference approximation, i.e., 0=(2) f(2 + pu) - -f(z p2) Bu,
2/1
and the backward approximation, i.c.,
gr (=) f(z) f(z -uu) Bu.
are used in the literature of ZO optimisation (see Nesterov Spokoiny (2017); Malladi al. (2023) for example). We should note that the proofs of all the results in this work only rely on
20

---

Published in Transactions on Machine Learning Research (09/2025)
(i) the unbiasedness of the random oracle an estimation of the gradient of the Gaussian smoothed version of the objective function; and
(ii) the boundedness of the variance of the random oracle.
Any random oracle satisfying the aforementioned properties can be employed as substitute for the forward
approximation oracle defined in (11), without affecting the convergence bounds established in Sections 3.1
3.2 and 3.3 Although the forward approximalion oracle is prevalent in the literature Nesterov & Spokoiny
[2017ps |s Liu et al. (2020); Wang et al. (203); Farzin & Shames (2024); Xu et al. (2020); Huang et al. (2022); Xu et al. (2023), the central difference approximation often provides higher accuracy by climinating the first-
order term in the Taylor expansion. Empirically, the central difference approximation oracle may outperform
both forward and backward approximations, particularly in scenarios with noisy feedback, as demonstrated
in Section 4.3
In this paper, we have considered noiseless function evaluations. In the presence of noisy evaluations
modelled as function values corrupted by additive noise with zero mean and bounded variance, i.e., Fl7) 0
and Eh < oo the variance bound associated with the forward approximation oracle defined in
scales by a factor of 1. bound improves, scaling it by +.. Although it should be noted that in each iteration of Algorithm 2 the central difference approximation requires 4t, function evaluations, whereas the forward or backward difference approximations require 2/, + 2 function evaluations, where l denotes the number of sampled directions. The practical benefits of the central difference approximation over the forward approximation are demonstrated numerically in Section 4.3 A rigorous theoretical analysis addressing the noisy feedback scenario remains an important direction for future research.
p In contrast, when employing the central difference approximation, the variance
Regarding the choice of the matrix B defined in 12 . it is common in the litcrature to select B as the identity matrix Balasubramanian & Ghadimi (2022):
15 Malladi et al. (2023); ; Wang et al. (2023); Xu et al.
(2020). However, our main theorems in Sections 3.1 3.2 and 3.33 are stated for general positive definite matrix B = B* > 0. A detailed discussions on the selection of the minimum and maximum eigenvalues of B are provided in Appendix C The impact of different choices of B is further investigated numerically in Section 4.3 Extending the theoretical analysis of the choice of B constitutes an important direction for future work.
Comparing the update rule in (Nesterov & Spokoiny 2017 (66)) with the update rules in Algorithms and 2 of this work, one key difference is that the random oracle in (Neterrvv & Spokoiny| 2017 (66) is multiplied by B-1, whereas in our work it is not. Furthermore, the results in Nesterov & Spokoiny (2117) are expressed in terms of the primal and dual norms, while our results are formulated using the difference in formulation explains why the eigenvalues and condition mumber of B do not appear in the final results of Nesterov & Spokoiny (2017). Spocifically, the use of primal-dual norms and multiplication by B-1 absorb the influence of B in their bounds. However, translating their results from primal-dual norms into the |-| norm would generally lead to more conservative bounds compared to deriving the results directly in the |-| norm, as we do in this work. Our motivation for using the |- norm is to make the decay of the iterates explicit without masking the influence of B. To illustrate this point, suppose |2|2 < C for some constant C O. Then, using the dual norm || ||=, we have ||=|| < Ç. This implies that by choosing À sufficienlly large, one can make || arbitrarily small. This highlights how the || norm can obscure the true behaviour of the algorithm unless B explicitly accounted for. For more details, see Appendix M Tt. is worth noting that the per-iteration complexity of Algorithm 2 is lower than that of Algorithm 3 as it avoids the additional vetrix-veclor multiplication step. Furthermore, in Algorithms Tand] 2 the matrix B is treated hyperparameter, and its selection influences the algorithm's performance with respect to the Euclidean norm of the gradient operator. In contrast, the hyperparameter choice in Algorithm B is independent of the choice of B, and for a fixed hyperparameter configuration, the algorithı guarantees consistent performance across all choices of B, measured with respect to the B-weighted primal and dual norms.
BBBBB norm. This
Next, we discuss the relationship between sccond-order optimality conditions and the results of this study. Prior works such as Daskalakis & Panageas (2018); : Jin et al.) (2020): Farzin et al. (2025): Cai et al. (2024) characterise local convergence behaviour and limit. points of certain first-order algorithms, analysing second-
21

---

Published in Transactions on Machine Learning Research (09/2025)
order optimality conditions to relate these limit points to local Nash equilibria, local min-max points, @-equilibria. To the best of our knowledge, the second-order optimality properties of limit points produced by ZO algorithms have not yet been investigated. In this study, we focused on establishing first-order optimality properties of the sequence generated by the ZO-EG algorithm. Examining second-order optimality constitules a promising avenue for future research.
4 Numerical examples
In this section, we evaluate the performance of Algorithm via numerical experiments. First, ZO-EG is applied to three toy functions, and the trajectory of iterates for each case is analysed. Second, a robust underdetermined least squares problem studied, and the convergence trajectory of Algorithm analysed and compared with other algorithms. The third example is concerned with data poisoning attack on a logistic regression problem. Algorithm [ is applied to this problem and it is shown how it compromises the prediction accuracy of logistic regressor. The performance of the algorithm is compared to that of the direct search (DS) algorithm from (Anagnostidis et al.) 2021). In the fourth example, a classifier neural network is trained and a corresponding empirical risk minimisation problem is solved using Algorithm [ Finally, a version of a lane merging problem, which can be formulated as min-max problem, is implemented and solved using 70-EG. In all the examples below, we set B- By" I, unless stated otherwsse.
4.1 Low Dimensional Toy Problems
In this section, we apply Algorithm
to the following three functions:
(z = 2x 2y²² + 4ry - s0sin(ry),
(39)
f2(2, v) log(1 + e²) ) + - 3 + e.),
(40)
fz(2,y) | - 1| - 11²² + 1/.
(41)
We consider the functions fi, f2 and fa the objective functions of the min-max Problem and thus fits into the setting discussed in Section 3.
Function
fi (z, y) is smooth and conconvex--noconee
Function
f2(1, y) is smooth and nonconvex-noncoonee
and is considered in a constrained setting where X
def
{or E R
|x] & 3) and y def {v E R : lvl s 2} and thus, the corresponding theory, is covered in Section 3.2
Function
Ja(x; y) is non-differentiable and nonconvex-nonconenn the performance of Algorithm
Hence, we can use the theory of Section For 33 and (41), we choose hı
3.3 to study
10-3, h2 = 10-3 and μ 10-
For (40), we choose h; 122 10 and Jr 10-6 The sequence { yk )220 for objective functions Si and f2 with two initial values (5, -7) and (-7,5) and for objective function fa with two initial values (7, and
(1, 7) are shown in Figure 0 For (41) Algorithm iis initialised through values where fi is non-differentiable.
1 we observe that Algorithm I successfully converges to the stationary point of the objective function for all three cases.
As expected from the theoretical results, from Figure
4.2 Robust Least-Squares Problem
We illustrate the behaviour of Algorithm when applied to a robust least-squares (RLS) problem. Slightly deviating from the notation so far, let A e =xx be the coefficient matrix and E R" be the noisy measurement vector for n, m E N. We assume that yo is subject to a bounded additive deterministic perturbation e Ra The RLS problem can be formulated as (El Ghaoui Lebrei 1997
min max |Ar - yo + 812.
2 [8
This problem has a compact convex constraint set (0) with respect to the optimisation variable d. We set p = 5, n = 150, m = 250 and sample the elements of and yo from (10,,) 1). In Algorithm ! we choose h, = h2 10-5 and μ 10-9. For comparison, we solve the same problem with Gradient Descent Ascent (GDA) and min-max Direct Search (DS) Anagnostidis et al. (2021) algorithms. The sequence of the objective function values is plotted against. the execution time (0.5 sec), the number of iterations, and the
22

---

Published in Transactions on Machine Learning Research (09/2025)
sMartay
Value xf and
2-
-2
Iteration
loa pal- 15,
sturtay from 1i
2: 1-3.5
starting frems (7:3)
y:lt 15
y:lta (-3.3)
Value of Xs and 9/
-2
2700
5000
7500 10500
12500
15500 17603 2000
Iteration
th 0.33
6
you, yal
you 6.77
5
6lx, x)
3-
Dven (1.71
2000 4005
1003
0020
1953
12603
1:500
Iserution
Figure 1: The trajectories of iterates generated by Algorithm appliedd to functions f2, in Section 4.1
number of function calls for ZO-EG, GDA, and DS in Figure 2 In cach iteration of ZO-EG, there are 2 oracle calls (i.e., 4 function evaluations), whereas the number of function evaluations per iteration in DS can vary. Notably, for this particular example, both ZO-EG and DS reached their target within 0.5 seconds, but DS made minimal progress. The average and the standard deviation over 10 runs of the wall-clock times, as
03003
10002
70020
00020
52000
5000
230003
8000
33000
23393
2002
20010
13000
1000
10000
161
102
160
104
1.0
100
Time
Iberaiionss
Function calls
Figure 2: On the left, objective function value versus the exccution time, in the middle, objective function value versus the number of ilerations, on the right, objective function value versus the number of function calls for RLS problem of Section 4.2
measured by the hyt time package, for each algorithm to yield iterate that results in the function value
23

---

Published in Transactions on Machine Learning Research (09/2025)
Table 1: Average wall-clock time reach 0.5%|| -
- -o -oo doll for
runs for the RLS problem Section 4.2
ZO-EG
GDA
DS
Average Wall-Clock Time (s)
0.39
0.21
24.56
Standard Deviation
0.13
0.04
3.80
of 0. + 6oll are presented Table Note that GDA, as a first-order method, uses the gradient of the objective function while ZO-EG only has access to the function values. Also, in each iteration of GDA, two gradient evaluations are needed, while we need four function evaluations in each iteration ZO-EG.
4.3 Choice of and the Oracle, Effect of Output Noise, and Impact of Increased Sample Size
In this section, we illustrate the behaviour of Algorithms 1 and 2 applied to the RLS problem described in Section 4.2 First, we analyse the effect of the choice of matrix defined in (12). Then, assuming noisy function evaluations, we study the performance of Algorithms | and 2 using forward, backward, and central difference approximation oracles with varying numbers of samples per iteration. We set 5, n 150, 250, and sample the elements of A and Yo from (0, In both algorithms, N 5000, and μ = 10-5, We run Algorithm [ with five different choices of B defined in (12). Specifically, B1 is diagonal matrix with all diagonal entries equal to 10, B₂ is diagonal matrix with all diagonal entries equal to 0.1, B3 is diagonal with entries randomly chosen between 10.1, 10) (yielding a condition number = 98.87), B3 diagonal with half of the diagonal entries equal to 10 and the other half equal to 1, randomly placed, and B5 is the identity matrix. Figure 3 plots the average objective function value over five runs. can be seen that, for this example, the choices of B with condition number equal 1 perform better and yield smoother convergence.
fix hı h2 10-
10
B
B2
B;
101
Bs
function values
10a
10a
109
1000
2000
3000
4000
5000
6000
7000
Number of Iterations
Figure 3: Objective function values over the generated sequence by Algorithm with different choice of B for the example of Section 4.3
Next, test Algorithms I and 2 in the case of noisy feedback. The parameter selection is mentioned above, and we choose B as the identity matrix. First, we consider output noise sampled from A/ 10 10-3), V(0010-3) and 10-11, and test Algorithms I and 2 with forward, backward, and central difference approximation oracles. The number of samples per iteration of Algorithun 2 is set to 100. The average objective function values over 3 runs are plotted in Figure 4 It can be observed that when the noise level is small, there little difference among the oracles; however, as the noise scale increases, the central difference oracle outperforms the forward and backward oracles. Additionally, in all three noise cases, the variance reduction technique employed in Algorithm 2 improves convergence by reducing variance, leading to better
24

---

Published in Transactions on Machine Learning Research (09/2025)
and more accurate results. We repeated the test with noise sampled from V(0,10-1), but with μ 10-4 The average objective function values over 3 runs are plotted in Figure 5 Comparing the bottom row of Figure | with Figure reveals the inverse dependency of variance on μr; under the same noise conditions, a larger smoothing parameter leads to more accurate convergence.
16
13
foeward, b-1 baskward
forwand, - 100 bsolward. 100 100
16
13
122
122
Unncoonatue
functon attues
122
124
13a
100
1000
2000
2005
3000
3003
16-1
1030
2010
1003
4002
3000
foeward
forward.
backword, 1
backward, &
100
centerr i,
105
center; 1,- 100
1und voaoooall
func enverialees
0.07
-02
10h
10F
1003
2000
1000
4000
5000
1020
201
3007
0072
300
Mamber
Nurroer karatorra
122
109
forwand, h- 100
bacloved, & 100
center, 100
102
forward, R- bacloward
10
Aumbrrof teritione
Number of Baratttttto ont
Figure 4: Performance of Algorithms 1 (left column) and (right column) under additive Gaussian output noise in the example of Section 4.3 The plots show the objective function values over the generated sequence for different noise levels. From top to bottom, the noise is sampled from NN0, 10-"), 100)), and (00 10-1), respectively.
4.4 Data Poisoning attack on Logistic Regression
Following the examples in Huang et al. (2022): Liu et al. 2200 as a next example, we consider a poisoning attack scenario where a fraction of the samples corrupted by an additive perturbation vector aiming compromise the training process and, consequently, deteriorate the prediction accuracy. This problem be formulated as
max min h(z (x) + h(0, y: D.) + 1 | y
where D, is the corrupted data set and D, the clean data set, < > 0 the maximum allowed perturbation magnitude, X > is regularisation parameter, y is the model parameter, and is the corruption vector. Note that this max-min problem can be reformulated a min-max problem: min Sc maxy f(x,,) y) with
25

---

Published in Transactions on Machine Learning Research (09/2025)
forward bodlward q-1 conteC, h-
forward 1
backward, &
center. c 100
Manter of FFFeatto
Figure 5: Performance of Algorithms and 2 with μ 10-4, under additive Gaussian output noise sampled
from (00 10-)) in the example of Section 4.3
f (x. v) def (h(x, D2) + h(0, D,) + \) The corruption ratio is set to 15%. We consider a binary cross-cntropy loss function, i..., h(z, D) card(() D(e,d.eeDlb log(g(z, y: (1-))(1-bb))))) log (0g,,,( y: a:)) and g(x, 0,) = T+exp(- (2+a;)" ") where card(D) denotes the cardinality of the set D.
In the experiment, (n= = m 20) from (),,)) Label b; 1 if I+exp(-(a] 8+e;]] 2 2, otherwise b; 0. Moreover, 0 and are sampled from W(0, 1) and (00, is implemented with the same parameter setting as the first experiment of (Anagnostidis et al. 2021 as a comparison. ZO-EG is run for 12000 iterations with h1 = h2 10-3 and DS is run for 330 iterations. We note that, for this particular example, on average, each iteration of ZO-EG takes 6.9 x 10-3 seconds and each iteration of DS takes 0.24 seconds. The average evaluation accuracy over 20 runs versus the number of iterations, the wall-clock execution time, and number of function calls for both algorithms are plotted in Figure 6 In each iteration of ZO-EG, there oracle calls (i.e., function evaluations), whereas the number of function evaluations per iteration in DS can vary. We note that ZO-EG's improved performance
generate 500 samples. Specifically, we randomly draw the fcature vectors a, R220
(0,110-5) 10- respectively, for i = 1,...,,.00 500. We let À 0.001 and ( 10. DS
1.0
1.0
Evelostion Accurscy
D Accuracy
08
Eraleatuu
0.7
0.6
10
10
Time (1)
Naration
Function calls
Figure On the left, evaluation accuracy versus the exccution time, in the middle, evaluation accuracy versus the number of ilerations, and the right, evaluation accuracy versus the number of function calls for the poisoning attack example of Section 4.4
(doing in increased amount of lime) in comparison to DS, i.e., ZO-EG successfully decreases the prediction accuracy to a lower level than DS, as it is the goal of poisoning attacks.
4.5 Robust Optimisation
The problem of empirical risk minimisation for a specific class of binary classification problems is formulated AAaggnsttdii al. 2021]
1
min max
Psly log log()(X;))) + we) log(1 0(x;;0))
P;
m
1=1l
26

---

Published in Transactions on Machine Learning Research (09/2025)
where X2 RR," E (I,...,m, ,,), are the data points, 0 E R" are the network parameters, and (Xx; 8), R are the predicted and the true class of data points X,, respectively. Moreover, I denotes the weights assigned to each data point. The positive scalar À is the regularisation parameter. The Wisconsin breast cancer data set is considered for this test. This dataset has 569 instances and cach instance has 30 (: = 30) Teatures. Specilically, we consider the case where the predicted class of a data point X, (XX; 0), generated by a neural network with a hidden layer of size 50 and the LeakyReLU activation function with n 1601 and m 513. We let 0.05, /1 10-2, h2 10-3 and μ 10 The min-max DS algorithm is implemented using the same setting the first test of Anagnostidis et al. (2021) for comparison purposes. In Figure 7 the evolution of the zero-one error and the total error are plotted against the wall-clock time. The algorithm is trained using & 10-fold cross-validation process (Refaeilzddeh et al. 2009). It can be observed that the
Z0-EG Test Error
DS Test Error
20-EG Train Error
DS Train Error
Ovnrall Ervor
Class Eroor
Close Error
Time
Time
Time
Figure 7: Numerical simulations for the binary classification problem of Scction 4.5
steady-state performance of the algorithms is the same for class 1 and DS performs slightly better for class 0. However, DS leads to a faster decrease in the transient in comparison to ZO-EG. This behaviour almost similar to that GDA (Anagnostidis et al. 2021 Appendix D1, Figure 4). is important to note that this objective function explicitly satisfies a more stringent assumption; it is strongly concave in p.
4.6 Lane Merging
In this subsection, we present a numerical example a lane merging problem formulated as a min-max optimisation problem. This scenario involves two cars. The first aims to maximise its velocity while staying in its lane, and the second aims to perform lane merging maneuver. Both vehicles aim avoid collision. The kinematic bicycle model used simulate the cars' dynamics, represented as:
((t) (o,((,(())
(t.(t)
e,(t) sin (8,(t)))
(t(t)
u,(t) = [t (,
d (t) f(,, (tt.
= vi(l) tan (I)) st(t) = (t)
0,(L)
v,(()
where i {1 indicates first second car, (I, v.) represents the position, 0 the heading angle, e the velocity, 8, the steering angle, the longitudinal acceleration, and L is the car's wheelbase. The imput for the first car defined as un (1) (t) 0] while the second car's input is uz(() = [a=(t) 82(t)]
To solve the problem using numerical optimisation, the contimuous-time system discrctised using the fourth order Runge-Kutta (RK4) method with fixed time step At 0. In RK4, an update is calculated using
hhttps://archive.ice uci. http:///www.ateeeeeooooocooaaata (Diigoootiiiiitiiaaaaaatttt))))i
27

---

Published in Transactions on Machine Learning Research (09/2025)
four intermediate evaluations of f at different points within the time step:
K1,iA= = f(l,, 8i,k, uz((z)), K3,4,k = f(tx + + S1. + 2 Kank uttx 1
K2 f(u - + At Sin + 2 Ki,,,, + 71,,
KA f(x + SiA + AtKa, us(tx + At)). (42)
Here, Si,k denotes the approximation of st + +t), to kåt, and assuming that the initial time satisfies = the resulting discrete-time dynamics arc:
s1,++1 81,k A (K1,t + 2K + 2K + Ka,ik).
where & E N denotes the discrete time steps. The discrele-time objective functions for the two cars are:
Tikk, 81,A, 82,x) 2 - 2exp (- 22.1) 2 + (V1, )22x)²))
(2 $1,A, 82,x) exp (- ((11, - x2,4)² (U1,A -2,)))) + +1 - Mtarget)
where ytarget is the g-coordinate of the target lane. These objective functions penalise proximity between the cars to avoid collisions, encourage the first car to increase its velocity, and encourage the second car to reach the target lane. This problem can be solved as an open-loop non-cooperative game over a time horizon of T > O, where we use the parameter == 20 for the numerical example. The control inputs are paramctrisod using +- 50 uniformly spaced control points leading continuous and piecewise linear by assumption, i.e., u,(tx + ) = (u,(t)) u, (tx + At))) is used in 42 for i E 21 and & E N. The optimisation problem is formulated as:
sampling time of A 0.4 second. The inputs are
min max Ulll
Σ k=
(k, 82,)) + T2(k, $1,A1 82,4,,
At
subject to
81,+11 = 8i +
(Ki + 2, + 2K3,i, + KA..),, ViE {1,2),
6
where U,= (t, & E (O..... . Φ - 1},, E {1, 2}, and 11 {(a, a E [amin: amax] d E [8mins m ]. The input dimensions are 50 for Un and 100 for U2. The steering input for the first car is fixed and does not contribute to the dimensionality.
We implement the ZO-EG algorithm with Bharget = 5, μ = 10-6, h4 2 10-9. h2 = 10-9 and N 4000. The initial states of the cars are 81 = [0, 5, 0, 2, for the first car and 62( - 15,0, for the second car. Figure shows the evolution of the objective function values over the iterations. The initial and final positions and paths of the cars depicted in Figure g
We also investigate the proximal MVI in this context. Using ZO-EG with the same time horizon T 20, 4- = 20 control values (sampling time At = 1 second), the same step sizes and smoothing parameter, and N = 7500 itcrations, we generate a candidate point Up = (uip, U2p) for the answer to the proximal MVT problem (candidate for =*). To evaluate the proximal MVI condition (Qe(u, h2, F(ū)), ū - up) 2 0, where is the indicator function of II, we sample 1000 samples for u and ā separately. All points are sampled from normal distribution centred at up- For the acceleration inputs, the covariance matrix is set 0.1I, while for the steering imputs, it is O.O1I. Among all tested points, the proximal MVI product is positive, as shown
in Figure 10
5 Conclusion And Future Research Directions
The performance of Gaussian ZO random oracles finding stationary points of Loncouvve--nnnoonenn func- tions, with or without constraints, differentiable or non-differentiable objective functions, was explored. For the unconstrained problem, the convergence and complexity bounds of the ZO-EG algorithm were studied when applied to notion of proximal variational inequalities and established convergence and complexity bounds of the ZO-EG algorithm. We also considered non-differentiabee objective functions and obtained convergence and complex- ity bounds of finding the stationary point of smoothed function and related that to the original function
objective functions. For the constrained problem, we introduced the
28

---

Published in Transactions on Machine Learning Research (09/2025)
11000
10000
loss function value
9000
8000
7000
6000
10
102
10a
Iterations
Figure 8: Objective function values versus iterations.
Final Initial
pocition
position
-10
100
150
200
X position (m)
Figure 9: Initial and final positions and paths of the cars.
using the existing literature and the definition of (GolsSenn stationary points. A number of numerical examples were presented to illustrate the findings. A future research direction includes the exploration of the constrained case where the diameter of the constrained set is unbounded. Another potential direction is to study the non-differentiable case, assuming local instead of global Lipschitz continuity properties. Another promising direction for future research is to analyse the second-order optimality conditions the limit points generated by the ZO-EG algorithm.
Acknowledgments
We sinceroly thank the anonymous reviowers and the Action Editor for their constructive feedback and insights, which significantly strengthened this mamuscript. P. Braun and Shames are supported by the Australian Research Council through a Discovery Project under Grant DP250101763 and the United States Air Force Office of Scientific Research under Grant No. FA2356-24-1-4014. A. Lesage-Landry and Y. Diouane are supported by the National Science and Engineering Research Council of Canada (NSERC).
References
Anagnostidis, Aurelien Lucchi, and Youssef Diouane. Direct-search for a class of stochastic min-max problems. In International Conference on Artificial Intelligence and Statistics, pp. 3772 3780. PMLR, 2021.
Charles Audet and Warren Hare. Derivative-free and Blackbor Optimization. Springer, 2017.
29

---

Published in Transactions on Machine Learning Research (09/2025)
500
400
Frequency
300
200
100
20000
40000
60000
80000
Proximal Minty Variational product Value
Figure 10: Distribution of proximal MVI values around the optimal solution.
Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order nonconvex stochastic optimization: Han- dling constraints, high dimensionality, and saddle points. Foundations of Computational Mathematics, 22 (1):35-70) 76, 2022.
Heinz H Bauschke, Walaa M Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Mathematical Programming, 189:55 74, 2021.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223 311, 2018.
Stephen Boyd. Convex optimization. Combridge UP, 2004.
Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen- Yu Wei, and Weiqiang Zheng. On tractable d- equilibria in non-concave games. arXiv preprint or orXim:2403.0811 08171, 2024.
Giuseppe C Calafiore and Laurent El Ghaoui. Optimization models. Cambridge university press, 2014.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and securily, pp. 15 26, 2017.
Tianyi Chen and Georgios Giannakis. Bandit convex optimization for scalable and dynamic iot manage- ment. IEEE Internet of Things Journal, 611):1776-1286, 2018.
Frank H Clarke. Generalized gradients and applications. Transactions of the American Matherattcall Society, 205:247-260 1975.
Frank H Clarke. Oplimization and Nonsmooth Analysis. STAM, 1990.
Patrick L Combettes and Teemu Pennanen. Proximal methods for cohypomonotone operators. SIAM journal on control and optimization, 43(2):731-742, 2004.
Cong D Dang and Guanghui Lan. On the convergence properties of non-ouelidean extragradient meth- ods for variational incqualities with generalized monotone operators. Computational Optimization and applications, 60:277-310, 2015.
30

---

Published in Transactions on Machine Learning Research (09/2025)
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-man optimization. Aduances in neural informalion processing systems, 31, 2018.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I Jordan. Efficient methods for structured noneonvee-nonnconcave min-max optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2746-278 2754. PMLR, 2021.
Laurent El Ghaoui and Hervé Lebret. Robust solutions to least-squares problems with uncertain data. SIAM Journal on Matrir Analysis and Applications, 18(4):1035-110) 1064, 1997.
Lawrence Craig Evans. Mensure Theory and Fine Properties of Functions. Routlodge, 2018.
F Facchinei. Sinite-dimensione Variational Inequalities and Complementarity Problems. Springer, 2003.
Amir Ali Farzin and Iman Shames. Minimisation of polyak-tojasewiez functions using random zeroth-order oracles. In 2024 European Control Conference (ECC), pp. 3207-322 221222 IEEE, 2024.
Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, and Iman Shames. Properties of fixed points of generalised extra gradient methods applied to min-max problems. IEEE Control Systems Letters, 2025.
Pierre Foret, Ariel Kleiner, Hosscin Mobahi, and Behnam Neyshabur. Sharpness-awary minimization for efficiently improving generalization. Tn International Conference on Learning Represenlations, 2021.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2):267 305, 2016.
Allen Goldstein. Optimization of lipschitz continuous functions. Mathematioal Programming, 13:14 22, 1977.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems, 27, 2014.
Zhihao Gu and Zi Xu. Zeroth-order stochastic mirror descent algorithms for minimax excess risk optimiza- tion. arXiv preprint arXiv:2408. 12209, 2024.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in Neural Information Processing Systems, 30, 2017.
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order and first-order momentum methods from mini minimax optimization. The Journal of Machine Learning Research, 23(1):1616-1666
2022.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonnooncarw minimax optimization? In International conference machine learning, pp. 4880-4889. PMLR, 2020.
David Kinderlehrer and Guido Stampacchia. An introduction to Variational Inequalities and Their Applica- tions. SIAM, 2000.
Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension-doopndencee for zero-order nons- mooth nonconvex stochastic optimization. Journal of Machine Learning Research, 25(122):1- 14, 2024.
Ming Lei, Ting Kei Pong, Shuqin Sun, and Man-Chung Yue. Subdifferentially polynomially bounded func- tions and gaussian smoothing-base based zeroth-order optimization. arXiv preprint arXtv:2405.04150, 2024.
Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic non- smooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160-26171 2022.
31

---

Published in Transactions on Machine Learning Research (09/2025)
Sijia Liu, Jie Chen, Yun-Yu Chen, and Alfred Hero. Zeroth-order online alternating direction method of multipliers: Convergence analysis and applications. In International Conference on Artificial Intelligence and Statistics, pp. 288 297. PMLR, 2018
Sijia Liu, Songtao Lu, Xiangyi Chen, Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Mingyi Hong, and Una-May O'Reilly. Min-max optimization without gradients: Convergence and applications to black-box evasion and poisoning attacks. In International conference on machine learning, pp. 2282- PMLR, 2020.
Yuanyuan Liu, Fanhua Shang, Weixin An, Junhao Liu, Hongying Liu, and Zhouchen Lin. A single-lopp accelerated extra gradient difference algorithm with improved complexity bounds for constrained minimax optimization. Aduances in Newral Information Processing Systems, 36, 2024.
Alejandro Maass, Chris Manzie, Iman Shames, and Hayato Nakada. Zeroth-order optimization on subsets of symmetric matrices with application to mpc tuning. IEFE Transactions on Control Systems Technology. 30(4):1654 1667, 2021.
Alcksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Represenlations, 2018.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Newral Information Processing Systems, 36:53038 53075, 2023.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR 2019- 7th International Conference on Learning Representations, pp. 1 1-23, 2019.
Seyed-Mohsen Moosavi-Dezfooli; Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9078 1078-9086, 2019.
Katta G Murty and Santosh N Kabadi. Some np-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39:117-129, 1987.
Arkadi Nemirovski.
with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Oplimization, 15(1):229 (211 2004.
Arkadij Semenovië Nemirovskij and David Borisovich Yudin. Problem Complezity and Method Efficiency in Oplimization. Wiley-Interscience, 1983.
Yurii Nesterov. Introductory lectures on convex programming volume Basic course. Lecture notes, 3(4):5, 1998.
Yurii Nesterov and Vladimir Spokoiny. Random gradient free minimization convex functions. Founda- tions of Computational Mathematics, 17(2):527-566, 2017. ISSN 1615-3375, 1615-3383. doi: 10.1007/ URL -10206-015-9296-2.
Yurii Nesterov et al. Lectures on Conver Optimization, volume 137. Springer, 2018.
Thomas Pethick, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq, and Volkan Cevher. Escaping limit cycles: Global convergence for constrained nonconvex-noncoocave minimax problems. ar preprint urXiv:2302.0989/ 2023.
Yuyang Qiu, Uday Shanbhag, and Farzad Yousefian. Zeroth-order methods for nondiffcrentiable, nonconvex, and hierarchical federated optimization. Advunces in Newral Information Processing Syslems, 36, 2023.
Marco Rando, Cesare Molinari, Lorenzo Rosasco, and Silvia Villa. An optimal structured zeroth-order algorithm for non-smooth optimization. Advances in Neural Information Processing Systems, 36, 2024.
32

---

Published in Transactions on Machine Learning Research (09/2025)
Payam Refaeilzadeh, Lei Tang, and Huan Liu. Cross- Validation,,, pp. 532-538. Springer US, Boston, MA.
2009. ISBN 978-0-388--3944--- doi: 10.1007/975500337-3999000- 565. URL http:::///oo..r///1.../ 978-0-387-39900-9255 565
Lais Miguel Rios and Nikolaos V Sahinidis. Derivative-free optimization: review of algorithms and com- parison of software implementations. Journal of Global Optimization, 56:1247-1293, 2013.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and llya Sutskever. Evolution strategies as a scalable alternative reinforcement learning. arXiv preprint arXiv:1703. 10..:1700..3864 2017.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. Advances in Newral Information Processing Systems, 33: 14303 143144, 2020.
Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So. On the finite-time complexity and practical computa- tion of approximate stationarity concepts of lipschitz functions. In International Conference Machine Learning, pp. 21360 21379. PMLR, 2022.
Luis Nunes Vicente. Worst case complexity of direct search. EURO Journal on Compulational Optimization, ((1):143-18)) 153, 2013.
Chi Wang, Qingyun Wu, Markus Weimer, and Erkang Zhu. Flaml: A fast and lightweight, automl library. Proceedings of Machine Learning ond Systems, 3:434 447, 2021.
Zhongruo Wang, Krishnakumar Balasubramanian, Shiqian Ma, and Meisam Razaviyayn. Zeroth-order algo- rithms for nonconvex nonconvex-strooggy -onncyee minimax problems with improved complexities. Journal of Global Optimization, 87(2):709 740, 2023.
Tengyu Xu, Zhe Wang, Yingbin Liang, and H Vincent Poor. Gradient free minimax optimization: Variance reduction and faster convergence. arXiv preprint arXiv:2006.0988 2020.
Zi Xu, Zi-Qi Wang, Jun-Lin Wang, and Yu-Hong Dai. Zeroth-order alternating gradient descent ascent algorithms for class conconvex-nonconent minimax problems. Journal of Machine Learning Research, 24(313):1-25, 2023.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for a class of conconvex-nonconeee minimax problems. arXiv preprint arXiv:2002.09621 2020.
Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaic. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, pp. 11173 11122. PMLR, 2020.
Taoli Zheng, Linglingzhi Zhu, Anthony Man-Cho So, José Blanchet, and Jiajin Li. Universal gradient descent ascent method for nonconvex-nonconccae minimax optimization. Advances in Neural Information Processing Systems, 36:54075 54110, 2023.
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W Glynn. Stochastic mirror descent in variationally coherent optimization problems. Advances in Neural Information Processing Systems, 30, 2017.
33

---

Published in Transactions on Machine Learning Research (09/2025)
A Complementary Lemmas, Corollaries and Remarks
The following lemmas are adopted from Nesterov & Spokoiny (2017). The results are used in the proofs of the main results.
Lemma 5 ((Nesterov & Spokoiny
Lemma 1)). Let u E Z be sampled from Gaussian distribution |e 31l-1 du. For p E [0,2] we have Mp I dš. For p 2 2 we have
2017
M(O, B)) If we define Mp det
d I Mp S (p+
Lemma 6 ((Nestervv & Spokoiny Lipschitz gradients with constant L ff) O, and fp be defined in 10 Then
Theorem 1)). Let f Z RR be continuously differentiable with - - [())|
2017
_ L(Dd, V
(43)
2
where fp Gaussian smoothed version of f-
Lemma (Nestcrov & Spokoiny 2017 Lemma 3)). Let f Z + R be continuously differentiable with Lipschilz conlinuous gradient with consland Lı( > 0, and Sr be defined in 110 Then
- - ~ー (() V
(44)
We contimue with a proof of Lemma introduced in Section 3.1
Proof of Lemma 1 Since 2n E Z satisfies the weak MVI 9 by Assumption 2 we know that (F(z), 2 - 2²) [=)]l 2 0, for all E Hence replacing 2 with 2 + pu we have
(F(z pm), pm ==) 2 F[ uumil
(F(z + μu), x- x²) + (F + μmn), pu) 2/2 F pw)l
(45)
Also, considering that the gradient of f is Lipschitz continuous, have (Nesterov 1998
L
(x1,1) S ((2, + y), - x2) + |20 x22 1l
and
L1 11 -2212
(1) S f(x + (V,f(E,2)))) U2) +
2
Considering above inequalities, we get
T1
f(x, + (u2) I f(x + pun,y + mu2) + (V.f(r + pmn, + puz), mmmn) +
||ur|1?.
2
Since f and ff satisfy the same Lipschitz continuity properties, holds that
-s + pmn, v) fx + pan. y (m2) + (- [ pmn, y + mu2), -uuu2) + Lin² ||u2|
Thus
(Vef(x 1mn, y paz)), (rn) I f(x + pul, + puz) - f(x. y + pm2) + LiR²
1 1|2
2
and
( + pui, + puz), (uz) S f(x + pui.y) f(x + pun, v + (wz) + Lip²
2 |22
Adding the above two inequalities, have
Lnpe || + f(x + pan, y) f(x, + puzz),
(F + pu), vu) S
2
34

---

Published in Transactions on Machine Learning Research (09/2025)
where 2 (x. and [u1, u2]. Now adding and subtracting f(z, y) we have
11 (F(z + pu), pu) $ ||u|| + (f(x + pmn. - f v)) + (f(x, - f(z y puz)).
(46)
2
Morcover, recalling the definition of Fç in 15] it holds that
[2 + pu)ll [1[x(2) + (F()))))((()FFF))))a)) - F.(x)) (z))
- +2 + F
- - -
- -m)))
where the last incquality is due to the Lipschitz contimuity of F. Thus considering Lemma 7 it holds that
[[ pa)ll
+ 10
(47)
Substituting 46 and
47
45
we have
(F(2 + pu), =²) 112 ||ll ())) u
2 [] 2pp 1i
(f(z + pu1, y) f(z v)) + (f f(x,y(fx= y pu2)).
(48)
Computing the expected value with respect to u the estimate
(FF(())), 2*) + p
2 +l( + P 2 Lu²Li 3)3 + 2pp Lid + (f v) f(x,)))) (f(r, - (x.
is obtained and where fax = En, [f + uui, y)1 and fu.y Lf (I, fanctions of f with respect to only x and y, respectively. Using Lemma we have
, y + |22)] are the Gaussian smoothed
0 -=)) Lun'
+ (+) + Lu² 13 3) + 2pp 2pd LIN2n
Lif²m
+
2
With n + m = d and using the fact that 2d + (d+3)² S (d + 3)3 for all d 2 2, the last expression can be simplified to
(Fa(2), =-=)) ( p (
3)² 0.
(49)
which completes the proof.
Remark 7. Eatending Qe(x, a, F(2)), we have
1
a,
(arg min -| - 2112 (F(F()), B(x 2)) + {(x)) - 2).
a
Then we have
x' arg min
[||- 2| 2a B(x 2)) [xx)]
1
|| =||² + 2 (F3), B(x =]) + (e(x))
arg min
arg min
| =||² + (F3), B(x - 2)) + [F()]| + ((x)))
arg min
(a 2) + 22 (((x))
0
= arg min [| - (= aF(3)) {())
Thus, if [(x) = 0 or f is a constant, then x' z aF (2) and Qe(2, o..,,,,F(33 F(2)) F(8) independent of positive scalar
35

---

Published in Transactions on Machine Learning Research (09/2025)
Before contimue with proof of Lemma
2 introduce the auxiliary variables def
Uy def Pz(z,, h1k: Fu(zx))
02 def Pz(e,, 12. Fu(2e)),
Pk Pz ((())))
(50)
to simplify the presentation in the following.
Proof of Lemma 2 Let su and 8g, be defined in 28 Pr be defined in 340. and Uk. 0k and ps be defined
in (50). Considering Algorithm [ and r22) along with 2 as defined in Section 3.2 when {(2) = [2)... we
have (-oxx(-) = (r) Qe(ER, h1, F(zx)) = p& and Qe(ER, h2, F(2x)) px- Thus, when Assumption is satisfied, we have
(pk, 2/ - 2²) P I 2 O,
(0k. 2x - -=²) + "11xxl1 O.
Considering the above inequalities, we have
(Pk: 2h 2²) + P
2 P
(skr 2k =²) + (pr: - Uk 2x - =²) + (Uk Sk, - z²) + 2/2 s/ + (p& Uk) + (Uk sk) 1
(skr 2k - =²) + Pk- - -vallz - 2'1 + {Uk - 5k 2k z²) + ا|| 312 + pll(D= - Un) + (v)- sx)l1
(Sk, 2h z²) + D2 F(t) - (z))l + D + +|
2px21|2 (1 - Fx(())l1 + 2x² PlEx
2pn
1s²
(sk, 2k x²)
" D D, 3)3/2 + pll
pm pn II(() ()) +2pk* +2px211E*11 (51)
2
The third inequality is due to 1pkk uk - ((x)) - (+x)l and || sk s (xx) ( which can be obtained directly from the non-expansiveness of the projection operator. The last inequality due to Lemma Inequality 51 proves (30 proof of (3I) follows the same arguments.
B Proof of Theorems and Corollaries
In this section, we give proofs of the main results presented in this paper.
Proof of Theorem Considering Lemma lz2 > O, and letting
E = Gf((z)) (z()) and E ====0 Gp(Ek)- Fa(Ek)
(52)
(with Eng [xn] = 0 and Eag [Ex] = 0), we have
S (F)()(())) 2x - -2") + F
h L + happ [. + 3)²
hz((G (2x), 2x -2") - -h2 & - -²") + hepl F2, (2x) 11: + h2p2 L,d h2pp2 + 3)3 h22(G, (2ss) 2k+1 - =x") + h2 (G,, (zx); - + h2 G, (2x) Gı(zz), ; 24 - -
(53a)
- -h2(EE, dx 2²) + h22l F (ax) 112 + h22² L,d + happ? [2 3))
(53b)
Here, we have additionally used L, (f) to shorten the expressions. As a next step, we derive a bound for the three terms in (53g.. Considering = Z and from Algorithm| I line 8, we know that 2 zk+1 = Gr2 (2x) as Projz(z) = =. Thus, it holds that.
h2 (2(Gu(Bb), 2x+1 - =²*) 2x+1
(2k
2k+1 1: 2k+1 2²)
--" 12
Zh
2k
2k
(54)
2
2
36

---

Published in Transactions on Machine Learning Research (09/2025)
Similarly, from Algorithm 1
line 5, we know that 21= 2xx = Gp(()( and thus the estimate
h22
(zx), 2k zR+1)
(zx
2x. 2x zk+1)
hi
112
(121: - 22422/2 12k
2k 1 |2k41 - =x(3)
2h1
h2
h22
h2
1z Zx+1
1
En
11?
11 zk+11 - =xl(?)
(55)
2/
2h1
2h1
is obtained. For the third term in (53a), we use the fact that the gradient of f is Lipschitz continuous. Henco, for any a > O, the chain of incqualitics
(2(G,((u) Gu(zx), 8k - 2k+1)= S h22 (z*))
zx+1l + 112 (Ex
Eks 2x. - zk+1)
S b221
=x|1|²
zk+ill
h2(Ex Ekr 26 2k+1)
124 KN Ka
h2L1N 11 2x41 112 + halEa Ex. 2x 2x41),
11 2x
(56)
2a
is satisfied.
Substituting
54
55
and
56 in 53a
letting Fk
1zk
2=1, and noting that 2k 2x41 (22 and
2x = h1Gap (2k), we get
5 1 (r
h2
1
122 11 zull? + 122p1
r +
I2e 224112
2h11
2
2
2h1
L
h22
+
24+1ll 112 122 12 2x - 2²) + h22 L1d + h2pp Li 11
2a
2h1
+
h2 (Ex
Ex, 2x
2x+1)
1
h22
2)
(MzTaka
h2
(ră
r + +12
G GGu(2x)2 +
[G + Fp
2
2h1
2
2
2h1
h2L1
h2
+
11&x 2x+1112 - -
2x - 2²) + h2p L + h2pp2 L + 33s
2a
2
+
-halEx
Ev, &x
Zz+1)-
(57)
Rearranging the above terms have
1
h2
1 |Gp(En))
S -12-))) (h2Inka
h22 hee) [ h (2x211 F
h2
2
2h1
2h1x)
h22L1
h2
+
112x z4+1ll 112 - 12 Ex - 2²) hz Lid hopp L
2a
2h,
+ h22 - Eú, G2 (2x) -2x) (Z)))
(58)
Choosing h1 I AL, and a = 1 ensures that the second and third right-hand side terms of 58 are
non-positive. For 2h
b2 to hold, h2 needs to satisfy h2 < hıs Considering these facts, choose
2p S h2 S 2 Li
by Considering Definition 10 p e [0, sz.ez) and we can guarantee that there exists h and
l22 such that
2p < h2 < 4. Thus, we have TA
h2
(Bk))
1 5 (r2 rk-1) helEr, 2 - 2²) 2T 1Fp(2))) S
P
12d
+
P p² Id +d 3)3
4
2πx
2Nx
+ +12lEx Ek, (22 h)GG(EE))
12d +
(r2 . ) Tea hea(En, 21 Gm)()(z)) +
P. 2 [d 3)3
2xx
+ +/2 Ex. (,, (ZK))
(59)
37

---

Published in Transactions on Machine Learning Research (09/2025)
The second inequality is due to the fact that Ex 2k (2((((2)) considering Algorithm line 5. For the last term of the inequality above, we have
le (2, h1 G(x)) (Ex Ek, h2(Es F((())) - (Ex Fu(z))))
= 1Ex En, h22a - h1Ex) + 122 - Eks h2 (Et) - he Fa(z))
(60)
For he Ek. fozxx h1Ex), we have
h2 Eu, haLk - h.Ek) = 1116fs1 12 + h2/11Ex (EN, -h2fx) + h2 12,,-hit Ex).
(61)
Substituting 60
and
61 in 59
we have
G (26)) 21, AAx F2(2)))2 S } -12 -12-11++1
12d + L + +h2h |Exl
4
2Xx 2
+ hz hbtkkx x" 2x + Gp (zk)) + -22(Ei Ek. h2 (Ei)) hn F,(x))))) + h2(Ekr - + h22tEe h1 Ex)
(62)
From Jensen's inequality, we know that Eu ( (2x))12 & Eu, [l Additionally, it can be concluded that Eug, (2x)] 2 Fu,, (Bx)] = (fx())), and thus
Evg ([ > (3x)))
(63)
Using this inequality we can lower bound Eu,, ( and by taking the expected value of 62
with respect
to and then with respect to 0k. noting that Eu, [Êx = O, Eu, [1 < XEu, [1 - xo Es, [Ex] = 0. and Ea, [| []] < X a Ell < oo=, we have
12
1 (12 - Eug. an (22+1)) + Fun, an (FF(())
1dd
P 1²
+
4 2L AAx
2
2dx
2)x
(64)
4L3XNe2 2L2
Since uk and ûg are independent by assumption, Es. 2k, and & are independent of us (Eu, and
Eug [Cx] = (x,) the expected value of the last four terms of (62) with respected to uy are zero. The technique of taking the expectation with respect to the last sampled random variable first, and then with respect the history has been leveraged before in ZO optimisation, c.g., (Nesterov & Spokoiny 2017 (67)).
Next, let Uh = [(uo, úo), (ui, un), ... (ux, ūx)] for A E [O...., N). Computing the expected value of 64
with respect to 14-1, letting Φ+ = Eu-,, [ and of = 2 we have
h2
P
Eus (Ex)))
5 (o + pd + P (d(+3))
1
o²
(65)
2L, AAK
2Ak
2Xn
4L3
2
Summing 65
from 0 to k= = N,, and dividing it by N 1, yields
2A k/20 20 - 2
2n² And 2/d2I3p(d+33
Eu [1 (2.)) (TAL xh -2p)(N +1) +
+
N
(TAL 2p))
(TALi -2p)
km
320²
(66)
LnA(asn1 2p)
which completes the proof
38

---

Published in Transactions on Machine Learning Research (09/2025)
Proof of Corollary 2 Adopting the hypothesis of Theorem 1 (and L1 L1(f) and letting B defined in
12
be B = AI with X 0, we have
1 N
21 - =112 2 + 2XT]p(d+ 3)3 (A²Lah² - -2p)
3
Σ
Eu (1A
(X²Lzh} (N - +
N +1 A=0
L1 1 2p)
We want to obtain a guideline on how to choose the parameters N and given a measure of performance in 2X L1 ==]l=0===11** and 2l1d42L)p(d+3)" (A²L, (200
order bound the above inoquality by c. Thus, by bounding terms
Ap (X#L,
separately by 2 2: we obtain the lower bound on the number of iterations N and upper bound on smoothing parameter Thus if
(A2 - -2p)
[
(
L12 (APL, - 22p)
c2-1
<and N
4AL,d + 4AL3p(d + 3)3
then,
3
Σ
Eu, (3x)
N N+1
(A212 2pT.1)
which completes the proof.
Proof of Corollary 3 Considering Lemma
(and Ln Iz(f) and letting B defined in 12 be AI where
À > 0, it can be seen that
2
1²
N Eus (IF2W)
Eu (2+ (d
N k=0
2
k=
Considering Theorem and 200, if
μ S min
V2AL1 (d-3) /V
E
pTYViE + 16AL]p(d 3)3
(12L -2p)
and N>
8
22p
-2-
then
N N +
62o²
Eu (1
X2L1(L,n3 -2p)
kmm0
and thus the assertion follows.
Proof of Theorem & The proof of Theorem
2
follows the proof of Theorem from beginning to 63 Using
(63) and by taking the expected value of (62 with respect to and then with respect to uz. noting that
Eng [G)] = 0, E., [1 XEa, [[3]
<
6u Eag [Ex] = O, and Esg [|Ex S XEa [E,,(1EE|11
S
Ao²
we have
2
h2
Emg, (Fx < 1 (r Eug, (r
1dd
1² In [d +33
2L
2
2
0²
o².
(67)
AL 2T
Since us and ûn are independent by assumption, εs, 2h, and &n are independent of uk, and Exg [Ex] = 0, the expected value of the last four terms of 662 with respected to uA are zero.
Next, let Us = [[uo: Go), (ui, 4z), ... (ux, (x)] for E (O....,N) N). Computing the expected value of 64
with respect to Ux-1, letting Φu Eug 1 and of = rg. we have
h2 P
Eu. (1 (0) -22+1)+ 1dd +
P 2 L,
(d +3)++
o²+
σ².
4
2T,
TAK
25x
2
4T7
21
(68)
39

---

Published in Transactions on Machine Learning Research (09/2025)
Summing 68 from to k = N, and dividing it by N 1, yields
2TALin 2-12
L LTd
2 Lip(d 3)3
N Σ Ea, (2)))))
(AALIKhi - -Np) +1)
(AAI - 2p)
(AAL - -pp)
3d0²
1
(69)
L - 2p)) N +
k=0 LK
which completes the proof
Considering Lemma matrix, it can be seen that
Proof of Corollary 4
(and L1 Lz(f) and let defined
12 be the identity
2
11² Σ Pau | (2x)
Σ Fas [F(()))
+T] 3)
N
N
2
Considering Theorem 2 and 21 if th =t
18A0
and
L1 2p)
22ALId+ + p(x 3)3
(12L 22p ) -2-1
12A
p S min
V3ALI (d + +3)
(22L 2p)
and
N2
then
N+1 Σ Eu (((W))
and thus the assertion follows.
Proof of Theorem 3 In the following we use I, = [s( to shorten expressions. Considering &a = Gy(())
(=x) and Ex -, (f())), hn h2 h, /
6p
h 1 and p 24LiNz; the following estimate
LIdAK
2LINĀ
holds:
12++1
124- hōs 2²
12k 2" 12 + h²2 S 12 2h ($ 2x 2²)
128- 2² 12 + 122 |/ 12 (3 2x - εx) - (h( En - 2²)
S 17k 12 + 1/ 12 - (8K, 2x - 2x) + 2h [115sa12
# D2 (f) 3) + +D1 + 112
+
pk² (f)( +3) +2pr211Ex11?
2
2
= 2 12 + 1/ 2- 27 (8x, 01) +2hpp 1s
" D2 (f) + 3) D.1 ll. + 112 _ pk [3(F)(d+33) +pxx 1| 113
2h
4hp (16x 2 +s 11sa1²))
2s 222 + 122 (16x -111-1
2
DD +3) D=H:1EENl- + 122 pn3² TT((() + +3)² + 2pp 11xx,11111
+2h 1
(70)
2
40

---

Published in Transactions on Machine Learning Research (09/2025)
The first incquality is obtained using Lemma Next, we derive an upper bound for the term |& 8k 12.
2 and the second inequality is obtained by completing squares.
We have
18
sk1² - (6x ux) + (8x - 6x) + (ok- st)1
S 2/0x- ual2 + 4| 0x| + 4 sxl2
< 2Ax² 21 (()) - [=x) + 42x A - (=66)) + (Ax](G,,(E)) - F((
s 21 >>,p>>>1'>> - =x 3 4x [xx 112 + 4TmilÉa11
= 21²x²* k² 11100112 4xm |x 4Xv 1[x
(71)
The third incquality is due to the incqualities , - and ||0g -vgll & (8x) F2 (*+))l, which can be directly obtained from the non-cxpansiveness of the projection operator. The forth inequality is obtained using the fact. that the gradient of the objective
- (G),
function is Lipchitz. Plugging (71 in (70),
we have
1kk+1 - 2²12 S 12k 2-12 + 12 (2h s + 4TMIIEH1E + -1sa
4hp/ (2h2X* k² 121ss11 Ex 4T + [|<all2) + (fn
+
A
+ D.HilEEll. + 122
2 (F 3) 2px (15x111)
S 1/ - 2-12 + 122 (213h2X 11(s2p + 4hp (2h2 L2 x²2 + 1)) 1)|sk( + uhD
2
+ h2hp L + 3)3 + +2hD2 =11x + (20hpp² + 4Akh2) ||xx + (16hpk² + 4Amh2) ) 1|
< 1zk 2²12-
2
122
|sne 2
+
3p
|sp|
| D2 (d +3) + p 333
2²
LIAAN
2Λ
21
+ D= [lEall +
10pk
1
11
8pp
+
1
11Ex
(72)
L
L
L
T
Letting r =1 12, the inequality
122
3p
252 -h+1 + #
Dd
3)
+ 122
2x p LId
D:
2 AA
2X
+
10ps
11 +
18pk.
LIX +
||Sal12
(73)
L
T
holds. As next step, we compute the expected value of 73 with respect to ug and then with respect to de.
and we use the fact that Ea, [I S a, Ea. PallllElle S σ, which follows from the assumptions of Theorem
3 and Jensen's inequality. Let Ux= (u), (u1, @n ..... (ux, ūx)] for k (0..... N) and Eu, _ of
Then, Computing expected value of (73) with respect to Uk-1. summing from k = 0 to k N, and dividing
it by N + 1, yields
2L, 2L12AR/20 - =0112
HD (d+
1² 12
33)3
Eug 11
+
N
(T, (N)(NN +1)
11 6p
T, 1AA2 - 6p
k==
(74)
(36px²) 2 + 12
2D=260
21 - 6p
L1h² 6p
which completes the proof.
41

---

Published in Transactions on Machine Learning Research (09/2025)
Proof of Corollary The proof is similar to the proof of Corollary 2 Adopting the hypothesis of Theorem 3 (and Ia = [T) and letting B defined in
12 be AI where À >> 0, we have
2 20 2012 (XPL, (
(d 33 X2L
Fu, [sx
N
X3L 6p
6p
(36p + )
2D=
X² 6p
X2 6p
We want to obtain guideline on how to choose the parameters N and H4, given a measure of performance 6, = and MAD.L, (d43))// X-
in order to bound the above inequality by e. Thus, by bounding terms 2A -ppiN-]]
(d+33)++ 1 X= 6p
separately by S obtain the lower bound on the number of iterations N and upper bound (dL and D. Thus if smoothing parameter p. Let Xpp
XLah 6p
- b + 1" + 2ac
412L 6-2-1 X3L11² 6p
1
and
N
2a
then,
(36p 1A0
2D2Ao
Eu ||
2
+
N
L2 6p
X²L, -6p
R=
which completes the proof.
Proof of Corollary 7 Let sy be defined in 288 be defined in 34 Uk be defined in (50 and B defined
in 12 be AI where x > 0. Adopting the hypothesis of Theorem 3 and considering the fact that |[ - sull S
F (zk) - G, which can be obtained directly from (Ghadimi et al. 2016 Proposition 1), we have
|uul < 2|s2| + 2/ su - 2/sk 2 + ([F)) - Gp(z))1 - 2|sk| 2/Ex1
Hence, taking the expected value with respect to Uz, summing it from k = 0 to k N, and dividing it by N + 1, yields
N
N
Fa [1ubl
Fu, [|sx| [] 22a2
N
Similarly, the chain of inequalities
1 (Z +3)
|pl 2 < 2|1112 2 + 2/pk vzl2 2/06/ 2(Fx(()) F(2))) 2/1b// 2
2
is obtained and the last incquality follows from Lemma
Thus
2
Eu 11 2 ((LL(()(d +
Eu 1 N
2
K=
R=0
and
Eug [1s [1sx||]]] 4 112 (T
Eug [1 1
4202
N + k=0
N
2
k=
Let def 40X13(110-3)) XL((1)=-
def (f (b
Considering Theorem 3 and
332 if
b Vb + ac
16)²
J < min
and N
-2-
2a
(2 3)
XL - -6p
42

---

Published in Transactions on Machine Learning Research (09/2025)
then
N Σ k=
4(36p + b,5))
8D₂A0
Eu (appplllsss s
X2T, - 6p + +2/ Ao²
N +
(2 66
and thus the assertion follows.
Proof of Theorem The proof of Theorem 4 follows the proof of Theorem 3 from beginning to 73 As a
next step; we compute the expected value (73) with respect to ug and then with respect todg, and we use
the fact that Eu, II| s VEL Ea.llEEll S VT
a which follows from the assumptions of Theorem and
Jensen's inequality. Let Uy -[(uo ūo), (u1 ūi),-.. (ug, 0g)] for & E {O...., ] and Eu = o T Then
Computing expected value of 73 with respect to M summing from k 0 to N, and dividing by N + 1, yields
2L, 2LI 20 - =2²12
DD (
+ 12 L7(d+3))
Σ Fan [|s||]]
+
N
AA (N)
LibeAA -6p
L1h2 60
(75)
(36pm2> A + 12
Li 10
N
N
2D_ARo
+
LNAAAN 6p N ++1
t L 6p N +1 k=0
vtk
k=0
which completes the proof
Proof of Corollary g Let sy be defined in
(8). Pk be defined in 34p. Uh be defined in (50 and B defined
in 12 be AI where > 0. Adopting the hypothesis of Theorem 4 and considering the proof of Corollary 7
have
N
N
Eu || P] 42o + 4² (f) +d
Eu Ilpn 1lppl
115
N
N
2
Let and 32
def (DNL)())(++)) def (d+33
(2) 6
(30p+ + +4)20²
1 and
2D Ag XL Considering Theorem 3
if 14 = 12 max (32c6-2 2,3222
{
-b + vb2 + ac
and N ( (XLL17)11-
32) -6p
) )22-1
# S min
2a
(d)
then
Eu [pp [| S
N
and thus the assertion follows.
Proof of Theorem Considering Assumption 4 h2 > 0, and letting &
- FF - and & Ga((k))
Fy (ōx) (and recalling that Exg [Ex] = 0 and Esg [x]] 0), we have
5 (F(( 2x - =²) + h2 L F (2x)
2
= (2)) 2s - =²") - hi (Ex, &n - =²) + h2 P 11 (2x)
= =ha(G,, #k+1 - >²) + h2 GG (2x), 2t = + h2 (r - G,(zz), =x+1)
- 122 Es - >²) + h22 2
e | (sx))l.
(76a)
43

---

Published in Transactions on Machine Learning Research (09/2025)
As a first step, we derive bound for the first three terms in (6a)). Considering that 2 Z, from Algorithm |
line 8, we know that Zn= -+++ = (xx)) Thus it holds that
h2 ( 26-1
2x-11 - =²
(2k 2k+1; 2x+1 - -2")
1 212² mx12 -//"" zx+1
2x+1 12
(77)
Similarly, form Algorithm 1 line 5, we know that 21= - -xx = 111 Gr (=x), and thus the estimate
h2 (2x
h2 (2(G)(z)); 8x - 2x41) =
Ek: 2x zk+1)
h1
112
(|2x:
-2++1|2 12- - |zk - 2x12 2 -|2x+1 -2xl2)
2h1
h2 1a
h2
h2 || - -2xll
2x+1|
1
8x113
(78)
2h1
2h A
2h1
is obtained. For the third term in 76 considering that the gradient of fu is Lipschitz contimuous, for any a > O, we have
(2 Gu(zn),ēn zx+1) S h2)
=k+i| + h22hx Eke 2x =x+11
S h221 (Jr)ss12 - =x1llēx zx+1|| + h2 - Ex. 2x - 2x+1)
h2b1(fu)an 11 1+ 122 h2L1 (fu)( 1 - zk+1| 12 + h2 h2g - Er, &1 2x+1). (79)
2a
Substituting 77
78
and
79 in 76ah. letting Tk = 1zk - -2 and noting that 2 - 2k41 h2G and
2 2x = h1 Gu 2 we get
l12
1)
- 2x+1l2 + (habi (Ju)an
l12
0 S 2
1r2 -12m1) +
12
1| =x11?
2h11
2
2h, x
+ 2a
(2)1(fu)
h22
11
26+1l12
h2 -22) + hr2
Eu, - 2x41) h12 11 (&x))1
2h1
1v2
1
GG,(Ex)) + 112 (1aLi(Su)ar
112
(r2
r + +12
|IGm(ze)12
2
2h1
2
2
2/1x)
112T (5
lo2
z6+1l12 - 2x =2) + h22tEx Ex, - =x41) + hr2 (x 11
2a
2h1
Rearranging the above terms, we have
h2 (1 h2
IGG)) 2 20 - r2+1) + hi
(hg (haLaffaox =,1x)) ||Gp(zx)1²= + h (1
2h1
2
+
12
11 Zx+1ll 1| he 2x 2²) + helEx - Ek, h2G (2w) h1 G(x)))
2b1 2a
(80)
Choosing hi < Li(fa)An and ensures that the second and third right-hand side terms of (80) are
non-positive. Also, we need 1
h2 2h
0 and thus h2 < hı needs to be satisfied. Considering Li(Sa)AN
h2 S by : we have
G,,a( < 1r2 r2-1) - hr (Ex. 24 - =²²) + hetEr - Ex. (2)))(2) - h G₂(()) + Age (1)
< (r - + - - (xx)) P
-1 Ex,, 1
aLI(fa)Adw
(81)
44

---

Published in Transactions on Machine Learning Research (09/2025)
The last term of the incquality above can be equivalently written
h2 - (x - (=)())))) = hb2 Exr Sx, 12(66 Fu(Ex)) - h1 (1 Fa(zx)))
(Ex Ex, h2Cu h1Ex) + h22(Ea Eki 1i, F( (82)
Morcover, for h2(Ek Ek, h2fx h1Ex) the equality
ha - Ek. h2gk hrEx) = n 1 + h2 h2(5k, h22k) + h2(fE, -h1
(83)
holds. Substituting and 83 in 81
we have
1 212 - h2lEa| + h2halEal h2 G (2x)) 4L (L1(5m)AM (2+))) -
P
th2(Ek: 2² -2 2 11 ( + he - Ek. ((k)) h2 Fz(x(z)) + h2(EEx h2Ex) + h2(Ex, -11x)) (84)
From Jensen's inequality, know that Eug (2x]l Euz ((G Also, it can be concluded that Eu, (2x)) 2 Eug (2x)) = (Fp(2)), and thus
Eus [[ (F)(3)))
(85)
Using this inequality and the taking the expected value of 81 with respect to and then with respect to 0g. noting that Eug [Ex] = O, Ev, [lÉx] S XEE,, [1] < 2o Ea, [Sx] = O, and En, 11 S XBe, [ll [3] S Xo we have
h2
1 7r² -En, (atall + 162022 + Li(fu)xx
h2d
Eug, (FF(())))))))
0².
(86)
4L (Fu)TAK
Since un and ůg independent by assumption, Ex. 2k, and 24 are independent of up, and Eug [Ex] 0, the expected value of the last four terms of (84 with respected to up zero.
Next, let Us = [[uo, ūo), (u,, aI),.... ... (uk. ūs)l for E (O...., Computing the expected value of 86 with respect to Ux-1, letting &n = Eu [r and oe = rū: we have
h2
P
Eu. 1PP 2(0 2241)
3
0².
(87)
Li (fff)AA
Summing 87
from k to & = N, and dividing it by N + 1, yields
2L, (fa) - =21 + (IAnf))AAnh3 -N) [LF.))(Ta(( p) p))
31
Eu (2
02.
N+1
K=
which completes the proof.
Proof of Corollary 10
We adopt the hypothesis of Theorem and use the definition ro ||:0 2*11. Let B
defined in Hence,
12 be the identity matrix. From Lemma we know that (f())) = 4!/2 To(
N 1 (
(P c-2- then (Li(fu)h3 p) )
N Eu. F (2+)) $
p)) 00
N
+
(F -p))
k=0
where positive scalar.
45

---

Published in Transactions on Machine Learning Research (09/2025)
Proof of Corollary matrix, we have
11
Adopting the hypothesis of Theorem 5 and letting B defined in be the identity
12
N
() (LI(fnh3 P) +1)
3
Eus III (A(A))
+ (1(f))(a(f))) o².
N+1
k=0
(1)) (Li(Jo)ng
1
Thus, for N 2
there exists point E in the sequence generated such that
-
2 +
3
Eu (l 4 LUMLUUEE - -)) o²,
which implies that
Fu, |1| (3) e + VLOALLWN p))
3
(88)
From Lemma we have
V/4(3) E 0xʃ(z) + (O))
This implies that
(ist(),0s/(3) < (Z)I +7,
(89)
where A) = min.e ||a]]. expected value, yields
Calculating the expected value of 89 and substituting
88 into the
Eue dist [(0(,{((()))] S + + V (UW)( - p))
Let S 3. Then, for μ S - Vdne (T,o(7) 11/4
3 é=et (F. D))
(dis S
i.c., 2 is a (6, Golddsinn stationary point of f.
Proof of Theorem 0 The proof of Theorem
follows the proof of Theorem 5 from beginning to 85 Using
85p and by taking the expected value
(84 with respect to uy and then with respect to ūk. noting that
Evg [Ex] 0, E.g, 11& AEu, [[]
Ao"
Eag [Ex] O, and Esg [|Ex|9] < AEn [|Ex
S 2%
Io
we have
h/
P
Eu Rn (Ex)( } (12 Eug, (r2+1l)) oo
h2d
0².
(90)
ALI(F,)AAW)
L LI
Since uh and dg independent by assumption, εs, #k, and &s independent of ug, and Eug [Se] = 0, the expected value of the last four terms of (84 with respected to up zero.
Next, let Us = [[uo. ūo), (u1, az),... ... (uk, úg)] for E (O....,Ny Computing the expected value of 90
with respect to Ux-1, letting Φe = EEu-, [ and of = r we have
h2
E IF
< 2 o
o².
(91)
L, (f,)AAAR)
Summing 91 from
0 to K N, and dividing it by N 1, yields
Σ Eu. (&)
2L, (f. 2212 (fAnhh - (p)(N +1) + L. -p)
3202
1
tk
which completes the proof.
46

---

Published in Transactions on Machine Learning Research (09/2025)
Proof of Corollary 12
Adopting the hypothesis of Theorem G and letting B defined in
12
be the identity
matrix, we have
(fw)
30
Eu. 1I (1x))1 (Lr(Sn) P)NN (L N
N+1
c- -1 1 (1
Thus, for N
and to = t WWWWWW c there exists point & in the
240
sequence generated such that
Eu [l 4'
which implies that
(x)I &
(92)
From Lemma we have
fz)(2) 0af(2)+ + (B)
This implies that
(ss((00sf(z)) - [1 +
(98)
where dist(0, A) = m ||a]]. Calculating the expected value of 93 and substituting 92 into the expected value, yields
Eu, (0, (0)),(())) +
Let 2 5- Then for μ S Vdne (1.
(
Eu (s](
i.e., is Goldssenn stationary point of f.
C Choice of B
In this section we provide discussion on the selection of the matrix B defined in (12 for the different settings in Sections 3.1 3.2 and 3.3 In particular, discuss how the smallest and the largest eigenvalues of B impact the results in Section and discuss how B can be used design parameter.
C.1 Unconstrained Differentiable Settings
To analyse the choice of minimum and maximum eigenvalues of B in the unconstrained case, consider Theorem 2 with la L. (the analysis holds for Theorem 1 with t 1). To simplify the notation, let (f) = L1 and let v-(-) denote the right-hand side of 21 i.c., we define
ANLINa + bL + ALIc
de
(12,,,12))
+
(94)
ALLinh3 2pp ALLInh3 2p LIK(AALINh3 2p))
where 21=0-="2 N-1 b 2ndd, 2p²ppd + 3)3, and with respect to all of its variables subject to < A s ī and h2 E (Vi, L, 2 where hı S Ax
30 We interested in minimising 21 Po by
Moreover, considering we know Li is dependent on B. Thus converting the norms in to | we get Vf(22) - vf(z)) I. 32 21 where L L. Rearranging v1(-) we get
2.
ALka + Lx b + L (Ax) -1 c+ x²I
Àa + bx- + [(Ax) -1 + 22
(2, = ALnh3 -2p
(95)
2Lmh3 2p
LAh? -2p
47

---

Published in Transactions on Machine Learning Research (09/2025)
where a La, b Lb, L2c, and é= L- Now, to minimise v1(-) with respect to h2, it can be seen that h2 only appears in denominator and dvn (A, X, h2) < 0. Thus the optimal he is the maximum feasible 8hg
value hī 2LddN 2L. Substituting h2 (-) we get
Xa + bn + +(nn + X
adn² + + =(AK) EARK
4L
(96)
13
2p
--8 --8LI
4LA
Minimising v-(-) with respect and X leads to the problem of finding the roots of polynomials of degree and above. According to the Abel-Ruffin theorem, no closed form solution to characterise the roots of the polynomials exist.
We thus proceed by numerically evaluating 1n (A, hg) for 500 different randomly selected values of param- eters P, |0 - 2 = ju, d, a and the numerical evaluation indicates that n² = provides the best bound. In particular, we can conclude that, based on numerical experiments, matrices B > with condition number K = and thus
(1))) 47, a1 + - EA²
- 8pp
provide the best bound and the selection of depends on the parameters of specific optimisation problem. As next step, we focus on the analysis of the selection of B under the assumption that p 0. Thus, (96) simplifies to
Na + bk
+ X26
b + +())
(A
4ixx
(97)
Aa
4LX
Due to the relationship = KA,, we can remove X
97
and minimise
b
(((A,n, AL + TAm:
subject to 2 1 and X 0. Taking the derivative of (-) with respect to À and equalling it to zero, get
X
and thus we have RE
v (A* kA", h2) = 4L(xx2 + 2V 2vbb).
Finally, from K 2 and au discussion, in the unconstrained case, A x
(A", RY* hgg) > for k > O, we can conclude that x = 1. Summarising the above
C.2 Constrained Differentiable Settings
To analyse the choice of minimum and maximum eigenvalues of B in the constrained case we proceed in the unconstrained case in Appendix C.1 and we consider Theorem 4 with t t (the analysis holds for Theorem 3 with t = 1). As in the unconstrained setting, we use the notation Lı( = L1 and and define
02 A, ANLiKa + dnLib + AN Lic + (36px² A
+ 2 Amp
(98)
AL 6p
c= (=))///,.c=3(33333""30" == /² and to denote the right-hand side of 35 with a 21a--2'12 b= (D (00"d=+333,"=="""000
N+1
p 2D.0 We interested in minimising v2(-) with respect to all of its variables subject to < < < X
Vi
and h E (v Lidsn A
Moreover, considering 7 we know L is dependent on B. Thus converting the
norms in 7 to 1. we get [V[(22) vf(=i) < 7. 21 where La +. Rearranging the individual terms
48

---

Published in Transactions on Machine Learning Research (09/2025)
in v2()) we get
Xa + b 22 -1 +dr + (36pk2
4A5
12 (2,
(99)
LIha 6p
where = La, b - Lb, and Lec Now, to minimise v2(+) with respect to h, it can be seen that h only appears in denominator and oh (2, X,h) O. Thus the optimal h is the maximum feasible value h² 2L1Nx 2Lx Substituting h in 1/2 get
(A = =L Axa + bn cxd pdn² + (36px* 2 12 De
-4ppL
Minimising v2(-) with respect and Ā leads to the problem of finding the roots of two polynomials of degree 5 and above. As before, thus proceed by numerically evaluating 12(2, h.") for 500 different randomly picked values of parameters L, Izo =- N, μt d, a and the nunerical evaluation again indicates that K* = 1 provides the best bound. In particular, we can conclude that, based on numerical experiments, matrices B > with condition number
and thus
Àā -+
+ -- 24pL
(36p2 + 4A²
I je
22 (2(A = 4L
provide the best bound and the selection of depends on the parameters of specific optimisation problem. We continue with the analysis for the case that p Thus, holds that
D2 02(AAA,1') = -I Axā bR pdx + 1
4x 4L
āx²² + bi
x²
pku + B
A
A
A
where ē = ee. We use again the relationship X = xd to replace and consider
X 12 22A,,2, = 4Lxx + bn + pn? + =xx?2)
subject to x 2 1 and A > and
Continuing with the same steps as the unconstrained setting, we get A
M2 A²(2* KA* hh) = 4L(pn² + ax² + 2V ber
and from and
G02 OK
0 for positive it follows that x² and 2 X
C.3
Unconstrained Non- Non-Differentiable Settings
To analyse the choice of minimum and maximum eigenvalues of B the non-differentiable case, consider Theorem G with 1 (the analysis holds for Theorem with = 1). Let Lf()) = In and let vs(-) denote hight side of 38 i.c., we define
2s (A, = ALL + 1(LIR)-'6
(100)
2R -p
where a 21 and b p.
30 We are interested in minimising 13(:) with respect to all of its variables
subject to 0 A X and h2 (V is dependent on B. Thus converting the norms in 7 to | we get [V)(22) v.((2)) s L 21 where
p L
2 where h1 S L,A Moreover, considering 7 we know L
L1 L Rearranging v-(-) we get
X, = Na + X²b
P3 P3(AA,,1))
(101)
LXh3
49

---

Published in Transactions on Machine Learning Research (09/2025)
where ā = Lo and b b= L. Now to minimise ps(-) with respect to h2, it can be seen that h2 only appears in denominator and 0ys
8h2 (2. A, h2) < 0. Thus the optimal h2 is the maximum feasible value h 2L1 2īx²
Substituting 12 in (-).) we get
Aā +
A
47. adx² 2 + 222kR.
33 AA (T)
X
4pLx
4LA
As before, we analyse (2 13) numerically for 500 different randomly picked values of parameters p, l2 N,, o, indicating that x* = 1 is optimal. In particular, we conclude that, based on numerical experiments, matrices B > 0 with condition number 1 are optimal and thus
Vy (a = 4L 01 6x²
À 4pL
provide the best bound. The optimal selection of À again depends on the paramoters of a specific optimisation problem.
For the case p == 0, we have
Xa + +2b
33 (A,,
4L(ax² bA).
A²
4EA
which is equivalent to
va(A, K2, 12)) = AL(ax2 + b2R)
for 2 and À O. We observe that the optimal value for vx(-) is obtained when À goes to zero. Moreover, from 2 and den (A, sA, hī) > for positive it follows that x²' = 1. Summarising the above discussion, dx
in the non-differentiable case, A = X - O. To give an intuition for this phenomena, note that We and ûs in Algorithm [ and 2 are sampled from AN B) and the smaller the eigenvalues of B get, the directions are sampled from a larger area and the smoothing process will be done over a larger domain. This leads smaller Lipschitz constant of the smoothed version of the non-differentiable function.
D A Noi-differentiabee Loss Function Satisfying MVI
In this section we prove that f(x, y) = |r| lul. y E I along with 2 = IR2 satisfies Assumption 4
Let
u1 U2 ~ NO0 o²) and z² = 0). Using [O0 we know that
(x E [f + pui.y + pu2)] Evg || + puil) + Englly + wuel].
To calculate these expected values, we note that + Lmd Vlx,p200) We define the random variable
y def (x + punl. It is well known that Y has folded normal distribution and the intended expected value is the mean of Y. Thus,
x² + x - 2Φ
))
2p Em, [| + puill = μo V exp
po
where ((x) =
22n S exp(- ee )dt is the cumulative distribution function of a Gaussian distribution. Sim- 2
ilarly we can obtain Evz [| puuz) and we have
fu(x.v) = p0
2
exp
222022)
x²
exp (-
2u200²
8² )) + 2r
(-1
+
2y
110
V= ()
To obtain Fx(2)
VySa(I v)
we need calculate Vafu(x, y) and Vyfn(z, v).
Taking the derivative
of fx(x, y) with respect to vr, have
Valn(z,)) μo V
/ exp 22202
x2
+ - 2
no
-F
+
μo
2x 1
2T
exp
2p220
x2
= 1-26
T
50

---

Published in Transactions on Machine Learning Research (09/2025)
Similarly, the expression
-
Vylu(r,y) = -1 2Φ
is obtained. We are interested in checking if (Fx(z); =*) have
for all 2,y E R. Substituting the terms, we
リリ HO ))
2 - 2④
-
+ y
1 24
Tt well known that = ((x). Also, if x < then x(x) < 1/2, 0 then ((x) > 1/2, and
<(0) 1/2.. Considering these facts, x and 2 =x) par
have the same sign and the same holds for y and
1 ( ). Thus,
x
2Φ
+
2Φ
y
2
or (Px(2),=- --)
110)
E B-Invariant upper bounds
In this section, analyse how obtain upper bounds for N Σ Fei [(x))]
N+I Ex Eu, (2x) invariant of minimum and maximum eigenvalues of B. Towards this end, we
modify Algorithm 2 described below. The main differences between Algorithms 2 and are the up-
Algorithm Modified Cariance-Reducee ZO-EG
Input: yz) N;N N; (hi,)) ( R 0: B1 BJ > 0; B2 B 0:
[4 N
for h == 0,..., N do
3: Sample " ait and "2 abi from V(O,BT) and (o, B
Calculate Gp (2x)... G using w² o i i= O,.... Lk. 14 and 13
5:
Compute Gf((z)) To Ele (Zk)
Compute 2 Projz h
it Sample 4 "I,x and u2,::"
"k from (O, 1 and No, B
Calculate (2x), ... G (2x) using u² u/y i O..... ........ tk.
and
Compute (2x) 1 Et (3x)
tu
10:
Compute 2++1 Projz B (Bx))
11: end for
12: return EN
dates changed from 2s Projz - h (zx), and zα+1 Projz G, in Algorithm 2 Lo & = (r - h (k: B G, and zk+1 = Proj - h2(k) G,x())) in Algorithm 3 as well as the left multiplication of the random oracle by B-1 in Algorithm 3 These modifications are similar to the one in [Nesterov & Spokoiny] 2017 (66)). Using these small modifications, we can obtain upper bounds for the average expected norm of the gradient operator invariant of eigenvalues of B. Tn the next subsections, we will show how the results will change alongside with their proofs.
E.1 Unconstrained Settings
In this section, we present an analogue of Theorem for the case where Algorithm instcad of Algorithm is employed.
Theorem 7. Let f: Z + R be continuously differentiable with Lipschitz continuous gradients with constant
N be (J) > O. Let o2 be upper bound the variance of the random oracle defined in Assumplion) 1
51

---

Published in Transactions on Machine Learning Research (09/2025)
the number of iterations, tú IN be the number of samples in each iteration of Algorithm 2 Fr be defined in 15p with smoothing parameter 0, Uk = [uo, uo), (u1, i.).... (ux, 0x)); k E (o....,,M and denotes the weak MVI parameter in Definition 10 Moreover, let {zR]k20 and {&s J220 be the sequences generated by Algorithm 5 lines 6 and 10, respectively, and suppose that Assumption 2 is satisfied. Then, for any iteration
N, with
1 and 12 = h2 E (V
2p h1
h1, = hn S Li(f)
[1(f)) 2
we have
2f)(f) 21 2p)Ln
(pf p(d+))
N Σ Eu, (+x))1 =
- -2)((N (L2(f)
+1) (L1 - 2p)
(L1(f)13- -2p)) -2p)
30
N
(102)
(())(12 - 2p) (N+1)
Uk
k=
Proof of Theorem 7
Considering Lemma I h2 > O, and letting
Es = Gz(Zz)) - FF((z)) and E = Gp(())- - Fu(2k)
(103)
(with Eug [Ex] = and Ea,, [Ex] = 0), we have
0 S (1((F 24 - =²) +
h22² Lid + h2pp2 2 3)²
h2( 2g. z²) - h2(Ea, &u x²) + h2p F (2x) + h2p² Lid h2pp² L2(d 3)3
h22(G (3k), 2k+1 =²) + h22 (zx, (2x), 2x =k+1) h2 (G G,(=k), 2x =x+1)
(104a)
- -h2(Et, 2x - 2") + h2pp | Fr (2x) 112 + L ad + h2pp [7 3)s
(104b)
Here, we have additionally used L = (J) to shorten the expressions. As next step, we derive a bound for the three terms in (104)). Considering Z = Z and from Algorithm 2 line 8, we know that 2k 2k+1 = h2B G2(()). Thus, it holds that
h2(G =111 =²) (B(zu zx+1), 1), 2x+1 - =²)
1
= 2 112" 2x 1 2/1 "1 - 2x+1 -2
- 11 2x+1l12
(105)
2
Similarly, from Algorithm 2 line 5, we know that 2x: -2 = B B-B G(((zt)) and thus the estimate
h2 (B(zx -Ex); 24 2x-1)
h2(G, 2041)
h,
h2
(1 - 2x41112 || - Exll2 || - =x
(106)
2h1
is obtained. For the third term in (104a), we use the fact that the gradient of f is Lipschitz continuous. Hence, for any a O, the chain of inequalities
(2 GGl(z,), & - z441) < (2)(Fa(8k) - (a(t))la - 2k-ill + liz - Eks &x - zx+1)
L2LL 11 2x
2k+1ll hzlEe Ex, 24 2x+1)
h2L1a a || 1=
h241 1| 21 + 122 Ek, &u. zxt1);
(107)
2a
is satisfied. The first incquality is due to the fact that for all and and this comes from the definition of the dual norm Boyd 2004 A.1.6).
Z we have (2, s ||
52

---

Published in Transactions on Machine Learning Research (09/2025)
Substituting 105
[166], and 1077 in 104a]. letting Th
1| 2*11. and noting that 24 2k+1
h2 BgBB-Gppaa and 2/:- Ek h1 B
1--GGr (=x))
we get
1 0 5
h2
1
1|zk zx+1l1² 2 + (h2L1a 12 11āx =x11? + h2pl (i
- 2
1)
+
2/11
2)
2
2/11
h2211
h12
+
1|ēx - =x+1l1
1 122 =x -z") + 112pe Lid + h2pp1 1 3)
20
2h11
+ he (Ex
EkS Ak=
=*++1)
1
112
11
h22
(r2 rk+1)
1/2
2)
11B Gx(t)1 + tn
(
2
2/11
2
2h1
h22n
l12
+
11 zk+ill 112 h2 he(Ee, 2x--xx=)) 2²) + h2p Lid + happy L3 + 3)
2a
2h1
+ NE2
EN. 2x - 2x+1)-
(108)
Rearranging the above terms and noting that G|(+)) = [x)](=))]l+ we have
and G,,' = (&+)(
1
h2
-. 1 702 r2+11) + 11 h2211 112
h/2
[[G((E4)1
+ h2pl (10,(2))((+++p)1446666600
||
2
2/1
2h1
122 h1zL1
h2
+
11 z 112 hetEre 2x 2²) + h2p Lid + h (](+)))
2a
2h1
+ he (Ex- - Ex. B G,(s)) - h1
G
(109)
Choosing h S and a = 1 ensures that the second and third right-hand side terms of 109 are non-
positive. For 1
h2 2h
> to hold, h2 needs to satisfy h2 < h1 Considering these facts, we choose V L <
h2 S by and we have
2
h2 (&G
1 5 - -R.11) - h2 Ex - -2") - P (2x) S
=²)++ + 1²d
+ 2 L, (d + 3)3
4
2L,
2
2
+ h2tfE ha, (- - BBB 1..Bloo Gx(()
2 (r2 rh41) 122 (E 2" 2* + h4 B -e--B-Oo (zx))
1
+ 12dd
+ P
2 L. (d+
2Ax 2
+ h22la Ek B (p())) h4 B- Gr(())
(110)
For the last term of the inequality above, we have
hzlte Ex,
GG. G(()) - h1 B G(xx) = h2l6s - Ex, h2 (Gx + Fy(()) -
h, B (Ex + Fa(2))
1e2 Ek₁ 122 B- En h B- h22 - Ex, h2 h1 b, - F,(z)),
(111)
For hz (Gx - Ex, 122 B2 - h1 B (x), we have
helEi - Ek, h2 B2 E - h, B (c) = n 1& + he 1E + he(En, - -h2 -h2) + - -1, (x)). (112)
Substituting 111 and 112 in 110
we have
h2 G (2x
P (Ex S 5 - -2+1)+++++
1
1idd P
+
Ly (3) + h l|
4
2T,
2
+ helEr, x-" - 2x + h1 - (z((a + h2
- Ex h - h1 B (F((()
+ helEk, - Ex) + he (E - B 1x))
(113)
53

---

Published in Transactions on Machine Learning Research (09/2025)
From Jensen's 's incquality, we know that E., [[, (++))lI] E., ( [1]) Additionally, it can be concluded that Fu, [& 2 Eu, [G (1x)]l = (2x))) Ilo, and thus
Eu, ( [1) 2 (
(114)
Using this inequality and by taking the expected value of 113) with respect to uy and then with respect to ue, noting that Eug [5x] = 0, Eu, I1lÉx S o2/th. Eug [Ex] = 0, and Ea, [lll I o² /tk, we have
(
2 1/3 P Eur (2x)) - (r - Eu un (+++
1dd + 2 (1 +) + AL2ts 0² + 217tx
4 2L1
o².
2
(115)
Since uy and ûg are independent by assumption, Eu, 2x, and &g are independent ug, and E [Ex] = 0, the expected value of the last four terms of (113) with respected to ug are zero.
Next, let U₂ [[mo, do), (u1, uz),.. .... (ux; úg)] for k E {0,...:N}, Computing the expected value of 115
with respect to 1x-1, letting Φb Eer-, [r and di = rd: we have
1/
Fan (I) (Ex)) S 202 (02 1 1dd p 2 L (d+3)
P
2 2
o²+ 0².
(116)
2L
4L7th
21
Summing 116
from k = 0 to k: N, and dividing it by N + 1, yields
2L 2=
2p²
24 Lxpld
Σ Eu. (1))()))))
+
(117)
(Lihg 2N +1) (L,
2p)
(L, - 2p)
302
N
+ L2(Ln - 2p) (N
(118)
+1)
t
k=
which completes the proof
It can be seen that (102) in the primal and dual norms, and the right-hand side of (102) is not dependent on the minimum and maximum eigenvalues of B directly. Thus, with an appropriate B invariant choice of hyperparameters, similar to the process in Section 3.1 can show the convergence of the sequence generated by Algorithm 3 to an e-stationary point of the objective function in the expectation sense.
E.2 Constrained Settings
In this section, we will show how Theorem proceeding further, we need to redefine (2 and (27 as below.
4 will change by using Algorithm B instead of Algorithm 2 Before
F(E)) def
B (TBxx(=-aB-FF(e)) 2). V2, Z,
(119)
a
and
P2 g()) def [=
(120)
h
where h and a are positive scalars. We note that when é is the indicator function, then Pz(z, (()) ((()), Then we can define the below auxiliary variables with respect to 119 and 120
$k
def (2 hy G,(zx)),
65 def Pz h2 G2.)))
(121)
Hence, using above auxiliary variables in the constrained case of Problem I then the update steps in lines and in Algorithm can be written as
Zk+1
2か B- and f Zk
11 B st.
(122)
Next, have the modified version of Lemma with respect to
119 and 120
54

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma 8. Let f(2) defined in Problem [ be continuously differentiable with Lipschitz continuous gradient def with constant (f) > O. Moreover, let &w and Ss. be defined in 121 & = GG((x) (2)),), En def - - F2k))), Gp and Fu be defined in (13) and (15) with smoothing parameter μ > 0, p denote the
prozimall weak MVT parameter defined in Definition 11, and D= be the diameter of 2 C TRd.. If there evists x' E z such that Assumption 3 is satisfied, then it holds that
1 (2 + 3) + D211E&l1 + 112
(Ak, 2k - =²) + p||sk|1
~ー
pIR(0)(++ 3)² 21
(123)
2
2
2²
($ 24 - 22) + || トーー (,Li(f)(d+3) +D.IEE + pL](f)(d+ 3) + 22pll 20.
(124)
2
Proof of Lemma 8 Let 85 and &n, be defined in 28 and
def P2(=k, M1 F((z))), 0g def Pz(ZE, h2 F2 (5x)), pk def Pz(ze, Mi F(xx)), pu def Pz(ze, h1, F(xx)) (125)
Uk
Considering A Algorithm and r(=) along with Z as defined in Section 3.2 when ((z) Iz(2), we have Proxę(-) (r)) Qe(z,, F(xx)) = pk and Qe(zk, h2, F(2))) = Pk. Thus, when Assumption is satisfied, we have
(pk, 2/ 2²) + 2 |Ipe 11: 2 0,
Ex -2)) + ?1 fl O.
Considering the above inequalities, we have
S (Pks 2x =²) + p |p 1 1
P |s (px - Ux) + (ex sk)ll?
(sk, 2k - =²) + (pk Uk 2h - 2²) (uu 5k 2h =²) )² +
< (sk: 2k - >²) + Ilpx- - ux 11l1=11zx - 2011 + (uk - 5k. 2k - =²) + pll 12= + pl((P) - uk) + (ux - sx)ll2
< (Sk, 2h - =²) + (zx)) - Fzy(z=)1 + D2 + /|| + 2p (z)) - Fz(()))1 + 2p11Ex
/²2
< (8k, Fh =²) + 2
D2 Li
3) + D= + 11
2 (L)( (d 33 111
(126)
The third incquality due to llpk uzll. - (2x) F2, (2x)l. and ||0-- sull. < (zx) G,((a))ll which can be obtained directly from the expassssass of the projection operator. The last inequality is due to Lemma 7 Incquality (16 proves 123). A proof of (144 follows the same arguments.
Next, we will have the modified version of Theorem
Theorem 8. Let [()), defined in Problem 1 be continuously differenliable with Lipschitz continuous gradient with constant Li(f) 0. Let o² be upper bound on the variance of the random oracle defined in Assump- tion N 2 0 be the namber of iterations, tx be the number of samples in each iteration of Algorithm 3 Sp be defined in (28) with smoothing parameter μ > O, Us = (u du), (u1, 0z),.... ..... ......(uu, (uk, (i:)); k E (O.....N), p denotes the procimal weak MVT parameter defined in Desimition 777 and D2 be diameter of the compact and convez set Z C IRd. Moreover, let {zu]azo and {2uhw2 be the sequences generated by Algoritimm 3 respectively, suppose that Assumption satisfied. Then, for any iteration N, with h2,k -22kk h and (V In (L.T)
we have
2L 2L)(f - 201 -
(D,L(()((+331)
(F
Σ Eag [13)
N N+1
(TT(1)22 (N) +1
In(s)h2 6p
In(S)²2 6p
(36p + 202
N
N
+ (f) - 6p
Σ
+ Ln(f)h - 6p N +1
2D
1
Σ
(127)
N +1
t
Vtx
0=
k=0
55

---

Published in Transactions on Machine Learning Research (09/2025)
Proof of Theorem In the following, we use L1 L1(f) to shorten expressions. Considering & Gx((t)
(zs) and &a- Gy((s)) (5x), h1 h22 h v
I h zो. and p S 21L, the following estimate holds:
|| - =²11 = || - hB 1-:--11 8/- - ==11
= || - ==1' "1 + 11
8x 12 1 2hh(BBBB 8k, 2s: - -²²
= = = =11 + 11 - -2h(sk, - =x) 2h(82; 2x =²))
S 1 11 + h² 1sall 20(8 2x - 2x) + 2h (pllsul12
+ トリ D2Li + 111 -/2 pL 20llkxl12)
112
= 1| - == 112 + 11111/111 - (8,, B- B-1 sk) + 5hpl15x11
+ /1
pL2(s)(d 333 + 201l
+ 2h
2
2
< || +1
- ||xx11] + 4hp(11 - sx11? + (1>xx113)
" (. +3) + D.lExll. + //2 112 2
+ 2h
pf + +3 + 2pllÉx
(128)
The first incquality is obtained using Lemma g and the second incquality is obtained by completing squares. Next, we derive an upper bound for the term |& - sx 1| We have
|ز l - (1 - vx) + (6x - 6x) + (un- ss
s 2/ u2ll3 + 4| - 0wl1? + 41|0x 1x + < F((()(())) - +=(2)))++++1,, (z)) - Fa [=(2)]]]+ (3)
< 2 - 41|++11 + + 11
24 Lil sx 113 1116x + 41| 112.
(129)
The third inequality is due to the inequalities || - vx 11+ S [(G((2))F[((())
(zw)ll 1| dxll. S [[,
Fg( and | uxl1- - (fx) - (=x)),,, which can be directly obtained from the non-expansivenoss of the projection operator. The forth inequality is obtained using the fact that the gradient of the objective function is Lipchitz. Plugging 129 in 128b, we have
|| 2² S 1| 20 11 + A² (2h² 5 + 1 + 411Ex113 - 11sxx11))
+ +4hp -4hp(2h2 22h2 0 11. + 41 + + I|sx11?) + 2h ( 3)
112
+ +1 + //22/ pT)(1) (3 3) + 2pl 221
1) $ || - 211 + h22 - 12 + 4hp(2h2 + +h) + 3)
uhDDL1
+ + + 3)3 + 11 + (20hpp + 4hh )1 + (16hp + 4h ||Ex1?
< |1 2=1
1/2
|1
3p
||
11 DDdddt 3)
12 pLd (d + 3)3
2
L1
2
D
10p
8pp +
+ T
|1 +
+
|1 +
(130)
Tu
T.
T
T2
Letting 1 = 12k 22, the inequality
22 3p
||s
< x
M D2(d+ (dd++3) +3)$
112
وLا (d (d+3)3 +
Da
IlÉall
2 L1
2
2
L,
10p
1
8p
+
1
||
(131)
L
I
L1
56

---

Published in Transactions on Machine Learning Research (09/2025)
holds. As next step, we compute the expected value of 131 with respect to ug and then with respect
to úgs and we use the fact that Evg [Ilxx S a/tk, Eag [llEx [|] S o o/tt, which follows from the assumptions of Theorem 8 and Jensen's incquality. Let Us [[ug. ug), (u1, ai),... (ug, ûz)] for k E {O..... .N and Eat, [r+]] o Then, Computing expected value of 131 with respect to Uk-1, summing from & = 0 to k = N, and dividing it by N + 1, yields
N
2L =00 - 2=1
(D
12 pL 3)
Σ
Bullls 111
Eu
+
(L,h² -6p) N +
L -6p
L1 - 66
(132)
(36p + i, ),
N
2D
N 1
+
Lnh² 6p
N +
tk
L1h² 6p
N
Vt"
k=
k=
which completes the proof.
It can be seen that 117 in the primal and dual norms, and the right-hand side of 117 is not dependent on the minimum and maximum eigenvalues of B directly. Thus, with an appropriate B invariant choice of hyperparameters, similar to the process in Section 3.2 we can show the convergence of the sequence generated by Algorithm 3 to e-stationary point of the objective function in the expectation sense.
E.3 Non-differentiable Settings
In this section, we will show how Theorem will change by using Algorithm 3 instead of Algorithm 2
Theorem 9. Let f(), defined in Problem be Lipschitz continuous with constant Lo(f) > 0. Let o² an upper bound on the variance of the random oracle defined in Assumption 7 2 be the number of iterations, t be the number of samples in each iteration of Algorithm 3. Fy. be defined in 15) with smoothing parameter μ >> 0, Ux [uu, ûn), (u1, ..),....,, (ux, ûx)], k "o,....,N NJ. P denotes the weak MVI porameter defined in Assumption 4 and (f()) be the Lipschitz constant of the gradient of fn- Moreover, let {2x 120 and {2x be the sequences generated by Algorithm ! (see lines and 8) and suppose Assumption
is
satisfied. Then, for any number of ilerations N, with h1. = h1 S Li(h and h2. -h2 E (v Li(la we have
(Vzn
h1
N Fa II (2x)113
< (L)( =1111 + (Lr(F,)2 P)(N +1) L0 p) N
302
1
(133)
N
R=0 tk
Proof of Theorem 0 Considering Assumption 4 h2 > 0, and letting & = G,(zx) -F (zx) and Ea = Gg((k))
(2k) (and recalling that Eug [Ex] 0 and Es, [xx] 0), have
0 < (22 24 - =²) + h2 2 (2x)
h2(GG((2)) 2s - -x)) - h1 (Ex, 2/ - 2²) + 1 (2
hh((G #x41 -z") + h2 (G GG (Zx), 2x =x+1) + 122 (e,( G,(zz), 2x -2++1)
- h22 Ex =²) h22 1 ($x))l
(134a)
As a first step, we derive a bound for the first three terms in 134aj. Considering that Z = Z, from Algorithm 3 line 8, we know that 2₁ 2k+1 = B Thus it holds that
h2(G 26+1 - =²") (B(2k zk+1) 1), 2k+1 - -²)
1 | 11.1
|| zu 1| ア || zu 11
(135)
2
57

---

Published in Transactions on Machine Learning Research (09/2025)
Similarly, form Algorithm 8 line 5, we know that 21:- 2xx = hhBBB1G (G(x)) and thus the estimate
h2
( zkt1) = (B(zk: - -²n); 2x =k=1)
h1
h22 (112k= =k+1|l 112 || Exll - || Ex 11
(136)
2h
is obtained. For the third term in 134a considering that the gradient of fo is Lipschitz continuous, for any a > O, we have
(2x) Gx(ex) 2x+1) S h221 h2)1F Fx( - 2k+1ll + he(le Ek. 2x -x++1)
I hh - 2+ 2x+1ll I| + h2(Ex - Ek. 2x 2k+1)
(f 112x - 2x12 h221 112 112 + h2 he(Ex - Ek.22 2k+1) (137)
2
2a
The first inequality is due to the fact that for all 2 E Z and & E Z we have (2, S || and this comes from the definition of the dual norm Boyd 2004
A.1.6).
Substituting
135
136)
and 137) in 134a),
letting Th = || - 2*1,, and noting that zn - Ek+1
B (&)) and
2k 2
h2 B Gu (zx). we get
h2
1)
(hzLi(fuj
h2
S
r2)1) (r
12x zx+1 12+
118k-2x1] =x11
2//1
2)
2
2/1
(f
l12
11
- 11? h helGa. 2k 2²) + holEr
-kk 2x - 2k+1) + 122 2 ( (1
2a
2h1
h2
1)
h2Li
h12 |IB-1Gu(Zx)11
(
2 r2)1) + h12
||B Gm + hi
22h1
2)
2
2h1
h22 h22T1 (Ja)
h22
|1
-
21+1l1
h2 he(Ga, &x - =²) + h22Er - Ek, 2x - -2+11) + 1122 2 Fn,(
2a
2h1
Rearranging the above terms and noting that |IB-'Gn(zz)) | and |B GB(s6l [GG((&))]+.. we have
2 h2
h2
h2 1// | + he2 F ((,((E))]1 S 2rx - r2+1))+ hi (haliffaaa
2h1
ha ) 1| 2011l12 104411--22200 h2lEe, 24 2") + h2lEr Ex. B B G B, G(zk)) (138) 2h:
+ 20
Choosing h1 S L.J and a = 1 ensures that the second and third right-hand side terms of 138 are non-
positive. Also, we need| }
b2 0 and thus h2 < hı needs to be satisfied. Considering 2h
( h2 hg
we have
4 G&) s 10 - 12)) - h2lbe, às x²) hatfa - Ev, -h
(F
s (ri - -24 h Er, x" 24 + th B B Gp(zx)) + (Lr(fa) |
-
(139)
The last term of the inequality above can be equivalently written as
(()() (Ex+ hz(Ee - h2 B - h1 B - G(zx) = hz - Ex, 12 ( +
- h1 B- (Ex + Fx(x)))
-b2 - Ev, h -f h1 11 + 122 le Ex, h2, 1 - P,,z))
(140)
Moreover, for he (Ex Ek, b2 11 Ex - B (x) the equality
(Ex Ex, 12 - B1BB-(x) = n131Ex 11: + h2 112 + h2( -h + h2(Ee, B-) (141)
58

---

Published in Transactions on Machine Learning Research (09/2025)
holds. Substituting [400 and 141 in 139
we have
h (Bx))
(L1(Fn) (+x)) - 2 (12-1111) h2l1E + hegh ||Ex|1
4
thzlEe, - 2x +h G (2x)) + h22kE1 - Ek. h2 (2 -1, FF,()),
h2 (Ex, -h1 13 [x))
(142)
From Jensen's inequality, we know that Eug |l| (2 || S Eng [l,),, Also, can be concluded that Eu, [I.] 2 [G,, (2x) ) and thus
E., [| > (1x((
(143)
Using this inequality and the taking the expected value of 139 with respect us and then with respect to 0g, noting that Eug [éx] = O, Eug E., |I| E. [12] = /tx, Eag [xx O, and Eag [llsa S o²/tz, we have
h2
1 a /1 [I+ & 2 (r Em (rk+1l) + h2 0²
h2
0².
(144)
4
(fp
t
Li(futt
Since up and ûg are independent by assumption, Ek. 2g, and 2g are independent of ug, and Eug [éx] 0, the expected value of the last four terms of (122) with respected to uy are
Next, let Us [[uo, ûo), (ui, u1),- ... (ux, ūn) for k E {0,.... Nj. Computing the expected value of 144 with respect to U4 letting Φb = EEr. [r and of = rū. we have
h2
P
Eu II (E) 200 21+1)
3
0².
(145)
L (frr)
Summing 145 from k = 0 to hs N, and dividing by N + 1, yields
N
30 (L 112 + (U - p) N (Ia(fu))g P)N +1)
N
N+ Fu (2)
f
1==
which completes the proof.
It can be seen that (33) in the primal and dual norms, and the right-hand side of (33 is not dependent on the minimum and maximum eigenvalues of B directly. Thus, with an appropriate B invariant choice of hyperparameters, similar to the process in Section 3.3 we can show the convergence of the sequence generated by Algorithm 3 to (6, sstattiory point of the objective function in the expectation sense.
59


Reviews:
[{"review_id": "6Zi4y7ebOe", "reviewer": "Reviewer_zS4u", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Authors tries to set up a clear structure of the paper\n\nWeaknesses:\n\n- Several technical aspects should be further clarified", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submitted manuscript has the following key points:\n\n(1) considering zeroth-order (extra)gradient based method to solve a min-max optimization problem;\n\n(2) the first-order stationary criterion authors claim to focus on is Goldstein stationary point\n\n(3) assumption of Lipschitz continuity for both objective and its derivative\n\n(4) proof of convergence relying on Gaussian smoothed version of an integrable function and the Minty variational equality", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Define \"locally Lipschitz\" in definition 4 on page 5\n\n2. Define \"extra\"gradient\n\n3. Add citation for \"Rademacher's theorem\" mentioned under definition 4 on page 5\n\n4. Show deduction of inequality (13) in subsection 3.1 under assumption 1 on page 8\n\n5. On page 28, answer the following questions:\n\n- It is implicitly assumed that $\\sqrt{\\frac{2\\rho}{L_1}} \\le \\frac{h_1}{2} \\le h_2 \\le \\frac{1}{2L_1} $. There is no guarantee that this will hold because the relationship between $\\rho$ and $L$ is undetermined. \n\n- Supplement missing subscript $G_{\\mu}$ in inequality (48)\n\n- In inequality (48), last row, the term $h_1 G_{\\mu}(z_k)$ comes out from nowhere\n\n- In inequality (51), I do not think the left hand side should be $ || F_{\\mu} ( \\hat{z}_{k} ) || $. It does not follow from $ \\mathbb{E}_{u_k} || G_{\\mu}(\\hat{z}_k) ||^2 \\ge || F_{\\mu}(\\hat{z}_k) || $\n\n- $\\xi_k$ and $\\hat{\\xi}_k$ are not independent, therefore the inner product terms in equation (50) do not vanish under expectation.\n\n- Most importantly, Lines 5 and 8 in Algorithm 1 on page 7 clearly entail a projection operator. The domain $\\mathcal{Z}$ is not clearly defined in the statement of the theorem, either. This projection operator is directly ignored in the proof process of this work. The claims, under inequality (45), that $z_k - z_{k+1} = h_2 G_{\\mu}(\\hat{z}_k)$ and $z_k - \\hat{z}_k = h_1 G_{\\mu} (z_k)$ do not hold.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZP1ByOL0yP", "reviewer": "Reviewer_jZZx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem setting and motivation are clearly explained, and the related work is discussed to a sufficient extent, which I consider to be a strength of the paper. The empirical validation through numerical experiments also appears to be convincing. Moreover, I believe the topic of this research will be of interest to a broad audience.\nThat said, I have some concerns regarding the soundness of the theoretical analysis and the comparison with prior work.\n\nFirst, I would like to raise a concern regarding the usage of results from (Nesterov & Spokoiny, 2017), which are cited at multiple points throughout the paper. In particular, the norm $\\\\| \\cdot \\\\|$ used in that work differs from the one adopted in the submitted manuscript, and this discrepancy does not appear to have been properly accounted for. Specifically, as can be seen from Section 1.3 of (Nesterov & Spokoiny, 2017), the norm is defined as $\\\\| x \\\\| = \\sqrt{x^\\top B x}$ for some matrix $B$, whereas in the submitted paper, according to the \"Notation\" paragraph in Section 2, the norm $\\\\| x \\\\|$ refers to the standard Euclidean norm.\n\nWith this in mind, it seems that expressions such as $\\\\| u \\\\|^2$ in Equation (6), and the norms appearing in Equation (13) as well as in Lemmas 5 and 7, should be interpreted in terms of the $B$-induced norm rather than the Euclidean one. Furthermore, (Nesterov & Spokoiny, 2017) appears to define Lipschitz constants and other quantities with respect to the $B$-induced norm, which also needs to be carefully considered. However, I could not find evidence that this distinction has been taken into account in the stated assumptions or inequalities in the main results.\n\nNext, in the Contributions section, the authors claim that their method finds an $\\epsilon$-stationary point within $O(\\epsilon^{-2})$ iterations. However, in Theorems 1 and 2, as well as Corollaries 1 through 4, the obtained upper bounds on the gradient norm appear to contain residual terms that depend on $\\sigma$. This suggests that the bound does not vanish as the number of iterations increases, which casts doubt on whether the claimed convergence to an $\\epsilon$-stationary point is actually achieved in the usual sense.\n\nGiven this, I am concerned about the validity of the statement in the Contributions section. It would be desirable for the authors to clarify whether this issue also exists in the related work they cite as comparisons. If those previous studies suffer from a similar limitation, it should be acknowledged; otherwise, the comparison may be misleading and would require appropriate qualification.\n\nThird, as mentioned multiple times in the paper, zeroth-order methods are often designed to handle noisy feedback, i.e., they are commonly applied in stochastic optimization settings. However, it appears that the current analysis does not actually support such scenarios. An explicit clarification on this point would be helpful.\n\nFor example, the last sentence of page 1 states, *\"Unlike first-order methods, ZO methods only require access to (often noisy) evaluations of the objective function,\"* and the **Related Work** section refers to methods for *\"stochastic min-max optimization problems with similar problem structures.\"* These statements may give the impression that the proposed method can handle stochastic settings with noisy function evaluations.\n\nHowever, as I understand it, the gradient estimator defined in Equation (10) would suffer from high variance when the two function evaluations involved contain independent noise, which is typically the case in stochastic settings. In such cases, the variance would scale with $1/\\mu$, potentially invalidating Assumption 1. This suggests that the current analysis does not cover the noisy evaluation setting.\n\nIf this is indeed the case, then directly comparing the results of this paper to prior work on stochastic ZO optimization may not be entirely fair, and the authors should clarify this distinction explicitly in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies min-max optimization problems involving nonconvex-nonconcave functions, with a particular focus on the zeroth-order optimization setting, where only function values of the objective are accessible. To address this problem, the authors propose a zeroth-order extragradient method based on random Gaussian smoothing, and provide theoretical analysis for both unconstrained and constrained settings. In addition, they validate the effectiveness of the proposed method through numerical experiments.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would appreciate it if the authors could verify whether there are any misunderstandings in the points of concern I raised above, and provide clarifications or revise the manuscript accordingly as appropriate.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "StIgoyDzYj", "reviewer": "Reviewer_HpAX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. I find this paper interesting because it dives deeply into the ZO-EG algorithm under various problem settings, across differentiability of the objective function and the existence of the constraint set. Each problem setting might be able to become a single paper, but this paper covers all of them.\n2. Remark 1 about scheduling the smoothing parameter is particularly interesting, having a practical implication.\n3. Numerical examples are abundant, providing many examples to future researchers to evaluate their minimax optimization algorithms.\n\n**Weaknesses**\n\n1. All the results are not exactly the convergence result towards an $\\epsilon$-stationary point. Instead, they only guarantee the near-convergence to a neighborhood of it. Even in the easiest setting, the unconstrained setting with Lipschitz continuous gradients, the exact convergence is not guaranteed in the paper. How optimal is it? Is the non-exact convergence inevitable?\n    * I don’t think this is usual for a zeroth-order optimization algorithm (e.g., [1, 2, 3]). \n2. Despite the non-exact convergence, the authors provide a remedy using a variance reduction scheme, by sampling many direction vectors (from a centered Gaussian) and taking the average of gradient oracles associated with the direction vectors $u$. I think this idea should be more analyzed. For instance, although the scheme helps reduce the radius of the convergent neighborhood by shrinking the variance, there must be a trade-off of sampling many direction vectors, let’s say, in a computational burden. If so, shouldn’t the convergence bound be described in the overall amount of computation? \n3. Another concern is that the constrained case analysis relies on the constraint set's finite diameter. However, there are many examples of constraint sets with infinite volume in the real world, which may have $D_z = \\infty$. I wonder whether the analysis can be extended to such cases.\n4. The paper lacks discussions in terms of other optimality criteria discussed in minimax optimization and multi-player game literature (e.g., local Nash [4] and $\\Phi$-equilibrium [5]).\n5. How do you choose the (PSD) matrix $B$ for Gaussian smoothing? I find it difficult to find the choice of $B_1$ and $B_2$ in both the theorem statement and the proof.\n\n---\n\n[1] Balasubramanian & Ghadimi, “Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints”, High-Dimensionality and Saddle-Points, arXiv:1809.06474\n\n[2] Malladi et al., “Fine-Tuning Language Models with Just Forward Passes”, NeurIPS 2023\n\n[3] Wang & Feng, “Convergence Rates of Stochastic Zeroth-order Gradient Descent for Łojasiewicz Functions”, arXiv:2210.16997\n\n[4] Jin, Netrapalli, & Jordan, “What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?”, arXiv:1902.00618\n\n[5] Cai et al., “On Tractable Φ-Equilibria in Non-Concave Games”, arXiv:2403.08171", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper analyzes the theoretical performance of ZO-EG (zeroth-order extragradient), which uses random Gaussian smoothing. The main problem setting is minimax optimization of (possibly) nonconvex-noncave objective function, either having globally Lipschitz continuous gradients (thus, continuously differentiable) or being globally Lipschitz continuous (and possibly not differentiable everywhere), defined on either entire d-dimensional Euclidean space (i.e., unconstrained case) or a convex and compact constraint set with finite diameter (i.e. constrained case). The main goal is to show the convergence to a neighborhood of an $\\epsilon$-stationary point.\n\nThis paper shows that, for an unconstrained minimax problem on an objective function with Lipschitz continuous gradients, the squared gradient norm of (smoothed) function (taking average over iterations and mean over iid sampling of direction vectors) is bounded by three terms: one vanishing as taking many iterations, one vanishing as taking a small Gaussian smoothing parameter, and one proportional to the variance of the zeroth-order random gradient oracle. The first and the second terms can be made small ($O(\\epsilon)$) by taking the number of iterations as $\\Omega(\\epsilon^{-2})$ and the Gaussian smoothing parameter as $O(d^{-3/2} \\epsilon)$, while the third term can be made small if we use variance reduction scheme (sampling many random directions to compute gradient oracle).\n\nThe second result is quite similar for constrained problems with a finite diameter of the given constraint set. One difference is that the convergence metric is slightly different from the gradient norm; instead, a sequence of auxiliary variables defined with the proximal (or projection) operator is used, which subsumes the gradient operator in the unconstrained case. Another difference is that the third term of the convergence upper bound is also proportional to the diameter of the constraint set.\n\nFor unconstrained and non-differentiable problems (with Lipschitz continuity), a similar convergence guarantee towards a neighborhood of the Goldstein stationary point of the objective function is proved. A crucial step is to utilize the relationship between the Goldstein subdifferential of the objective function and the gradient of the Gaussian-smoothed objective function.\n\nLastly, the paper showcases a bunch of numerical evaluations of ZO-EG.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Required Changes**\n\n- Every point I listed above in the weaknesses should be resolved.\n\n**Recommended Changes & Some Questions expected to be answered**\n\n- As far as I know, the gradient approximation used in the paper is not that stable: the first-order Taylor expansion error remains. As a remedy, another approximation method is widely used: $\\frac{f(z+\\mu u) - f(z- \\mu u)}{2\\mu} Bu$. Why did the author not use this option? Was there any technical difficulty?\n- Can a variance reduction scheme be conducted adaptively & iteration-dependently? Can we have any computational benefits by periodically increasing the number of sampled vectors?\n- Minor typos I found in the main text are listed below:\n    - Two lines below Eq. (2): Put a space (”For$k\\in \\mathbb{N}$…” → ”For $k\\in \\mathbb{N}$…”)\n    - Definition 8, 9, 10: Erase the commas at the end of the math equations.\n    - Corollary 2: redundant parenthesis in “$(L_1(f)h_2^2 - 2\\rho$”\n    - Eq. (20): Is it a typo? In “$\\langle Q_\\ell (z, a, F(\\bar{z})), z-z^*\\rangle…$”, should “$z-z^*$” become “$\\bar{z}-z^*$”?\n    - Eq. (23): Two equations must be exchanged with each other.", "broader_impact_concerns": "Since this paper mostly focuses on the theoretical aspects of optimization algorithms, the Broader Impact Statement section seems unnecessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)