Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry

Authors: raef  bassily
cristóbal  guzmán
michael  menart
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:45:34

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.

Main paper: 
 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 a convex-concave loss,EQUATIONwhere D is an unknown distribution for which we have access to an i.i.d. sample S. Problems of this kind have important applications in stochastic optimization [NJLS09, JNT11, ZL15], federated learning [MSS19] , 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 a monotone operator, G D (z) := E x∼D [g(z;x)], the objective is to approximate the point z * ∈ Z, whereEQUATIONStochastic saddle point problems can be easily related to variational inequalities by observing that the saddle operator (an operator closely related to the gradient) of a 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 convex-concave SSP [JN19] .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 a 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 is an important task.Thus far, work on differentially private SSPs and SVIs has focused primarily on Euclidean settings. However, a 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. In this work, we provide the first systematic study of SSPs and SVIs in general geometries. The new analysis tools we develop lead to optimal rates for a number of these important setups.In this work, we provide the first systematic study of stochastic saddle point problems and variational inequalities in both Euclidean and non-Euclidean geometries. Our first results pertain to stochastic saddle point problems where the primal problem has an ℓ p -setup and the dual problem has an ℓ q -setup, where p, q ∈ [1, 2]. Here we assume the convex-concave loss is Lipschitz. We generalize the recursive regularization framework developed in previous works to more handle non-Euclidean geometries [AZ18, 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 at the heart of many other works studying SSPs [LYYY21, OPZZ22, BGM23], as the presence of a supremum in the strong SP-gap accuracy measure (see Eqn. (4)) 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 a new accuracy measure measure which, when used in conjunction with the recursive regularization algorithm, eventually translates into a strong gap guarantee. Our technique stands in 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) factor in non-Euclidean setups such as the ℓ 1 setting [Pan08] . Using these new techniques, we provide the first analysis which obtains the near optimal rate of Õ 1√ n + √ d nϵon the strong SP-gap for any p, q ∈ [1, 2]. Our algorithm achieves this rate in Õ min n 2 ϵ 1.5 √ d , n 3/2 number of gradient evaluations. We note that the near optimality of this rateDifferentially private stochastic optimization now has a broad body of work spanning over a decade [JKT12, BST14, JT14, TTZ15, BFTT19, FKT20, AFKT21]. Such work has rigorously characterized the problem of stochastic convex optimization in a variety of geometries. In ℓ p setups, for p ∈ [1, 2], it is now known that the optimal rate is Õ(1 √ n + √ d nϵ )for such problems [AFKT21, BGN21] . It has also been shown that additional improvements are possible in the ℓ 1 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 [YHL + 22, ZTOH22, BGM23, GGP24]. Without privacy, optimal O(1/ √ n) guarantees on the strong SP-gap have long been known [NY78] . With privacy, the (near) optimalÕ 1 √ n + √ d nϵ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 = q = 2, despite the fact that important problems are naturally formulated in other geometries. In particular, the case where q = 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 ℓ 1 /ℓ 1 setting when the loss is additionally assumed to be smooth and the constraint set is polyhedral; they achieved the rate Õ 1 √ n + 1 (nϵ) 1/2 . We note that smoothness is fundamentally necessary in achieving this dimension independent rate, as otherwise existing lower bounds of Ω 1√ n + √ dnϵ hold for such problems [AFKT21] . The work [ZB24] studied the problem of differentially private worst-group risk minimization, which is closely related to DP-SSPs in the ℓ 1 /ℓ 2 setting, but requires the loss to have a specific linear structure with respect to the dual parameter. For ℓ 1 /ℓ 2 saddle point problems having this structure, their result implies a rate of O 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 as long as it is clear that these goals are not attained by the paper. 
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, θ] to denote the concatenation of the vectors w and θ. For a function f , we let ∇f denote an arbitrary subgradient selection of f . Finally, we let Unif(U ) denote the uniform distribution over the set U .Operators. Let X be some abstract data domain and let S ∼ D n for n > 0 and D some unknown distribution over X . Let ∥ • ∥ be some norm and ∥ • ∥ * its dual. We consider some compact convex parameter space Z ⊆ R d of diameter B with respect to ∥ • ∥. Let B d ∥•∥ (r) denote the d-dimensional ball of radius r > 0 w.r.t. ∥ • ∥ centered on zero. We assume there existsL > 0 such that g : Z × X → B d ∥•∥ * (L)is a bounded operator and that for any x ∈ X , g(•; x) is monotone. That is, ∀z 1 , z 2 ∈ Z it holds that ⟨g(z 1 ; x) -g(z 2 ; x), z 1 -z 2 ⟩ ≥ 0. We define the empirical and population operators asG S (z) = 1 n n i=1 g(z; x i ) and G D (z) = E x∼D [g(z; x)].Stochastic Saddle Point Problems. SSPs have the following structure in addition to the above. Let d w , d θ ≥ 0 such that d w + d θ = d. We assume Z is the product of the convex compact sets W ⊆ R dw and Θ ⊆ R d θ equipped with norms ∥ • ∥ w and ∥ • ∥ θ and having diameters B w and B θ respectively. Then Z = W × Θ. We let ∥[w, θ]∥ = ∥w∥ 2 w + ∥θ∥ 2 θ , and thus the diameter of Z satisfies B ≤ B 2 w + B 2 θ ; note the geometric mean of two norms is always a norm. In SSPs, we consider the case where the monotone operator is the saddle operator of a convexconcave loss function f : W × Θ × X → R. The saddle operator is defined as g(w, θ; x) = [∇ w f (w, θ; x), -∇ θ f (w, θ; x)] and is always monotone if f is convex-concave. We also define the corresponding population loss and empirical loss functions asF D (w, θ) = E x∼D [f (w, θ; x)]and F S (w, θ) = 1 n x∈S f (w, θ; x) respectively. The boundedness assumption on g means f is L-Lipschitz. Concretely, ∀w 1 , w 2 ∈ W and ∀θ 1 , θ 2 ∈ Θ:EQUATIONUnder such assumptions, a solution for problem (1) always exists [Sio58] , and is referred to as the saddle point. Further, given an SSP (1), 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 [A w (S), A θ (S)] ∈ W × Θ, this is defined asEQUATIONFor notational convenience, we define the following function which is closely related to the SP-gap, Gap SP ( w, θ) = max θ∈Θ {F D ( w, θ)} -min w∈W F D (w, θ) . Usefully, this function is known to be Lipschitz whenever f is Lipschitz.Fact 1. ([BGM23]) If f is L-Lipschitz then Gap SP is √ 2L-Lipschitz.Finally, we define ℓ p /ℓ q saddle point problems as those which, in addition to the above, also have the following structure. Assume ∥ • ∥ w = ∥ • ∥ p and ∥ • ∥ θ = ∥ • ∥ q and that W and Θ have diameters bounded by B w and B θ with respect to ∥ • ∥ p and ∥ • ∥ q respectively. We assume that for any x ∈ X that f (•, •; x) is L w Lipschitz in its first parameter w.r.t. ∥•∥ p and L θ Lipschitz in its second parameter w.r.t. ∥ • ∥ q . Note this implies an overall Lipschitz parameter, as per Eqn.(3), of L ≤ L 2 w + L 2 θ .Stochastic Variational Inequalities. For SVIs, in addition to the assumption that the monotone operator is L-bounded, we will also assume it is β-Lipschitz. The objective for stochastic variational inequalities is to find an approximation of the (population) equilibrium point z * , where z * is characterized by Eqn. (2). We refer to such a solution as an equilibrium point. For approximate solutions, the quality of the approximation is characterized by the strong VI-gap:EQUATIONNote 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-concave loss (see Fact 3 in Appendix A).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 g is µ-strongly monotone if for anyz 1 , z 2 ∈ Z that ⟨g(z 1 ; x) -g(z 2 ; x), z 1 -z 2 ⟩ ≥ µ 2 ∥z 1 -z 2 ∥.Stability. Important to our analysis will be the notion of uniform stability [BE02] .Definition 1. A randomized algorithm A : X n → W × Θ satisfies ∆-uniform argument stability (UAS) if for any pair of adjacent datasets S, S ′ ∈ X n it holds that E A [∥A(S) -A(S ′ )∥] ≤ ∆.The notion of strong convexity is often important in analyzing stability. A function ψ :Z → R is µ- strongly convex w.r.t. ∥•∥ if for any z, z ′ ∈ Z one has ψ(z)-ψ(z ′ ) ≥ ⟨∇ψ(z ′ ), z -z ′ ⟩+ µ 2 ∥z -z ′ ∥ 2 .We call a function F : W × Θ → R µ-strongly-convex/strongly-concave (SC/SC) if for any θ ∈ Θ and w ∈ Θ the functions F (•, θ) and -F (w, •) are µ-strongly-convex.Notably, adding a SC/SC regularizer leads to stability properties. The following fact results from a more general result for regularized SVIs; see Lemma 5 in Appendix A. Lemma 1. Let ψ : W × Θ → R be µ-strongly-convex/strongly-concave w.r.t. ∥ • ∥ w and ∥ • ∥ θ . Then the algorithm which returns the saddle point of (w, θ)→ 1 n z∈S f (w, θ; z) + ψ(w, θ) is ( 2L µn )-UAS.Differential Privacy (DP) [DMNS06] . An algorithm A is (ϵ, δ)-differentially private if for all datasets S and S ′ differing in one data point and all events E in the range of the A, we have,P (A(S) ∈ E) ≤ e ϵ P (A(S ′ ) ∈ E) + δ.2 E xj ∼Dj [f (w; x j )] = min w∈W max θ∈∆ k j=1 θ (j) E xj ∼Dj [f (w; x j )],where here ∆ 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 θ is a simplex, it is natural to endow this space with the ℓ 1 -geometry. We thus end up with a SSP problem in ℓ p /ℓ 1 setup. (where ∥ • ∥ 2 w and ∥ • ∥ 2 θ are 1 κ strongly convex), constraint set diameter B, Lipschitz constant L. 1: Let n ′ = n/ log 2 (n), and T = log 2 ( L Bλ ). 2: Let S 1 , ..., S T be a disjoint partition of S with each S t of size n ′ (which is always possible due to the condition on λ)Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The specific assumptions made are detailed in the preliminaries and theorem statements.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 in 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
a new analysis for recursive regularization: 
 3: Let [ w0 , θ0 ] be any point in W × Θ 4: Define function (w, θ, x) → f (1) (w, θ; x) = f (w, θ; x) + 2λ ∥w -w0 ∥ 2 w -2λ θ -θ0 2 θ 5: for t = 1 to T do 6: [ wt , θt ] = A emp S t , f (t) , [ wt-1 , θt-1 ], B 2 t 7: Define (w, θ, x) → f (t+1) (w, θ; x) = f (t) (w, θ; x) + 2 t+1 λ ∥w -wt ∥ 2 w -2 t+1 λ θ -θt 2 θ 8: end for 9: Output: [ wT , θT ]In this section, we present our modified recursive regularization algorithm, first developed in [AZ18] and extended to Euclidean SSPs in [BGM23] . We then discuss the key components of our analysis needed to obtain our results for non-Euclidean geometries. We conclude the section by applying our general result for recursive regularization to DP ℓ p /ℓ q -SSPs.Algorithm Overview. As in [BGM23] , our recursive regularization implementation, Algorithm 1, solves a series of regularized saddle point problems defined by f (1) , ..., f (T ) . 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, [ wt-1 , θ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. At each round, the empirical subroutine A emp is required to find a point, [ wt , θt ], which is close (under ∥ • ∥) 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 A emp which satisfy the notion of relative accuracy succeed at finding such points.Definition 2 (α-relative accuracy). Given a dataset S ′ ∈ X n ′ , loss function f ′ , and an initial point [w ′ , θ ′ ], we say that A emp satisfies α-relative accuracy w.r.t. the empirical saddle point[w * S ′ , θ * S ′ ] of F ′ S ′ (w, θ) = 1 n ′ x∈S ′ f ′ (w, θ; x) if, ∀ D > 0, whenever E [∥[w ′ , θ ′ ] -[w * S ′ , θ * S ′ ]∥] ≤ D, the output [ w, θ] of A emp satisfies E F ′ S ′ ( w, θ * S ′ ) -F ′ S ′ (w * S ′ , θ) ≤ D α.In contrast to [BGM23] , our algorithm uses more general regularization to ensure strongconvexity/strong-concavity 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 A emp satisfy α-relative accuracy for any (5L)-Lipschitz loss function and dataset of size n ′ = n log(n) and assume ∥ • ∥ 2 w and ∥ • ∥ 2 θ are 1 κ -strongly convex under ∥ • ∥ w and ∥ • ∥ θ respectively. Then Algorithm 1, run with A emp as a subroutine and λ = 48B ακ 2 + Lκ 3/2 √ n ′ , satisfies Gap SP (R SSP ) = O B ακ 2 log(n) + BLκ 3/2 log 3/2 (n) √ n .The similarity of this result to [BGM23, Theorem 5] and our exposition thus far belies the difficulty of adapting their result to non-Euclidean 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 to 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 ℓ 1 setup, necessarily incurs an additional √ d factor [Pan08] . Thus, a fundamentally new analysis is needed. One should also note that the squared norms ∥ • ∥ 2 w may not be strongly convex for certain norms, such as ∥ • ∥ 1 . Regardless, in some such cases, we can still leverage this result by modifying the underlying problem, as we will show in Section 4. 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 ∈ [T ], defineF (t) D (w, θ; x) := E x∼D f (t) (w, θ; x) and let [w * t , θ * t ] be its saddle point; define F (t) S := 1 n ′ x∈St f (t) (w, θ; x). We are interested in the functions,H (t) D ([w, θ]) := F (t) D (w, θ * t ) -F (t) D (w * t , θ) and H (t) S (w, θ) := F (t) S (w, θ * t ) -F (t) S (w * t , θ). (6)Notably, the strong-convexity/strong-concavity ofF (t)D means that a bound onH (t) D ([w, θ]) yields a bound on ∥[w, θ] -[w * t , θ * t ]∥.Ultimately, finding a point sufficiently close to [w * t , θ * t ] at each round is all recursive regularization needs to succeed. The question then, is how to obtain guarantees on H (t) D . We accomplish this via a stability-implies-generalization argument.Lemma 2. Let f : Z × X → R be L-Lipschitz. Let [w * , θ * ] ∈ Z be the population sad- dle point. For any x ∈ X define h([w, θ]; x) = f (w, θ * ; x) -f (w * , θ; x). For S ∼ D n , let H S (z) = 1 n x∈S h(z; x) and H D (z) = E x∼D [h(z; x)]. Then for any ∆-UAS algorithm, A, one has E S,A [H D (A(S)) -H S (A(S))] ≤ 2∆L.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 H D and H S can be written as the expectation of f w.r.t. z ∼ D and z ∼ Unif(S) respectively, we can apply standard stability-implies-generalization results to h to obtain the claimed result [BE02] . We provide a full proof in Appendix B.1. This analysis bypasses difficulties of working directly with Gap SP experienced by [OPZZ22, BGM23] H (t) S (w, θ) = F (t) S (w, θ * t ) -F (t) S (w * t , θ) ≤ max w ′ ,θ ′ F (t) S (w, θ ′ ) -F (t) S (w ′ , θ) .Particular to our analysis, we will leverage the fact that the exact empirical saddle point is ( L λn )-stable and has an empirical gap of 0.4 Optimal Rates for Private ℓ p /ℓ q Saddle Point Problems Setup. In this section, we apply Theorem 1 to obtain results for ℓ p /ℓ q saddle point problems. In order to do this, we will apply recursive regularization using norms slightly different than the ℓ p and ℓ q norms. Specifically, to solve an ℓ p /ℓ q SSP, we define p = max p, 1 + 1 log(d) andq = max q, 1 + 1 log(d)and will apply recursive regularization with∥ • ∥ w = 1 Bw ∥ • ∥ p and ∥ • ∥ θ = 1 Bw ∥ • ∥ p. We also have ∥ • ∥ p ≤ ∥ • ∥ 1 ≤ d 1-1/ p∥ • ∥ p ≤ 2∥ • ∥ p.Thus, under these norms we have diameter boundB 2 = 1 and Lipschitz constant L 2 ≤ 4B 2 w L 2 w + 4B 2 θ L 2 θ [NJLS09]. Further the strong convexity assumption needed by Theorem 1 is satisfied with κ = max 1 p-1 , 1 q-1 . This is because for anyp > 1, 1 2 ∥ • ∥ 2 p is (p -1)-strongly convex w.r.t. ∥ • ∥ p [Bec17].Private Algorithm Satisfying Relative Accuracy. To apply Theorem 1, we must construct an algorithm satisfying relative accuracy and (ϵ, δ)-DP. For this, we use the stochastic mirror prox algorithm of [JNT11], Algorithm 2. This algorithm will also have application in our analysis of SVIs later on.Require:Learning rate η, Operator oracle O, Initial point z 0 ∈ Z, Regularization function ψ minimized at z 0 , Iterations T 1: for t = 1 . . . T do 2: zt = arg min u∈Z {ψ(u) + ⟨ηO(z t-1 ) -∇ψ(z t-1 ), u⟩} 3: z t = arg min u∈Z {ψ(u) + ⟨ηO(z t ) -∇ψ(z t-1 ), u⟩} 4: end for 5: SSP output: 1 T T t=1 z t 6: SVI output: z t * for t * ∼ Unif([T ])This algorithm takes as input a stochastic oracle for the saddle operator of f , O, and a strongly convex regularizer, ψ. We leverage this algorithm by constructing a differentially private version of the operator oracle O, and taking as output the average iterate z = 1 T T t=1 z t . We make the oracle private by adding Gaussian noise to minibatch estimates of the saddle operator. It is then easy to show the whole algorithm is private by composition results and the post processing properties of differential privacy. We defer these details to Appendix C.2, and here state the final relative accuracy bound.Algorithm 3 Recursive Regularization for SVIs: R SVI Require: Dataset S, monotone operator g, Subroutine A emp , regularity parameter κ > 0, regularization parameter λ ≥ L √ κ B √ n , constraint set diameter B, Strongly monotone operator ρ 1: Let n ′ = n/ log 2 (n), and T = log 2 ( L κBλ ). 2: Let S 1 , ..., S T be a disjoint partition of S with each S t of size n ′ (always possible due to the condition on λ) 3: z0 be any point in Z4: Define function (z, x) → g (1) (z; x) = g(z; x) + 2λ • ρ(z -z0 ) 5: for t = 1 to T do 6: zt = A emp S t , g (t) , zt-1 , B 2 t 7: Define function (z, x) → g (t+1) (z; x) = g (t) (z; x) + 2 t+1 λ • ρ(z -zt ) 8:end for 9: Output: zT Lemma 3. Under the setup described above, there exists an (ϵ, δ)-DP algorithm which satisfies α-relative accuracy with parameterα = O κ(B 2 w L 2 w + B 2 θ L 2 θ ) √ d log(1/δ)κ nϵ + 1 √ nand runs in O min√ κn 2 ϵ 1.5 log 2 (n) √ d log(1/δ)κ , √ κn 3/2 log 3/2 (n) number of gradient evaluations, where κ = 1 + 1 {p < 2 ∨ q < 2} • log(d).Main Result for DP ℓ p /ℓ q SSPs. Applying now the result of recursive regularization, Theorem 1, we obtain the optimal rate for ℓ p /ℓ q SSPs (up to logarithmic factors). Recall under our chosen norm that B ≤ 1 andL 2 ≤ 4B 2 w L 2 w + 4B 2 θ L 2 θ .Further, the privacy of Algorithm 1 follows from the privacy of A emp and the parallel composition and post processing properties of differential privacy. Corollary 1. There exists an Algorithm, R, which is (ϵ, δ)-DP, has number of gradient evaluations bounded by O min√ κn 2 ϵ 1.5 log(n) √ d log(1/δ)κ , √ κn 3/2 √ log(n), and satisfies (up to log(n) factors),Gap SP (R) = Õ κ 2.5 B 2 w L 2 w + B 2 θ L 2 θ d log(1/δ)κ nϵ + 1 √ n .(κ is at most log(d).)Note that in the ℓ 2 /ℓ 2 -setting κ = 1 and the above exactly recovers the result of [BGM23] . We further recall that the near optimality of this result is established by existing lower bounds for stochastic minimization, which is a special case of SSPs [BFTT19, BGN21] .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]• 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error 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. 
extension to variational inequalities: 
 In this section, we start by discussing the modifications that must be made to the recursive regularization algorithm to handle the more general structure of SVIs. We then discuss key ideas in the analysis and how to apply the algorithm to SVIs in the ℓ p setting. We recall that we here assume the operator g is monotone, L-bounded and β-Lipschitz.Algorithm 3 bears many similarities to Algorithm 1. Most notable among the differences is that we here regularize with a strongly monotone operator ρ instead of a strongly-convex/strongly-concave function. In our eventual application we will use ρ = ∇( 1 2 ∥ • ∥ 2 ), but strictly we only require that ρ satisfies the following. Assumption 1. For κ > 0, ρ : Z → R d is 1 κ -strongly monotone w.r.t. ∥ • ∥ and satisfy ∥ρ(z)∥ * ≤ ∥z∥ for all z ∈ Z.When ρ = ∇( 1 2 ∥ • ∥ 2 ), the second half of the condition is always guaranteed by the properties of the dual norm (see Fact 2). When ρ satisfies Assumption 1, we obtain the following guarantee.Theorem 2. Let A emp satisfy α-relative stationarity for any (5L)-bounded monotone operator and dataset of size n ′ = n log(n) . Let ρ satisfy Assumption 1. Then Algorithm 1, run with A emp as a subroutine and λ = 48B ακ 3 + (βB+L)κ 2 √ n ′ , satisfies Gap VI (R SVI ) = O log(n)B ακ 3 + log 3/2 (n)B(βB + L)κ 2 √ n .The full proof is in Appendix B.2. We discuss the key ideas in the following subsection.Unfortunately, the analysis used for stochastic saddle point problems does not easily extend to variational inequalities due to the fact that the VI-gap and SP-gap behave in fundamentally different ways. Even though SSPs are a 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 a bound on the SSP-gap. Further, a natural attempt to extend the notion of relative accuracy (Definition 3) to SVIs by asking A emp to bound ⟨G D (z * S ), A(S) -z * S ⟩ does not work, because such a term does not yield an upper bound on the distance ∥A(S) -z * S ∥. A similar problem holds for generalization measures in Eqn. (6).A New Empirical Accuracy Measure. Motivated by the above issues, we introduce a new relative accuracy measure for our analysis of SVIs. Importantly, this notion will allow us to bound the distance between the output of A emp and the empirical equilibrium point of the strongly monotone operator created at each round of the recursive regularzation algorithm.Definition 3 (α-relative stationarity). Given a dataset S ′ ∈ X n ′ , operator g ′ , and an initial point z ′ , we say that A emp satisfies α-relative stationarity w.r.t. to the empirical equilibriumz * S ′ of G S ′ (z) = 1 n ′ x∈S ′ g ′ (z; x), if, ∀ D > 0, whenever E [∥z ′ -z * S ′ ∥] ≤ D, the output z of A emp satisfies E [⟨G(z), z -z * S ′ ⟩] ≤ D α.Modified Generalization Measure. The generalization measure we use can be modified in a similar fashion. Lemma 4. Let g(z; x) = g 1 (z; x) + g 2 (z) such that g 1 : Z × X → R d is L-bounded and β-Lipschitz with respect to z and g 2 : Z → R d is any (data indepedent) operator. Let z * ∈ Z be its population equilibrium point. For any x ∈ X , define h(z; x) = ⟨g(z; x), z -z * ⟩. For S ∼ D n , letH S (z) = 1 n x∈S h(z; x) and H D (z) = E x∼D [h(z; x)].Then for any ∆-UAS algorithm, A, one hasE S,A [H D (A(S)) -H S (A(S))] ≤ ∆(βB + L).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 g 2 above, is not Lipschitz. This happens, for example, in the ℓ 1 setting. Thus, we must decompose h in the stability-impliesgeneralization analysis and handle the non-Lipschitz, but data-independent, term g 2 separately. Then, the Lipschitzness of the remainder is established using that fact that g 1 is both bounded and Lipschitz. The full proof is in Appendix D.1.In order to apply Theorem 2 to SVIs with an ℓ p setup, we pick ∥ • ∥ = 1 B ∥z∥ p where p = max{p, 1 + 1 log(d) }2 . We will use the regularizer,EQUATIONNote the above operator is uniquely defined since p > 1, and thus ∥ • ∥ 2 p is differentiable [Gui09] . This choice of ρ satisfies Assumption 1 with parameter κ = 1 p-1 . To see this, first observe that for any p > 1, 1 2 ∥ • ∥ 2 p is (p -1)-strongly convex w.r.t. ∥ • ∥ p and the gradient operator of a differentiable µ-strongly convex function is µ-strongly monotone. Second, for any norm and it's dual ∥∇( 1 2 ∥z∥ 2 )∥ * ≤ ∥z∥ for all z (see Fact 2 in Appendix A). To obtain relative stationarity guarantees, we again apply Algorithm 2 with a differentially private oracle for the empirical operator G S . The proof falls out of our existing analysis for stochastic mirror prox given in Appendix C.2. Specifically, Theorem 4 in the case where Θ is the empty set implies there exists an (ϵ, δ)-DP implementation of mirror prox which satisfies α-relative stationarity withα = O √ κBL d log(1/δ)(1 + 1 {p < 2} • log(d)) nϵ + √ κBL √ n .We here highlight one notable difference that arises with the algorithm. Typically, after running an algorithm like stochastic mirror prox for t iterations, one obtains a bound on the quantityE 1 T T t=1 ⟨G S (z t ), z t -z⟩ .Analysis then proceeds to bound the (empirical) VI-gap of the average iterate by leveraging monotonicity of 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 is nonstandard as such a selection does not necessarily yield any bound on the (empirical) VI-gap.Main Result for ℓ p DP SVIs. Using Algorithm 3 and the implementation of A emp 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 1 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 2. There exists an Algorithm, R, which is (ϵ, δ)-DP, has gradient evaluations bounded byO min √ κn 2 ϵ 1.5 log(n) √ d log(1/δ)κ , √ κn 3/2 √ log(n), and satisfies (up to log(n) factors)EQUATIONwhere κ =1 max{p,1+ 1 log(d) }-1 is at most log(d) and κ = 1 + 1 {p < 2} • log(d).Near Linear Time Algorithm for the ℓ 2 Setting. Because we assume the operator is Lipschitz, in the ℓ 2 setting, we can leverage existing accelerated optimization techniques to achieve a near linear time version of A emp , in a similar fashion to [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 O(n + βn log(n/δ)) gradient evaluations. We provide full details in Appendix D.3.Proof. Let z λ 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 anyz ∈ Z ⟨G S (z λ ) + λ[ρ(z λ ) -ρ(z 0 )], z -z λ ⟩ ≥ 0 ⟨G S ′ (z ′ λ ) + λ[ρ(z ′ λ ) -ρ(z 0 )], z -z ′ λ ⟩ ≥ 0 =⇒ ⟨G S (z λ ) -G S ′ (z ′ λ ) + λ[ρ(z λ ) -ρ(z ′ λ )], z ′ λ -z λ ⟩ ≥ 0.Since ρ is a 1-strongly monotone operator we have⟨G S (z λ ) -G S ′ (z ′ λ ), z ′ λ -z λ ⟩ ≥ λ ⟨ρ(z λ ) -ρ(z ′ λ ), z λ -z ′ λ ⟩ ≥ µλ∥z λ -z ′ λ ∥ 2 . Now we can use the monotonicity of G to derive, µλ∥z λ -z ′ λ ∥ 2 ≤ ⟨G S (z λ ) -G S ′ (z ′ λ ), z ′ λ -z λ ⟩ = ⟨G S (z λ ) -G S ′ (z λ ), z ′ λ -z λ ⟩ + ⟨G S ′ (z λ ) -G S ′ (z ′ λ ), z ′ λ -z λ ⟩ (i) ≤ ⟨G S (z λ ) -G S ′ (z λ ), z ′ λ -z λ ⟩ (ii) ≤ ∥G S (z λ ) -G S ′ (z λ )∥ * • ∥z ′ λ -z λ ∥ (iii) ≤ 2L n ∥z ′ λ -z λ ∥.Above (i) comes from the monotonicity of G, step (ii) comes from Hölder's inequality, and step (iii) comes from the fact that S and S ′ differ in at most one point. Simple algebra now obtains ∥z λ -z ′ λ ∥ ≤ 2L µλn . Fact 3. There exists a differentiable convex-concave loss, distribution D, and point z ′ such that when the operator is the saddle operator of the loss, Gap VI (z) < Gap SP (z).Proof. We show that the VI-gap is upper bounded by the excess risk of some convex function with operator g(z) = ∇f (z). Since stochastic convex optimization is a special case of SSPs, this shows there exist scenarios where Gap SP ≰ Gap VI . Specifically, when the dual player space Θ is singleton, the SP-gap becomes the excess risk. Let f (z; x) = z 2 be defined over z ∈ [0, 1], and so it does not matter what the distribution or data domain is. Note that Gap VI becomesGap VI (z) = max u∈[0,1] {⟨∇f (u), z -u⟩} = max u∈[0,1] 2uz -2u 2 .Note that in this case the SP-gap is just the excess risk,Gap SP (z) = z 2 -min z∈[0,1] z 2 = z 2 .Consider the point z = 1. It is easy to show that Gap VI (1) = 0.5 but Gap SP (1) = 1, proving the claim.3 B.1 Proof of Lemma 2 Lemma 6. (Restatement of Lemma 2) Let f : Z × X → R be L-Lipschitz. Let [w * , θ * ] ∈ Z be the population saddle point. For any x ∈ X define h([w, θ]; x) = f (w, θ * ; x) -f (w * , θ; x). For S ∼ D n , let H S (z) = 1 n x∈S h(z; x) and H D (z) = E x∼D [h(z; x)]. Then for any ∆-UAS algorithm, A, one has E S,A [H D (A(S)) -H S (A(S))] ≤ 2∆L.Proof. This result follows simply from two facts. First, because f is an L-Lipschitz function for any x ∈ X , we can show that h is L-Lipschitz. For any[w, θ], [w ′ , θ ′ ] ∈ Z observe, h([w, θ]) -h([w ′ , θ ′ ]) = [f (w, θ * ; x) -f (w * , θ; x)] -[f (w ′ , θ * ; x) -f (w * , θ ′ ; x)] = f (w, θ * ; x) -f (w ′ , θ * ; x) + f (w * , θ ′ ; x) -f (w * , θ; x) ≤ 2L∥[w, θ] -[w ′ , θ ′ ]∥.The rest of the proof essentially follows from the stability implies generalization proof of [BE02] since H D and H S have a statistical form w.r.t. h. In more detail, for any i ∈ [n] denote S (i) as the dataset which replaces the i'th datapoint of S, x i , with a fresh sample from D, x ′ . We have the following:E S,A [H D (A(S)) -H S (A(S))] = E S,A E x [h(A(S); x)] - 1 n x∈S [h(A(S); x)] = E S,x ′ ∼D n+1 ,i∼Unif([n]) h(A(S (i) ); x i ) -h(A(S); x i ) = E h(A(S (i) ; x i ) -h(A(S); x i ) ≤ E L∥A(S (i) ) -A(S)∥ ≤ 2L∆.The last step follows from the previously established Lipschitzness property of h.We will first prove the following more general version statement of Theorem 1.Theorem 3. Let λ ≥ 48Lκ 3/2 B √ n ′and A emp be such that for all t ∈ [T ] it holds thatE zt -z * S,t 2 ≤ B 2 12•2 2t κ 3/2 . Then Recursive Regularization satisfies Gap SP (R SSP ) = O log(n)B 2 λ .To prove this result, it will be helpful to first show several intermediate results. We start by defining several useful quantities. Define {F t } T t=0 as the filtration where F t is the sigma algebra induced by all randomness up to zt . For notational convenience we denote f (0) (w, θ; x) = f (w, θ; x). Then for every t ∈ {0, 1, ..., T } we define EQUATIONH (t) D is that it bounds the distance of a point to z * t . Fact 4 ([ZHWZ21], Theorem 1). Let F : Z → R d be a γ-SC/SC function and let [w * , θ * ] be the saddle point. Then ∥[w, θ] -[w * , θ * ]∥ 2 ≤ 2(F (w,θ * )-F (θ * ,w)) λ .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 of the output of the t-th round to the equilibrium of G (t) D . The second inequality bounds how far the population equilibrium moves after another regularization term is added.Lemma 7. Assume the conditions of Theorem 3 hold. Then for every t ∈ [T ], the following holdsP.1 E [∥z t -z * t ∥] 2 ≤ E ∥z t -z * t ∥ 2 ≤ B 2 2 2t κ ; and, P.2 B 2 t := E z * t -z * t-1 2 ≤ E z * t -z * t-1 ] 2 ≤ B 2 2 2(t-1) .We note that in contrast to [BGM23] and other analyses of recursive regularization, we define PropertyP.2 to bound E z * t -z * t-1 instead of E [∥z * t -zt-1 ∥].In [BGM23] , the latter choice led to a need to bound E Gap SP (z t-1 ) for all t ∈ [T ], which our analysis avoids. In particular, one can observe how the derivation of Eqn. (11) in the proof changes when z * t-1 is replaced with zt-1 .Proof of Lemma 7. We will prove both properties via induction on B 1 , ..., B T . Specifically, for each t ∈ [T ] we will introduce two terms E t and F t ,, and show that these terms are bounded if the bound on B t holds and that B t holds if E t-1 and F t-1 are bounded. Property P.1 is then established as a result of the fact that E ∥z t -z * t ∥ 2 ≤ 2(E t + F t ). Note that B 1 holds as the base case becauseE ∥z * 1 -z * 0 ∥ 2 ≤ B 2 .Property P.1: We here prove that if B t is sufficiently bounded, then E t and F t are bounded where for t ∈ [T ] we defineEQUATIONAdditionally, this will establish property P.1 because for any t ∈ [T ] it holds that,EQUATION)The second inequality comes from the strong monotonicity of the operator (see Fact 4).Note that E t is bounded by the assumption made in the statement of the theorem statement. We thus turn our attention towards bounding F t . We haveκ 2 t λ E H (t) D z * S,t = κ 2 t λ E E H (t) D z * S,t F t-1 (i) ≤ κ 2 t λ E E H (t) S z * S,t F t-1 + κL 2 2 t λn ′ = κ 2 t λ E E F (t) S (w * S,t , θ * t ) -F (t) S (w * t , θ * S,t ) F t-1 + 2κL 2 2 t λn ′ (ii) = 2κ 2 L 2 2 2t λ 2 n ′ ≤ B 2 1152 • 2 2t κ .Inqeuality (i) comes from the fact that stability implies generalization for H (t) , Lemma 2. Note the algorithm which outputs this exact equilibrium point is L 2 2 t λn ′ stable (see Lemma 5/Assumption 1).Step (ii) uses the fact that z * S,t is the exact saddle point of the regularized objective, and so for any[w, θ] ∈ Z, F (t) S (w * S,t , θ) -F (t)S (w, θ * S,t ) ≤ 0. The final inequality uses the setting of λ.We thus have a final bound 2(E t + F t ) ≤ B 2 2 2t .Property P.2: Now assume B t-1 holds. We haveEQUATIONInequality (i) above comes from removing negative terms and the fact that z * t-1 is the saddle point w.r.t. F (t-1) D. Using the induction argument we then complete the bound with the following:E z * t -z * t-1 2 ≤ E κ∥z * t-1 -zt-1 ∥ 2 ≤ κ(E t-1 + F t-1 ) ≤ B 2 2 2tWe now turn to analyzing the utility of the algorithm to complete the proof.proof of Theorem 3. Using the fact that Gap SP is √ 2L-Lipschitz and property P.1, we have EQUATION) What remains is showing E Gap SP (w * T , θ * T ) is Õ(B α + BL √ n ′ ). Let w ′ =EQUATIONwhere G D is the population loss saddle operator. Further by the definition of F (T ) and denoting G (T ) Das the saddle operator for F (T )D we have G D (w * T , θ * T ) = G (T ) D (w * T , θ * T ) -2λ T -1 t=0 2 t+1 ∇(∥[w * T , θ * T ] -[ wt , θt ]∥ 2 )Thus plugging the above into Eqn. (13) we haveGap SP (w * T , θ * T ) ≤ G (T ) D (w * T , θ * T ), [w * T , θ * T ] -[w ′ , θ ′ ] -2λ T -1 t=0 2 t+1 ∇(∥w * T , θ * T ] -[ wt , θt ]∥ 2 ), [w * T , θ * T ] -[w ′ , θ ′ ] ≤ -2λ T -1 t=0 2 t+1 ∇(∥w * T , θ * T ] -[ wt , θt ]∥ 2 ), [w * T , θ * T ] -[w ′ , θ ′ ] ≤ 2Bλ T -1 t=0 2 t+1 ∇(∥w * T , θ * T ] -[ wt , θt ]∥ 2 ) * ≤ 2Bλ T -1 t=0 2 t+1 [w * T , θ * T ] -[ wt , θt ] .Above, the second inequality comes from the first order optimally conditions for [w * T , θ * T ], the third from Cauchy Schwartz and a triangle inequality. The last inequality comes from the relationship between a norm and its dual, see Fact 2.Taking the expectation on both sides of the above we have the following derivation,EQUATIONAbove, (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 λ and T . Now using this result in conjunction with Eqn. (12) we haveGap SP (R) = √ 2λB 2 + 12T λB 2 = O log(n)B 2 λ .Above we use the fact that T = log( L Bλ ) and λ ≥ L B √ n ′ , and thus T = O(log(n)).Finally, we prove Theorem 1 leveraging the relative accuracy assumption.Proof of Theorem 1. First, observe that under the setting of λ = 48B ακ 2 + Lκ 3/2 √ n ′ used in the theorem statement that log(n)B 2 λ = O log(n)B ακ 2 + log 3/2 (n)BLκ 3/2 √ n. Thus what remains is to show that the distance condition required by Theorem 3 holds. That is, we now show that if A emp satisfies α-relative accuracy, then for all t ∈ [T ] it holds that E zt -z * S,t2 ≤ B 2 12•2 2t κ .To prove this property, we must leverage the induction argument made by Lemma 7. Specifically, to prove the condition holds for some t∈ [T ], assume B 2 t = E z * t -z * t-1 ] 2 ≤ B 22 2(t-1) (recall the base case for t = 1 trivially holds). As shown in the proof of Lemma 7, this implies that the quantities E t , F t (as defined in 9) are bounded by B 2 1152•2 2t . We thus haveEQUATION)where B t is as defined in property P.2. Inequality (i) comes from the strong monotonicity of G (t) S , Fact 4. Inequality (iii) comes from the setting λ ≥ 48ακ 2 /B. Inequality (ii) comes from the α-relative accuracy assumption on A emp , which holds so long as the expected distance is sufficiently bounded and each regularized loss is (5L)-Lipschitz. In this regard, note thatE ∥z * S,t -zt-1 ∥ ≤ E ∥z * S,t -z * t ∥ + ∥z * t -z * t-1 ∥ + ∥z * t-1 -zt-1 ∥ ≤ ( F t + B t + E t-1 + F t-1 ) ≤ B 2 t .Further, each f (t) is 5L-Lipschitz. We can see that,max z∈Z ∥∇f (t) (z, x)∥ * ≤ L + ∥ t-1 k=0 2 k+1 λ∇(∥z -zt ∥ 2 )∥ * ≤ L + t-1 k=0 B2 k+1 λ ≤ L + 4B2 T λ ≤ 5L.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 a convex-concave function is a monotone operator, but the following holds for any monotone operator. Lemma 8 (Implicit in [JNT11] , Theorem 1). Let ψ : Z → R be any non-negative function which is 1-strongly convex w.r.t. ∥•∥. Assume ∀t ∈ [T ] that E [O(z t )] = G(z t ) and E ∥O(z t ) -G(z t )∥ 2 * ≤ τ 2 . Then for for any z ∈ Z Algorithm 2 satisfies E 1 T T t=1 ⟨G(z t ), z t -z⟩ = O E [ψ(z)] T η + 7η 2 (L 2 + 2τ 2 ) .The above is slightly different than the statement in [JNT11] , but can be easily extracted from their proof. Let V ψ denote the Bregman divergence w.r.t.ψ; i.e. V ψ (z, z ′ ) = ψ(z) -ψ(z ′ ) - ⟨∇ψ(z ′ ), z -z ′ ⟩. Under our assumptions [JNT11, Eqn. (80)] gives E 1 T T t=1 ⟨G(zt), zt -z⟩ = O E [V ψ (z, z0)] T η + 7η 2 (L 2 + 2τ 2 ) .Note that since z 0 is the minimizer of ψ, we have V ψ (z, z 0 ) ≤ ψ(z).Before proving the relative accuracy guarantee of stochastic mirror prox, we also restate the following composition result for Gaussian mechanism known as the moments accountant. Lemma 9 ([ACG + 16, KLL21]). Let ϵ, δ ∈ (0, 1] and c be a universal constant. Let D ∈ Y n be a dataset over some domain Y, and let h 1 , ..., h T : Y → R d be a series of (possibly adaptive) queries such that for any y ∈ Y, t∈ [T ], ∥h t (y)∥ 2 ≤ L. Let σ ≥ cL √ T log(1/δ) nϵand T ≥ n 2 ϵ b 2 . Then the algorithm which samples batches of size B 1 , .., B t of size b uniformly at random and outputs 1 b y∈Bt h t (y) + g t for all t ∈ [T ] where g t ∼ N (0, I d σ 2 ), is (ϵ, δ)-DP.Lemma 3 is easily established from the following theorem which holds more generally for any monotone operator (rather than just the saddle operator of a convex-concave function). This generalization will allow us to use this theorem again in our results on SVIs.∥[w, θ]∥ = 1 B 2 w ∥w∥ 2 p + 1 B 2 θ ∥θ∥ 2 q and have defined κ = max 1 p-1 , 1 q-1 and κ = 1 + 1 {p < 2 ∨ q < 2} • log(d).For any t ∈ {0, ..., T } define [w t , θ t ] = z t , where z t is as given in Algorithm 2. We have the following.Theorem 4. Let [w 0 , θ 0 ], [w, θ] satisfy E [∥[w 0 , θ 0 ] -[w, θ]∥] ≤ D. Let g : W × Θ × X → B dw ∥•∥p (B w L w ) × B d θ ∥•∥q (B θ L θ ) be a monotone operator and G S (w, θ) = 1 n x∈S g([w, θ]; x).There exists an implementation of O such that Algorithm 2 is (ϵ, δ)-DP and the following holdsE [⟨G S ([w t * , θ t * ]), [w t * , θ t * ] -[w, θ]⟩] = E 1 T T t=1 ⟨G S ([w t , θ t ]), [w t , θ t ] -[w, θ]⟩ = O D B 2 w L 2 w + B 2 θ L 2 θ √ κ d log(1/δ)κ nϵ + √ κ √ nFurther, the resulting algorithm makes O min√ κn 2 ϵ 1.5 log 2 (n) √ d log(1/δ)κ , √ κn 3/2 log 3/2 (n) gradient evalua- tions.Before proving this statement, we first quickly show how to obtain Lemma 3, the relative accuracy guarantee for SSPs, using this result.Proof of Lemma 3. To obtain Lemma 3 from this statement, observe that in the special case where g is the saddle operator of the loss, f , convexity-concavity impliesE F ( 1 T T t=1 w t , w) -F (θ, 1 T T t=1 θ t ) ≤ E 1 T T t=1 ⟨G D (z t ), z t -z⟩ ,and Lemma 3 is thus obtained from the bound in Theorem 4.All that remains is to prove the above theorem. Note the following proof leverages the structure Z = W × Θ, but does not assume that g is the saddle operator of some convex-concave loss.Proof of Theorem 4.Let L = B 2 2 L 2 w + B 2 θ L 2θ and let p * = p p-1 and q * = q q-1 be the conjugate exponents of p and q, respectively. For t∈ [T ] denote the result of O(z t ) as [∇ w,t , ∇ θ,t ] such that ∇ w,t ∈ R dw and ∇ θ,t ∈ R d θ .We consider the following construction of the private operator oracle, O, for G S . Our implementation adds Gaussian noise to minibatch estimates of G S . That is, to evaluate O(z t ), we uniformly sample a minibatch of size m = max n ϵ T , 1 , call it M t , as well as Gaussian noise vectors ξ w,t ∼ N (0, I dw σ 2 w ) and ξ θ,t ∼ N (0, I d θ σ 2 θ ), for some σ w , σ θ > 0. We then have that[∇ w,t , ∇ θ,t ] = 1 m x∈Mt g(w t , θ t ; x) + [ξ w,t , ξ θ,t ].Privacy Bound: We first bound the privacy of Algorithm 2. Since for any u, ∥u∥ 2 ≤ √ d 1-2/p * ∥u∥ p * , we can bound the privacy loss using the guarantees of the moments accountant, Lemma 9. Specifically, we set T = κ min n, Utility Bound: We now establish the convergence guarantee by applying the general convergence guarantee of stochastic mirror prox (Lemma 8, Appendix C.1) with ψ([w, θ]) = κ 2B 2 w ∥w∥ 2 p + κ 2B 2 θ ∥θ∥ 2q , which is 1-strongly convex w.r.t. ∥ • ∥. Clearly our saddle operator oracle yields unbiased estimates of G S (z) at each iteration. To bound the variance, τ , note when p ̸ = 2 the private estimate of ∇ w,t satisfiesE ∥∇ w,t -∇ w F S (w t , θ t )∥ 2 p * (i) ≤ d 2/p * w E ∥ξ w,t ∥ 2 ∞ ≤ d 2/p * w σ 2 w log(d) ≤ c 2 B 2 w L 2 w T d w log(1/δ) log(d) n 2 ϵ 2 .When p = 2, then p * = 2, and one can replace bound (i) with E ∥ξ w,t ∥ 2 2 . Combining these cases yields a bound ofc 2 B 2 w L 2 w T dw log(1/δ)κ n 2 ϵ 2on the variance of ∇ w,t . A similar analysis holds for ∇ θ,t .Ultimately, with respect to the norm chosen above, we getE ∥O(z t ) -G(z t )∥ 2 * ≤ τ 2 with τ 2 ≤ (B 2 w L 2 w + B 2 θ L 2 θ ) 1 + c 2 T d log(1/δ)κ n 2 ϵ 2 = O(L 2 κ).The last equality uses the fact that κ ≥ 1.Recall we choose ψ([w, θ]) = κ 2B 2 w ∥w∥ 2 p + κ 2B 2 θ ∥θ∥ 2 q , and thus ψ([w, θ]) = κ∥[w, θ]∥ 2 . Now the guarantees of Lemma 8 imply E [⟨G S (z t * ), z t * -z⟩] = E 1 T T t=1 ⟨G D (z t ), z t -z⟩ = O κ D2 T η + 7η 2 (L 2 + 2τ 2 ) .The theorem statement now follows from plugging in the parameter settings of T and η and the bound on τ established above.Let h 1 (z; x) = ⟨g 1 (z; x), z -z * ⟩. First, we observe that h 1 is (βB + L)-Lipschitz. To see this, we have for any z, z ′ ∈ Z and x ∈ that⟨g 1 (z), z -z * ⟩ -⟨g 1 (z ′ ), z ′ -z * ⟩ = ⟨g 1 (z) -g 1 (z ′ ) + g 1 (z ′ ), z -z * ⟩ -⟨g 1 (z ′ ), z ′ -z * ⟩ = ⟨g 1 (z) -g 1 (z ′ ), z -z * ⟩ + ⟨g 1 (z ′ ), z -z ′ ⟩ ≤ (βB + L)∥z -z ′ ∥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 (i) as the dataset which replaces the i'th datapoint of S, x i , with a fresh sample from D, x ′ . We have the following:E S,A [H D (A(S)) -H S (A(S))] = E S,A E x [g 1 (A(S); x)] + g 2 (z), A(S) -z * - 1 n x∈S [g 1 (A(S); x)] + g 2 (z), A(S) -z * = E S,A E x [g 1 (A(S); x)] , A(S) -z * - 1 n x∈S [g 1 (A(S); x)], A(S) -z * = E S,x ′ ∼D n+1 ,i∼Unif([n]) g 1 (A(S (i) ); x i ), A(S (i) ) -z * -⟨g 1 (A(S); x i ), A(S) -z * ⟩ = E h 1 (A(S (i) ); x i ) -h 1 (A(S); x i ) ≤ E (βB + L)∥A(S (i) ) -A(S)∥ ≤ (βB + L)∆.The last step follows from the previously established Lipschitzness property of h 1 .In this section, we define L = βB + L. Define Gap VI (z) = max z ′ {⟨z ′ , z -z ′ ⟩}. We have the following fact.Fact 5. If g is L-bounded then Gap VI is L-Lipschitz.Proof of 5. For any z 1 , z 2 ∈ Z we haveGap VI (z 1 ) -Gap VI (z 2 ) = max z {⟨G D (z), z 1 -z⟩} -max z ′ {⟨G D (z ′ ), z 2 -z ′ ⟩} ≤ max z {⟨G D (z), z 1 -z⟩ -⟨G D (z), z 1 -z⟩} = max z {⟨G D (z), z 1 -z 2 ⟩} ≤ ∥G D (z)∥ * ∥z 1 -z 2 ∥ ≤ L∥z 1 -z 2 ∥.We recall the assumption made on ρ. Assumption 2. For some κ > 0 let ρ : Z → R d be 1 κ -strongly monotone w.r.t. ∥ • ∥ and satisfy ∥ρ(z)∥ * ≤ ∥z∥ for all z ∈ Z.We will first prove the following more general version statement of Theorem 2, which will be useful later.Theorem 5. Let λ ≥ 48 Lκ 2 B √ n ′ and A emp be such that for all t ∈ [T ] it holds that E zt -z * S,t 2 ≤ B 2 12•2 2t κ 2 . Then Recursive Regularization satisfies Gap VI (R VI ) = O log(n)B 2 λ .To prove this result, it will be helpful to first show several intermediate results. We start by defining several useful quantities. Define {F t } T t=0 as the filtration where F t is the sigma algebra induced by all randomness up to zt . For notational convenience we define g (0) (z; x) = g(z; x). Then for every t ∈ {0, 1, ..., T } we define • z * t : equilibrium of G (t) D (z) := E x∼D g (t) (z; x) ; • z * S,t : equilibrium of G (t) S (z) := 1 n ′ x∈St g (t) (z; x); • H (t) D (z) := G (t) D (z),S and z * t .As discussed in Section 5.2, the power ofH (t)D is that it bounds the distance of a point to z * t . Fact 6. Let G : Z → R d a µ-strongly monotone operator and let z * be the equilibrium point.Then ∥z -z * ∥ 2 ≤ 2⟨G(z),z-z * ⟩ µ . Proof. By strong monotonicity, for any z ∈ Z, µ 2 ∥z -z * ∥ 2 ≤ ⟨G(z) -G(z * ), z -z * ⟩ ≤ ⟨G(z), z -z * ⟩ .The last step comes from the fact that ⟨-G(z * ), z -z * ⟩ = ⟨G(z * ), z * -z⟩ ≤ 0 since z * is the equilibrium.We now establish two 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 GD . The second inequality bounds how far the population equilibria moves after another regularization term is added. Lemma 10. Assume the conditions of Theorem 5 hold. Then for every t ∈ [T ], the following holdsP.1 E [∥z t -z * t ∥] 2 ≤ E ∥z t -z * t ∥ 2 ≤ B 22 2t κ 2 ; and,P.2 B 2 t := E z * t -z * t-1 2 ≤ E z * t -z * t-1 ] 2 ≤ B 2 2 2(t-1) .Proof. We will prove both properties via induction on B 1 , ..., B T . Specifically, for each t ∈ [T ] we will introduce two terms E t and F t , and show that these terms are bounded if the bound on B t holds and that B t holds if E t-1 and F t-1 are bounded. Property P.1 is then established as a result of the fact that E ∥z t -z * t ∥ 2 ≤ 2(E t + F t ). Note that B 1 holds as the base case becauseE ∥z * 1 -z * 0 ∥ 2 ≤ B 2 .Property P.1: We here prove that if B t is sufficiently bounded, then E t and F t are bounded where for t ∈ [T ] we defineEQUATIONAdditionally, this will establish property P.1 because for any t ∈ [T ] it holds that,EQUATIONThe second inequality comes from the strong monotonicity of the operator (see Fact 6).Since E t is bounded by the assumption made in the statement of Theorem 5, we focus on bounding F t . We haveκ 2 t λ E H (t) D z * S,t = κ 2 t λ E E H (t) D z * S,t F t-1 ≤ κ 2 t λ E E H (t) S z * S,t F t-1 + κ L2 2 t λn ′ = κ 2 t λ E E G (t) S (z * S,t ), z * S,t -z * t F t-1 + κ L2 2 t λn ′ ≤ κ 2 L2 2 2t λ 2 n ′ ≤ B 2 2304 • 2 2t κ 2 .The inequality comes from the fact that stability implies generalization for H (t) , Lemma 4. Note the algorithm which outputs this exact equilibrium point is L 2 t λn ′ uniform argument stable (see Lemma 5/Assumption 1). The second inequality comes from the fact that z * S,t is the exact empirical equilibrium point of the regularized objective, and so for any z ∈ Z, G (t) S (z * S,t ), z * S,t -z ≤ 0. The final inequality uses the setting of λ.We thus have a final bound 2(E t + F t ) ≤ B 2 2 2t .Property P.2: Now assume B t-1 holds. We haveE z * t -z * t-1 2 ≤ E κ 2 t λ G (t) D (z * t-1 ), z * t-1 -z * t = E κ 2 t λ G (t-1) D (z * t-1 ) + 2 t λρ(z * t-1 -zt-1 ), z * t-1 -z * t = E κ 2 t λ G (t-1) D (z * t-1 ), z * t-1 -z * t + κ ρ(z * t-1 -zt-1 ), z * t-1 -z * t (i) ≤ E κ 2 2 ∥ρ(z * t-1 -zt-1 )∥ 2 * + 1 2 ∥z * t-1 -z * t ∥ 2 (ii) ≤ E κ 2 2 ∥z * t-1 -zt-1 ∥ 2 + 1 2 ∥z * t-1 -z * t ∥ 2 .Inequality (i) above comes from Young's inequality and the fact that z * t-1 is the equilibrium point w.r.t. G (t-1) D. Inequality (ii) comes from Fact 2/Assumption 1. After re-arranging we can continue as follows:E z * t -z * t-1 2 ≤ κ 2 E ∥z * t-1 -zt-1 ∥ 2 ≤ κ 2 (E t-1 + F t-1 ) ≤ B 2 2 2t .We now turn to analyzing the utility of the algorithm to complete the proof.Proof of Theorem 5. Using the fact that Gap VI is L-Lipschitz and property P.1, we haveEQUATION)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 Gap VI (z * T ) = O(log(n)B 2 λ). By the definition of G (T ) D we have G D (z) = G (T ) D (z) -2λ T -1 t=0 2 t+1 ρ(z -zt ) Let z ′ = arg max z ′ ∈Z {⟨G D (z ′ ), z * T -z ′ ⟩}.We obtain the following bound on the Gap VI (w * T , θ * T ).Gap VI (z * T ) = G (T ) D (z ′ ), z * T -z ′ + 2λ T -1 t=0 2 t+1 ρ(z ′ -zt ), z ′ -z * T (i) ≤ 2λ T -1 t=0 2 t+1 ρ(z ′ -zt ), z ′ -z * T (ii) ≤ 2λ T -1 t=0 2 t+1 ρ(z * T -zt ), z * T -z ′ (iii) ≤ 2Bλ T -1 t=0 2 t+1 ∥ρ(z * T -zt )∥ * (iv) ≤ 2Bλ T -1 t=0 2 t+1 * T -zt ∥ .Above, (i) comes from the fact that z * T is the equilibrium point of G Taking the expectation on both sides of the above we have the following derivation,E Gap VI (z * T ) ≤ 2BE λ T -1 t=0 2 t+1 ∥z * T -zt ∥ (i) ≤ 4BE λ T -1 t=0 2 t ∥z * t -zt ∥ + T -1 r=t z * r+1 -z * r = 4BE λ T -1 t=0 2 t ∥z * t -zt ∥ + λ T -1 t=0 2 t T -1 r=t z * r+1 -z * r (ii) = 4BE λ T -1 t=0 2 t ∥z * t -zt ∥ + λ T -1 r=0 r-1 t=0 2 t z * r+1 -z * r = 4BE λ T -1 t=0 2 t ∥z * t -zt ∥ + λ T -1 r=0 z * r+1 -z * r r-1 t=0 2 t (iii) ≤ 4B λ T -1 t=0 2 t B 2 t + λ T -1 r=1 B 2 r r-1 t=0 2 t ≤ 4B λ T -1 t=0 2 t B 2 t + λ T -1 r=1 B 2 r-1 • (2 r -1) = 4λ T -1 t=0 B 2 + 8λ T -1 r=1 B 2 ≤ 12T λB 2 (19)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 λ and T . Now using this result in conjunction with Eqn. (18) we haveGap VI (R SVI ) = √ 2λB 2 + 12T λB 2 = O log(n)B 2 λ .Above we use the fact that T = log( L Bλ ) and λ ≥ L Finally, we prove Theorem 2 leveraging the relative stationarity assumption.Proof of Theorem 2. First, observe that under the setting of λ = 48B ακ 3 + Lκ 2 √ n ′ used in the theorem statement that log(n)B 2 λ = O log(n)B ακ 3 + log 3/2 (n)B Lκ 2 √ n. Thus what remains is to show that the distance condition required by Theorem 5 holds. That we now show that if A emp satisfies α-relative stationarity, then for all t ∈ [T ] it holds that E zt -z * S,t2 ≤ B 2 12•2 2t κ 2 .To prove this property, we must leverage the induction argument made by Lemma 10. Specifically, to prove the condition holds for some t ∈ [T ], assumeB 2 t = E z * t -z * t-1 ] 2 ≤ B 22 2(t-1) (recall the base case for t = 1 trivially holds). As shown in the proof of Lemma 10, this implies that the quantities E t , F t (as defined in 16) are bounded by B 2 2304•2 2t . We thus haveEQUATION)where B t is as defined in property P.2. Inequality (i) comes from the strong monotonicity of G (t) S , Fact 6. Inequality (iii) comes from the setting λ ≥ 48 ακ/B. Inequality (ii) comes from the αrelative stationarity assumption on A emp , which holds so long as the expected distance is sufficiently bounded and the operator is bounded. In this regard, note thatE ∥z * S,t -zt-1 ∥ ≤ E ∥z * S,t -z * t ∥ + ∥z * t -z * t-1 ∥ + ∥z * t-1 -zt-1 ∥ ≤ ( F t + B t + E t-1 + F t-1 ) ≤ 2B 2 t . Further, each g (t) is 5L-bounded. That is, observe max z∈Z ∥g (t) (z, x)∥ * ≤ ∥z∥ * + t-1 k=0 2 k+1 λ∥ρ(z -zt )∥ * ≤ L + t-1 k=0 B2 k+1 λ ≤ L + 4B2 T λ ≤ 5L.Because we assume the operator is Lipschitz, in the ℓ 2 setting, we can leverage existing accelerated optimization techniques to achieve a near linear time version of A emp , in a similar fashion to [ZTOH22, BGM23] . Specifically, the work [PB16] gives the following result for strongly monotone variational inequalities when applying their accelerated SVRG algorithm3 . Lemma 11. (Implicit in [PB16, Theorem 3]) Let β, µ, K > 0 and c a universal constant. Let g : Z × X → R be monotone and β-Lipschitz and ρ : Z → R a µ-strongly monotone operator. Let z * S be the equilibrium of G S (z) = 1 n x∈S g(z; x) + ρ(z). There exists an algorithm, which inO(n + √ nK β µ ) gradient evaluations find a point z such that E [∥z * -z∥ 2 ] = cBe -K .We now construct A emp in the following way. At each round t ∈ [T ], we use the accelerated algorithm mentioned above to find a point ẑ such that E ∥ẑ -z * S,t ∥ 2 ≤ ( δL 52 t λn ′ ), where z * S,t is the equilibrium point ofG (t) S (z) = 1 n ′ x∈S g (t) (z; x). We then have A emp output the point zt = ẑt + ξ t , where ξ t ∼ N (0, I d σ 2 t ) and σ t = 8L √ 2/δ 2 t λn ′ ϵ .Using this construction, we can obtain the following result. Theorem 6. Let A emp be as described above. Then Algorithm 1 is (ϵ, δ)-DP and when run withλ = 48 B L √ n ′ + L √ d log(2/δ) n ′ ϵ satisfies Gap(R SVI ) = O log 3/2 (n)BL √ n + log 2 (n)BL d log(1/δ) nϵ ,and runs in at most O(n + βn log(n/δ)) gradient evaluations.Proof. Privacy Guarantee We show that A emp is (ϵ, δ) at any iteration t ∈ [T ] using the stability properties of the regularized operator. Specifically, the exact equilibrium to G t S . Now because A emp guarantees E ∥ẑ -z * S,t ∥ 2 ≤ ( δL 52 t λn ′ ), an application of Markov's inequality implies that with probability at least 1 -δ that ∥ẑ t -z * S,t ∥ = 1 δ cBe -K ≤ L 2 T λn . Thus by a triangle inequality ẑt is ( 2L 2 t λn ′ )-stable with probability at least 1 -δ. The guarantees of the Gaussian mechanism thus imply A emp is (ϵ, δ)-DP.Utility Guarantee: We prove the utility guarantee by leveraging Theorem 5, which guaranteesGap VI (R) = O(log(n)B 2 λ) = O log 3/2 (n)BL √ n + log 2 (n)BL √ d log(1/δ) nϵ, so long as for everyt ∈ [T ] it holds that E ∥z t -z * S,t ∥ 2 2 ≤ B 2 12•2 2t. Note here that under the choice of ρ in Eqn. (7), we satisfy Assuption 1 with κ = 1. We thus finish the proof with the following analysis,E zt -z * S,t 2 2 = E ∥ξ t ∥ 2 2 + ∥ẑ t -z * S,t ∥ 2 2 ≤ dσ 2 t + δ 5 • L 2 t λn ′ 2 ≤ 64dL 2 log(2/δ) 2 2t λ 2 (n ′ ) 2 ϵ 2 + B 2 25 • 2 2t ≤ B 2 12 • 2 2t .Running Time: By the guarantees of Lemma 11, we can achieve the condition E ∥ẑ -z * S,t ∥ 2 ≤ ( δL 52 t λn ′ ) made in the description of A emp by settingK = log cB δ • 2 T λn L . Recall T = log 2 ( L κBλ ) ≤ n. Thus the overall running time is O(n + β µ K √ n) = O(n + βn log(n/δ)).The lower bound for SVIs in the ℓ 2 setting was established in [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 f (z; x) = ⟨z, x⟩ and define the operator g(z; x) = ∇f (z; x) = x. Then Gap VI (z) = F D (z) -min u∈Z {F D (u)}. That is, the strong VI-gap w.r.t. g is equal to the excess population risk w.r.t. the f .Proof. We haveGap VI (z) = max u E x∼D [x] , z -u = E x∼D [x] , z + max u E x∼D [x] , -u = F D (z) -min u∈Z {F D (u)} .We now restate the lower bound result of [BGN21] for non-Euclidean setups. E S∼D n ,A F D(A(S) -min z∈Z {F D (z)} = Ω max 1 √ n , (p -1) √ d nϵ .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 VI-gap rate we obtain,Õ BL max 1 √ n , (p-1) √ d nϵ, is near optimal for p ∈ (1, 2] when p -1 = Ω(1). 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Justification: There are no experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The theoretical nature of the results means there are minimal ethical concerns.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: No such assets are used as a part of this research.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: No such assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.In contrast to our results on SSPs, rescaling by 1 B is not necessary in this case, but we do so to maintain consistency.B √ n ′ , and thus T = O(log(n)).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 A of their paper. 
: 
 √ n + √ dnϵ 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 ∈ [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 ∈ [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 ℓ p -setups, p ∈ [1, 2].Here, we provide the first analysis which obtains a bound on the strong VI-gap of Õ 1√ n + √ d nϵ .For p -1 = Ω(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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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].
strength_weakness: strength_weakness: 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.
questions: questions: I have two main comments:

1. The subroutine $\mathcal{A}_{emp}$ is never explicitly introduced. Here are some of sources of confusion for the reader:
-  Is this subroutine the same one in Algorithms 1 and 3? 
-  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}$.
- 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.

2. 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: 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?
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The boundedness assumption is a bit restricted, regarding many unconstrained problems in practice.
2. 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 
3. 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.

Typo:
1. In Algorithms, the parameters of $\mathcal{A}_{\text{emp}}(\cdot,\cdot,\cdot,\cdot)$ are not clearly defined
questions: questions: /
limitations: limitations: /
paper_summary: paper_summary: This paper is quite far from my area, so please consider this review accordingly.

The 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.

The main result is the development of an algorithm that achieves optimal excess error measured by the strong SP-gap.
strength_weakness: strength_weakness: The main weakness of the work is its presentation. It is very difficult to parse many parts of the paper.
questions: questions: n/a
limitations: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: I have a few concerns on the technical results.

(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?

(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.

(3) can you give some practical examples to prompt the need of considering noneuclidean geometry, otherwise it looks somewhat incremental.

There are numerous typos.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.

Comments: comment: Thank you for your response! The paper can benefit from adding these explanations/discussions. I will maintain my score.