Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry
Authors: Raef Bassily
Cristóbal A Guzmán
Michael Menart
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Stochastic Saddle Point Problem
Stochastic Variational Inequality
Strong Gap
Stochastic Minimax Optimization
Algorithmic Stability
Primary area: optimization
TL;DR: In this work, we conduct a systematic study of stochastic saddle point problems (SSP) and stochastic variational inequalities (SVI) under the constraint of $(\epsilon,\delta)$-differential privacy (DP) in both Euclidean and non-Euclidean setups.

Abstract: In this work, we conduct a systematic study of stochastic saddle point problems (SSP) and stochastic variational inequalities (SVI) under the constraint of $(\epsilon,\delta)$-differential privacy (DP) in both Euclidean and non-Euclidean setups. We first consider Lipschitz convex-concave SSPs in the $\ell_p/\ell_q$ setup, $p,q\in[1,2]$. That is, we consider the case where the primal problem has an $\ell_p$-setup (i.e., the primal parameter is constrained to an $\ell_p$ bounded domain and the loss is $\ell_p$-Lipschitz with respect to the primal parameter) and the dual problem has an $\ell_q$ setup. Here, we obtain a bound of $\tilde{O}\big(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}\big)$ on the strong SP-gap, where $n$ is the number of samples and $d$ is the dimension. This rate is nearly optimal for any $p,q\in[1,2]$. Without additional assumptions, such as smoothness or linearity requirements, prior work under DP has only obtained this rate when $p=q=2$ (i.e., only in the Euclidean setup). Further, existing algorithms have each only been shown to work for specific settings of $p$ and $q$ and under certain assumptions on the loss and the feasible set, whereas we provide a general algorithm for DP SSPs whenever $p,q\in[1,2]$. Our result is obtained via a novel analysis of the recursive regularization algorithm. In particular, we develop new tools for analyzing generalization, which may be of independent interest. Next, we turn our attention towards SVIs with a monotone, bounded and Lipschitz operator and consider $\ell_p$-setups, $p\in[1,2]$. Here, we provide the first analysis which obtains a bound on the strong VI-gap of $\tilde{O}\big(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\epsilon}\big)$. For $p-1=\Omega(1)$, this rate is near optimal due to existing lower bounds. To obtain this result, we develop a modified version of recursive regularization. Our analysis builds on the techniques we develop for SSPs as well as employing additional novel components which handle difficulties arising from adapting the recursive regularization framework to SVIs.

Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry
Raef Bassily
Cristóbal Guzmán
Department of Computer Science & Engineering Translational Data Analytics Institute (TDAI)
Inst. for Mathematical and Comput. Eng. Fac. de Matemáticas and Esc. de Ingenieria Pontificia Universidad Católica de Chile crguzmanp@uc.cd cl
The Ohio State University bassily a@oos.ueeee edu
Michael Menart
Department of Computer Science & Engineering
The Ohio State University
Department of Computer Science, University of Toronto Vector Institute menart 20....
Abstract
In this work, we conduct a systematic study of stochastic saddle point problems (SSP) and stochastic variational incqualities (SVI) under the constraint of (e, 8)- differential privacy (DP) in both Euclidean and non-Fuclidean setups. We first consider Lipschitz convex-concave SSPs in the l,/C, setup, P,q [1,2]. That is, we consider the case where the primal problem has an l--setup (i.e., the primal parameter constrained to lp bounded domain and the loss is En-Lipschitz with respect to the primal parameter) and the dual problem has an ly setup. Here, we obtain bound of Ö v
the number of samples and d is the dimension. This rate is nearly optimal for any q E [1, Without additional assumptions, such as smoothness or linearity requirements, prior work under DP has only obtained this rate when p q 2 (i.e., only in the Euclidean setup). Further, existing algorithms have each only been shown work for specific settings of and and under certain assumptions on the loss and the feasible set, whereas we provide general algorithm for DP SSPs whenever p, q E []. Our result is obtained via a novel analysis of the recursive regularization algorithm. particular, we develop new tools for analyzing generalization, which may be of independent interest. Next, turn attention towards SVIs with a monotone, bounded and Lipschitz operator and consider Ep setups... p E [1, 2]. Here, provide the first analysis which obtains bound on the strong VI-gap 0 vdd For - = (11), this rate is near optimal due to existing lower bounds. To obtain this result, we develop modified version of recursive regularization. Our analysis builds on the techniques develop for SSPs as well as employing additional novel components which handle difficulties arising from adapting the recursive regularization framework to SVIs.
vd) on the strong SP-gap, where
'This work was done while M. Menart was at The Ohio State University.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
Stochastic saddle point problems (SSP), are an increasingly important part of the machine learning toolkit. These problems model optimization settings with an inherent min-max structure, and for this reason are also referred to as stochastic min-max optimization problems. Concretely, the goal is to find an approximate solution of the following problem defined over convex-concave loss
min max [FD(w, 0) == (f }, weW AEB
(I)
where D is unknown distribution for which we have access an i.i.d. sample S. Problems of this kind have important applications in stochastic optimization [N]LS09 JNTII ZLI5), federated learn-
ing [SSS distributionally robust learning [YLMJ22 ZZZ 24a ZB24 reinforcement learning
DSL 18) and algorithmic fairness [ABD+ 18 WM19].
Closely related to saddle point problems are stochastic variational inequalities (SVIs). Given
monotone operator, Gz(z)= == E
[9(2; r)), the objective is to approximate the point 2" E Z, where g0 D
(GD(z"), 2) S 0, 22 Z.
Stochastic saddle point problems can be easily related to variational inequalities by observing that the saddle operator (an operator closely related to the gradient) of convex-concave function is monotone. While SSPs and SVIs are closely related, it can be the case that a problem which can be formulated as a monotone SVI is not easily cast as a Sanvex-concave SSP [N19..
Parallel to the above, the problem of privacy has become increasingly important in the big data era. In this regard, the notion of differential privacy has arisen as the premier standard. Stochastic optimization problems are a natural target for privacy concerns due to the fact that they are frequently formulated using dataset of (potentially sensitive) individual data records. For many such problems, the constraint of differential privacy necessitates fundamentally new rates and techniques, and as such the formal characterization of these problems an important task.
Thus far, work on differentially private SSPs and SVIs has focused primarily on Euclidean settings. However, number of important, including many of those referenced at the start of this section, are naturally formulated in other geometries. Prior to this work, the optimal utility rate for DP SSPs was known only in Euclidean and polyhedral settings. For SVIs, the best achievable utility was unknown in any geometry (including Euclidean), at least under canonical utility measures. this work, we provide the first systematic study of SSPs and SVIs in general geometries. The new analysis tools develop lead to optimal rates for number of these important setups.
1.1 Contributions
In this work, we provide the first systematic study of stochastic saddle point problems and variational incqualities both Euclidean and non- -on-Euclidean geometries. Our first results pertain to stochastic saddle point problems where the primal problem has fp-setup and the dual problem has fy-setup, where p. E [1, 2). Here we assume the convex-concat loss is Lipschitz. We generalize the recursive regularization framework developed in previous works more handle -un-Euclidean geometries [AZ88 BGM23] At the heart of this extension is a fundamentally new analysis of the generalization properties of this algorithm. The issue of generalization has in fact been a key issue the heart of many other works studying SSPs (LYYY2] OP/722 [GM23], as the presence of a supremum in the strong SP-gap accuracy measure (see Eqn. breaks more traditional generalization techniques. In contrast to prior work, our generalization technique works by avoiding entirely any generalization bound for the strong gap itself. Rather, we introduce new accuracy measure measure which, when used in conjunction with the recursive regularization algorithm, eventually translates into strong gap guarantee. Our technique stands particular contrast to [BGM23). which is thus far the only work in the DP literature to obtain optimal strong SP-gap rates in the Euclidean setting and also uses recursive regularization. However, their technique fundamentally relies on a McDiarmids style concentration bound that is worse by a poly(d) d) factor in non-Euce -on-Euciieean setups such as the é setting [Pan0]]. Using these new techniques, we provide the first analysis which obtains the near optimal + Vd
rate of Ô
the strong SP-gap for any p. q E [1, 2]. Our algorithm achieves this rate in Va n2/23) number of gradient evaluations. We note that the near optimality of this rate
Va
ne
Ō( mmnn

---

is established by lower bounds for DP stochastic convex optimization, which is special case of DP SSPs AFKT221, Previously, comparable rates on the strong gap had only been obtained in the case where p q 2 or under strong additional assumptions (BGM23 7B24
GGP24].
Next, consider DP stochastic variational inequalities with monotone, bounded, and Lipschitz operator. We adapt the recursive regularization framework even further and again leverage novel generalization analysis. Here, we obtain the rate Ô
vi on the strong VI-gap (see Eqn. 5
in the fp-setting, p [1. Our algorithm again achieves this rate in Ō min { n
va .n) number
of gradient evaluations. This the first result to obtain the near optimal convergence rate on the strong Vl-gap for p 1 = ((1), which notably includes the Euclidean case. The corresponding lower bound for p was established in [BG23], and we provide a simple extension of their technique to the case where p -1- 52(1). See Appendix B Finally, for the setting 2, we show that our rate can be achieved a near linear number of gradient evaluations by leveraging acceleration techniques for Lipschitz and strongly monotone variational inequalities.
1.2 Related Work
Diffcrentially private stochastic optimization now has a broad body of work spanning over a decade [KT12 BST14 ITI4ITTZIS [FTTI9] FKT20 AFKT2I]. Such work has rigorously characterized the problem of stochastic convex optimization in a variety of geometries. In e, setups, for p E [1, 2].
vd for such problems [AFKT21 [GN21] It has also is now known that the optimal rate is Ō <m ze
been shown that additional improvements are possible in the & setting under smoothness assumptions. The study of stochastic saddle point problems under differential privacy is much less developed, but has nonetheless attracted a surge of recent interest VHL-22 ZTOH22 BGM23 GGP24). Without privacy, optimal O(1/ /z) guarantees the strong SP-gap have long been known [Y788. With
privacy, the (near) optimal Ō + yd) rate was obtained only recently, and then only in the Euclidean setting [BGM23]. In fact, work on DP-SSPs has focused largely on the case where p = g = 2, despite the fact that important problems are naturally formulated in other geometries. In particular, the case where = 1 has important applications in distributionally robust optimization, federated learning, and algorithmic fairness. In this regard, the works [GGP24 ZB24 have recently studied DP SSPs with q = 1. The work [GGP24] studies the & / setting when the loss is additionally assumed to be smooth and the constraint set is polyhedral: they achieved the rate Ō + (nt)) We note that smoothness fundamentally necessary in achieving this dimension independent rate, Ad as otherwise existing lower bounds of Š2( (2(22) + or hold for such problems [FFT2T The work [ZB24) studied the problem of differentially private worst-group risk minimization, which is closely related to DP-SSPs in the f setting, but requires the loss to have a specific lincar structure with respect to the dual parameter. For l//E2 saddle point problems having this structure, their result implies a rate of O
me
vzd on the strong gap.
Work SVIs is less developed. Non-privately, the optimal strong VI-gap rate of 0 ())) was established in [NTTT] (although related techniques trace back to [NY78). Work on differentially private variational inequalities is limited to the work [BG23). In the Euclidean setup, this work vd on the strong VI-gap under DP.
achieved rate of (,t73 + n273.)
Preliminaries
In this section, we detail preliminaries for stochastic saddle point problems and differential privacy. Both SSPs and SVIs share a similar structure, which we detail first. Throughout, we use [w, 0 to denote the concatenation of the vectors w and 0. For a function f. we let Vf denote an arbitrary subgradient selection of f. Finally, we let Unif(U') denote the uniform distribution over the set U.
Stochastic Monotone Operators. Let X' be some abstract data domain and let S D for and D some unknown distribution over X. Let || || be some norm and || ||+ its dual. We consider some compact convex parameter space Z C Rd of diameter B with respect to || ||. Let B (r) denote the d-dimensional ball of radius > 0 w.r.t. || centered on zero. We assume there exists
3

---

L > 0 such that x X' + Bi--1-
-ll. (L) is a bounded operator and that for any a E A, g(:z)
is monotone. That is, 12 E 2 it holds that (0(2) ((>2; x), 21 22) 2 0. We define the empirical and population operators as Gs(z)= + Eimm g(2; and GD(z) = E [g(2;x)).
Stochastic Saddle Point Problems. SSPs have the following structure in addition to the above. Let du dg 2 0 such that dw + dg d. We assume Z the product of the convex compact sets W S Rd and θ _ Fdde equipped with norms || ll and || lla and having diameters Bw and Ba respectively. Then Z = W x O We let IIfe, 0Il / -- - |101). and thus the diameter of Z satisfies B S v B2 + :3g note the geometric mean of two norms is always norm.
In SSPs, we consider the case where the monotone operator is the saddle operator of a convex- concave loss function f W x ④ x X + R. The saddle operator is defined as g(w, 0; = [V 8; z), (w, 0; x)] and is always monotone if f is convex-concave. We also define the corresponding population loss and empirical loss functions as Fo(w, () E [f 0;z)]
m~D
and Fs(w, 0) = + Exes f(w,, 0x)) respectively. The boundedness assumption on g means f is L-Lipschitz. Concretely, Ywi, W2 W and v01,0z O:
Lipschitzness:
((w1001;2) - f(22, 02) S L [[[ 01] Iw2, 02]l
Under such assumptions, a solution for problem 4 always exists [Sio58], and is referred to as the saddle point. Further, given an SSP (T). we will denote a saddle point as (w"."").
The utility of an approximation to the saddle point is characterized by the strong SP-gap. Given a (randomized) algorithm A with output (S), Ag E W x O, this is defined
(A))
E A.S
max (A. (S), 0)}
min Ao wEW
PEB
For notational convenience, we define the following function which is closely related to the SP-gap. Gapsp ( 0) = max (w, 0)} - min (F }).. Usefully, this function is known to be Lipschitz whenever is Lipschitz.
Fact (BM23 If is I--iischiit then Gapsp is v Lipppsshii.
Finally, we define Lp saddle point problems as those which, in addition to the above, also have the following structure. Assume || 1w = || [pp and
| = || -1ly and that W and θ have diameters bounded by Bu and Bg with respect to || 1lp and - respectively. We assume that for any x E X that f(; :;) is L Lipschitz in its first parameter w.r.t. I1-1Ip and Lo Lipschitz in its second parameter w.r.t. 1I-11 Ilg. Note this implies overall Lipschitz parameter, per Eqn. of L L + Lg-
Stochastic Variational Inequalities. For SVIs, in addition to the assumption that the monotone operator is L-bounded, inequalities is to find an approximation of the (population) equilibrium point z", where =" is charac- terized by Eqn. 2 We refer to such solution an equilibrium point. For approximate solutions. the quality of the approximation is characterized by the strong VI-gap:
will also assume it B-Lipschitz. The objective for stochastic variational
(A)
E max (GD(2),AAS)) =2} A.S
(5)
=EZ
Note that it is not true in general that the VI-gap bounds the SP-gap even when the monotone operator in question is the saddle operator of some convex-coneall loss (see Fact Appendix Ap.
However, in such a case it is true that the equilibrium point of the of the SVI is the saddle point of the corresponding SSP.
We say that an operator is p-strongly monotone if for any 21, 22 (g(=1; - _(22;=), 22) 2 [2 22|l-
E
that
Stability. Important to our analysis will be the notion of uniform stability BE02
Definition 1. A randomized algorithu A : X + W x θ satisfies A -Lunfform argument stability (UAS) for any pair of adjacent datasets S, E n it holds that E [IIA(S) A(S' A.
l

---

The notion of strong convexity is often important in analyzing stability, A function w;: - R
strongly convex w.r.t. ||- || for any 2, z' E Z one has - 2 (Vi(z'), 22) - We call function F W x θ - IR saatrongly-covvev/sroonyyyyyyyoo and w E the functions ((.,0) 0) and F(w.)) are y-strongly-coovvx.
(SC/SC) if for any 0 E Q
Notably, adding a SC/SC regularizer leads to stability properties. The following fact results from more general result for regularized SVIs; see Lemma in Appendix
Lemma 1. Let 3b W θ R be y-strongly connnnggyyoommeesttooonnnooeeeee the algorithm which returns the saddle point of (w, 0) + EEes [w, 0; 2) (ww, 0) is 21 JUAS.
w.E.t. || II and || lle. Then
Differential Privacy (DP) [DMNS06]. An algorithm A is (c. -i-iifferettially private if for all datasets S and 5' differing one data point and all events in the range the A, we have, (AA(S) E 8) S e (A(S") E +..
2.1 Example of
SSP
One important example of non-Euclidean SSPs arises from the problem of minimizing the worst case risk over multiple populations. This problem has arisen in group distributionally robust optimization to name just one of many applications [SGI22 ZZZ 24b. [MG24]. Let f : W X + & and W have standard Ep setup. Consider i distributions, Di...., DR. and the goal of selecting model w E W which guarantees the lowest worst-case risk for the distributions above:
min max Sax,EEEeee RRyDD, (f(;; xy)] wEW BEA
min max
Σ j=1
g Bl [f(1;;;))
wEW SE(A]
where here A denotes the standard k-dimensional simplex, and the equality above holds by the maximum principle for convex functions [Bau58]. Given that the feasible set for 0 is simplex, is natural to endow this space with the fi-geometry. We thus end up with SSP problem in fp/E, setup.
3 A New Analysis for Recursive Regularization
Algorithm 1 Recursive Regularization: RSSp
Require: Dataset S E X", loss function f. subroutine Aemp, regularization parameter À 2 Le (where ||- 112 and || 11 are 1
Byn
x strongly convex), constraint set diameter B, Lipschitz constant L. 1: Let n' n/ log (n), and T = log2( fA).
2: Let Si,..,, be a disjoint partition of S with each S, of size n' (which is always possible due to the condition
3: Let (moo00) be any point in W x θ
4: Define function (w, 0,x) f (2) (w, (w, 0; (ww 0; + 2A ||w woll 22 110 00
5: for = to T do
6: [10e, 0.] Aemp (S,, f()), [i,,,, 0-11 B
X w|w w. -2--2t 2 1110 110 0.112 7: Define (w, 0, + ((++1) 0;2x) ((t) 0; 2
8: end for
9: Output: (wT, 0r]
In this section, we present our modified recursive regularization algorithm, first developed in [ZZ18 and extended to Euclidean SSPs in [BGM23] We then discuss the key components of our analysis needed obtain our results for non-Euclidean geometries. We conclude the section by applying our general result for recursive regularization to DP fp/
regulatiinn
Algorithm Overview. As in BGM23 our recursive regularization implementation, Algorithm
1 solves series of regularized saddle point problems defined by f(),..., (f f(T), The saddle point problem defined in each round of Algorithm is solved using some empirical subroutine, Aemp- This subroutine takes as input subset of the dataset, S,, the regularized loss function for that round, f(1),
starting point, [1;-1, 0,-1), and an upper bound the expected distance to the empirical saddle
5

---

point of the problem defined by St and f(t). The exact implementation of Aemp, Algorithm 3, will be discussed the next section. Here, we focus on the guarantees of Recursive Regularization given that Aemp satisfies a certain accuracy condition. At each round, the empirical subroutine Aemp is required to find a point, [ 0z). which is close (under || II) to the empirical saddle point. Because the scale of regularization doubles each round, this task becomes easier each round. Specifically, (BGM23) observed that implementations of Aemp which satisfy the notion of relative accuracy succeed at finding such points.
Definition 2 (é-relative accuracy). Given a dataset S' E x",,, function f', and an initial point tw',0", we say that Aemp satisfies â-relative accuracy w.r.l. the empirical saddle point [wrs, 0gg) of F'g (w, 0) = Ne Eres: ['w x) if. VD > O, whenever E [[][w', ,0] [wg. 0 S D, the output [w, 0 of Aemp satisfies E [F'g (. 0z.)
F's. (w 0)] - Då.
In contrast [BGM23), our algorithm uses more general regularization ensure strong- ewvexittysstong-concavii with respect to the appropriate norm.
Guarantees of Recursive Regularization. Our general result for recursive regularization is stated as follows, and its full proof is given in Appendix B.2
Theorem 1. Let Aemp satisfy â-relative accuracy any size n' login] and assume ||
any (5L)-Lipschitz loss function and dataset of 1| and 11 are 1/2 _-strongly convex under ||- Illl and
|| lle respectively.
Then Algorithm run with Aamp as subroutine and À
48
(áx²
+
Lx3/2
satisfies
B
vn"
Gapsp (RSsP) = OBan" log(n)) BLx log 3/2 (m)
Vn
The similarity of this result to [BG223 Theorem 5] and our exposition thus far belies the difficulty of adapting their result to non-Euelidean setups. The key challenge addressed by the analysis of [BGM23) was that of generalization. In this regard, their key insight was to use McDiarmid style concentration bounds show that the empirical saddle point obtains non-trivial guarantees on the strong gap. However, such concentration results critically rely on the fact that the underlying norm is Euclidean. A generalization of this concentration to, for example, the ε setup, necessarily incurs an additional vi factor [Pan08] Thus, fundamentally new analysis is needed. One should also note that the squared norms 1| may not be strongly convex for certain norms, such as ||- ||. Regardless, in some such cases, we can still leverage this result by modifying the underlying problem, as we will show in Section
Key Proof Ideas. We circumvent the above issues by providing a fundamentally new generalization analysis for the intermediate iterates of recursive regularization. Specifically, our analysis avoids entirely any analysis of the strong gap at intermediate stages of the algorithm. Instead, we introduce two new functions, which are similar in nature to the quantity used in the definition of relative accuracy. but are taken with respect to the population saddle point. For t E
[T]. define F!! (w, 0;x) =
E [f() (w, 0; x:] and let [ut 6;] be its saddle point; define F == n anD interested in the functions,
1 + Exes, f(t) (w, 02z). We
H0 ([w, 0)) = (t) (w, 07) 1 and
0) = PS (w. - F ( 0). (6)
Notably, the strong-convexity//stonn -onncv/aat of F(O means that bound 17.0 ([w, 0) yields bound on [[w, 0] - [w 01l1| Ultimately, finding a point sufficiently close to [w] 07) at each round is all recursive regularization needs to succeed. The question then, how to obtain guarantees on argument.
H We accomplish this via a sallliy--mmllis--geeeriiiaaa
Lemma 2. Let f Z x X + R be L-Lipschitz. Let [w- (0) E Z be the population sad- dle point. For any I E X define h([w, 0): f(w, x)) f(w", 0).). For S ~ D let Hs(z) = Eres h(2;z) and Hz(2)= = E [h(;;))). Then for any A-UAS algorithm, A, one has
z>D
E [HD(A(S) - (A(S)) < 2AL.
S,A

---

The proof relies on two main observations. First, it is easy to see that because f is Lipschitz, then h is also Lipschitz. Then, because HD and Hş can be written as the expectation of f w.r.t. D and Z ~ Unif (S) respectively, we can apply standard obtain the claimed result [BF02). We provide a full proof in Appendix [.1 This analysis bypasses
results to h to
difficulties of working directly with Gapsp experienced by [OP7722 BGM23 and other works
since, in general, there is no function h such that Gapsp (z) E (2;=a)] Note also it is important
I>D
that we have defined h(2;;;) w.r.t. the data independent point [ur], 07). Were [m, 0;]] depend on S, this result would not hold.
Because H uses the population saddle point in its definition, it may not be immediately clear how one could first minimize H Direct access H& is in fact not possible without knowledge of [w]. (t). which the algorithm does not have. In this regard, we observe that algorithms which
minimize the empirical gap are powerful enough minimize H even without knowledge of [wt, 0,], since
(w, F (w,07) 0,) - (0) (w] (w, S max (w, (w, F (w', .01}
Particular to our analysis, we will leverage the fact that the exact empirical saddle point is and has an empirical gap of O.
d sttable
4 Optimal Rates for Private lp Saddle Point Problems
Setup. In this section, we apply Theorem to obtain results for fp/Cy saddle point problems. In order to do this, we will apply recursive regularization using norms slightly different than the lp and by norms. Specifically, to solve an lp/Cg SSP, define p max p. 1 + log(d) and
q = max q. f..1 + logid) } and will apply recursive regularization with || 1/ F lls and ||- lle B. 1111. We also have || |ls S || 11 s d' 11p|| 11s - 2|| 11.- Thus, under these norms we have diameter bound B 1 and Lipschitz constant L S 4B L3 4B NJLSS09. Further the strong convexity assumption needed by Theorem is satisfied with k = max
1 This 7-1
is because for any p > _ 11:-1 is (p 1)-strongly convex w.r.t. ||. ||p [Bc 17..
Private Algorithm Satisfying Relative Accuracy, To apply Theorem 1 we must construct an algorithm satisfying relative accuracy and (e, 0)-D. For this, use the stochastic mirror prox algorithm of [NTII] Algorithm 2 This algorithm will also have application in our analysis of SVIs later on.
Algorithm Stochastic Mirror Prox
Require: Learning rate Operator oracle O, Initial point zo E Z, Regularization function vp minimized 2y, Iterations T
1: for t = =.... .T do
2: & = arg min (v² + (70(2-1) V(((a))) u)} = arg min {w(u) + (1)(2) (
3:
4: end for
5: SSP output: +Σ
6: SVI SVI output: 21- for t" Unif((T])
This algorithm takes as input stochastic oracle for the saddle operator of O, and a strongly convex regularizer, tb. We leverage this algorithm by constructing a differentially private version of the operator oracle O, and taking as output the average iterate 2 ΣT_ 2t. We make the oracle private by adding Gaussian noise to minibatch estimates of the saddle operator. show the whole algorithm is private by composition results and the post processing properties of differential privacy. We defer these details to Appendix C22 and here state the final relative accuracy bound.
then easy to
7

---

Algorithm 3 Recursive Regularization for SVIs: RsvI
Require: Dataset S, monotone operator g, Subroutine Aemp, regularity parameter > 0, regulariza-
tion parameter 2 LvfE
Byn constraint set diameter B, Strongly monotone operator
1: Let n' = n/ logz (n), and = log,( x.B.
2: Let Si, Sr be a disjoint partition of S with each St of size n' (always possible due to the condition X)
3: Zo be any point Z
4: Define function (2,z) + ggggg 11) (2:x) g(2;2) +2 p(z Eu)
5: for t = 1 to T do
6: Σ1 = Aemp (Se, (0 1:
7: Define function (z, x) + ( = (z;z) + 2 p(z - 2x)
8: end for
9: Output: 2T
Lemma 3. Under the setup described above, there exists 8e,8 algorithm which sat-
isfies â-relative accuracy with parameter â = =0 - BgT (1)o)(1/6)R
ne
and runs in O( min
S 3/2
}) number of gradient evaluations, where Rc
lo) /dlog(1/08 log (/))
1 1+1 2V 2} log(d).
Main Result for DP lp/Lg SSPs. Applying now the result of recursive regularization, Theorem 1 obtain the optimal rate for ep/ee SSPs (up to logarithmic factors). Recall under our chosen norm that B < 1 and L < 4B, L + L3. Further, the privacy of Algorithm I follows from the privacy of Aemp and the parallel composition and post processing properties differential privacy. Corollary 1. There exists an Algorithm, R, which (e, O)DP, has number of gradient evaluations 2/2 }), and satisfies (up to log(n) factors),
bounded by O (min log(n) (
Vlug(n)
Gapsp (R) = (0000 2.5
B2 12 + B3 Vdlog(1/0){
1 )
(K is at most log(d)))
Note that in the l2/ f2/bg-setting x = and the above exactly recovers the result of [GM233] We further recall that the near optimality of this result is established by existing lower bounds for stochastic minimization, which is special case of SSPs [BFTTI9 BGN2I]
5 Extension to Variational Inequalities
In this section, we start by discussing the modifications that must be made the recursive regulariza- tion algorithm to handle the more general structure of SVIs. We then discuss key ideas in the analysis and how to apply the algorithm SVIs in the lp setting. We recall that we here assume the operator g is monotone, L--bounded and L-pischiit
5.1 Recursive Regularization Algorithm for SVIs
Algorithm 33 bears many similarities to Algorithm | Most notable among the differences is that here regularize with a strongly monotone operator p instead of a woongglycoovex//toonlyyooooooe function. In our eventual application we will use p v [|²), but strictly we only require that p satisfies the following.
Assumption For K > 0, p: Z d is stronglly monotone w.e. || and satisfy [|p(=)]|+ < ||=|| for all 2 E Z.
When p v 12). the second half of the condition always guaranteed by the properties the
dual norm (see Fact 2) When satisfies Assumption I obtain the following guarantec.

---

Theorem 2. Let Aemp satisfy â-relative stationarity for any (5L)- monotone operator and dataset of size n' Tog(n)' Let p satisfy Assumption subroutine and X âxd + (0B+L)n2) satisfies
Then Algorithm
7
run with Aemp as
Vi
log log 2/gg/((n) (n) L)n²
Gapvi(Rsv) = O (og(()) +
vn
The full proof is in Appendix B.2
We discuss the key ideas in the following subsection.
5.2 Analysis Idea
Unfortunately, the analysis used for stochastic saddle point problems does not easily extend to variational inqqualities due to the fact that the VI-gap and ga-gap behave in fundamentally different ways. Even though SSPs are special case of SVIs (when the operator in question is the saddle operator of the loss function), a bound on the VI-gap does not imply bound on the SSP-gap. Further, natural attempt to extend the notion of relative accuracy (Definition 3) to SVIs by asking Aemp to bound (GD(2š), A(S) =3) does not work, because such term does not yield an upper bound on the distance |AA(S) agll. A similar problem holds for generalization measures in Eqn. (6)
New Empirical Accuracy Measure. Motivated by the above issues, we introduce new relative accuracy measure for our analysis of SVIs. Importantly, this notion will allow us to bound the distance between the output of Aemp and the empirical equilibrium point of the strongly monotone operator created at each round of the recursive regularzation algorithm.
Definition 3 (á-relative stationarity). Given dataset S E X" operator g', and initial point z', we say that Aemp satisfies â-relative stationarity w.r.t. to the empirical equilibrium als of (2)(2) = + Evesi z'(z;z), if. vD > 0, whenever E [||2' -2g S D, the output 2 of Aemp satisfies ( 23/i1 ( Dá.
Modified Generalization Measure. The generalization measure can be modified in similar fashion.
Let g(2;x) (1 + 92(2) such that 91 x X' Rdd is L-bounded and B- Lipschitz with respect to and 92 Z Rd is any (data indepedent) operator. Let z" E Z be its population equilibrium point. For any x E X, define h(2;x) (g(2;z),= 2²). For S ~ D", let Hs(z) Eves 122;x) and Hp(z) E [h(2z))] Then for any UAS algorithm, A, one has I~D
Lemma 4.
E (H)((()) Hs(A(S)) S ABBB L.). S.A
The proof is similar to that of Lemma 2 but must account for additional complications. First, the function h may not be Lipschitz. if the regularizer, represented by 92 above, is not Lipschitz. the stabilityiimplies
This happens, for example, in the l setting. Thus, we must decompose generalization analysis and handle the non-Lipschitz, but data-independent, term 92 separately. Then, the Lipschitzness the remainder is established using that fact that øi is both bounded and Lipschitz. The full proof is in Appendix D.I
5.3
Application to DP variational inequalities in the lp setting
In order to apply Theorem 2 to SVIs with an Ep setup, we pick || ||-||= =1>1= where ø max(p, 1 We will use the regularizer,
1
log(d)
1
p(z) v()=v(222 2B ll=1)))
Note the above operator is uniquely defined since > 1, and thus || 113 is differentiable (Gui09 - To this, first observe that
This choice of p satisfies Assumption with parameter
In contrast to our results on SSPs, rescaling by 1 is not necessary in this case, but we do so to maintain consistency.

---

for any p > 1, b11 1 is (5 ( 1-5-1)-stn strrongly convex w.r.t. 11 and the gradient operator of differentiable p-strongly convex function is je-ttrongly monotone. Second, for any norm and it's dual || I ||=|| for all = (see Fact 2 in Appendix
To obtain relative stationarity guarantees, oracle for the empirical operator Gs. The proof falls out of our existing analysis for stochastic mirror prox given in Appendix C.2 Specifically, Theorem 4 in the case where θ the empty set implies there exists an (e, (-DP implementation of mirror prox which satisfies â-relative stationarity with
again apply Algorithm 2 with differentially private
à = 0 /RBLydlog(L/01C nE
(p < 2) log(d))
VRBL)
vn2
We here highlight one notable difference that arises with the algorithm. Typically, after running an algorithm like stochastic mirror prox for & iterations, one obtains bound on the quantity
(G 4 - =)} Analysis then proceeds to bound the (empirical) VI-gap of the average iterate by leveraging monotonicity the operator. However, this application of monotonicity does not help for the purposes of relative stationarity. For this reason, we instead select an iterate uniformly at random. We note this step nonstandard as such a selection does not necessarily yield any bound on the (empirical) VI-gap.
Main Result for C, DP SVIs. Using Algorithm and the implementation of Aemp described above, we ultimately obtain the following result as a corollary of Theorem 2 and Theorem 4 Recall under our choice of norm we have diameter bound and operator bound BL. Further, we can leverage existing lower bounds to show that this rate is near optimal: more details are available in Appendix E
Corollary There exists an Algorithm, R, which (c. 6)-DP, has gradient evaluations bounded by 2 vkn2/2 }), and satisfies (up log(n) factors) O( min (oo Vlog(n)
Gapvi(R) = 0(13'0 (log(1/0){
(8)
where K.
is at most log(d) and R = 1 1 2} log(d).
max
logta
Near Linear Time Algorithm for the & Setting. Because we assume the operator Lipschitz, in
the E2 setting, we can leverage existing accelerated optimization techniques to achieve a near linear time version Aemp. in a similar fashion [ZTOH22 BGM23]. Specifically, using the accelerated SVRG algorithm of [PB16] and Gaussian noise it is possible to obtain the rate in Eqn. (8) (with 1) in On + Bn (og(n/)) gradient evaluations. We provide full details in Appendix D.3
Acknowledgments and Disclosure of Funding
R. Bassily's 's and M. Menart's research was supported by NSF CAREER Award 2144532 and, in part, by NSF Award 2112471. C. Guzmán's research was partially supported by INRIA Associate Teams project, ANID FONDECYT 1210362 grant, ANID Anillo ACT210005 grant, and National Center for Artificial Intelligence CENIA FB210017, Basal ANID.
References
[ABD+ 18] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach fair classification. In Jennifer Dy and Andreas Krause, editors. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Pruceedings of Machine Learning Research, pages 60-69. PMLR, 10-15 Jul 2018.
[ACG+ 16] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. CCS '16, page 308-318, New York, NY, USA, 2016. Association for Computing Machinery.
[AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates & geometry. In International Conference on Machine Learning, 2021.
10

---

[AZ18] Zeyuan Zhu. How to make the gradients small stochastically: Even faster convex and nonconvex sgd. Advances in Neural Information Processing Systems, 31, 2018.
[Bau58] Heinz Bauer. Minimalstellen von funktionen und extremalpunkte. Archiv der Mathe- matik, 9(4):389 393, 1958.
[BE02] Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[Bec17] Amir Beck. First-Order Methods in Optimization. SIAM-Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2017.
[BFTTI9] Raef Bassily. Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Pri- vate stochastic convex optimization with optimal rates. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Con- ference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1179--1228, 2019.
[BG23] Digvijay Boob and Cristóbal Guzmán. Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-poin problems. Mathematical Programming, pages 1-43, 2023.
[BGM23] Raef Bassily, Cristóhal Guzmán, and Michael Menart. Differentially private algorithms for the stochastic saddle point problem with optimal rates for the strong gap. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2482-2506 PMLR, 12-15 Jul 2023.
[BGN21] Raef Bassily, Cristobal Guzman, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. In Mikhail Belkin and Samory Kpotufe, ed- itors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 474-499, PMLR, 15-19 Aug 2021.
[BST14] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimiza- tion: Efficient algorithms and tight error bounds. In IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS 2014). (arXiv preprint 1405: pages 464-473. 2014.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265 284. Springer, 2006.
[DSL + +8] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. SBEED: Convergent reinforcement learning with nonlinear function ap- proximation. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1125-117 1134. PMLR, 10-15 Jul 2018.
[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.
[GGP24] Tomás González, Cristóbal Guzmán, and Courtney Paquette. Mirror descent algorithms with nearly dimeension-indeeendenn rates for differentially-prig stochastic saddle-poin problems. CoRR, abs/2403.02912, 2024.
[Gui09] A Guirao. Uniformly convex functions on banach spaces. Proceedings of the American Mathematical Society, 137(3):1081-1091 2009.
[JKT12] Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In 25th Annual Conference on Learning Theory (COLT), pages 24. 1-2.34, 2012.
11

---

[JN19] Anatoli B. Juditsky and Arkadii S. Nemirovski. Signal Recovery by Stochastic Optimiza- tion. Automation and Remote Control Avtomatika Telemekhanika, 80(10):188--182, October 2019.
[NTTI]] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic pirror--poxx algorithm. Stochastic Systems, 1(1):17 58, 2011.
[JT14] Prateek Jain and Abhradeep Thakurta. (near) dimension independent risk bounds for differentially private learning. In ICML, 2014.
[KLL21] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in subquadratic steps. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 4053 4064. Curran Associates, Inc., 2021.
[LYYY21] Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generaliza- tion of stochastic gradient methods for minimax problems. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6175-6186. PMLR, 18 24 Jul 2021.
[MSS19] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4615-4622 PMLR, 09-15 Jun 2019.
[NJLS09] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and And Shapiro. Robust stochastic approximation approach stochastic programming. Society for Industrial and Applied Mathematics, 19:1574-1609, 01 2009.
[NMG24] Quan Nguyen, Nishant A. Mehta, and Cristóbal Guzmán. Beyond minimax rates in group distributionally robust optimization via a novel notion of sparsity, 2024.
[NY78] Arkadi Nemirovski and D Yudin. On cezari's convergence of the steepest descent method for approximating saddle point of convex-concave functions. In Soviel Mathematics. Doklady, volume 19, pages 259,269, 1978.
[OP7722] Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. What is good metric to study generalization of minimax learner?? In Advances in Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2022.
[Pan08] Liam Paninski. A coincidence- test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory, 54:4750-4755, 2008
[PB16] Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for maddle-point problems. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[SG122] Tasuku Soma, Khashayar Gatmiry, and Stefanie Jegelka. Optimal algorithms for group distributionally robust optimization and beyond. arXiv preprint arXiv:2212.13666 2022.
[Sio58] Maurice Sion. On general minimax theorems. Pacific Journal of Mathemticc, 8(1):171 176, 1958.
[TTZ15] Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Nearly optimal private lasso. In NIPS, 2015.
[WM19] Robert Williamson and Aditya Menon. Fairness risk measures. International Confer- ence Machine Learning, pages 7796. PMLR, 2019.
12

---

[YHL #2] Zhenhuan Yang, Shu Hu, Yunwen Lei, Kush R Vashney, Siwei Lyu, and Yiming Ying. Differentially private sgda for minimax problems. In James Cussens and Kun Zhang, editors, Proceedings of the Thirty-Fighth Conference on Uncertainty in Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pages 2192- 2202. PMLR, 01-05 Aug 2022.
[YLMJ22] Yaodong Yu, Tianyi Lin, Eric Mazumdar, and Michael I. Jordan. Fast distributionally robust learning with variance reduced min-max optimization. AISTATS, 2022.
[ZB24] Xinyu Zhou and Raef Bassily. Differentially private worst-group risk minimization. CoRR, 0ts/2402.114377 2024.
ZHWZ21] Junyu Zhang, Mingyi Hong, Mengdi Wang, and Shuzhong Zhang. Generalization bounds for stochastic saddle point problems. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 568-576. PMLR, 13-15 Apr 2021.
[ZL15] Yuchen Zhang and Xiao Lin. Stochastic primal-dual coordinate method for regularized empirical risk minimization. In International Conference on Machine Learning, pages 353-361. PMLR, 2015.
[ZTOH22] Liang Zhang, Kiran Koshy Thekumparampil, Sewoong Oh, and Niao He. Bring your own algorithm for optimal differentially private stochastic minimax optimization. In Advances Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2022.
[4ZZ+24a] Lijun Zhang, Peng Zhao, Zuen-Hua Zhuang. Tianbao Yang. and Zhi- Zhou. Stochas- tic approximation approaches to group distributionally robust optimization. CoRR, 2024.
[777+24b] Lijun Zhang, Peng Zhao, Zuen-Hua Zhuang, Tianbao Yang, and Zhi-Hua Zhou. Stochas- tic approximation approaches to group distributionally robust optimization, 2024.
A Supplementary Lemmas
Fact 2. For any 2, it holds that [|V(||== < |=|||
Proof. By the chain rule we have =11 = ||||| (I]==] and so | = ||||| [[= Thus, only remains to show that |V[I= < 1. By the definition of the dual norm we have || [[]=))] = max [[V([I=]), e) Further, by the definition of the subgradient we s:
have for any z' that ||a||| - || Z (V[[==])), 2). Substituting v = - 2, we have
(V[I=)))) < ||u 2|| - || < ||^|| + ||||| |||||| ||a||| - 1,
as desired.
Lemma 5. Let p. X > O and be p-sttrongyy monotone w.r.l. ||. Then for any point zn E Z, the algorithm which outputs the unique equilibrium of Gs(z) + (p(z) p(zo)) is (ax ( -uniform argument stable w.r.t. S.
Note without loss of generality we can always choose 2p to be the point such that p(=)) = 0, which guaranteed to exist since p strongly monotone. Thus this result also holds for regularization of the form Gs(z) + À p(z). Further, since the saddle operator of a strogllycomvee/&tronlyyooooo loss strongly monotone, and the resulting SSP shares equilibrium point with the corresponding SVI. Lemma given in the preliminaries is also established through this result.
13

---

Proof. Let 2 and z denote the equilibrium points of the regularized operators w.r.t. to adjacent
datasets S and S" respectively. By the equilibrium condition we have for any & E Z
(Gs(zx) + Mp(za) - p(zo)); 2x) 2 0
(Gs + (l(zz() - -(zo)), - x11 2 0
(Gs(zx) (z) + N[((z)) -(<\))=>' - =A) 2 0.
Since p is 1-strongly monotone operator we have (Gs(zx) (z), 21 - 2x) 2 A (p(z)) - p(z)): 22 - -z1 2 2xllla - =111..
Now
the monotonicity of G to derive,
μAl|zy - xX12 < (Gs(z>) - (z)())) - ox)
(Gs(zx) - Gs-(s)), - =x) + -GGs(eN)- - 2x)
(Gs(zx) - (zx),,), -2x)
(0)
[[Gs(z>) - (x))l) || zxll
(40) 2L
11 - -x
n
Above (i) comes from the monotonicity of G. step (ii) comes from Hölder's inequality, and step (idi) comes from the fact that S and S differ in at most one point. Simple algebra now obtains ||Ex
x1I S pAn'
2L
Fact 3. There exists differentiable convex-concave loss, distribution D, and point z! such that when the operator is the saddle operator of the loss, Gapvi(z) < Gapsp(z).
Proof. We show that the VI-gap is upper bounded by the excess risk of some convex function with operator g(=) = f=). Since stochastic convex optimization is special case of SSPs, this shows there exist scenarios where Gapsp L Gapvi. Specifically, when the dual player space singleton, the SP-gap becomes the excess risk.
Let (z; a)) 22 be defined over E [0, 1). and it does not matter what the distribution or data domain is. Note that Gapvi becomes
Gapvi(=) max ((Vf(), u)} = max {2uz 2u²} wE[0.1]
WE (,1)
Note that in this case the SP-gap is just the excess risk, Gapsp = 2² minze(o.11 {22] 22.
Consider the point 1. It is easy to show that Gapvi(1) = 0.5 but Gapse (1) 1, proving the claim.
B Missing Results from Section
B.1 Proof of Lemma 2
Lemma 6. (Restatement of Lemma 2 Let f 2 + R be L-Lipschitz Let [w*, 0-] E Z be the population saddle point. For any a E X define h[[w, 0]: = f(w, 0z;z) f(w", 0;x).. For S ~ D", let Hz(z) = : Exes h(2;; x)) and Hz(z) = E [h(=;z)]] for any UAS algorithm, END
A, one has E [HD(A(S)) - Hs(A(S)) S 2AL. S.A
Proof. This result follows simply from two facts. First, because ff is an L-Lipschitz function for any I E X, we can show that is L-Lipschitz. For any [w, 0), [wo', 0 E Z observe,
h[[w, 0)) h[w',, 8'T)
[w, ;x) f(w", 0(=)] - [f( ,0 -f(w", ,'';
= f(w, 0²;z)) f(w', 00;z)) + f(w", ,0::))
- 2L I|w, 0 - [w'', 0711-
14

---

The rest of the proof essentially follows from the stability implies generalization proof of [BE2 since HD and Hs have a statistical form w.r.t. h. In more detail, for any E [n]] denote S as the dataset which replaces the i'th datapoint of zi, with fresh sample from D, x'. We have the following:
E (H((S)) Hs(A())) = E 3
S.A B(((A(S):
[Ih(A(():)))
DES
E
(A(A(S()):)) M(A(S):
S UnUnnf(()]))
E }
M(A(5;; x.)
< E - < 2LA.
The last step follows from the previously established Lipschitzness property of h.
B.2 Convergence of Recursive Regularization for SSPs
We will first prove the following more general version statement of Theorem 1
Theorem 3. Let X
2
Lx2 and Aemp be such that for all t E [T] it holds that
Byn
Then Recursive Regularization satisfies 2 - 23.ell x777
Gapsp(Rssp) 0 (log(n)B22)
To prove this result, will be helpful to first show several intermediate results. We start by defining several useful quantities. Define {Fr} as the filtration where Fr is the sigma algebra induced by all randomness up to &. For notational convenience we denote f(0 (w, 0; x) fww, 0; x). Then for every 1 {0, 1,,,..,,,,, ..., T} we define
[w, 0,] saddle point of FT! (w, 0) == E anD
(w,,
S.. = [ws,er 05,1 saddle point of F (w, 0) = 1 n 1! ([w, 0]) r (w, 07) ( (wi 0) the relative accuracy function w.r.t. the popula- tion loss and population saddle point; and,
Exes, (w,
H ([w, Ol) := Fo(() (w, 07) - (0(() (wf, 0) the relative accuracy function w.r.t. the empiri- cal loss and population saddle point
We recall the generalization properties of ( and H shown in Lemma 6 Crucially, the power of H(()) that it bounds the distance of a point to =7.
Fact 4 ([ZHWZ1]) Theorem 1). Let F 2 R be S-SC/SC function and let [w*, 0*) be the saddle point. Then [w, 0] [w", 11 2(F(w,00)- F(O" .n))
We now establish two distance inequalities which will be used when analyzing the final gap bound in Theorem 3 The first inequality below bounds the distance the output of the t-th round to the equilibrium of G The second inequality bounds how far the population equilibrium moves after another regularization term added.
Lemma 7. Assume the conditions of Theorem hold. Thenfor every I [T), the following holds
P.I E [| - - ||
z < 2 and,
P.2 := := - 1 2 E
|| 2 _1]?²]
B² <
22(1-13.
15

---

We note that in contrast to [BGM23] and other analyses of recursive regularization, we define Property
P22 to bound E [| 2 instead of EE 2| 2-111l. In [GGM33]. the latter choice led
need to bound E Gapsp(2r-1 for all E [T], which our analysis avoids. In particular, one can
observe how the derivation of Eqn. (11 in the proof changes when =/-1 is replaced with 2t-1-
Proof of Lemma 7 We will prove both properties via induction on Bi...., Br. Specifically, for each t [T] we will introduce two terms E, and Pr.. and show that these terms are bounded if the bound on B, holds and that B₁ holds if Et-1 and F2- are bounded. Property P.I is then established as
|| =;1]]] x 2 + Ft). Note that B₁ holds as the base case because
result of the fact that E
E |
=61? < B
Property fort E
P.1
We here prove that if B, is sufficiently bounded, then Eg and F; are bounded where we define
E = =
E
| =5. =s
E H 1 F,
(25.:)
(9)
2
Additionally, this will establish property
P.1 because for any E [7] it holds that,
E -112-=211
s =
E
&
=š.ell
+ E
|| - =7 1
2
E
23.
K
D
(2
(10)
2
E
Fi
The second inequality comes from the strong monotonicity of the operator (see Fact Note that E, is bounded by the assumption made in the statement of the theorem statement. We thus turn our attention towards bounding Fe. We have
E 2
H (1)
(25.))
E
H
(6) (=5,) Fi-1]
2
(4)
K
(=$.)
[F-1I] 1]
KL?
2cA
2 Xm
E
E
(t) (w 07) F (w 0z Fo-1
[c-1] +
2nL2
2'A
2
(8)
2k
L
B²
2 Xm
1152 2
Ingeuality (i) comes from the fact that stability implies generalization for (t), Lemma Note the 1,2 algorithm which outputs this exact equilibrium point is प stable (see Lemma 5 Assumption
Step (di) uses the fact that =5,, is the exact saddle point of the regularized objective, and so for any
[w, 0) E Z, (()) (wis 0) F (w, 0z,) < 0. The final inequality uses the setting of X.
We thus have a final bound 2(E, + F.) S
n² n
Property P2
Now assume B,-1 holds. We have
16

---

E
1|
z/_1 [|]]
E
(0) (2i_1)
2
F (wi-1,
(wi, 02 1) 1, 0,) 1/-01// (wt;
2
1) (wi (1 07) F (w 07- 07-1)
2
+ k (1|w w4 -l - 110, 01-1110 l 1| - 12 + 110, - 0
B [x 11
(11)
Inequality (1) above comes from removing negative terms and the fact that =i-1 is the saddle point
w.r.t. P p(t-1). 1)_ Using the induction argument we then complete the bound with the following:
B²
E 2 2ل 11]] - E | 2-1113] s < K(E + Fi-1) 1
2
We now turn analyzing the utility of the algorithm complete the proof.
proof of Theorem
Using the fact that Gapsp is 22--Lisschitz and property P.1 we have
E
(2psp(2T) Gapsp (27)
$ 22L -| - 21
V2BL 2T S V2B²2.
(12)
What remains is showing E
Gapsp (wi,, 07)) is Ō ÕBBa + BL). Let w arg min arg ED(W, 07.) and
0' = arg max FD (n 0). Using the fact that FD is convex-concave we have wEW
Supsp(wpr 07) = Fo(w7, 0²) - FD(w'00)) < (Go(wī, 07), [w7. 07l - [w',0')
(13)
where GD is the population loss saddle operator. Further by the definition F(T) and denoting G
the saddle operator for ro)7 we have
Gr(wr, 67) = (wi. 07) 2A
2 V (1] [ 07] [w/, 0,]1
Thus plugging the above into Eqn.
13 we have
Gapsp 07, <
(T)
(wi, 07), [wi 071 - -Iw', (w',01)
21
2 V V (1| 07] [we, 0.]112), [wir 071 - -[w', .1)
1=
T-1
21
2
v(1wg 07] [ 0.]112), (wi. 07] - [w0' 01)
1=
T-1
<
2BX
Σ
21+1
[[] 071 - |wr, 0.]113|11
V
2BA
Σ
2++1
||
07]
[w,, 0.]
1=
Above, the second inequality comes from the first order optimally conditions for [wi., 07). the third from Cauchy Schwartz. and a triangle inequality. The last inequality comes from the relationship between norm and its dual, see Fact 2
17

---

Taking the expectation on both sides of the above we have the following derivation,
E
Gapsp (wi,, 07)
x 2BE
2+1
[wi, 0r]
-[wr, 6.11
(9)
T-1
T-1
4BE
2'
|| 00]
[wx, 0:]1
|ut++,, 0++1] -Iw7, [
4BB
2 || [5] -[wr, 0c]1 + A
2'
|| |[ 0++1] - 0:]
(1) 4BB
2' ||| [mm] 0%] - -wwr, 0c]l + Σ
Σ
2' || [| 0 1
| 0.1
= 4BB
2' | 08]
[wx, 8c]l|
+
|| 0-+1] - [wF Σ 2
(40)
S 4B
A
Σ
2
B
+
T-1 1
B
Σ 2
x-1
2
2
T-U
r=1
2-0
<BB
T-1
Σ 2-0
2
B
T-1
Σ
B
(2" -1)
2
2n-1
T-1
T-1 Σ
4A
Σ
B - 82
B²
t=
< 12
(14)
Above, (i) and the following inequality both come from the triangle inequality. Equality (ii) is obtained by rearranging the sums. Inequality (iii) comes from applying properties P.1 and P.2 proved above. The last equality comes from the setting of X and T.
Now using this result in conjunction with Eqn. (12) we have
Gapsp < + 12T O (Iog(n) B²>) X). Above we use the fact that T = log( 4 and X 2 BV and thus T Ollo((n))
Finally, we prove Theorem |
leveraging the relative accuracy assumption.
Proof of Theorem 1 First, observe that under the setting of A 18
(ān²
L/2/2 Vx
used in the
B
theorem statement that log = O (ongn))as"
lon)
Thus what remains is to
vn
show that the distance condition required by Theorem 3 holds. That is, we now show that if Aemp satisfies â-relative accuracy, then for all & E [7] it holds that E
[||= 11
Ba
12-2-6
To prove this property, we must leverage the induction argument made by Lemma 7 Specifically, to prove the condition holds for some E [T]. assume B3- = [||= - = < 2 (recall
the base case for I. = trivially holds). As shown in the proof of Lemma this implies that the
quantities Et, Fe (as defined in are bounded by 1152-2 We thus have
B²
KE F (we, 03,,) - F (WS,.: B.)
(ii) 2k (N)
B
E 3[12
(15)
2'
22
12
12
where B, is as defined in property
P.2 Inequality (i) comes from the strong monotonicity of G
Fact 4 Inequality (iii) comes from the setting 2 48dx2 2 Inequality (ii) comes from the â-relative accuracy assumption on Aemp. which holds long as the expected distance is sufficiently bounded and each regularized loss is (5L)-Lipschitz. In this regard, note that
E [| 2 11]
< E [||=3,- - 2 ll + || ال-1ج + | - 2, 2--1]]
B
s (v F + + E, + / F < 2t
18

---

Further, each f(() is 5L-LLisschite We can see that,
max =EZ
Vf (2, S
2 =|1l)|1~
S
Σ B2 S L 4B2 X S 5L.
C Missing Results from Section
C.1 General Guarantee for Stochastic Mirror Prox
We start with the follow general statement regarding the stochastic mirror prox algorithm applied to monotone operators. Notable for our purpose of solving SSPs is that the saddle operator of convex-concave function is a monotone operator, but the following holds for any monotone operator.
Lemma 8 (Implicit in (NTII], Theorem 1). Let t Z R be any non-negative function which 1- strongly convex w.t.. |1-1|. Assume VI E [T') that E [z)z)] = G(zz) and E [z]((z) G(=))l=] < 72.
Then for for any z E Z Algorithm satisfies
T
E [xb(2)
E
1
Σ 1=1
(G(2),, - 2) =0 -0 Tn
7n (L² (L2 +272)
T
2
The above is slightly different than the statement in [NTII but be easily extracted from their proof. Let Vi denote the Bregman divergence w.rt. tb; i.e. Vo(2, ((2) v122)
(Vv(='), ='). Under our assumptions [JNTI]] Eqn. (80)] gives
(G(x), 2 -2 x) 0 Tn Σ
E (2, zo)l
TT (L² + 27²)
E
Note that since 2o is the minimizer of th, we have V2 20) S (b2).
Before proving the relative accuracy guarantee of stochastic mirror prox, also restate the following composition result for Gaussian mechanism known as the moments accountant.
Lemma 9 ( 16 KLL2I). Ler e, 8 E (0, and e be a universal constant. Let y" be dataset some domain Y, and let h1 .... hr y + Rdd be series of (possibly adaptive) queries
such that for any y y, I E [T), [[le(y)]l2 < L. Let 2 cL./Tlog(1// and T 2 5 Then the algorithm which samples batches of size BI.... B, of size b uniformly at random and outputs EyeB, he(y) + gi for all t E [T] where Dr ~ N'0 I2o"), ), is (e,5)-DP.
C.2 Proof of Lemma 3
Lemma 3 is easily established from the following theorem which holds more generally for any mono- tone operator (rather than just the saddle operator of a convex-concave function). This generalization will allow to this theorem again in our results SVIs.
Recall we consider the norm [[[,,, 0]1 BZ
1
|012 and have defined k = max --
and A = 1 + 1 (p 2 V q < 2} log(d). For any t E {O..., T) define [wy, 0g] = 21, where 2, is as We have the following.
given in Algorithm 2
Let g W + x Theorem 4. Let (wo, 0o), [w, 0) satisfy E [l[ 0o] [w, 0]] D.
Pl-llp (BoLw) f1 (BoLs) be monotone operator and Gs(w, 0) = + Eves g(w, 0); There
exists an implementation of O such that Algorithm 2 is 8)P and the following holds
1
E (KGS((uu=,,0)) [we-; 01-] [w, 0)} = E
(Gs([wr, 0z]), [we. Oz] [wu, 01)
T
=0 D B2L2 B3L3
VRV d log 1/5)
K
19

---

Further, the resulting algoritim makes O min tions.
V
SFn log log"/2(m) })
gradient evalua-
(n)
Before proving this statement, we first quickly show how to obtain Lemma guarantee for SSPs, using this result.
3 the relative accuracy
To obtain Lemma 3 from this statement, observe that the special case where is the saddle operator of the loss, f. convexityconncavity implies
Proof of Lemma 3
E
W/, w)) - F(O, T t=1
Σ
0.)
S
E
Σ t=1
(GD(z,), 2)
T
t=1
and Lemma is is thus obtained from the bound in Theorem
All that remains is to prove the above theorem. Note the following proof leverages the structure Z = Wx x O, but does not assume that g is the saddle operator of some convex-concave loss.
Proof of Theorem Let L L + L and let p"
P and o' 4 be the conjugate --r
q-I exponents of p and q. respectively. For E [T] denote the result of O(z) as (V We Va.e] such that V.,t E Rdw. and Va. RRdo
We consider the following construction of the private operator oracle, O, for Gs. Our implementation adds Gaussian noise minibatch estimates of Gs. That is, to evaluate Oz)), uniformly sample minibatch of size m max { , 1]. call it M,, as well Gaussian noise vectors Sw.t ~ (0, Id,, oi and Ee. NO( Ia, oz), for some ow 0o O. We then have that
1
g(we, 0r; + [S E0,e-
m
M
Privacy Bound: We first bound the privacy of Algorithm 2 Since for any u, ||u||2 S Vdl-2/p" | /ulppe
we can bound the privacy loss using the guarantees of the moments accountant, Lemma 9 Specifically,
we set T = 16 min n1 2og6(1/8
n²²²
TVT use minibatches of size m = max /"V F. }. and
set oer cB.,, Lo /
log(1/5) and ag
cB T44 ne
2/1" log(1/8) for some universal constant
It can be verified this scale of noise satisfies the conditions of Lemma and thus ensures (e, 0)
nhe
Utility Bound: We now establish the convergence guarantee by applying the general convergence
guarantee of stochastic mirror prox (Lemma 8 Appendix C.I) with ((w,, 0)) = 2 w|1 28
x
2Bg |0]|
which is 1-strongly convex w.r.t. || |]. Clearly our saddle operator oracle yields unbiased estimates of (z(z) (z) at each iteration. To bound the variance, note when * 2 the private estimate of V V..t satisfies
2 2 L2 log ( 18)) log(d) n²²²
[[|V m1t vw 0.)1
d2/p [1.. s d2/p" of log(d) <
When 2, then p² 2, and one can replace bound (i) with E [1 Combining these cases
yields bound of BB Td. log(1/8) on the variance of V w, A similar analysis holds for Ve,r- a²F²
Ultimately, with respect to the norm chosen above, we get E [z]((z)) - G(=)) s 7² with
7² (B + BBL3) (1
@Tdlog(1/5)6 = k).²x). n²e²
The last equality uses the fact that x 2 1. Recall we choose (ww 0))
a 28
Im + 283 1101 and
thus d(w,, f)) = xe][we, 12 Now the guarantees of Lemma imply
xD² Tn The theorem statement now follows from plugging in the parameter settings of T and y and the bound on established above.
E ((((s(z)) ), 2)) E
Σ
T
(Go(z),, =
+
7t (I. + 27
T
D
20

---

D Missing Results from Section
D.1 Proof of Lemma
Let h1 (z) = (g1
(2) 2), 2²). First, we observe that hı is (3B + Lipischhi To see this, we have for any z' Z and that
(g1( 2n) - (9) (2'22)), )²), - = (g1(z) - g1(2)) + 91 --)
2²)
= -(n(==) - (=)),====))))))))))) (=)(=")===>))
S (BB + 1)||= -
The rest of the proof is similar to existing stability implies generalization proofs, but with the additional accounting of the regularization term. In more detail, for any i [n] denote S the dataset which replaces the i'th datapoint of S, z₁ with fresh sample from D, x'. We have the following:
E HD (A(S)) - Hs(A(S)))
S.A
(1 - - ",Enn 922)) -z') }
E
S.A
RES
I0i ((() -3-) }1
( (BloI(((S):))) -=²) Σ
E
S.A
FES
Sp (nif((((( (3 ::)) A(S(0) x²) ((1(())))))) 2*)]
$ (BB + ()( - ((5) S (BB + L)A.
The last step follows from the previously established Lipschitzness property of f1-
D.2
Convergence of Recursive Regularization for SVIs
In this section, we define L 3B + L. Define Gapvi(z) maxy/ 1(='==== ==)}. We have the following fact.
Fact 5. g is L-bounded then Gapvi is L-Lipschitz.
Proof of For any 21, 22 E 2 we have
Gapvi(z1) Gapvi(=2) max ((Go(z), 2)} -max ((Go(z') -
max ((Gp(2), 2) (GD(2), 21 2)}
max ((Go(2), -
< [GD(s)]l.[[a, -22 s L||2] - -1
We recall the assumption made on p. Assumption 2. For some K. > 0 let p 2 + Rdd be z/- -tstrongly monotone w.r.t. - and satisfy [[((z)] S for all Z.
We will first prove the following more general version statement of Theorem 2 which will be useful later.
18 and Aemp be such that for all t E it holds that
Theorem 5. Let A
Byn
E
B² || 23,all < 22
Then Recursive Regularization satisfies
Gapvi(Rv)) = 0( (lg(())
21

---

To prove this result, it will be helpful to first show several intermediate results. We start by defining several useful quantities. Define {Fo as the filtration where F, is the sigma algebra induced by all randomness up to ε,. For notational convenience define go (2; ((2 Then for every t E {0, 1,.,, 7 we define
z equilibrium of (z) E InD
[o
Ss, equilibrium of Gg == 1 n Ezes. (2:
(s) ( ) the relative stationarity function w.r.t. G and af: and,
HH = (3)
the relative stationarity function w.r.t. G and 27
As discussed in Section 5.2 the power of 11 is that bounds the distance of a point to 27. Fact 6. Lel G 2 + _2 be a u-strongly monotone operator and let z" be the equilibrium point. Then ||2 2" 112 -112 < 2(G(
Proof. By strong monotonicity, for any E 2,
- (G(z) G(=*), 2¹) S (G(z), - --)).
The last step comes from the fact that ( (-G(="), 2²) = (G(2"), -2) S since =" is the equilibrium.
We now establish distance inequalities which will be used when analyzing the final gap bound in Theorem 5) The first inequality below bounds the distance of the output of the t-th round to the equilibrium of G(-) The second inequality bounds how far the population equilibria moves after another regularization term is added.
Lemma 10. Assume the conditions of Theorem 5 holld. Then for every E [T], the following holds
P.I E 2| - 2 S E
|| =211²] S
B² 22 and,
P.2 Bi = E 2ل=111
111
= E
|| -=111?
B²
221--13-
Proof. We will prove both properties via induction BI...,, Specifically, for each t E [T] we will introduce two terms E, and F,, and show that these terms are bounded if the bound on B, holds and that B, holds if E and F bounded. Property P. is then established result of the fact that E
|| =[1|²] < (FF + Ft). Note that B₁ holds as the base case because
E
||=
=
< B
Property
P.I
We here prove that if B, is sufficiently bounded, then F, and F, are bounded where
fort E
we define
E, B 25. =5..12]
F. 2 [ (=5.))
(16)
Additionally, this will establish property
P.I because for any E [7' it holds that,
E 1 2
=211?]
s 2
E
||
23 1|
+ E
||
27 11]
< 2
E
||
3
+
K
H D
(z
(17)
2c x
E.
F.
22

---

The second inequality comes from the strong monotonicity of the operator (see Fact 6 Since Fr is bounded by the assumption made in the statement of Theorem we focus on bounding
Fe. We have
E 11 (25.,)
E
(
(23,)) Fi-1]]
2º
2
kL?
K
E
E
H
(ES.))
[r-1 +
2
2 Amn
xi?
K
E
E
(z5,)) 2ss.
24) [T.11]]
2'A
2
R² L
B
22
2304 22
The first inequality comes from the fact that stability implies generalization for H+), Lemma 4 Note the algorithm which outputs this exact equilibrium point is z The second inequality comes from the fact that =5,, is the exact empirical
L uniform argument stable (see
Lemma | Assumption !
equilibrium point of the regularized objective, and for any E 2, (a') (0 (=b,,) =3,0 - =) s 0.
The final inequality uses the setting of A.
We thus have a final bound 2(E, + Fi) S
B² 2
Property P.2
Now assume B
holds. We have
K
G (zi_1) 2--1 =t)]
E
=
<
E
2
X
( (=ī-1) + 2' Ap(z =11 -
E
2
E
K
((l-1)) (2f-1); 2/=1 1..1),2...
- 2 + ni (plzi-s -i-
2
K²
-
IE
||p(z]-1 x0-1))13 + - =1ll0=1 2 1|
2
(0)
1
E
2 211112
1 - 2/
2
Inequality (i) above comes from Young's inequality and the fact that 2i-1 is the equilibrium point w.r.t. G(f-1). Inequality (ii) comes from Fact 2 Asssmpption as follows:
After re-arranging we can continue
B²
E || 2i=11? s B || 2-11133 s (Ex + Fi S
22r
We now turn to analyzing the utility of the algorithm to complete the proof.
Proof of Theorem
5
Using the fact that Gapvi is L-Lipschitz and property P.1 we have
E
Gapvi(Er) - Gapvi
S LE žr 27
BL 2T < B²X.
(18)
Note that because the above is a statement with respect to the unregularized gap function, we do not have to worry about whether or not the regularization term is smooth.
What remains is showing E
[Gapvi (2))
((log(n)B>X) By the definition of G we have T-1
Gr(2) = (z) 2x
Σ
21+ 2 p(z
2,)
t=
23

---

Let x' = arg maxxaaxee /E [GD((=)) 27 z²)}. We obtain the following bound on the Gapvi 07-)
T-1
Gapvi(27)
( (z)) 2 2 +
2A
2 p(= =z))=² - 27
t=0
T-
2A
2 p(z' - -Et), 21
1=0
(1)
T-1
2A
Σ
21 p(2g 2)) 25
1=0
(10)
T-1
S 2BA
Σ
2
110(2) - 2+]l+
1=0
(10)
T-1
W 2BA
2
1| - Zell-
1=0
Above, (i) comes from the fact that 27 is the equilibrium point of G Inequality (it) uses monotonicity of p. i.e. 0 < (p(z7 - 2r) - p(=" žr), z²). Inequality (iid) comes from Holder's inequality and triangle inequality. Finally, (iv) comes from Assumption 1
Taking the expectation on both sides of the above we have the following derivation,
E Gapvi(z (
< 2BE
21+1 ||
=el
(
+ |]
4BE
2 ||
Eell Σ
T
4BE
2 ||
æ. +
2
| - =11|
1=0
T-1r-1
(8
4BE
2' || - all + A
Σ
|
y=0
t=0
T-1
4BE
11
+1
||
Σ 2
0-
(18)
4B
Σ
2
ΣΦ 2
24
T-1
B
B
<B
À Σ 2t
(2" -1)
2
2--1
1=0
T-1
T-1
4A
Σ
Ba + 8A
Σ
B²
t=0
1=1
12T
(19)
Above, (i) and the following inequality both come from the triangle inequality. Equality (ii) is obtained by rearranging the sums. Inequality (fii) comes from applying properties P.I and P2 proved above. The last equality comes from the setting of À and T.
Now using this result in conjunction with Eqn.
18 we have
Gapvi(Rvii = 22B² 12TAB = =0 (log(n))B) B²>)
Above we use the fact that T = log( L BX and A 2
L
and thus T = O(lo((n)).
By
24

---

Finally, we prove Theorem leveraging the relative stationarity assumption.
Proof of Thhorrmm First, observe that under the setting of
B (ax +
Lxs Vnl
used in the
theorem statement that log(n) - (log(n)Bán)) log (n)) Thus what remains is to
show that the distance condition required by Theorem holds. That is, we now show that if Aemp satisfies â-relative stationarity, then for all E [T] it holds that E
| -=3,1
8a 12.2
To prove this property, we must leverage the induction argument made by Lemma 10
Specifically,
to prove the condition holds for some E [T'. assume B E ||| =[=1l]]²
n²
(recall
2
the base case for t 1 trivially holds). As shown in the proof of Lemma 10 quantities E,, Ft (as defined in 16) are bounded by 2301-220-
this implies that the
B² We thus have
(4) <E K
(z.), 28a2)
(20)
2x
(18)
B
E
|| 23,
(20)
2
2 12
2
where B3 is as defined in property
P.2 Incquality (i) comes from the strong monotonicity of G(t)
Fact 6 Inequality (iii) comes from the setting 2 48 B. Inequality (ii) comes from the â- relative stationarity assumption on Aemp- which holds so long as the expected distance is sufficiently bounded and the operator is bounded. In this regard, note that
E [|I=š,- 1|11 - E [||=š, zill +
|| zi=1
+ ||ži_1 -
2B
S (V P. + Br V E + v F(-1)
2
Further, each ( is bL-bounded. That is, observe
max (2, s || +
- Allp(z - 2,)11a $ L Σ
B2 ++ X
x
4 5L.
#E2
R=
k=0
D.3 Near Linear Time Algorithm for SVIs the &g Setting
Because we assume the operator is Lipschitz, in the l setting, we can leverage existing accelerated optimization techniques to achieve a near linear time version Aemp- in similar fashion to [TTH22 BGM23). Specifically, the work [B166] gives the following result for strongly monotone variational incqualities when applying their accelerated SVRG algorithm 3
Lemma 11. (Implicit in [PB16 Theorem 3]) Let B, μ. K > 0 and universal constant. Let
g: 2 x X' Let z be the equilibrium of Gs(2) = Exes g(2; x) + p(2). There exists an algorithm, which in
be monotone and Bipischittz and p + R p-strongly monotone operator.
O(n+ + vik ()) gradient evaluations find a point such that E - =112|
c
We now construct Acmp in the following way. At each round E [T], we use the accelerated algorithm mentioned above to find point such that E [|| 12, <
52 where zš.; is the equilibrium
5L
point of G (=) = #/ E' (2; We then have Aemp output the point Σ, ã + &., where & ~ V(0,Lao7) and SL//2/6
"'n' Using this construction, we can obtain the following result. Theorem 6. Let Aemp be described above. Then Algorithm is OD and when with
48 B
I
2vdlog(2/6)
satisfies
log 3/2 (1)
log log2(n) log((1/))
Gap(Rsvi) =0
Vn
and runs in at most (n + 3n log(n/5)) gradient evaluations.
In the main body of [PB16), the authors discuss only saddle point problems. However, they prove their result more generally for monotone operators. See their discussion in Section 6 and Appendix of their paper.
25

---

Proof. Privacy Guarantee We show that Aemp is (c. 8) at any iteration t E [T] using the stability properties of the regularized operator. Specifically, the exact equilibrium G.g. Now because Aemp guarantees [[] - ] _ (2 ) an application of Markov's inequality implies that with probability at least 1 - 5 that || -,,,,11 (3 (cBe- k)) S
L An Thus by triangle inequality
is (2 >-stable with probability least 1 6. The guarantees of the Gaussian mechanism thus imply Aemp is (e,
Unility Guarantee: We prove the utility guarantee by leveraging Theorem which guarantees log (m)) ( so long as for every
(R) = B2 o
1 E [T] holds that [||E, = 11B S
Baa Note here that under the choice p in Eqn. we
12-2
satisfy Assuption
with 1. We thus finish the proof with the following analysis.
E Et - =5,01 = [11&:1 12 +
1| -3
(8 L
S do +
2'An'
64dL2 1og(2/6)
B²
B
2 22
25 2
12
2
Running Time: By the guarantees of Lemma 11 we can achieve the condition E [[] 23,1122] s
6L made in the description of Aemp by setting K = log (o An Recall I' = log2 KBA
A2
S
Thus the overall running time is Onn @ K Kv) O(n + Bn log(n/0))
#
E Lower Bound for SVIs
The lower bound for SVIs in the & setting was established [BG23] Their technique can easily be extended to other geometries. Specifically, the lower bound comes from two observations. First, for linear losses, the strong VI-gap is equal to the excess population risk when the operator in question is the gradient. Second, the nearly tight lower bound constructions for DP stochastic minimization problems use linear losses.
We establish the first fact more formally here.
Lemma 12. Let f2; (2, and define the operator g(2;x) vz(zz)) I. Then Gapvi(2) = F2(2)- - minuez {Fb(u)}. That is, the strong VI-gap w.r.t. is equal to the ex- cess population risk w.r.t. the f.
Proof. We have
Gapvi(z) max
E [x] , -u)}
L
[x] [x],2)
+ max { ED [a]] --
L>>D
a
= FD(2) min (Fo(u)}. wE2
We now restate the lower bound result of [BGN21] for non-Euclidean setups. Theorem 7. (BBG22 Theorem 7.1]) Let p (1,2) and p" p-1 and Z B1 (1). Let and 0 < 8 < лमसपर and let f(z;z) = {2, x). For any (e, d) algorithm A, there exists distribution D over X = BBI-11,- 1 (1) such that
(p 1)va })
1
S~D",A A FD(A(S) min (Fo(:)) = á max
2E2
/n
ne
26

---

Note that a linear dependence on BL can be obtained using classic rescaling arguments. The two above results (and the result of (BG23) then imply that the strong Vl-gap rate we obtain, Ö BL BLmmxx
1 (e-1)vā] vn ne
}). is near optimal for p E [1,2] when p 1 ((1).
27

---

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

---

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

---

Answer:
[NA]
Justification:
There is no associated code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppi.ccppulli//uuuiu wwwticccguie//eeeeeeeeeii CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
30

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
There are no experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
The thcoretical nature the results means there are minimal ethical concerns.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[NA]
Justification: The theoretical nature of the work means that any societal impact would be very indirect.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No such assets are used as a part of this research.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No such assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No such assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects were involved.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No human subjects were involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "pQ5Gqk5D6w", "reviewer": "Reviewer_mPfo", "summary": "The authors study differentially private algorithms for stochastic saddle point (SSP) problems and stochastic variational inequalities (SVI). The proposed method relies on recursive regularization approach and obtain near optimal rates for settings were the parameters of interest are constrained to be in a bounded \\ell_p ball and p \\in [1,2].", "questions": "I have two main comments:\n\n1. The subroutine $\\mathcal{A}_{emp}$ is never explicitly introduced. Here are some of sources of confusion for the reader:\n-  Is this subroutine the same one in Algorithms 1 and 3? \n-  In line 6 of Algorithm 1 the subroutine takes 4 inputs, none of which seems to be related to privacy parameters ?. However,  in lines 258-258 the authors say that the privacy of Algorithm 1 follows from the privacy of $\\mathcal{A}_{emp}$.\n- The construction of $\\mathcal{A}_{emp}$ in lines 754-757 consists of taking the output of the SVRG algorithm of Palaniappan and Bach (2016) and add Gaussian noise to it? I think the precise SVRG algorithm the authors have in mind should also be presented. Some none trivial adaptations seems to be required.\n\n2. Algorithm 1 requires $T=O(\\log n)$ since $\\lambda\\geq \\frac{K\\kappa}{B\\sqrt{n}}$ and $T=\\log_2(\\frac{L}{B\\lambda})$. However, Lemma 3 requires a much larger number of gradient evaluations of roughly $\\tilde{\\Omega}(n^{3/2})$ to get the claimed accuracy that in turn is also needed in Corollary 1? Essentially the same comment applies to Theorem 2 and Corollary 2.", "limitations": "The nature of this work is theoretical but it is natural to wonder if the methods are easy to implement. Have the authors tried to run any numerical experiments?", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The methods proposed by the authors recover many existing optimal results using different proof techniques. They extend the scope of the existing results with a unified analysis.", "weaknesses": "The paper does not seem to be self-contained. Some important components of the algorithms are not explicitly described, which makes it difficult to verify some of the claims in this work. The authors should include more details in the supplementary materials.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. We will add the following text to the ``Algorithm Overview'' paragraph (line 179), as well as additional comments: \n\n*The saddle point problem defined in each round of Algorithm 1 is solved using some empirical subroutine, $A_{emp}$. This subroutine takes as input a subset of the dataset, $S_t$, the regularized loss function for that round, $f^{(t)}$, a starting point, $[\\bar w_{t-1}, \\bar \\theta_{t-1}]$, and an upper bound on the expected distance to the empirical saddle point of the problem defined by $S_t$ and $f^{(t)}$. The exact implementation of $A_{emp}$, Algorithm 3, will be discussed in the next section. Here, we focus on the guarantees of Recursive Regularization given that $A_{emp}$ satisfies a certain accuracy condition.*\n\nAdditionally to your other points:\n\n- Yes, we state in the paper that we use Algorithm 3 for the subroutine when discussing both SSPs and SVIs; see lines 241-244 and 321.\n- The subroutine does indeed depend on the privacy parameters when one is interested in implementing Recursive Regularization in a private way. However 1) there may be value in our algorithm/analysis beyond privacy and 2) the privacy parameters do not change for each run of $\\mathcal{A}_{emp}$, and so omitting them reduces cumbersome notation.\n- We can include the pseudocode for SVRG if the reviewer feels it is necessary, but we are unaware of the non-trivial changes being referred to, as we use it as a black box. Note that [PB16] details their algorithm for monotone operators in their appendix, as we state in our paper; see footnote 2 on page 24. \n\n2. Algorithm 1 runs in roughly $T=O(\\log n)$ rounds. Each round uses runs the subroutine $\\mathcal{A}_{emp}$. To obtain Corollary 1, we show an implementation of this subroutine which runs in roughly $n^{3/2}$ gradient evaluations. Thus the overall running time of the algorithm is $\\tilde{O}({n^{3/2}})$ gradient evaluations.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "1Ktc566NJH", "reviewer": "Reviewer_9vNb", "summary": "This work studied stochastic saddle point and variational inequality problems in potentially non-Euclidean cases.  For stochastic saddle point problems, they proposed a recursive regularization framework, and provided the convergence guarantee and sample complexity for convex-concave problems. They further extended the framework to variational inequalities and incorporated differential privacy. Corresponding convergence guarantees and complexities results are also provided.", "questions": "/", "limitations": "/", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. First work on SSPs and SVIs in general non-Euclidean settings.\n2. The proposed rate is nearly optimal", "weaknesses": "1. The boundedness assumption is a bit restricted, regarding many unconstrained problems in practice.\n2. Some important assumptions are hidden in the statement of Theorems, for example, the strong convexity of $||\\cdot||_\\omega$  and $||\\cdot||_o$, while it is not fully rationalized (beyond $\\ell_p, p\\in(1,2]$ case), and it may not be satisfied in some important special case like $\\ell_1$, I think the motivation for non-Euclidean \n3. The paper flow and main results are a bit similar to [BGM23], which makes it a little incremental. Even though the authors claimed some differences, but from the appendix, many proofs are still very similar to those in [BGM23] with minor changes like $\\kappa$. But I agree the changes in some parts like the proof of Property P.2 reveal certain novelty.\n\nTypo:\n1. In Algorithms, the parameters of $\\mathcal{A}_{\\text{emp}}(\\cdot,\\cdot,\\cdot,\\cdot)$ are not clearly defined", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Assuming the parameter space is bounded is very common in SSPs due to the problems unconstrained domains incur. For example, even for simple bilinear losses, say $f(w,\\theta) = \\langle w, \\theta \\rangle$, an unbounded domain means the strong gap is *infinite* at any non-zero point.\n\n2. It is indeed not always the case that $\\lVert \\centerdot \\rVert_w^2$ and $\\lVert \\centerdot \\rVert_\\theta^2$ are strongly convex. However, as we elaborate more in Section 4, this assumption is satisfied for $p\\in[1+\\frac{1}{\\log(d)}, 2]$, where the squared norm is *strongly convex*. Further, for $p=1$ (and more generally, for $p\\in[1,1+\\frac{1}{\\log(d)}]$), we easily solve the problem by instead solving a problem with $p'=1+\\frac{1}{\\log(d)}$, as we describe in Section 4. We will add more discussion after Theorem 1 so that this point does not feel hidden from the reader.\n\n3. While [BGM23] contains several ideas that serve as a starting point for the current submission, note that this work makes key novel contributions which allow the nontrivial extensions to SVIs and non-Euclidean settings, as acknowledged by reviewer nH8p. Most importantly, our new generalization analysis for these problems (see `key proof ideas' in page 6) permits the use of sequential regularization in SVIs and non-Euclidean settings. To our knowledge, this result is entirely new, and of interest beyond differential privacy.\n\n4. We will clarify the parameters of $A_{emp}$ by adding the following comment to the ``Algorithm Overview'' section, line 179: \n   \n*The saddle point problem defined in each round of Algorithm 1 is solved using some empirical subroutine, $A_{emp}$. This subroutine takes as input a partition of the dataset, $S_t$, the regularized loss function for that round, $f^{(t)}$, a starting point, $[\\bar w_{t-1}, \\bar \\theta_{t-1}]$, and an upper bound on the expected distance to the empirical saddle point of the problem defined by $S_t$ and $f^{(t)}$. The exact implementation of $A_{emp}$, Algorithm 3, will be discussed in the next section. Here, we focus on the guarantees of Recursive Regularization given that $A_{emp}$ satisfies a certain accuracy condition.*", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "Jpcp1A35ZV", "reviewer": "Reviewer_sj99", "summary": "This paper is quite far from my area, so please consider this review accordingly.\n\nThe paper addresses the problem of private Stochastic Saddle Points and Variational Inequalities. The primary contribution is extending previous work that focused solely on the L2/L2 setup to more general lp/lq settings, where the primal problem follows an lp-setup and the dual problem follows an lq-setup.\n\nThe main result is the development of an algorithm that achieves optimal excess error measured by the strong SP-gap.", "questions": "n/a", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper, in general, feels quite dense. For instance, the second paragraph mentions monotone operators without providing a definition. Additionally, the contribution section is not clear to me.\n\nThe algorithmic aspect of the work is very similar to [BGM23]. However, the authors needed to make some changes to the analysis, and they did a good job describing these necessary modifications.", "weaknesses": "The main weakness of the work is its presentation. It is very difficult to parse many parts of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We provide a definition of monotone operators in the preliminaries section, line 122. We can use the extra page allowed in the final version to provide more background.\n\nWith regards to the contribution of our work, while some algorithmic changes are needed in comparison to [BGM23], we emphasize that our primary contribution is our analysis technique.\nThere is some algorithmic novelty in that we 1) need to use non-Euclidean regularizes and 2) need to implement new DP techniques for the subroutine $\\mathcal{A}_{emp}$. That is, for the purposes of [BGM23], noisy stochastic gradient descent-ascent was sufficient, but our more general setup required a private implementation of the stochastic mirror prox algorithm. With that said, our main claim to novelty is in our analysis, which differs in crucial and non-obvious ways from [BGM23], as we detail in Section 3.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "hLYCJIOIDW", "reviewer": "Reviewer_nH8p", "summary": "This paper studies private SSP beyond Euclidean geometry. They prove a near optimal bound on SP-gap for geometry between $\\ell_1 ,\\ell_2$. This result is then extended to SVI.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The results are solid improvement over previous work. The method on overcoming the generalization issue is novel and interesting.", "weaknesses": "I have a few concerns on the technical results.\n\n(1) what’s $A_{emp}$ in your algorithm. It’s the key subroutine while never formally defined or specified. Can you give a concrete example as you claimed in line 182?\n\n(2) is there any algorithmic novelty compared with previous work, or it’s just an improved analysis? The comparison with BGM23 can be made more clear.\n\n(3) can you give some practical examples to prompt the need of considering noneuclidean geometry, otherwise it looks somewhat incremental.\n\nThere are numerous typos.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. The exact instantiation of $\\mathcal A_{emp}$ we use is given by Algorithm 2, Stochastic Mirror Prox. Lemma 3 shows that the implementation satisfies the needed relative accuracy guarantee. We will add the following comment to the ``Algorithm Overview'' section, line 179, to make this more clear.\n\n \n   *The saddle point problem defined in each round of Algorithm 1 is solved using some empirical subroutine, $\\mathcal A_{emp}$. This subroutine takes as input a partition of the dataset, $S_t$, the regularized loss function for that round, $f^{(t)}$, a starting point, $[\\bar w_{t-1},\\bar \\theta_{t-1}]$, and an upper bound on the expected distance to the empirical saddle point of the problem defined by $S_t$ and $f^{(t)}$. The exact implementation of $\\mathcal A_{emp}$, Algorithm 3, will be discussed in the next section. Here, we focus on the guarantees of Recursive Regularization given that $\\mathcal A_{emp}$ satisfies a certain accuracy condition.*\n\n\n2. There is some algorithmic novelty in that we 1) need to use non-Euclidean regularizes and 2) need to implement new DP techniques for the subroutine $\\mathcal A_{emp}$. That is, for the purposes of [BGM23], noisy stochastic gradient descent-ascent was sufficient, but our more general setup required a private implementation of the stochastic mirror prox algorithm. With that said, our main claim to novelty is in our analysis, which differs in crucial and non-obvious ways from [BGM23], as we detail in Section 3. \n\n3. Yes, the $\\ell_1/\\ell_2$ setup is particularly important. This is used to formulate problems that allow an adversary to mix different possible loss functions. Concretely, assume $f_1(w;x),...,f_k(w;x)$ are $\\ell_2$-Lipschitz loss functions. Then one can consider the saddle point problem: \n\n    $$ F_{\\mathcal D}(w,\\theta) = \\mathbb E_{x\\sim\\mathcal D}\\Big[{\\sum_{j=1}^k \\theta_j f_j(w;x)}\\Big],$$\n\n    where $\\theta$ is constrained to the standard simplex and $w$ is constrained to some compact, $\\ell_2$-bounded set. \n    This setup has been used in agnostic federated learning [MSS19] as just one example. We will add this example to our paper using the extra space given for the revision.\n\n    [MSS19]: Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. ICML 2019", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper considers differentially private algorithms for stochastic saddle point and variational inequality problems. Its key contribution is that the proposed methods can deal efficiently with non-Euclidean norms, obtaining near-optimal rates. This requires an analysis of regularizations of the function under consideration, which leads to new insights. 

The general evaluation of the reviewers was that this is a borderline/weak accept paper (scores were 5,5,5,6). It seems that some of the perceived weaknesses, such as the lack of adequate definition of $\mathcal{A}_{\rm emp}$, which were addressed in the rebuttal. One unresolved issue was the relative lack of novelty: while the analysis does require new ideas, it is somewhat restricted in scope ($\ell^p$ norms with $1\leq p\leq 2$) and strongly related to reference [BGM23]. My own evaluation is that the paper does present some interesting ideas, but with certain limitations that make it not too appealing to the NeurIPS audience.
Decision: Accept (poster)