Private optimization in the interpolation regime: faster rates and hardness results

In non-private stochastic convex optimization, stochastic gradient methods converge much faster on interpolation problems -- problems where there exists a solution that simultaneously minimizes all of the sample losses -- than on non-interpolating ones; we show that generally similar improvements are impossible in the private setting. However, when the functions exhibit quadratic growth around the optimum, we show (near) exponential improvements in the private sample complexity. In particular, we propose an adaptive algorithm that improves the sample complexity to achieve expected error $\alpha$ from $\frac{d}{\varepsilon \sqrt{\alpha}}$ to $\frac{1}{\alpha^\rho} + \frac{d}{\varepsilon} \log\left(\frac{1}{\alpha}\right)$ for any fixed $\rho>0$, while retaining the standard minimax-optimal sample complexity for non-interpolation problems. We prove a lower bound that shows the dimension-dependent term is tight. Furthermore, we provide a superefficiency result which demonstrates the necessity of the polynomial term for adaptive algorithms: any algorithm that has a polylogarithmic sample complexity for interpolation problems cannot achieve the minimax-optimal rates for the family of non-interpolation problems.


Introduction
We study differentially private stochastic convex optimization (DP-SCO), where given a dataset S = S n 1 iid ∼ P we wish to solve minimize f (x) = E P [F (x; S)] = Ω F (x; s)dP (s) subject to x ∈ X , (1) while guaranteeing differential privacy. In problem (1), X ⊂ R d is the parameter space, Ω is a sample space, and {F (·; s) : s ∈ S} is a collection of convex losses. We study the interpolation setting, where there exists a solution that simultaneously minimizes all of the sample losses.
Interpolation problems are ubiquitous in machine learning applications: for example, least squares problems with consistent solutions [SV09, NWS14], and problems with over-parametrized models where a perfect predictor exists [MBB18, BHM18, BRT19]. This has led to a great deal of work on the advantages and implications of interpolation [SST10, CSSS11, BHM18, BRT19].
For non-private SCO, interpolation problems allow significant improvements in convergence rates over generic problems [SST10, CSSS11, MBB18, VBS19, WS21]. For general convex functions, [SST10] develop algorithms that obtain O( 1 n ) sub-optimality, improving over the minimax-optimal rate O( 1 √ n ) for non-interpolation problems. Even more dramatic improvements are possible when the functions exhibit growth around the minimizer, as [VBS19] show that SGD achieves exponential rates in this setting compared to polynomial rates without interpolation. [AD19, ACCD20, CCD22] extend these fast convergence results to model-based optimization methods. Despite the recent progress and increased interest in interpolation problems, in the private setting they remain poorly understood. In spite of the substantial progress in characterizing the tight convergence guarantees for a variety of settings in DP optimization [BST14, BFTT19, FKT20, AFKT21, ALD21], we have little understanding of private optimization in the growing class of interpolation problems.
Given (i) the importance of differential privacy and interpolation problems in modern machine learning, (ii) the (often) paralyzingly slow rates of private optimization algorithms, and (iii) the faster rates possible for non-private interpolation problems, the interpolation setting provides a reasonable opportunity for significant speedups in the private setting. This motivates the following two questions: first, is it possible to improve the rates for DP-SCO in the interpolation regime? And, what are the optimal rates?

Our contributions
We answer both questions. In particular, we show that 1. No improvements in general (Section 3): our first result is a hardness result demonstrating that the rates cannot be improved for DP-SCO in the interpolation regime with general convex functions. More precisely, we prove a lower bound of Ω( d nε ) on the excess loss for pure differentially private algorithms. This shows that existing algorithms achieve optimal private rates for this setting.
[BST14] study the closely related problem of differentially private empirical risk minimization (DP-ERM) where the goal is to minimize the empirical loss, and obtain (minimax) optimal rates of d/nε for pure DP and d log(1/δ)/nε for (ε, δ)-DP. Recently, more papers have moved beyond DP-ERM to privately minimizing the population loss (DP-SCO) [BFTT19, FKT20, AFKT21, ADF + 21, BGN21,ALD21]. [BFTT19] was the first paper to obtain the optimal rate 1/ √ n + d log(1/δ)/nε for (ε, δ)-DP, and subsequent papers develop more efficient algorithms that achieve the same rates [FKT20, BFGT20]. Moreover, other papers study DP-SCO under different settings including non-Euclidean geometry [AFKT21, ADF + 21], heavy-tailed data [WXDX20], and functions with growth [ALD21]. However, to the best of our knowledge, there has not been any work in private optimization that studies the problem in the interpolation regime.
[SST10] propose algorithms that roughly achieve the rate 1/n + f ⋆ /n for smooth and convex functions where f ⋆ = min x∈X f (x). In the interpolation regime with f ⋆ = 0, this result obtains loss 1/n improving over the standard 1/ √ n rate for non-interpolation problems. Moreover, [VBS19] studied the interpolation regime for functions with growth and show that SGD enjoys linear convergence (exponential rates). More recently, several papers investigated and developed acceleration-based algorithms in the interpolation regime [LB20, WS21].

Preliminaries
We begin with notation that will be used throughout the paper and provide some standard definitions from convex analysis and differential privacy.
Notation We let n denote the sample size and d the dimension. We let x denote the optimization variable and X ⊂ R d the constraint set. s are samples from Ω, and S is an Ω-valued random variable. For each sample s ∈ Ω, F (·; s) : R d → R ∪ {+∞} is a closed convex function. Let ∂F (x; s) denote the subdifferential of F (·; s) at x. We let Ω n denote the collection of datasets S = (s 1 , . . . , s n ) with n data points from Ω. We let f S (x) := 1 n s∈S F (x, s) denote the empirical loss and f (x) := E[F (x; S)] denote the population loss. The distance of a point to a set is dist (x, Y ) = min y∈Y x − y 2 . We use Diam(X ) = sup x,y∈X x − y 2 to denote the diameter of parameter space X and use D as a bound on the diameter of our parameter space.
Definition 2.1. A randomized mechanism M is (ε, δ)-differentially private ((ε, δ)-DP) if for all datasets S, S ′ ∈ Ω n that differ in a single data point and for all events O in the output space of M , we have We define ε-differential privacy (ε-DP) to be (ε, 0)-differential privacy.
We now recall a couple of standard convex analysis definitions.

A function
Equivalently, a function is L-Lipschitz if ∇f (x) 2 ≤ L for all x ∈ X .

A function
h is H-smooth if it has H-Lipschitz gradient: for all x, y ∈ X ∇h(x) − ∇h(y) 2 ≤ H x − y 2 .

A function
We formally define interpolation problems: Definition 2.3 (Interpolation Problem). Let X ⋆ := argmin x∈X f (x). Then problem (1) is an interpolation problem if there exists x ⋆ ∈ X ⋆ such that for P -almost all s ∈ Ω, we have 0 ∈ ∂F (x ⋆ ; s).
Interpolation problems are common in modern machine learning, where models are overparameterized. One simple example is overparameterized linear regression: there exists a solution that minimizes each individual sample function. Classification problems with margin are another example.
Crucial to our results is the following quadratic growth assumption: Definition 2.4. We say that a function f satisfies the quadratic growth condition if for all x ∈ X This assumption is natural with interpolation and holds for many important applications including noiseless linear regression [SV09, NWS14]. Past work ([VBS19, WS21]) uses this assumption with interpolation to get faster rates of convergence for non-private optimization.
Finally, the adaptivity of our algorithms will crucially depend on an innovation leveraging Lipchitizian extensions, defined as follows. (2) The Lipschitzian extension (2) essentially transforms a general convex function into an L-Lipschitz convex function. We now present a few properties of the Lipschitzian extension that are relevant to our development.
Lemma 2.1. Let f : X → R be convex. Then its Lipschitzian extension satisfies the following: We use the Lipschitzian extension as a substitute for gradient clipping to ensure differential privacy. Unlike gradient clipping, which may alter the geometry of a convex problem to a non-convex one, the Lipschitzian extension of a function remains convex and thus retains other nice properties that we leverage in our algorithms in Section 4.

Hardness of private interpolation
In non-private stochastic convex optimization, for smooth functions it is well known that interpolation problems enjoy the fast rate O(1/n) [SST10] compared to the minimax-optimal O(1/ √ n) without interpolation [Duc18]. In this section, we show that such an improvement is not generally possible with privacy. The same lower bound of private non-interpolation problems, d/nε, holds for interpolation problems.
To state our lower bounds, we present some notation that we will use throughout of the paper. We let S denote the family of function F and dataset S pairs such that F : X × Ω → R is convex and H-smooth in its first argument, |S| = n, and f S (y) = 1 n s∈S F (y, s) is an interpolation problem (Definition 2.3). We define the constrained minimax risk to be where M (ε,δ) be the collection of (ε, δ)-differentially private mechanisms from Ω n to X . We use M (ε,0) to denote the collection of ε-DP mechanisms from Ω n to X . Here, the expectation is taken over the randomness of the mechanism, while the dataset S n is fixed.
We have the following lower bound for private interpolation problems; the proof is deferred to Appendix B.1.
Recall the optimal rate for pure DP optimization problems without interpolation is O( 1 √ n + d nε ). The first term is the non-private rate, as this is the rate one would get if ε = 0. The second term is the private rate, as this is the price algorithms have to pay for privacy. In modern machine learning, problems are often high dimensional, so we often think of the dimension d scaling with some function of the number of samples n. Thus, the private rate is often thought to dominate the non-private rate. For this reason, in this section, we focus on the private rate. The lower bounds of Theorem 1 show that it is not possible to improve the private rate for interpolation problems in general. Similarly, for approximate (ε, δ)-DP, the lower bound shows that improvements are not possible for d = 1. For completeness, as we alluded to earlier, we note that our results do not preclude the possibility of improving the non-private rate from O(1/ √ n) to O(1/n). We leave this as an open problem of independent interest for future work.
Despite this pessimistic result, in the next section we show that substantial improvements are possible for private interpolation problems with additional growth conditions.

Faster rates for interpolation with growth
Having established our hardness result for general interpolation problems, in this section we show that when the functions satisfy additional growth conditions, we get (nearly) exponential improvements in the rates of convergence for private interpolation.
Our algorithms use recent localization techniques that yield optimal algorithms for DP-SCO [FKT20, ALD21] where the algorithm iteratively shrinks the diameter of the domain. However, to obtain faster rates for interpolation, we crucially build on the observation that the norm of the gradients is decreasing as we approach the optimal solution, since ∇F (x; s) 2 ≤ H x − x ⋆ 2 . Hence, by carefully localizing the domain and shrinking the Lipschitz constant accordingly, our algorithms improve the rates for interpolating datasets. However, this technique alone yields an algorithm that may not be private for non-interpolation problems, violating that privacy must hold for all inputs: the reduction in the Lipschitz constant may not hold for non-interpolation problems, and thus, the amount of noise added may not be enough to ensure privacy. To solve this issue, we use the Lipschitzian extension (Definition 2.5) to transform our potentially non-Lipschitz sample functions into Lipschitz ones and guarantee privacy even for non-interpolation problems.
We begin in Section 4.1 by presenting our Lipschitzian extension based algorithm, which recovers the standard optimal rates for (non-interpolation) L-Lipschitz functions while still guaranteeing privacy when the function is not Lipschitz. Then in Section 4.2 we build on this algorithm to develop a localization-based algorithm that obtains faster rates for interpolation-with-growth problems. Finally, in Section 4.3 we present our final adaptive algorithm, which obtains fast rates for interpolation-withgrowth problems while achieving optimal rates for non-interpolation growth problems.

Lipschitzian-extension based algorithms
Existing algorithms for DP-SCO with L-Lipschitz functions may not be private if the input function is not L-Lipschitz [BFGT20, FKT20, ALD21]. Given any DP-SCO algorithm M L (ε,δ) , which is private for L-Lipschitz functions, we present a framework that transforms M L (ε,δ) to an algorithm which is (i) private for all functions, even ones which are not L-Lipschitz functions and (ii) has the same utility guarantees as M L (ε,δ) for L-Lipschitz functions. In simpler terms, our algorithm essentially feeds M L (ε,δ) the Lipschitzian-extension of the sample functions as inputs. Algorithm 1 describes our Lipschitzianextension based framework.

Algorithm 1 Lipschitzian-Extension Algorithm
Require: Dataset S = (s 1 , . . . , s n ) ∈ S n ; 1: Let F L (x; s i ) be the Lipschitzian extension of F (x; s i ) for all i.
For this paper we consider M L (ε,δ) to be Algorithm 2 of [ALD21] (reproduced in Appendix A.2 as Algorithm 5). The following proposition summarizes our guarantees for Algorithm 1.
Proof For the first item, note that Lemma 2.1 implies that For the second item, Lemma 2.1 implies that F L = F when F is L-Lipschitz. Thus, in Algorithm 1, we apply M L (ε,δ) over F itself.
While clipped DP-SGD does ensure privacy for input functions which are not L-Lipschitz, our algorithm has some advantages over clipped DP-SGD: first, clipping does not result in optimal rates for Algorithm 2 Domain and Lipschitz Localization algorithm Require: Dataset S = (s 1 , . . . , s n ) ∈ S n , Lipschitz constant L, domain X , probability parameter β, initial point x 0 1: Set L 1 = L, D 1 = Diam(X ) and X 1 = X 2: Partition the dataset into T partitions (denoted by {S k } T k=1 ) of size m each; S k = (s (k−1)m+1 , . . . , s km ) 3: for i = 1 to T do 4: Set L i+1 = HD i+1 8: end for 9: return the final iterate x T pure DP, and second, clipped DP-SGD results in time complexity O(n 3/2 ). In contrast, our Lipschitzian extension approach is amenable to existing linear time algorithms [FKT20] allowing for almost linear time complexity algorithms for interpolation problems. Finally, while clipping the gradients and using the Lipschitzian extension both alter the effective function being optimized, only the Lipschitzian extension is able to preserve the convexity of said effective function (see item 2 in Lemma 2.1). We make a note about the computational efficiency of Algorithm 1. Recall that when the objective is in fact L-Lipschitz, computing gradients for the Lipschitzian extension (say in the context of a first-order method) is only as expensive as computing the gradients for the original function. In particular, one can first compute the gradient of the original function and use item 4 of Lemma 2.1; when the problem is L-Lipschitz, ∇f (x) 2 is always less than or equal to L and thus the gradient of the Lipschitzian extension is just the gradient of the original function.

Faster non-adaptive algorithm
Building on the Lipschitzian-extension framework of the previous section, in this section, we present our epoch based algorithm, which obtains faster rates in the interpolation-with-growth regime. It uses Algorithm 1 with M L (ε,δ) as Algorithm 5 (reproduced in Appendix A.2) as a subroutine in each epoch, to localize and shrink the domain as the iterates get closer to the true minimizer. Simultaneously, the algorithm also reduces the Lipschitz constant, as the interpolation assumption implies that the norm of the gradient decreases for iterates near the minimizer. The detailed algorithm is given in Algorithm 2 where D i denotes the effective diameter and L i denotes the effective Lipschitz constant in epoch i.
The following theorem provides our upper bounds for Algorithm 2, demonstrating near-exponential rates for interpolation problems; we present the proof in Appendix C.
Theorem 2. Assume each sample function F is L-Lipschitz and H-smooth, and let the population function f satisfy quadratic growth (Definition 2.4). Let Problem (1) be an interpolation problem.
log n , T = n/m and any µ > 0, Algorithm 2 returns x T such that For δ > 0, β = 1 n µ , m = 256 log 2 n H log(1/β) , T = n/m and any µ > 0, The exponential rates in Theorem 2 show a significant improvement in the interpolation regime over the minimax-optimal O(( 1 ALD21]. To get the linear convergence rates, we run roughly n/ log n epochs with log n samples each. Thus, each call of the subroutine runs the algorithm on only logarithmic number of samples compared to the number of epochs. Intuitively, growth conditions improves the performance of the sub-algorithm, while growth and interpolation conditions reduce the search space. This in tandem leads to faster rates.
To better illustrate the improvement in rates compared to the non-private setting, the next corollary states the private sample complexity required to achieve error α in the interpolation regime.
Corollary 4.1. Let the conditions of Theorem 2 hold. For δ = 0 , Algorithm 2 is ε-DP and requires As the sample complexity of DP-SCO to achieve expected error α on general quadratic growth problems is [ALD21] Corollary 4.1 shows that we are able to improve the polynomial dependence on 1/α in the sample complexity to (nearly) logarithmic for interpolation problems.
Remark 1. In contrast to Corollary 4.1, we can tune the failure probability parameter β to get the sample complexity d ε log 2 1 α . Even though this sample complexity does not have the polynomial factor, it may be worse than 1 α ρ + d ε log 1 α , because generally the dimension term is the dominant one. We end this section by considering growth conditions that are weaker than quadratic growth.
Remark 2. (interpolation with κ-growth) We can extend our algorithms to work for the weaker κ- We present the full details of these algorithms in Appendix C.1 (see Algorithm 6). In this setting, we obtain excess loss for interpolation problems, improving over the minimax-optimal loss for non-interpolation problems which is As an example, when κ = 3, this corresponds to an improvement from roughly (d/nε) 3/2 to (d/nε) 3 . Like our previous results, we are again able to show similar improvements for (ε, δ)-DP with better dependence on the dimension. Finally, we note that we have not provided lower bounds for the interpolation-with-κ-growth setting for κ > 2. We leave this question as a direction for future research.

Adaptive algorithm
Though Algorithm 2 is private and enjoys faster rates of convergence in the interpolation regime, it is not necessarily adaptive to interpolation, i.e. it may perform poorly given a non-interpolation problem. In fact, since the shrinkage of the diameter and Lipschitz constants at each iteration hinges squarely on the interpolation assumption, the new domain may not include the optimizing set X ⋆ in the noninterpolation setting, so our algorithm may not even converge. Since in general we do not know a priori whether a dataset is interpolating, it is important to have an algorithm which adapts to interpolation.
To that end, we present an adaptive algorithm that achieves faster rates for interpolation-withgrowth problems while simultaneously obtaining the standard optimal rates for general growth problems. The algorithm consists of two steps. In the first step, our algorithm privately minimizes the objective without assuming it is an interpolation problem. Next, we run our non-adaptive interpolation algorithm of Section 4.2 over the localized domain returned by the first step. If our problem was an interpolating one, the second step recovers the faster rates in Section 4.2. If our problem was not an interpolating one, the first localization step ensures that we at least recover the non-interpolating convergence rate. We stress that the privacy of Algorithm 3 requires that the call to Algorithm 2 remains private even if the problem is non-interpolating. This is ensured by using our Lipschitzian extension based algorithm with M L (ε,δ) as Algorithm 5. The Lipschitzian extension allows us to continue preserving privacy. We present the full details of this algorithm in Algorithm 3.
The following theorem (Theorem 3) states the convergence guarantees of our adaptive algorithm (Algorithm 3) in both the interpolation and non-interpolation regimes for the pure DP setting. The results for approximate DP are similar and can be obtained by replacing d with d log(1/δ); we give the full details in Appendix C.
Theorem 3. Let each sample function F be L-Lipschitz and H-smooth, and let the population function f satisfy quadratic growth (Definition 2.4) with coefficient λ. Let x adapt be the output of Algorithm 3. Then 1. Algorithm 3 is ε-DP.

Without any additional interpolation assumption, x adapt satisfies
3. Let problem (1) be an interpolation problem. Thenx adapt satisfies Proof The privacy of Algorithm 3 follows from the privacy of Algorithms 1 and 2 and post-processing.
To prove the convergence guarantees, we first need to show that the optimal set X ⋆ is in the shrinked domain X int . Using the high probability guarantees of Algorithm 1, we know that with probability 1 − β/2, we have Using the quadratic growth condition, we immediately have x ⋆ − x 1 2 ≤ D int /2 and hence X ⋆ ⊂ X int .
Using smoothness, we have that for any x ∈ X int , Since Algorithm 2 always outputs a point in its input domain (in this case X int ), even in the noninterpolation setting that In the interpolation setting, the guarantees of Algorithm 2 hold and result is immediate.

Optimality and Superefficiency
We conclude this paper by providing a lower bound and a super-efficiency result that demonstrate the tightness of our upper bounds. Recall that our upper bound from Section 4 is roughly (up to constants) 1 for any arbitrarily large c. We begin with an exponential lower bound showing that the second term in (5) is tight. We then prove a superefficiency result that demonstrates that any private algorithm which avoids the first term in (5) cannot be adaptive to interpolation, that is, it can not achieve the minimax optimal rate for the family of non-interpolation problems. Theorem 4 below presents our exponential lower bounds for private interpolation problems with growth. We use the notation and proof structure of Theorem 1. We let S λ ⊂ S be the subcollection of function, data set pairs which also have functions f S n that have λ-quadratic growth (Definition 2.4). The proof of Theorem 4 is found in Appendix D.1.
This lower bound addresses the second term of (5); we now turn to our superefficiency results to lower bound the first term of (5). We start with defining some notation and making some simplifying assumptions. For a fixed function F : X , Ω → R which is convex, H-smooth with respect to the first argument, let S L λ (F ) be the set of datasets S of n data points sampled from Ω such that f S (x) := 1 n s∈S n F (x, s) is L-Lipschitz and have λ-strongly convex objectives. For simplicity, we will assume that 1. inf x∈X F (x; s) = 0 for all s ∈ Ω, 2. X = [−D, D] ⊂ R, and 3. the codomain of F is R + . With this setup, we present the formal statement of our result; the proof of Theorem 5 is found in Appendix D.2.
Theorem 5. Suppose we have some S ∈ S L λ (F ) with L = 2HD such that (F, S) satisfy Definition 2.3. Suppose there is an ε-DP estimator M such that for some t > 0 and absolute constant c. Then, for sufficiently large n, there exists another dataset S ′ ∈ S L λ (F ), where (F, S ′ ) may not satisfy Definition 2.3, such that To better contextualize this result, suppose there exists an algorithm which atttains a exp(− Θ (nε/d)) convergence rate on interpolation problems; i.e., the algorithm is able to avoid the 1/n c term in (5). Then Theorem 5 states that there exists some strongly convex, non-interpolation problem on which the aforementioned algorithm will optimize very poorly; in particular, the algorithm will only be able to return a solution that attains, on average, constant error on this "hard" problem. More generally, recall that in the non-interpolation quadratic growth setting, the optimal error rate is on the order of 1/(nε) 2 [ALD21]. Theorem 5 shows that attaining better-than-polynomial error complexity on quadratic growth interpolation problems implies that the algorithm cannot be minimax optimal in the non-interpolation quadratic growth setting. Thus, the rates our adaptive algorithms attain are the best we can hope for if we want an algorithm to perform well on both interpolation and non-interpolation quadratic growth problems.

A.2 Algorithms from [ALD21]
A.3 Theoretical results from [ALD21] We first reproduce the high probability guarantees of Algorithm 4 as proved in [ALD21].

5:
Letx i be the output of the optimization algorithm.
Now, we reproduce the high probability convergence guarantees of Algorithm 5.
Theorem 6. Let β ≤ 1/(n + d), D 2 (X ) ≤ D and F (x; s) be convex, L-Lipschitz for all s ∈ Ω. Assume that f has κ-growth (Assumption 2.4) with κ ≥ κ > 1. Setting T = 2 log n κ−1 , Algorithm 5 is ε-DP and has with probability 1 − β Theorem 7. Let β ≤ 1/(n + d), D 2 (X ) ≤ D and F (x; s) be convex, L-Lipschitz for all s ∈ Ω. Assume that f has κ-growth (Assumption 2.4) with κ ≥ κ > 1. Setting T = 2 log n κ−1 and δ > 0, Algorithm 5 is (ε, δ)-DP and has with probability 1 − β . We select V to be a γ-packing (with respect to the ℓ 2 norm) of diameter D ball contained in X . Define the separation between v, v ′ ∈ V with respect to the loss f v and f v ′ by For the sake of contradiction, suppose that where inequality (ii) follows from the definition of the separation, and (iii) follows from privacy and the disjoint nature of the events in the union. Rearranging, we get that τ ≥ kHγ 2 8n(1 + e kε (|V| − 1) −1 ) , which is a contradiction. By standard packing inequalities [Wai19], we know that |V| ≥ (D/2γ) d . Setting k = d/ε and γ = D/2e and using the fact that x/(x − 1) is decreasing in x gives We now prove the (ε, δ)-DP lower bound. Consider the following sample risk function We define the datasets S n v := {0} n−k ∪ {v} k inducing the corresponding population risk We select two points v, v ′ contained within the diameter D ball contained in X such that |v − v ′ | = D. Define the separation between v, v ′ ∈ V with respect to the loss f v and f v ′ as For the sake of contradiction, suppose that where inequality (ii) follows from the definition of the separation, and (iii) follows from group privacy of (ε, δ)-privacy [DR14]. Rearranging, we get that which is a contradiction. Setting k = 1/ε and using the fact δ ≤ εe ε−1 /2 gives the first result.

C Proofs from Section 4
We first prove a lemma that each time we shrink the domain size, the set of interpolating solutions still lies in the new domain with high probability, and the new Lipschitz constant we define is a valid Lipschitz constant for the loss defined on the new domain. We prove it in generality for κ-growth.
Lemma C.1. Let X ⋆ denote the set of interpolating solutions of problem (1). Then X ⋆ ⊂ X i for all i ∈ [T ] with probability 1 − β, and ∇F (y; s) 2 ≤ L i for all y ∈ X i .
Proof We prove this lemma for the case when δ = 0, the case when δ > 0 follows similarly. For epoch i, using Theorem 2 of [ALD21], we have with probability 1 − β/T , Using the growth condition on f (·), we have Using c κ = 2(C κ κ) 1/κ , we get x i − x ⋆ 2 ≤ D i+1 /2 with probability 1 − β/T . Thus, for each epoch i, with probability 1 − β/T , each point in the set X ⋆ of optimizers lies in the domain X i . Using a union bound on all epochs, we have X ⋆ ⊂ X i for all i ∈ [T ] with probability 1 − β.
We now prove the second part of the lemma. Using the smoothness of F (·; s) and that ∇F (x ⋆ ; s) = 0 for all x ⋆ ∈ X ⋆ , we have We now restate and prove the convergence rate of Algorithm 2 Theorem 2. Assume each sample function F is L-Lipschitz and H-smooth, and let the population function f satisfy quadratic growth (Definition 2.4). Let Problem (1) be an interpolation problem.
Then Algorithm 2 is (ε, δ)-DP. For δ = 0, β = 1 n µ , m = 256 log 2 n H log(1/β) log n , T = n/m and any µ > 0, Algorithm 2 returns x T such that (3) , T = n/m and any µ > 0, Algorithm 2 returns x T such that Proof First we prove the privacy guarantee of the algorithm. Each sample impacts only one of the iteratesx i , thus Algorithm 2 satisfies the same privacy guarantee as Algorithm 5 by postprocessing. We divide the utility proof into 2 main parts; first is to check the validity of the assumptions while applying Algorithm 5 and second is using its high probability convergence guarantees to get the final rates. To check this, we ensure that the optimum set lies in the new domain X i at step i and that the Lipschitz constant L i defined with respect to the domain is a valid lipschitz constant. This follows from Lemma C.1.
Next, we use the high probability convergence guarantees of the subalgorithm Algorithm 5 to get convergence rates for Algorithm 2. We prove it for the case when δ = 0, the case when δ > 0 is similar. We know that Thus we have

Algorithm 6 Epoch based epoch based epoch based clipped-GD
Require: number of epochs: T , samples in each round: m = n/T , Diameter at the start: D 1 , lipschitz constant at the start L 1 , domain X 1 , initial pointx 0 1: for i = 1 to T do 2:x i ← Output of Algorithm 5 when run on domain X i (diameter D i ), with lipschitz constant L i using m samples.

3:
if δ = 0 then 4: Set L i+1 = HD i+1 10: end for 11: return the final iterate x T Proof The privacy guarantee follows from the proof of Theorem 2. We divide the utility proof into 2 main parts; first is to check the validity of the assumptions while applying Algorithm 5 and second is using its high probability convergence guarantees to get the final rates. To check this, we ensure that the optimum set lies in the new domain defined at every step and that the lipschitz constant defined with respect to the domain is a valid lipschitz constant. This follows from Lemma C.1.
Next, we use the high probability convergence guarantees of the subalgorithm Algorithm 5 to get convergence rates for Algorithm 2.
We prove it for the case when δ = 0, the case when δ > 0 is similar. We know that Thus, we have We note that for T ∼ log n, 1 (κ−1) T −1 ≈ 1 n log(κ−1) and thus for large n, we ignore the terms of the form a − 1 n log(κ−1) since they are ≈ 1. Ignoring these terms by including an additional constant C ′ we can write Using Theorem 2 of [ALD21] on the last epoch, we have with probability 1 − β that Choosing T = log n and m = n/ log n, we have log(log n/β) log 3/2 (n/ log n) n/ log n , d log(log n/β) log(n/ log n) εn/ log n κ κ−2 L κ n 1 .
Now we write results in terms of sample complexity required to achieve a particular error. The sufficient number of samples.
Proof First, we note that the privacy of Algorithm 3 follows from the privacy of Algorithm 2 and Algorithm 1 and post-processing.
To prove the convergence guarantees, we first need to show that the optimal set X ⋆ is included in the shrinked domain X int . Using the high probability guarantees of Algorithm 1, we know that with probability 1 − β/2, we have Using the quadratic growth condition, we immediately have x ⋆ − x 1 2 ≤ D int /2 and hence X ⋆ ⊂ X int . Using smoothness, we have that for any x ∈ X int , Since Algorithm 2 always outputs a point in its input domain (in this case X int ), even in the noninterpolation setting we have that In the interpolation setting, the guarantees of Algorithm 2 hold and the result is immediate.

D Proofs from Section 5 D.1 Proof of Theorem 4
The proof is exactly the same as Theorem 1, except we set k = λn H to ensure that f v (x) for any v ∈ X has λ-quadratic growth. Finally we set γ = D 2 exp( −λnε Hd ) and use the fact that e λnε H ≥ 2 and the fact that x/(x − 1) is decreasing in x to give the desired lower bound.

D.2 Proof of Theorem 5
The proof of this result hinges on the two following supporting propositions. We first copy Proposition 2.2 from [AD20] (listed as Proposition 4 below) in our notation for convenience. We then state Proposition 5 which gives upper and lower bounds on the modulus of continuity (defined in Proposition 4). We note that the lower bound presented in Proposition 5 is one of the novel contributions of this paper; the proof of Proposition 5 can be found in Appendix D.2.1. We will first assume this to be true and prove Theorem 5 before returning prove its correctness.
Proposition 4. For some fixed F : X , Ω → R which is convex and H-smooth with respect to its first argument, let S ∈ S L λ (F ) for L = 2HD. Let Define the corresponding modulus of continuity Assume the mechanism M is ε-DP and for some γ ≤ Proposition 5. Let F : X , Ω → R be convex and H-smooth in its first argument and satisfying inf x∈X F (x; s) = 0 for all s ∈ Ω. Suppose we have some S ∈ S L λ (F ) with L = 2HD which also induces an interpolation problem (a problem which satisfies Definition 2.3). With respect to the dataset S, the modulus of continuity ω(S, 1/ε) satsifies D nε ≤ ω(S, 1/ε) ≤ 8HD λnε With these two results, we can now prove Theorem 5. Restating the conditions of the theorem formally, suppose for some constants c 0 and c 1 there is an ε-DP estimator M such that If t > 1, set t = min(1, t), then the bound certainly still holds for large enough n. If we let x ⋆ S = argmin x∈X f S (x), using the definition of strong convexity, we have that there exists some c 2 and c 3 such that To satisfy the expression from Proposition 4, we select γ such that γω(S; 1/ε) 2 = c 2 De −c3(nε) t .
Using Proposition 5 we must have λnε 4H c 2 exp(−c 3 (nε) t ) ≤ γ ≤ 2nεc 2 exp(−c 3 (nε) t ). Using Proposition 4, we have that Before performing a further lower bound on this quantity, we first verify that log(1/2γ) 2ε does not exceed the total size of the dataset, n. Using our bounds on γ, we see that For any t ∈ (0, 1], for sufficiently large n, this quantity is less than n. We now lower bound the modulus of continuity by using the fact that it is a non-decreasing function in its second argument: This is the desired result; the last inequality comes from another application of Proposition 5 but with c3(nε) t −log c2−log(4nε) 2ε in place of 1/ε.
By smoothness and strong convexity we have However, this implies that γ > λ − H nε which is a contradiction.
The next lemma is a standard result on the closure under addition of strongly convex functions.
This lemma provides some growth conditions on the gradient under smoothness, strong convexity and quadratic growth.
Proof We note that by first order optimality conditions, for all x ⋆ ∈ X ⋆ , ∇g(x ⋆ ) = 0. To prove the first inequality, we have that for any x ⋆ ∈ X ⋆ , the following is true: In particular, minimizing over x ⋆ on the right hand side and rearranging gives the desired result. To prove the second result, we know that by strong convexity for any To prove the last result, we know that by smoothness for any Minimizing over x ⋆ on the right hand side gives the desired result.
This lemma controls how much the minimizers of a function can change if another function is added. This will directly be useful in lower bounding the modulus of continuity. h be the largest minimizer of h and x ⋆ g be the smallest minimizer of g, and assume that x ⋆ h ≤ x ⋆ g . Let x ⋆ be any minimizer of h + g. Assume that h(x ⋆ h ) = 0 and g(x ⋆ g ) = 0. If h has λ h -quadratic growth and g is H g -smooth, then