Abstract

1
Introduction
In recent years, big data has become more prolific and widely used, while at the same time there has been a growing desire among the public (and regulators) for guarantees that their data remains private. Thus, an important problem in modern machine learning is how to conceal individuals' sen- sitive information in a dataset while simultaneously training a useful model on that dataset. Differential privacy provides a rigorous guarantee that, with high probability, an adver- sary cannot discover an individual's data by observing the output of an algorithm. More precisely, a randomized algo- rithm A : X n → R d is said to be ( ε , δ )-differentially pri- vate if for all measurable subsets K ⊂ range( A ) and all n- element data sets X , X ′ ∈ X n which differ by at most one observation (i.e. | X ▲ X ′ | ≤ 2), we have P(A(X) ∈ K) ≤ P(A(X') ∈ K)ec + δ, where the probability is (solely) over the randomness of A (Dwork and Roth 2014). We refer to data sets dif- fering in only one observation (|XΔΧ′| ≤ 2) as "ad- jacent." If δ  =  0, we may say an algorithm is ε- differentially private. An ( ε, δ )-differentially private algo- rithm  is  ε-differentially private   with  probability  1  –  δ (Dwork and Roth 2014, Lemma 3.17). Therefore, while large values of ε can still provide some privacy, δ ≪ 1 is necessary for meaningful privacy guarantees. In fact, δ ≪ニュis typically desirable: otherwise, a model may leak individ- uals' data and still satisfy the privacy constraint (Dwork and Roth 2014). For example, if δ > 0, then we may have P(A(X) ∈ K) = 0, and P(A(X') ∈ K) = δ for some K ⊂ range( A ), adjacent datasets X , X ′ ∈ ˙ X n . Therefore, if K occurs, then A completely reveals the underlying data set X ′ . While a lot of the literature has focused on efficient algo- rithms for ( ε, δ)-differentially private algorithms, the impor- tant case of δ = 0 has been neglected. The first contribution of this work is to fill this void. Assume the parameters of a machine learning model are trained via solving the minimization problem: w(X) ≈ arg min F(w, X).
In the case of empirical risk minimization (ERM), where F(w,X) =  π ∑ i=1 f(w,x i), algorithms for maintaining differential privacy through observing w(X) is well stud- ied (Chaudhuri et al. 2011; Bassily et al. 2014; Zhang et al. = 2017; Wang et al. 2017). Here (and throughout) X { x i } n =1 is a data set with observations in some set X ⊂ R q , and the weights w ∈ R d . More recently, several works have also considered private stochastic convex optimization (SCO), where the goal is to minimize the expected popula- tion loss F ( w, X ) = E x~D [ f ( w, x )], given access to n i.i.d samples X = {x,} π =1 (Bassily et al. 2019; Feldman et al. 2020; Arora et al. 2020). However, the algorithms in these works are only differentially private for δ > 0, which, as dis- cussed earlier, provides substantially weaker privacy guaran- tees. Therefore, providing efficient, practical algorithms for (ε, 0)-differentially private SCO is an important gap that we fill in the present work. Our second main contribution is differentially private con- vex optimization for general (non-ERM, non-SCO) loss functions. While ERM and SCO are useful if average perfor- mance is the goal, there are situations where another objec- tive besides average performance is desirable. For example, one may want to train a machine learning model that ensures some subsets of the population are treated fairly (see e.g. (Datta et al. 2015)), or one that is robust to corrupted data or adversarial attacks (Goodfellow et al. 2015), or one that has lower variance to allow for potentially better generalization. One may also want to diminish the effect of outliers or in- crease sensitivity to outliers. In these cases, it may be more fruitful to consider an alternative loss function that is not of ERM form. For example, the max-loss function F(w,X) = max{f(w,x1),...f(w,xn)} provides a model that has good "worst-case" performance and such F is clearly not of ERM form. The recently pro- posed "tilted ERM" (TERM) framework (Li et al. 2020) aims to address these shortcomings of standard ERM and encompasses the max-loss mentioned above. As another ex- ample, one may want a ML model that offers "accuracy at the top" (AATP) for applications such as recommenda- tion systems, since many users will only browse the first (‘top’’) few suggestions that are returned (Boyd et al. 2012). Maximizing accuracy at the top can be formulated as an optimization problem that is not ERM form (Boyd et al. 2012). Existing differentially privacy utility and runtime re- sults have all been derived specifically for standard ERM or SCO and therefore would not apply to objectives such as TERM and AATP, which do not fall into either of these two (ERM or SCO) categories. Beyond machine learning, non- ERM losses appear in other engineering applications, such as power grid scheduling and sensor networks (Fioretto et al. 2019; Wang et al. 2018). Our last main contribution is to specialize our theory and framework to DP TERM (discussed above) and adversarial training. In particular, for smooth strongly convex TERM, we derive excess risk bounds that (nearly) extend the op- timal differentially private ERM bounds of (Bassily et al. 2014), since the TERM objective encompasses ERM in the limit. In adversarial training, the goal is to train a model that has robust predictions to an adversary's perturbations (with respect to some perturbation set S ) of the feature data. This problem has gained a lot of attention in recent years, since it was first observed that neural nets can often be fooled by tiny, human-imperceptible perturbations into misclassifying images (Goodfellow et al. 2015). However, the challenging task of ensuring such adversarial training is executed in a differentially private manner has received much less atten- tion by researchers. Indeed, we are not aware of any prior works that have shown how to keep the adversarial train- ing procedure differentially private and provided adversar- ial risk and runtime bounds. Perhaps the closest step in this direction is the work (Phan et al. 2020), which provides a differentially private algorithm for training a classifier that is "certifiably robust," in the sense that with high probabil- ity, the classifier's predicted label is stable under small per- turbations. However, our measure of adversarial robustness is different: we look at excess adversarial risk and provide tight bounds that depend expicitly on the privacy parameters. This allows for an interpretation of the tradeoffs between ro- bustness, privacy, and runtime. Furthermore the algorithm of (Phan et al. 2020), a noisy stochastic batch gradient descent, is quite complicated to implement and does not come with runtime bounds. Our theory is built on the idea of output perturbation . Conceptually, the output perturbation mechanism outputs
WA(X) := Π B(0,R) [W(X) + b] ,
where ữ is the output of some non-private algorithm and b ∈ R d is some suitably chosen random noise vector. Here Π B (0,R)(2) := arg min w ∈ B (0,R) ∥ z − w ∥ 2 is the projection onto the closed euclidean ball (centered at 0) of radius R , B(0, R) ⊂ R d , which is large enough to contain w*( X ); see "Notation" paragraph below for more detail. Techni- cally, projection is necessary for our excess risk analysis in the non-smooth case, since we require Lipschitzness at W A (X) (recall that strongly convex function cannot be Lip- schitz on the whole space). Output perturbation has been studied in the differential privacy literature for many years (Dwork et al. 2006; Chaudhuri et al. 2011; Zhang et al. 2017). In early works, which culminated in (Dwork et al. 2006), the method was introduced and proven to be differ- entially private. In (Chaudhuri et al. 2011), high probabil- ity excess risk and population loss bounds for linear classi- fiers with strongly convex regularizers in the ERM and SCO settings are given for output perturbation (Chaudhuri et al. 2011, Thm 15, Lemma 16). However, no practical imple- mentation is provided. As a first step in the practical direc- tion, (Zhang et al. 2017) shows how to implement output perturbation with gradient descent in the smooth ERM set- ting, providing excess empirical risk and runtime bounds. Their privacy analysis is tied to the particular non-private optimization method they use, which hinders their runtime potential and makes their analysis less transparent. Notation. Recall that a function h : W → R on some do- main W ⊂ R d is convex if h (λw + (1 − λ) w ′ ) ≤ λh (w) + (1 − λ) h (w ′ ) for all λ ∈ [0, 1] and all w , w ′ ∈ W . We say h is L-Lipschitz if ‖h(w) −与‖w‖ž is convex. Also, w, w' ∈ W and β-smooth if h is differentiable and ∇ h ( w ) is β -Lipschitz. We always assume that F : R d × X n :→ R is such that for all X ∈ X n , F ( , X ) is convex on R d and L-Lipschitz on B (0, R) , where
and the infimum is over w*(X) ∈ argmin w ∈ R d F(w, X). B(0,R)) functions by GLR. Thus, if F w GLR, then B(0, R) contains at least one global minimizer of F( · , X ) in its interior for all X  ∈  X n . The data uni- verse X can be be any set, and we often denote X = ( x 1 , · · , x n ) ∈  X n . We will also work with the fol- lowing families of functions, which are each subsets of GL,R, throughout: F μ,L,R  :=  {F  :  R d  ×  X n R| F( , X ) is μ -strongly convex ∀ X}; H β,μ,L,R := {F ∈ F μ,L,R : F( · , X )  is β -smooth ∀ X }; and J β,L,R := {F ∈ GL,R : F( , X ) is β -smooth ∀  X w Xn}. For F H β,μ,L,R , denote the condition number by κ = β . Also, F µ,L,R, H β,µ,L,R, … are defined to be the subset of func- tions in F μ,L,R,H β,μ,L,R, ... that are of ERM form, i.e. AN F(w,X) = " ∑"=1 9(w,xi) for all w ∈ Rd, X ∈ X" for some convex g : R d × X → R . Finally, define the fol- lowing constant that is used in our choice of Gaussian noise vector: c δ := (Zhao et al. 2019).
Output Perturbation for General
Differentially Private Convex Optimization
In this section, we implement the classical output pertur- bation algorithm and provide a tight analysis for different classes of loss functions:
Strongly Convex Loss
Our framework when F ( w , X ) in (1) is strongly convex in w is described in Algorithm 1. Note that it accepts as in- put any non-private optimization algorithm and transforms it into a differentially private one, by adding noise to the ap- proximate minimizer w T . As a result, we are able to obtain runtimes as fast as non-private optimization method. Algorithm 1 Black Box Output Perturbation Algorithm for F μ,L,R and H β,μ,L,R Require:   non-private (possibly randomized) optimization method M , n , d ∈ N , privacy parameters ε > 0, δ ≥ 0, data set X ∈ X n , function F ( w, X ) ∈ F μ,L,R , ac- curacy parameter α > 0 with corresponding iteration number T = T(α) ∈ N (such that E [ F( w T( X ), X ) − F(w*(X),X)] < α).
1: Run  M  for  T T(α) iterations to ensure ll EF(wT(X),X) – F(w*,X) ≤ α.
First, let us establish the privacy guarantee for this algo- rithm. Proposition 2.1  Algorithm 1 is (ε, δ)-differentially private. For F ∈ F μ , L , R , instantiating Algorithm 1 with the sub- gradient method (Nesterov 2014) results in the following. Theorem 2.1  Take M to be the Subgradient Method with u(t +1) in Algorithm 1. Let F ∈ F μ,L,R EAF(WA(X),X) - vradient evalua-
If F is additionally β -smooth ( F ∈ H β,μ,L,R ), our excess risk bounds and runtime can be improved using Nesterov's Accelerated Gradient Descent (AGD) (Nesterov 2014): Theorem 2.2  Let F ∈ H β,μ, L, R . Take M to be Nesterov's Accelerated Gradient Descent (AGD) (Nesterov 2014) in

Convex Loss
Our Black Box implementation procedure for general con- vex loss (but in the absence of strong convexity) is described in Algorithm 2. Our first result is that this method is differ- entially private: Proposition 2.2  Algorithm 2 is (ε, δ)-differentially private. Next, we establish excess risk and runtime bounds for Al- gorithm 2 combined with the subgradient method: Theorem 2.3  Let F ∈ GL,R. Put M to be the subgradient method in the Black Box Algorithm 2 with α and T as prescribed below. Then there exist choices of λ > 0 such that the following results hold: a) If δ = 0, ξ ≤ 1, Algorithm  2  Black  Box  Output  Perturbation  Algorithm with Regularization for GL.R and Jβ,L,R Number of data points n ∈ N , dimension d ∈ N Require: of data, non-private (possibly randomized) optimization method M , privacy parameters ε > 0, δ ≥ 0, data uni- verse X , data set X ∈ X n , function F (w, X) ∈ G L R , accuracy and regularization parameters α > 0, λ > 0 with corresponding iteration number T = T (α,λ) ∈ N (such that E[F λ ( w τ ( X ) − F λ ( w * ( X ), X )] ≤ α ). 1: Run M on F λ (w,X) = F (w,X) +ミ∥ w ∥ ≥ for
As in the strongly convex, assuming smoothness allows us to improve our excess risk and runtime bounds:

DP SCO: Population Loss and Runtime
Bounds
Recent works (Bassily et al. 2014, 2019; Feldman et al. 2020) have established tight bounds on the expected pop- ulation loss of ( ε, δ )-private stochastic optimization algo- rithms for δ > 0. However, the important case of δ = 0, which provides the strongest privacy guarantee, has largely been overlooked, except for (Bassily et al. 2014). We show that our simple output perturbation algorithm results in ex- cess population loss bounds that improve the excess popu- lation loss bounds in (Bassily et al. 2014) and can be exe- cuted in substantially less runtime. Our method also works for δ > 0, where it serves as a simple, flexible, efficient al- ternative which, unlike other algorithms, allows for arbitrary € > 0. To proceed, we change some notation for further clar- ity and introduce some new definitions. Let the data have some (unknown) distribution x ～ D . We are given a sample dataset X ～ D n . We denote the empirical loss F ( w, X ) := n ∑ i=1 f(w, x i) and the population loss F(w, D) := E x~D f ( w, x ). Our goal is to understand perturbation frame- work in privately minimizing the excess population loss, defined at a point w ∈ R d by F ( w, D ) − min w ∈ R d ( w, D ) = F(w,D) - F(w*(D), D), where we denote the parameter that minimizes the population loss by w*( D ). To avoid any ambiguity, we will denote the minimizer of the empirical loss for a given data set X by ŵ( X ).
Strongly Convex, Lipschitz Loss
We begin with our results for strongly convex (and possibly non-smooth) loss. By using stochastic subgradient descent (SGD) to approximately minimize the empirical objective F in Algorithm 1, we can attain tight excess population loss bounds efficiently. Theorem 3.1  Let  f (w, x)  be  μ-strongly  convex  and  L- Lipschitz in w for all x ∈ X . Run A = Algorithm 1 on ith M as the stochastic subgradient method with step μ(t +1) and T, α as prescribed below. Then putting
Then
The optimal non-private excess population loss for μ- strongly convex, L -Lipschitz f is O(ニュー) (Hazan and Kale 2014). So if δ = 0 and d < ε, then we match the optimal non-private rate and in effect get "privacy for free." Like- wise, for δ > 0, if √ dc δ + √ ε √ ε , we get privacy for free. As noted earlier, neither (Bassily et al. 2019), nor (Feld- man et al. 2020) provide excess population loss bounds for δ = 0. The only population loss bound with δ = 0 is √ log(n) + |ニュ|お(Bassily et al. 2014, Theorem 0 F.2), obtained by exponential sampling + localization. Thus, we outperform their bounds by a logarithmic factor. More- over, as noted above, our runtime is O (max { n²d, en { ) for δ = 0. By contrast, the worst-case runtime of the ex- ponential sampling + localization method is much larger:ֲֲ²d9ֲ² max{1,ֲח} ) (Bassily et al. 2014).
Smooth, Strongly Convex, Lipschitz Loss
With the smoothness assumption, we can also use Katyusha (Allen-Zhu 2018), an accelerated stochastic method, instead of SGD for implementation and obtain faster runtimes: Theorem 3.2  Let L f(w,x) be   μ-strongly   convex, Lipschitz, β-smooth in w for all x ∈ X , and let X ∈ X n . Run  A = Algorithm 1 on F with M as Katyusha with = O ((n + √πκ) log( √π) and α as prescribed below. Suppose putting dient evaluations. The resulting runtime is
The non-private statistically optimal population loss is ), as for non-smooth. Hence, if δ = 0, we get "privacy 0(ミ) for free" whenever κ ( ξ ) 2 ≤ n or d ≤ ε . For δ > 0, we get "privacy for free" whenever * P ξ ξ  < n or √ dc δ + √ ε √ ε √ ε . There are no private population loss bounds we are aware of for the smooth, strongly convex, Lipschitz class with δ = 0, other than the one from exponential sampling + localization mentioned above, which does not benefit additionally from smoothness (Bassily et al. 2014). Therefore, our method pro- vides the tightest ( ε , 0)-differentially private excesss popula- tion loss bounds that we are aware of and runs in less time than any competing algorithm.
Convex, Lipschitz Loss
For convex loss f(w,x), applying the regularized output perturbation Algorithm 2 with SGD yields the following ex- cess population loss and runtime bounds: Theorem 3.3 Let f(w,x) be μ-strongly convex and L- Lipschitz in w for all x ∈ X . Run A = Algorithm 2 on F λ with M as the stochastic subgradient method with step sizes η t = X(t + 1) and T,  α as prescribed below. There exist
vex, L-Lipschitz functions is O( m ) (Hazan and Kale n 2014). Thus, we have "privacy for free" when d < ε, δ = 0, or when d(c δ + √c 2 + c) ≥ ε 2 , δ ∈ (0 , ½). For δ = 0, the only competing excess population loss bound for this class (LR)² that we are aware of is O ob- tained by the exponential mechanism (Bassily et al. 2014), which is larger than our bound by a factor of LR . Its runtime O(R 2 d 6 n 3 max{d,enR}), is also generally much larger than ours.
Smooth, Convex, Lispchitz Loss
If we assume additionally that f is β -smooth, then with Katyusha as the non-private input algorithm, our excess pop- ulation loss and runtime bounds improve: Theorem 3.4  Let f (w, x) be β-smooth, μ-strongly convex, and L-Lipschitz in w for all x ∈ X . Run A = Algorithm 2 on F λ with M as Katyusha with α , T as prescribed below.

Specialization to TERM and Adversarial
Training
Differentially Private Tilted ERM (TERM)
Consider for τ > 0 the Tilted ERM (TERM) objective
(see e.g. (Kort and Bertsekas 1972; Pee and Royset 2011; Cohen and Shashua 2014; Cohen et al. 2016; Katharopoulos and Fleuret 2017; Li et al. 2020) and the references therein for the applications of this loss). It is easy to show that as τ → 0,F r (w,x) → π ∑ i =1 f (w,x i ), so this extends the classical ERM framework in the limit. It also encompasses the max loss ( F max ( W , X ) = max { f ( W , x 1 ), …, f ( W , x n }) for instance, by letting τ → ∞. More generally, a benefit of the TERM framework is that it allows for a continuum of solutions between average and max loss, which, for exam- ple, can be calibrated to promote a desired level of fairness in the the machine learning model (Li et al. 2020). Another interpretation of TERM is that as τ increases, the variance of the model decreases, while the bias increases. Thus, τ can also be tuned to improve the generalization of the model via the bias/variance tradeoff. In what follows, we specialize our developed theory to the TERM objective function. Strongly convex, Lipschitz, twice differentiable f(·, x ) Next we show that if f is "nice enough," then F r ∈ F μ , L , R , so that the excess risk bounds proved earlier hold; we will also refine these results to show how excess risk depends on the parameter τ > 0. Lemma 4.1 ((Li et al. 2020, Lemmas 1 and 3)) As- sume f ( ·, x ) is a μ -strongly convex, twice differentiable, L-Lipschitz (on B(0,R)) loss function for all x ∈ X. Then F τ ( · , X ) is μ -strongly convex, twice differentiable, L- Lipschitz (on B(0, R)) for all X ∈ X n . By Lemma 4.1, if we put the subgradient method as M in Algorithm 1, then we get E A F ( W A ( X ), X ) - F(w*(X),X) < 9 π = in runtime O(nc) for δ = 0 by invoking Theorem 2.1, with α = ニュξ , T =  ξ . Similarly, for δ > 0, we get E A F ( W A ( X ), X ) — F(w*(X),X) ≤ 9 L 2 √d(c s + √c z +c) in runtime O ( n √ εd ). These results hold even as τ → ∞. If, in addition, f is bounded on B (0, R) × X , then we get the following more refined excess risk bounds. Proposition 4.1  Let τ > 0. Suppose f ( · , x ) is L-Lipschitz on B(0, R) (where ‖ w*(X)‖ ≤ R), twice differentiable, and μ-strongly convex for all x ∈ X. Moreover, as- sume a R  ≤  f(w,x)  ≤  A R  for  all  w  ∈  B(0,R) and all x ∈ X . Denote C τ = e τ ( AR −ar ). Then run- with M as the subgradient ning Algorithm 1 on F 7 method yields E A F (w A (X), X) F = (w*(X), X) in Note that the boundedness condition is not very restric- tive; indeed, it is automatic if X is compact (e.g. if data is normalized) and f is continuous, by the extreme value theo- rem. Smooth, strongly convex, Lipschitz f( , x ) If we as- sume additionally that f ( · , X ) is β -smooth, then the below Lemma implies that F ⁄ ∈ H β ,μ,L,R : Lemma 4.2 Assume f ( ·, x i ) is β -smooth and L-Lipschitz for all i ∈ [n]. Then for any τ > 0, the TERM objective F τ ( · , X ) is β τ -smooth for X = ( x 1 , · · · , x π ), where β τ := β + L 2 τ . β+ ξ ²¹ and appealing to Theo- Then denoting κ , rem 2.2 gives
β + L 2 τ . These bounds also hold as τ → ∞. If we assume again that f is also bounded on B (0, R) × X , then we can obtain the following more refined bounds: Proposition 4.2  Assume f ( · , x i ) is L-Lipschitz on B (0 , R ), β-smooth, twice differentiable, and μ-strongly convex. As- sume further that a R  ≤  f(w,x)  ≤  A R for all w  ∈ = et(AR-ar) B(0,R) and all x ∈ X. Denote C + Then running Algorithm 1 with M as AGD yields E A F ( W A ( X ), X ) − F , ( w * ( X ), X ) ≤ 26 κ, L 2C = ( ≥ ) 0, and E AF (w δ (X), X) (X),X) 13.5K, L 2 C if δ ∈ (0, ξ ). Both of these bounds are realized in runtime O(nd / κ , Note that we nearly (up to a factor of κ ) recover the op- timal ERM excess risk bounds of (Bassily et al. 2014) as T → 0.
Differentially Private Adversarial Training
In recent years, adversarial attacks on neural networks have raised significant concerns on reliability of these methods in critical applications. Adversarial attacks are input examples to a machine learning model crafted by making small per- turbations to legitimate inputs to mislead the network. These adversarial examples lead to highly confident, but incorrect outputs; see e.g. (Szegedy et al. 2014; Goodfellow et al. 2015; Papernot et al. 2016; Eykholt et al. 2018; Moosavi- Dezfooli et al. 2016) and the references therein. A natural approach to training a model that is robust to such adver- sarial attacks is to solve the following adversarial training problem (Madry et al. 2018; Zhang et al. 2019; Nouiehed et al. 2019):
Here X = ( x 1 , · · · , x n ) ∈ X n contains the feature data, y ∈ Y n is the corresponding label/target vector (e.g. y i ∈ {0, 1} for a binary classification task), and S is a set of per- missible adversarial perturbations. As discussed in the In- troduction, solving Eq. (2) with a practical differentially pri- vate algorithm to ensure privacy, robustness, and computa- tional speed simultaneously is an important open problem. Indeed, we are not aware of any works that provide privacy, robustness ("excess adversarial risk"), and runtime guaran- tees for solving Eq. (2). In this section, we illustrate how our methods and results developed so far can be easily ap- plied to establish excess adversarial risk bounds (robustness guarantees) and runtime bounds via output perturbation. Notation and preliminaries Let D = (X,y) ((x 1 , y 1 ), · · · , (x n , y n )) ∈ (X × Y) n be a given training data set. Assume that the adversarial perturbation set S is convex and compact with L 2 diameter ρ and that the ad- versary chooses v = ( v 1 , · · · , v n ) ∈ S n corresponding to the training examples (( x 1 , y 1 ), . . . , ( x n , y n )). The follow- ing definition is for notational convenience: Definition 1  For a loss function F : R d × ( X + S ) n × Y n , and dataset D = (X, y) ∈ (X × Y) n , denote the function of the weights and perturbations corresponding to F by H D : R d × S n → R, H D (w,v) := F (w,X + v,y). We make the following additional assumptions: Assumption 1  H D ( , v ) ∈ F μ , L , R for all v ∈ S n and all D ∈ ( X × Y) ″ . Assumption 2  HD(w, ·) is continuous and concave for all w ∈ B (0, R) and all D ∈ (X × Y) n . Note that Assumption 2 is a standard assumption in the min- max literature (Nouiehed et al. 2019; Lin et al. 2020). To- gether with Assumption 1, it ensures the existence of a sad- dle point (see definition below) and enables us to (approxi- mately) find the saddle point and implement our output per- turbation method efficiently. Next, we recall a basic notion from min-max optimization: Definition 2  For α ≥ 0, say a point (ŵ,ˆ∀) ∈ R d × S n is an α-saddle point of a convex (in w)-concave (in ν) function H ( w , v ) if
Observe that by Assumption 1, Assumption 2, and con- vexity and compactness of B (0, R ) and S , there exists at least one α -saddle point point ( ψ, ˆ ν ) ∈ B (0, R) × S n of H D for any α ≥ 0. Also, if we denote GD(w) := max HD(w,v) = max F(w,X +v,y), which is in F μ , L , R (by Assumption 1 and compactness of S n ), and w*(D) := argmin G D (w) = argmin max H D (w,v) ∈ B (0, R), wERd then for any α -saddle point ( ŵ , ˆ v ) of H D , we have: G D ( W ) − G D ( w * ( D )) ≤ α, by Sion's minimax theorem (Sion 1958). For a model w A trained on loss function F (by some ran- domized algorithm A ), the measure of adversarial robust- ness that we will consider is: Definition 3  Let w д be the output of a randomized algo- rithm A for solving Eq. (2). Define the excess adversarial risk of A by
In what follows, we aim to quantify the tradeoffs between excess adversarial risk, privacy, and runtime for output per- turbation. In order to practically implement the output per- turbation mechanism, we make the following additional as- sumption: Assumption 3  H D ( w, ·) is βv -smooth as a function of v ∈ S n for all w ∈ B(0, R) and all D = (X, y) ∈ (X × Y) n . Then Eq. (2) is a smooth (in w and v ), strongly convex- concave min-max problem and there are efficient non- private algorithms for solving such problems (Nesterov and Scrimali 2007; Alkousa et al. 2020; Lin et al. 2020). In Al- gorithm 3, we give a Black Box Algorithm tailored to the special min-max structure of the F that is present in the ad- versarial training setting. We then instantiate the Algorithm with the near-optimal (in terms of gradient complexity) al- gorithms of (Lin et al. 2020) and provide upper bounds on the runtime for privately optimizing the adversarially robust model. Definition 4  For α ≥ 0, a point (ŵ, ˆ ν) ∈ B(0, R) × B亮is an α-saddle point of function F ( w, X + v, y ) if F(w,X + v) ≤ α. max F ( w , X + v , y ) − wEB(0,R) The same arguments used before show that the Algo- rithm 3 is ( ε, δ )-differentially private. Furthermore, instan- tiating Algorithm 3 with the Minimax-AIPP algorithm (Lin et al. 2020) leads to the following guarantees: Algorithm 3 Black Box Output Perturbation Algorithm for Implementing DP Adversarial Training Require:   Number of data points n ∈ N , dimension d ∈ N of feature data, non-private (possibly randomized) opti- mization method M , privacy parameters ε > 0, δ ≥ 0, feature data universe X ⊆ R d and label universe Y , data set D = (X, y) ∈ (X × Y) n , convex compact perturbation set S ⊂ R d of diameter ρ ≥ 0, loss func- tion F ( w, X, y ) that is L -Lipschitz and μ -strongly con- vex in w on B (0, R ) and concave in ν ∈ S n , accuracy parameter α > 0 with corresponding iteration number T = T(α) ∈ N such that ( wτ, vτ ) is an α -saddle point
Theorem 4.1  Let D = (X,y) ∈ (X × Y) n be a dataset and let ε > 0, δ ∈ [0, ≒ ]. Assume that S is a convex compact set in R d of L 2 diameter ρ and that the loss function F is such that Assumption 1, Assumption 2, and Assumption 3 hold (see Definition 1). Furthermore, assume that H D ( · , v ) is β-smooth for all ν ∈ S n with condition number κ = β/μ. Run Algorithm 3 with M = Minimax-AIPP.
ent evaluations
If, in addition, H D (w, ·) is μ N -strongly concave in v for all w ∈ B(0, R), then the above bounds are all attained and the gradient complexity improves to T = O ( √ κκ v ) and runtime improves to O (nd / κκ , ) Note also that a similar result for F ∈ F μ , L , R can easily be written down as a consequence of our earlier results. Ex- cess adversarial population loss bounds can also be derived from our DP-SCO results.
5
Conclusion
In this work, we highlighted the importance of differentially private optimization for general non-ERM loss functions, and provided a simple yet practical algorithm for address- ing this problem, along with excess risk and runtime bounds. We also used our method to obtain tight population loss and runtime bounds for the differentially private SCO problem, where, unlike prior works, we guarantee (ε,δ)-DP for all δ ≥ 0. Finally, we applied our results to two practical ap- plications in machine learning: DP Tilted ERM and DP Ad- versarial Training. An interesting question for future work is whether our excess risk bounds for general non-ERM loss are tight. Currently, the only known DP excess risk lower
Acknowledgments
We would like to thank Zeyuan Allen-Zhu, Larry Goldstein, and Adam Smith for helpful comments. Mohammad Alkousa, Darina Dvinskikh, Fedor Stonyakin, Alexander Gasnikov, and Dmitry Kovalev.  Accelerated methods for composite non-bilinear saddle point problem, 2020. Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods.  Journal of Machine Learning Research , 18(221):1–51, 2018.  URL http://jmlr.org/papers/ v18/16-410.html. Aleksandr Aravkin, James Burke, and Dmitry Drusvyatskiy. Convex Analysis and Nonsmooth Optimization . 2017. Raman Arora, Teodor V. Marinov, and Enayat Ullah. Private stochastic convex optimization: Efficient algorithms for non- smooth objectives. arXiv:2002.09609v1 , 2020. Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Dif- ferentially private empirical risk minimization: Efficient al- gorithms and tight error bounds. arXiv:1405.7085v2 , 2014. Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates.  Advances in Neural Information Processing Systems , 32:11282–11291, 2019. Olivier Bousquet and Andre Elisseeff.  Stability and gener- alization. Journal of machine learning research , 2002. Stephen Boyd, Corinna Cortes, Mehryar Mohri, and Ana Radovanovic. Accuracy at the top. In  F.  Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, ed- itors, Advances in Neural Information Processing Sys- tems , volume 25, pages 953–961. Curran Associates, Inc., 2012.  URL https://proceedings.neurips.cc/paper/2012/file/ 7fe1f8abaad094e0b5cb1b01d712f708-Paper.pdf. Sebastian Bubeck.  Convex optimization: Algorithms and complexity.  Foundations and Trends in Machine Learning , 8, 2015. Kamalika Chaudhuri, Claire Monteleoni, and Anand Sar- Differentially private empirical risk minimization. wate. Journal of Machine Learning Research , 12:1069–1109, 2011. Nadav Cohen and Amnon Shashua.  Simnets: A generaliza- tion of convolutional networks. arXiv:1410.0781v3 , 2014. Nadav Cohen, Or Sharir, and Amnon Shashua.  Deep sim- nets.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , pages 4782–4791, 2016.  doi: 10.1109/CVPR.2016.517. Amit Datta, Michael Carl Tschantz, and Anupam Datta. Au- tomated experiments on ad privacy settings: A tale of opac- ity, choice, and discrimination.  Proceedings on privacy en- hancing technologies , 2015(1):92–112, 2015. Cynthia Dwork and Aaron Roth. The Algorithmic Founda- tions of Differential Privacy. 2014. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In Advances in Cryptol- ogy - EUROCRYPT 2006 , volume 4004 of Lecture Notes in Computer Science . Springer, Berlin, Heidelberg, 2006. Kevin Eykholt, Ivan Evtimov, Earlance Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song.  Robust physical-world attacks on deep learning visual classification. In 2018 IEEE/CVF Con- ference on Computer Vision and Pattern Recognition , pages 1625–1634, 2018. doi: 10.1109/CVPR.2018.00175. Vitaly Feldman, Tomer Koren, and Kunal Talwar.  Private stochastic convex optimization: Optimal rates in linear time. arXiv:2005.04763v1 , 2020. Ferdinando Fioretto, Terrence WK Mak, and Pascal Van Hentenryck. Differential privacy for power grid obfus- cation. IEEE Transactions on Smart Grid , 11(2):1356–1366, 2019. Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Interna- tional Conference on Learning Representations , 2015. URL http://arxiv.org/abs/1412.6572. Moritz Hardt, Benjamin Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient de- scent.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Ma- chine Learning Research , pages 1225–1234, New York, New York, USA, 20–22 Jun 2016. PMLR.  URL http: //proceedings.mlr.press/v48/hardt16.html. Elad Hazan and Satyen Kale. Beyond the regret mini- mization barrier: Optimal algorithms for stochastic strongly- convex optimization.  Journal of Machine Learning Re- search, 2014. Biased Angelos Katharopoulos and François Fleuret. importance sampling for deep neural network training. arXiv:1706.00043 , 2017. Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression.  In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Con- ference on Learning Theory , volume 23 of Proceedings of Machine Learning Research , pages 25.1–25.40, Edinburgh, Scotland, 25–27 Jun 2012. PMLR.  URL http://proceedings. mlr.press/v23/kifer12.html. Barry W. Kort and Dimitri P. Bertsekas.  A new penalty function method for constrained minimization. In Proceed- ings of the 1972 IEEE Conference on Decision and Con- trol and 11th Symposium on Adaptive Processes , pages 162– 166, 1972. doi: 10.1109/CDC.1972.268971. Tian Li, Ahmad Beirami, Maziar Sanjabi, and Vir- Tilted empirical risk minimization. ginia Smith. arXiv:2007.01162v1 , 2020. Hongzhou Lin, Julien Mairal, and Zaid Harchaoui.  A univer- sal catalyst for first-order optimization.  Advances in neural information processing systems , 28:3384–3392, 2015. Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal al- gorithms for minimax optimization. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Con- ference on Learning Theory , volume 125 of Proceedings of Machine Learning Research , pages 2738–2779. PMLR, 09– 12 Jul 2020.  URL http://proceedings.mlr.press/v125/lin20a. html. Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learn- ing models resistant to adversarial attacks.  In 6th Interna- tional Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Con- ference Track Proceedings . OpenReview.net, 2018.   URL https://openreview.net/forum?id=rJzIBfZAb. Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard.  Deepfool: A simple and accurate method to fool deep neural networks.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2574–2582, 2016.  doi: 10.1109/CVPR.2016.282. Yurii Nesterov.  Introductory Lectures on Convex Optimiza- tion: A Basic Course. Springer Publishing Company, Incor- porated, 1 edition, 2014. ISBN 1461346916. Yurii Nesterov and Laura Scrimali. Solving strongly mono- tone variational and quasi-variational inequalities.  Discrete and Continuous Dynamical Systems, 31, 01 2007. doi: 10.2139/ssrn.970903. Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn.  Solving a class of non- convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems 32 , pages 14934–14942. Curran Associates, Inc., 2019. URL http://papers.nips.cc/paper/9631-solving-a-class-of- non-convex-min-max-games-using-iterative-first-order- methods.pdf. Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami.  The limitations of deep learning in adversarial settings.  In 2016 IEEE European Symposium on Security and Privacy (EuroS P), pages 372–387, 2016. doi: 10.1109/EuroSP.2016.36. E.Y. Pee and J. O. Royset.  On solving large-scale finite minimax problems using exponential smoothing.  Journal of Optimization Theory and Applications , 148(2):390–421, February 2011.  URL https://ideas.repec.org/a/spr/joptap/ v148y2011i2d10.1007_s10957-010-9759-1.html. Hai Phan, My T Thai, Han Hu, Ruoming Jin, Tong Sun, and Dejing Dou.  Scalable differential privacy with certified ro- bustness in adversarial learning. In International Conference on Machine Learning , pages 7683–7694. PMLR, 2020. Maurice Sion. On general minimax theorems. Pacific Jour- nal of Mathematics, pages 171–176, 1958. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks.  In International Conference on Learning Representations , 2014.  URL http: //arxiv.org/abs/1312.6199. Di Wang, Minwei Ye, and Jinhui Xu.  Differentially private empirical risk minimization revisited: Faster and more gen- eral.  Advances in Neural Information Processing Systems , 30:2722–2731, 2017. Jun Wang, Rongbo Zhu, Shubo Liu, and Zhaohui Cai. Node location privacy protection based on differentially private grids in industrial wireless sensor networks. Sensors , 18(2): 410, 2018. Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Lau- rent El Ghaoui, and Michael Jordan.  Theoretically prin- cipled trade-off between robustness and accuracy.  In Ka- malika Chaudhuri and Ruslan Salakhutdinov, editors, Pro- ceedings of the 36th International Conference on Machine Learning , volume 97 of Proceedings of Machine Learning Research , pages 7472–7482. PMLR, 09–15 Jun 2019.  URL http://proceedings.mlr.press/v97/zhang19p.html. Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives.  In Proceedings of the 26th International Joint Conference on Artificial In- telligence , pages 3922–3928, 2017. Jun Zhao, Teng Wang, Tao Bai, Kwok-Yan Lam, Zhiying Xu, Shuyu Shi, Xuebin Ren, Xinyu Yang, Yang Liu, and Han Yu. Reviewing and improving the gaussian mechanism for differential privacy. arXiv:1911.12060v2 , 2019.
Andrew Lowy¹ and Meisam Razaviyayn ² l, 2University of Southern California ¹ lowya@usc.edu and ² razaviya@usc.edu We will require a definition and a lemma for several proofs. Definition 1  Define the L 2 sensitivity of a (strongly convex in w) function F : R d × X n → R as
where w*(X) = arg min werd F(w, X). The following result generalizes Corollary 8 in (Chaud- huri et al. 2011) (beyond smooth linear ERM classifiers with bounded label space). Lemma 0.1  For any F  ∈  F μ,L,R,  Δ F  ≤  ≥  For F  ∈ FERM , ∀ F ≤ 2L The proof relies on the following generalization (to non- differentiable functions on a possibly constrained ( W̸= R d ) domain) of Lemma 7 from (Chaudhuri et al. 2011). Lemma 0.2  Let  G(w), g(w)  be  continuous  convex  func- tions on some convex closed set W ⊂ RP and suppose that G(w) and G(w) + g(w) are μ-strongly convex. Assume further that g is Lg-Lipschitz. Define W1 ll arg min w G(w) arg min w ∈ W [G(w) + g(w)]. Then ‖ w 1 − w 2‖ 2 ≤ Proof: At a point w ∈ W , let h ( w ) and H ( w ) denote sub- gradients of g and G , respectively. By first-order optimality conditions, for all w ∈ W , we have and
〈H(w2), (w − w2)〉 + 〈h(w2), (w − w2)〉 ≥ 0. Plugging w 2 for w in the first inequality and w 1 for w in the second inequality, and then subtracting gives: (1) 〈H(w 1 ) − H(w 2 ), w 1 − w 2 〉 ≤ 〈h(w 2 ), w 1 − w 2 〉. Now, by strong convexity of G , we have μ||w1 − w2||2 ≤ 〈H(w1) − H(w2),w1 − w2〉. Copyright ( C ) 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Combining this with Eq. (1) and using Cauchy-Schwartz yields: μ||w1 − w2||≥ ≤ 〈H(w1) − H(w2),w1 − w2 ≤ ⟨h(w2),w1 − w2⟩ ≤ ∥h(w2)∥2‖w1 − w2‖2 Finally, using L g -Lipschitzness of g and dividing the above inequality by μ ‖ w 1 − w 2 ‖ 2 gives the Lemma. Now we can prove Lemma 0.1: Let X, X' E X'' such that (WLOG) x n̸= x ′ n , but all other data points are the same. Apply Lemma 0.2 to G(w) = F(w,X),g(w) = F(w, X') − F(w, X) and note that g is 2L-Lipschitz by the triangle inequality. For F of ERM form, we have g(w) = =[f(w,x'n) − f(w,xn)], which is 2 = -Lipschitz. This com- pletes the proof. Define Δ T := sup|xΔx'|<2 || wr(X) − wr(X')||2. First, ′². Now, note that since we show that Δτ ≤ Δ F + 2. F(wT(X),X)−F(w*,X) ≤ α by the choice of T and since F( · , X ) is μ -strongly convex, we have
we have
Now recall the well-known post-processing property of differential privacy, which states that any function (e.g. pro- jecting onto W ) of an ( ε, δ )- differentially private method is itself ( ε, δ )- differentially private (Dwork and Roth 2014). By this fact, it suffices to show that the algorithm w A ′ (X) := w T (X) + ˆ ∅ (without projection) is differen- tially private. Assume first δ  =  0. Then by the defini- tion of differential privacy, it suffices to show that for any s ∈ range( w A ′ ) (for which p ′ (s)̸= 0) and any X , X ′ ∈ X n such that | X ▲ X ′ | ≤ 2,
where p and p ′ are the probability density functions (pdfs) of A ′ ( X ) and A ′ ( X ′ ) respectively. Now note that p ( s ) = pz(s − wT(X)) and p'(s) = pz(s − wT(X')), where pz is the pdf of the noise. Then
where the second to last line uses the reverse trian- gle inequality and the last line uses the definition of Ar. Now, by the post-processing property (Dwork 2014), Roth we conclude that the algorithm and =  Π w ( Α ′ ( Χ )) is (ε, 0)- differen- A(X) = wA(X) tially private. For δ > 0, the proof follows similarly, using the following result of (Zhao et al. 2019): Theorem 0.1 (Theorem 5 in (Zhao et al. 2019)) For δ  ∈ (0,.5), (ε,δ)- differentially privacy can be achieved by adding Gaussian noise with mean 0 and standard deviation σ =  (c+√c2+c)△ to each dimension of a query with L2 sen- c √ 2 sitivity Δ. Here c = log Here, our "query" is wT(X), which has sensitivity ΔT, and hence A ′ (as defined above) is ( ε, δ ). Applying the post-processing property again shows that A is (ε,δ)- differentially private. The result is a corollary of (the first part of) the following: Theorem 0.2  Run Algorithm 1 with arbitrary inputs.
|<
To prove this, we will need to recall the following basic fact about projections onto closed, convex sets: Lemma 0.3  Let W be a closed, convex set in R d , and let α ∈ R d . Then π = Π W (α) if and only if ⟨ α − π, w − π ⟩ ≤ 0 for all w ∈ W. We include the proof for completeness: Fix any a E Rd. By definition, ΠW(α) = arg minwew ž‖w − α‖ž := arg min w ∈ W h ( w ). Then ∇ h ( w ) = w − a and by first-order optimality conditions, π = arg min w ∈ W h ( w ) if and only if for all w ∈ W, 〈∇h(π), w−π〉≥ 0 ⇔ 〈π−α, w−π〉≥ 0 ⇔ 〈α−π, w−π〉≥ 0.
where we used Lemma 0.3 in the last inequality. Now for δ = 0, E A F ( W A ( X ), X ) − F ( W * ( X ), X ) ≤ √ 2 L ( Δ F + ( ξ ) + α. Then using Lemma 0.1 to bound △ F proves the first statement in each of 1a) and 2a). Similarly, for δ > 0, we have
Appealing again to Lemma 0.1 completes the proof. The verification that the prescribed choices of α achieve the re- spective fundamental upper bounds is routine, using the as- sumptions stated in the theorem. Next, we recall the following convergence guarantee for strongly convex, Lipschitz objective: Proposition 0.1  (Aravkin et al. 2017, Proposition 5.3)  For F ∈ F μ , L , R , running the subgradient method for T = iterations and step sizes η t = μ ( t + 1) results in a point w τ ∈ W such that F( wr, X) – F( w*( X), X) ≤ α. Here wr = argmin w t ,t ∈ [ T ] F ( W t , X ). Then Theorem 2.1 is a direct consequence of Proposi- tion 0.1 and Theorem 0.2. We begin by proving an analogue of Theorem 0.2 for β- smooth loss functions. Theorem 0.3  Run Algorithm 1 on F ∈ H β,μ,L,R with arbi- trary inputs.
To prove Theorem 0.3, write
where in the last line we used the descent lemma and Lemma 0.3. Now for δ = 0,
Substituting the bounds on △ F from Lemma 0.1 proves the first statement in each of 1a) and 2a). Similarly, for δ > 0,
Again appealing to Lemma 0.1 establishes the first state- ments in 1b) and 2b). Verification that the prescribed choices of α achieve the claimed bounds is straightforward, complet- ing the proof of Theorem 0.3. ( μ + β ) R 2 = O( √ κ) it- Recall that running T = √ κ log ( erations (each iteration involves a full gradient evaluation of F ) of Nesterov's AGD is sufficient for finding ŵ T ( X ) such that F( ŵ T ( X ), X ) – F( w *( X ), X ) ≤ α (Bubeck 2015). Combining this with Theorem 0.3 yields Theorem 2.2. By standard  arguments, that sup|XAX'|≤2 || wr(X) — wr Let | X △ X ′ | ≤ 2. Then
The last line follows because: λ-strong convexity of F λ im- plies the middle term is bounded according to Lemma 0.1 and the other two terms are both bounded by a similar argu- ment as in the proof of Proposition 2.1, again using λ-strong convexity of F λ . As before, we first prove a general result for our black box Algorithm 2, whence Theorem 2.3 will follow as a corollary.
To prove Theorem 0.4, decompose excess risk into 3 terms:
bound follows: terms Now as the + AR)Ellur(X ( L AE WAX(X) (b) 0; + E [ z λ  2]; and  O w (X) + z λ  ≥ (L + XR)[V] F λ (w*(X), X)] + [F λ (w*(X), X) [F λ (w ) (X) - F(w*(X),X)] < 0 +슬‖w*(X)‖≥ ≤ ∧雲² since w*(X is the unique minimizer of F ( · , X ) by strong con- E A F ( W A ( X ), X ) F(w*(X),X) vexity. Hence (L + λ R )み+ E||zメ||2 Assume that F E GERM : the proof of the non-ERM case is very similar (but simpler since n disappears). First √2d( △ x +2√ 25) 0, so E 2( L+λR) A , by our choice of λ
gives the first statement of part 2b). Using the assumptions and estimates above, it is easy to verify that the prescribed choices of α yield the second statements in each part of the theorem. We can now prove Theorem 2.3: Recall that the itera- tion complexity of the subgradient method on F λ for find- ing wT such that F λ ( wT ( ∑ )) − F λ ( w ) ( X ), X ) ≤ α 2(L+AR)² is T  < ≤  ↹ ² (Aravkin et al. 2017) by λ -strong λα convexity and ( L + λ R )-Lipschitzness of F λ ( · , X ), as well as our choices of λ (see proof of Theorem 0.4). Then plug- ging in the exact choices of λ and α gives the risk bound results. For runtime results, multiply the iteration complex- ity by d since each iteration requires one gradient evaluation of F. We begin with a more general result:
VI
VI V +
To prove Theorem 0.5, first decompose excess risk into 3 terms as usual:
follows: Now bound terms as (a) the ll < 0. By the descent lemma (note çE||w a,x (X)||² )( , X ) is ( β + λ )-smooth) and independence of the noise z λ and ∇ F λ ( w , X ), we have (b =
[F λ (w ) (X), X)   −  F λ (w*(X), X)]   + Lastly,   ©   = [F λ (w*(X),X) − F(w*(X),X)] < 0 + ≥ ||w*(X)||≥ ≤ YR² since w ) (X) is the unique minimizer of F λ ( · , X) convexity.  Hence by E A F ( W A ( X ), X ) strong F(w*(X), X) ≤쓰쓰+ (β + λ)E||zｽ||≥ + α. Assume that F ∈ J β L R : the proof of the non-ERM case is very similar, but simpler since n disappears. First 2d2(2,/2号+Δι)2 Suppose  δ  =  0, so E||zλ||3 that for our choice of λ given in Theorem 0.5, and ( L + λ R )  ≤  2L by the assumption < Rβ always holds for and since  L 2(L+XR)
Putting these pieces together proves the first statement in part 2a). Verifying the second statement is routine, using the assumptions stated in the theorem and the estimates obtained above.
△ to bound the first two terms in the sum. Then plugging 2/3 1/3 √d(cs+√cz+c) BL² and using the esti- in λ = mates and assumptions completes the proof of the first state- ment of the theorem. Again, the second statement is easy to verify by plugging in the prescribed α . This proves Theo- rem 0.5. Theorem 2.4 then follows from the above theorem and the iteration complexity of AGD (Nesterov 2014). We begin with a definition and lemma from (Bassily et al. 2019) that will be very useful for us. Definition 2 (Uniform stability) Let α > 0. An algorithm A : X n → W is α-uniformly stable (w.r.t loss function f) if for any pair of data sets X , X ′ ∈ X n differing by at most one point (i.e. | X X ′ | ≤ 2), we have sup E A [f(A(X), x) - f(A(X'), x)] < α. Lemma 0.4  Let A : X n → W be an α-uniformly stable algorithm w.r.t. loss function f and let X ～ D n . Then E X~D~,A[F(A(X),D) - F(A(X),X)] < α. Combining Lemma 0.4 with our excess empirical risk bounds from before for each ERM function class will en- able us to upper bound the population loss.
as before. Observe that △ T with respect to f by Lemma 0.4. Plugging in the choices of α given in the Corollary shows that (a) < 5年. Next, by
α and T . Finally, (c) < 0. Putting these estimates together completes the proof of the excess loss bounds. μ , L Recall that running SGD on F ∈ F , with η  = µ(t + 1) produces a point w T such that EF ( w T , X ) 2 L 2 stochastic gradient eval- F(w*(X),X) ≤ α in T = uations (Bubeck 2015, Theorem 6.2). Since each iteration amounts to just one gradient evaluation of f ( w, x i ) (with runtime d ), the resulting runtime of the full method is O(dT). The proof follows exactly as the proof of Theorem 3.1, but using Theorem 0.3 instead of Theorem 0.2 to bound (6). The runtime bounds follow from applying the following: Theorem 0.6  (Allen-Zhu 2018, Theorem 2.1 simplified)  Let F : R d → R, F (w) = 1 ∑ i=1 f i (w) = 1 ∑ i=1 9 i (w) + strongly convex, and κ := β . Then running Katyusha fo F(wo)-F(w") ( n + √ n κ ) log stochastic gradi- ent iterations returns a point ŵ T ∈ R d such that F ( ŵ T ) F(w*) < α. Clearly, given any F u H β,μ,L,R and any X n ∑ i=1 f(w,x i) X n , we can write F(w,X) ll n ∑ i=1 g(w,x i) + ψ(w), where ψ(w) :=  ζ ∥ w ∥ 2 is strongly convex, g( , x i ) = f( , x i ) − ψ( · ) is convex and ( β − μ )-smooth (hence β -smooth) for all x i ∈ X . Decompose
as before. First, A is LΔτ-uniformly stable with res = supixax'i strong convexity of F λ . Hence ( a ) ≤ 2 h Lemma 0.4. Now
by decomposing and bounding as done in the proof of The- orem 0.4. Also, ✓ ≤ 0 as usual. Then combining the above with our choices of λ,α, T and using plugging in expected values of the noise completes the proof of the loss bounds. The runtime bounds follow from the SGD runtime bounds stated earlier and the choices of λ prescribed above. The proof follows almost exactly as the proof of Theorem 3.3 above, but uses the descent lemma to bound ① with a (βξλ|E||zｽ||² term (instead of (L + λR)E||zｽ||2) and uses Theorem 2.4 (Katyusha) instead of Theorem 2.3 (SGD), along with the alternative choices of α and λ , to obtain the stated loss bounds in faster runtime. We first require a tighter estimate of the sensitivity of F t : Lemma 0.5  Let τ > 0. Suppose  f( , x ) is L-Lipschitz on B(0, R) (where ‖w*(X)‖ ≤ R) and μ-strongly convex for all x ∈ X . Moreover, assume a R ≤ f (w,x) ≤ A R for all w ∈ W and all x ∈ X . Then
where C τ := e τ ( A R − a R ) To prove the lemma, we follow the same approach used in proving ??. Let X,X' E X n such that |X X ′ | 2 and assume WLOG that xn Lemma 0.2 with g t (w) := F t (w. G 7 (w) := F 7 (w,X'). Denote vi(T,W) Then observe that
Now convexity and L -Lipschitzness of f impl ||∇ɡｧ(w)|| ≤ 2L max{vn(τ,w),vn(τ,w)} ≤ 2LC τ This proof is completed by noticing that G r is μ -strongly convex and appealing to Lemma 0.2. Then to obtain Proposition 4.1, simply plug the esti- mate for △ F  given above into the proof of Theorem 0.2 L²Cz min { m , Cz d } for δ  =  0 and α  = for δ ∈ (0, ξ ). The run- time bounds are proved by recalling that the iteration com- plexity of the subgradient method for obtaining an α- suboptimal point w T of F t is T = (and noting that each gradient evaluation of F 7 has runtime O ( nd )). First, we have ∇ F 7 (w, X) i=1 Vi(w,T)Vfi(w), where f i ( w ) we T)fi(w2))|, i=1 (Vi(W1,T)Vfi(W1) + Lv, || w1 — w2 || 2L ) L e=1 (vi(w1,τ)β||w1 − β|| w1 L wi W2 2 w2||2 __i=1 (Lvi), Lipschitz where L v denotes the constant of a function of w. Next, we compute V z ( W , T ) as bounding by ||∇ v i ( w , τ ) || V v;(w, T) Lvi τε f i(w)∇ f i(w)(Σ i =1 e ≠ f j(w))—1 e ≠ f j(w)∇ f j(w)e ≠ f i(w) ( ∑ j = 1 c t j ( w ) ) 2
Aleksandr Aravkin, James Burke, and Dmitry Drusvyatskiy. Convex Analysis and Nonsmooth Optimization . 2017. Raman Arora, Teodor V. Marinov, and Enayat Ullah. Private stochastic convex optimization: Efficient algorithms for non- smooth objectives. arXiv:2002.09609v1 , 2020. Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Dif- ferentially private empirical risk minimization: Efficient al- gorithms and tight error bounds. arXiv:1405.7085v2 , 2014. and hence Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates.  Advances in Neural Information Processing Systems , 32:11282–11291, 2019. ≤ (β + 2L²τ) || w1 − w2 || 2 , which completes the proof. Olivier Bousquet and Andre Elisseeff.  Stability and gener- alization. Journal of machine learning research , 2002. Plugging the estimate for △ F  from Lemma 0.5 into the proof of Theorem 0.3 and set Stephen Boyd, Corinna Cortes, Mehryar Mohri, and Ana Accuracy at the top. Radovanovic. In  F.  Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, ed- itors, Advances in Neural Information Processing Sys- tems , volume 25, pages 953–961. Curran Associates, Inc., 2012. URL https://proceedings.neurips.cc/paper/2012/file/ 7fe1f8abaad094e0b5cb1b01d712f708-Paper.pdf. Sebastian Bubeck.  Convex optimization: Algorithms and complexity.  Foundations and Trends in Machine Learning , 8, 2015. Kamalika Chaudhuri, Claire Monteleoni, and Anand Sar- wate.  Differentially private empirical risk minimization. Journal of Machine Learning Research , 12:1069–1109, 2011. if δ ∈ (0, ξ ). The runtime claim follows by recalling the O( √ κ τ ) gradient complexity of AGD. Nadav Cohen and Amnon Shashua.  Simnets: A generaliza- tion of convolutional networks. arXiv:1410.0781v3 , 2014. Nadav Cohen, Or Sharir, and Amnon Shashua.  Deep sim- nets.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , pages 4782–4791, 2016.  doi: 10.1109/CVPR.2016.517. Theorem 4.1 is an immediate consequence of Theorem 0.3 combined with the following: Proposition 0.2 ((Lin et al. 2020, Thm 5.1/Cor 5.2)) As- sume G( ·, ν) is μ-strongly convex, β-smooth, (with condi- tion number κ = β/μ) for all ν ∈ B ν , G( w , · ) is β ν -smooth and concave as a function of v ∈ B v for all w ∈ W . Then 1. Minimax-APPA returns an α-saddle point in at most l =β=ν) total gradient evaluations. T = O( 2. If, in addition, G(w, ) is μ v -strongly concave, then Minimax-APPA returns an α -saddle point in at most T = O( √ RK v ) gradient evaluations, where κ v = β = is the con- dition number. Amit Datta, Michael Carl Tschantz, and Anupam Datta. Au- tomated experiments on ad privacy settings: A tale of opac- ity, choice, and discrimination.  Proceedings on privacy en- hancing technologies , 2015(1):92–112, 2015. Cynthia Dwork and Aaron Roth. The Algorithmic Founda- tions of Differential Privacy. 2014. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In Advances in Cryptol- ogy - EUROCRYPT 2006 , volume 4004 of Lecture Notes in Computer Science . Springer, Berlin, Heidelberg, 2006. Kevin Eykholt, Ivan Evtimov, Earlance Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song.  Robust physical-world attacks on deep learning visual classification. In 2018 IEEE/CVF Con- ference on Computer Vision and Pattern Recognition , pages 1625–1634, 2018. doi: 10.1109/CVPR.2018.00175. Mohammad Alkousa, Darina Dvinskikh, Fedor Stonyakin, Alexander Gasnikov, and Dmitry Kovalev. Accelerated methods for composite non-bilinear saddle point problem, 2020. Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods.  Journal of Machine Learning Research, 18(221):1–51, 2018.  URL http://jmlr.org/papers/ v18/16-410.html. Vitaly Feldman, Tomer Koren, and Kunal Talwar.  Private stochastic convex optimization: Optimal rates in linear time. arXiv:2005.04763v1 , 2020. Ferdinando Fioretto, Terrence WK Mak, and Pascal Van Hentenryck.  Differential privacy for power grid obfus- cation. IEEE Transactions on Smart Grid , 11(2):1356–1366, 2019. Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Interna- tional Conference on Learning Representations , 2015. URL http://arxiv.org/abs/1412.6572. Moritz Hardt, Benjamin Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient de- scent.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning , volume 48 of Proceedings of Ma- chine Learning Research , pages 1225–1234, New York, New York, USA, 20–22 Jun 2016. PMLR. URL http: //proceedings.mlr.press/v48/hardt16.html. Elad Hazan and Satyen Kale. Beyond the regret mini- mization barrier: Optimal algorithms for stochastic strongly- convex optimization.  Journal of Machine Learning Re- search, 2014. Angelos Katharopoulos and François Fleuret. Biased importance sampling for deep neural network training. arXiv:1706.00043 , 2017. Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression.  In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Con- ference on Learning Theory , volume 23 of Proceedings of Machine Learning Research , pages 25.1–25.40, Edinburgh, Scotland, 25–27 Jun 2012. PMLR.  URL http://proceedings. mlr.press/v23/kifer12.html. Barry W. Kort and Dimitri P. Bertsekas.  A new penalty function method for constrained minimization. In Proceed- ings of the 1972 IEEE Conference on Decision and Con- trol and 11th Symposium on Adaptive Processes , pages 162– 166, 1972. doi: 10.1109/CDC.1972.268971. Tian Li, Ahmad Beirami, Maziar Sanjabi, and Vir- ginia Smith. Tilted empirical risk minimization. arXiv:2007.01162v1 , 2020. Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A univer- sal catalyst for first-order optimization.  Advances in neural information processing systems , 28:3384–3392, 2015. Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal al- gorithms for minimax optimization. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Con- ference on Learning Theory , volume 125 of Proceedings of Machine Learning Research , pages 2738–2779. PMLR, 09– 12 Jul 2020.  URL http://proceedings.mlr.press/v125/lin20a. html. Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learn- ing models resistant to adversarial attacks.  In 6th Interna- tional Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Con- ference Track Proceedings. OpenReview.net, 2018.  URL https://openreview.net/forum?id=rJzIBfZAb. Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard.  Deepfool: A simple and accurate method to fool deep neural networks.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2574–2582, 2016. doi: 10.1109/CVPR.2016.282. Yurii Nesterov.  Introductory Lectures on Convex Optimiza- tion: A Basic Course. Springer Publishing Company, Incor- porated, 1 edition, 2014. ISBN 1461346916. Yurii Nesterov and Laura Scrimali. Solving strongly mono- tone variational and quasi-variational inequalities.  Discrete and Continuous Dynamical Systems , 31, 01 2007. doi: 10.2139/ssrn.970903. Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn.  Solving a class of non- convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems 32 , pages 14934–14942. Curran Associates, Inc., 2019. URL http://papers.nips.cc/paper/9631-solving-a-class-of- non-convex-min-max-games-using-iterative-first-order- methods.pdf. Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami.  The limitations of deep learning in adversarial settings.  In 2016 IEEE European Symposium on Security and Privacy (EuroS P), pages 372–387, 2016. doi: 10.1109/EuroSP.2016.36. E.Y. Pee and J. O. Royset.  On solving large-scale finite minimax problems using exponential smoothing.  Journal of Optimization Theory and Applications , 148(2):390–421, URL https://ideas.repec.org/a/spr/joptap/ February 2011. v148y2011i2d10.1007_s10957-010-9759-1.html. Hai Phan, My T Thai, Han Hu, Ruoming Jin, Tong Sun, and Dejing Dou.  Scalable differential privacy with certified ro- bustness in adversarial learning. In International Conference on Machine Learning , pages 7683–7694. PMLR, 2020. Maurice Sion. On general minimax theorems. Pacific Jour- nal of Mathematics, pages 171–176, 1958. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks.  In International Conference on Learning Representations , 2014.  URL http: //arxiv.org/abs/1312.6199. Di Wang, Minwei Ye, and Jinhui Xu.  Differentially private empirical risk minimization revisited: Faster and more gen- eral.  Advances in Neural Information Processing Systems , 30:2722–2731, 2017. Jun Wang, Rongbo Zhu, Shubo Liu, and Zhaohui Cai. Node location privacy protection based on differentially private grids in industrial wireless sensor networks. Sensors , 18(2): 410, 2018. Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Lau- rent El Ghaoui, and Michael Jordan.  Theoretically prin- cipled trade-off between robustness and accuracy.  In Ka- malika Chaudhuri and Ruslan Salakhutdinov, editors, Pro- ceedings of the 36th International Conference on Machine Learning , volume 97 of Proceedings of Machine Learning Research , pages 7472–7482. PMLR, 09–15 Jun 2019.  URL http://proceedings.mlr.press/v97/zhang19p.html. Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives.  In Proceedings of the 26th International Joint Conference on Artificial In- telligence , pages 3922–3928, 2017. Jun Zhao, Teng Wang, Tao Bai, Kwok-Yan Lam, Zhiying Xu, Shuyu Shi, Xuebin Ren, Xinyu Yang, Yang Liu, and Han Yu. Reviewing and improving the gaussian mechanism for differential privacy. arXiv:1911.12060v2, 2019.