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

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.

   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.

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

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

   $F_{\mathcal D}(w,\theta) = \mathbb E_{x\sim\mathcal D}\Big[{\sum_{j=1}^k \theta_j f_j(w;x)}\Big],$

   where $\theta$ is constrained to the standard simplex and $w$ is constrained to some compact, $\ell_2$-bounded set. 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.

   [MSS19]: Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. ICML 2019

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.

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

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.

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

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

4. We will clarify the parameters of $A_{emp}$ by adding the following comment to the ``Algorithm Overview'' section, line 179:

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.

1. We will add the following text to the ``Algorithm Overview'' paragraph (line 179), as well as additional comments:

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.

Additionally to your other points:

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

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