# Differentially Private Worst-group Risk Minimization

Xinyu Zhou Department of Computer Science & Engineering, The Ohio State
University<EMAIL_ADDRESS>Raef Bassily11footnotemark: 1
Department of Computer Science & Engineering and the Translational Data
Analytics Institute (TDAI), The Ohio State University, bassily.1@osu.

###### Abstract

We initiate a systematic study of worst-group risk minimization under
$(\epsilon,\delta)$-differential privacy (DP). The goal is to privately find a
model that approximately minimizes the maximal risk across $p$ sub-populations
(groups) with different distributions, where each group distribution is
accessed via a sample oracle. We first present a new algorithm that achieves
excess worst-group population risk of
$\tilde{O}(\frac{p\sqrt{d}}{K\epsilon}+\sqrt{\frac{p}{K}})$, where $K$ is the
total number of samples drawn from all groups and $d$ is the problem
dimension. Our rate is nearly optimal when each distribution is observed via a
fixed-size dataset of size $K/p$. Our result is based on a new stability-based
analysis for the generalization error. In particular, we show that
$\Delta$-uniform argument stability implies
$\tilde{O}(\Delta+\frac{1}{\sqrt{n}})$ generalization error w.r.t. the worst-
group risk, where $n$ is the number of samples drawn from each sample oracle.
Next, we propose an algorithmic framework for worst-group population risk
minimization using any DP online convex optimization algorithm as a
subroutine. Hence, we give another excess risk bound of
$\tilde{O}\left(\sqrt{\frac{d^{1/2}}{\epsilon
K}}+\sqrt{\frac{p}{K\epsilon^{2}}}\right)$. Assuming the typical setting of
$\epsilon=\Theta(1)$, this bound is more favorable than our first bound in a
certain range of $p$ as a function of $K$ and $d$. Finally, we study
differentially private worst-group _empirical_ risk minimization in the
offline setting, where each group distribution is observed by a fixed-size
dataset. We present a new algorithm with nearly optimal excess risk of
$\tilde{O}(\frac{p\sqrt{d}}{K\epsilon})$.

##  1 Introduction

Multi-distribution learning has gained increasing attention due to its close
connection to robustness and fairness in machine learning. Consider $p$ groups
(or, sub-populations), where each group is associated with some unknown data
distribution. In the multi-distribution learning paradigm, the learner tries
to find a model that minimizes the maximal population risk across all groups.
Let $D_{i}$ denote distribution of group $i\in[p]$ and
$\ell:\mathcal{W}\times\mathcal{Z}$ be a loss function over the parameter
space $\mathcal{W}$ and data domain $\mathcal{Z}$, our objective of minimizing
the worst-group population risk can be formulated as a minimax stochastic
optimization problem written as

$\min_{w\in\mathcal{W}}\max_{i\in[p]}\left\\{L_{D_{i}}(w)\coloneqq\mathbb{E}_{z\sim
D_{i}}\ell(w,z)\right\\}$ (1)

When each group distribution $D_{i}$ is observed by a dataset $S_{i}$, we also
define the worst-group empirical risk minimization problem as

$\min_{w\in\mathcal{W}}\max_{i\in[p]}\left\\{L_{S_{i}}(w)\coloneqq\frac{1}{|S_{i}|}\sum_{z\sim
S_{i}}\ell(w,z)\right\\}$ (2)

The worst-group risk minimization problems (1) and (2) have wide applications
in a variety of learning scenarios. In the regime of robust learning, the
objective represents a class of problems named as group distributionally
robust optimization (Group DRO) [SGJ22, ZZY+23, SKH+19]. This formulation also
captures the mismatch between distributions from different domains (or, sub-
populations). In this type of scenarios, instead of assuming a fixed target
distribution, this formulation can be used to find a model that can work well
for any possible target distribution formed as a mixture of the distributions
from different domains/sub-populations. From the perspective of learning with
fairness, each group may represent a protected class or a demographic group.
Minimizing the worst-group risk leads to the notions of good-intent fairness
[MSS19] or min-max group fairness [AAK+22, DGK+21, PMB+22]. By making sure the
worst-off group performs as good as possible, the objective prevents the
learner from overfitting to certain groups at the cost of others. Moreover,
the objectives are also connected to other learning applications such as
collaborative learning [BHP+17] and agnostic federated learning [MSS19] where
the output model is optimized to perform well across multiple distributions.

Meanwhile, machine learning algorithms typically depend on large volumes of
data, which may pose serious privacy risk, particularly in certain privacy-
sensitive applications like healthcare and finance. Therefore, it is important
that we provide a strong and provable privacy guarantee for such algorithms to
ensure that the sensitive information always remains private during the
learning process. Although there has been a significant progress in
understanding worst-group risk minimization in the non-private setting [SGJ22,
HJZ22, ZZY+23], this problem has not been formally studied in the context of
learning with provable privacy guarantees.

Motivated by this, in this paper, we initiate a formal study of worst-group
risk minimization under $(\epsilon,\delta)$-differential privacy (DP). We
consider the setting where the loss function is convex and Lipschitz over a
compact parameter space $\mathcal{W}\subset\mathbb{R}^{d}$. For the sample
access model, each group distribution is accessed via a sample oracle and the
learner is able to sample new data points from any group distribution via its
sample oracle as needed during the learning process.

###  1.1 Contribution

As we mentioned earlier, we let $p$ denote the number of groups , $K$ denote
the total number of samples drawn from all groups and $d$ denote the problem
dimension.

We first provide a new algorithm adapted from the phased-ERM approach in
[FKT20] with the excess worst-group population risk of
$\tilde{O}\left(\sqrt{\frac{p}{K}}+\frac{p\sqrt{d}}{K\epsilon}\right)$. The
first term in this bound matches the optimal non-private bound [SGJ22] and the
second term represents the cost of privacy. Our rate is optimal up to
logarithmic factors in the offline setting where each distribution is observed
via a a fixed-size dataset of size $K/p$. The utility guarantee of our
algorithm relies on a new stability based argument to establish the
generalization error bound. Roughly speaking, we show that $\Delta$-_uniform
argument stability_ (see Definition 1) with respect to the parameter $w$
implies a $\tilde{O}(\Delta+1/\sqrt{n})$ generalization error where $n$ is the
number of samples drawn from each sample oracle. This is distinct from
existing generalization results based on uniform convergence [MSS19, AAK+22],
which lead to suboptimal rates for general convex losses. On the other hand,
our result also circumvents a known bottleneck in deriving generalization
guarantees using argument uniform stability in the stochastic saddle-point
problems. In particular, in the $L_{2}/L_{2}$ setting, the best known
generalization guarantee for a $\Delta$-uniform argument stable algorithm is
$\sqrt{\Delta}$ generalization error based on the analysis of the strong
duality gap [OPZ+22].

Our algorithm is akin to the Phased ERM approach of [FKT20], which was
introduced to solve private stochastic convex optimization. We repurpose this
approach for the private stochastic minimax optimization. In particular, we
define a sequence of regularized minimax problems, which are solved
iteratively using any generic non-private solver. Our version of this
algorithm requires different tuning of parameters across iterations and, more
crucially, a new analysis that utilizes the uniform argument stability of the
solutions of the regularized minimax problems.

As a side product, our stability result naturally leads to a new non-private
regularization based method for the worst-group risk minimization problem,
which matches the non-private lower bound in [SGJ22] up to logarithmic
factors. This may be of independent interest because existing non-private
methods with (nearly) optimal rate for this problem rely on single-pass first-
order methods rather than regularization.

Next, we give a framework to minimize the worst-group population risk using a
black-box access to any DP online convex optimization (DP OCO) algorithm as a
subroutine. Our framework leverages the idea in [SGJ22, HJZ22] on casting the
worst-group risk minimization objective in a zero-sum game and decomposing the
excess worst-group risk into the expected regret of both players. By
instantiating our framework with the DP-FTRL algorithm from [KMS+21], we
obtain another bound on the excess worst-group population risk of
$\tilde{O}\left(\sqrt{\frac{d^{1/2}}{\epsilon
K}}+\sqrt{\frac{p}{K\epsilon^{2}}}\right)$. Assuming the typical setting for
the privacy parameter $\epsilon$, namely, $\epsilon=\Theta(1)$, this bound is
more favorable than our bound based on the Phased ERM approach in a certain
range of $p$ as a function of $K$ and $d$, particularly, when
$p\geq\max\\{\sqrt{d},K/d\\}$ or $\sqrt{\frac{K}{d^{1/2}}}\leq p\leq\sqrt{d}$.

Finally, we investigate the worst-group _empirical_ risk minimization problem
(2) in the _offline setting_ , where each distribution $D_{i}$ is observed by
a fixed-size dataset $S_{i}$. We present a new algorithm based on a private
version of the multiplicative group reweighing scheme [AAK+22, DGK+21]. We
show that our algorithm achieves a nearly optimal excess worst-group empirical
risk of $\tilde{O}\left(\frac{p\sqrt{d}}{K\epsilon}\right)$.

###  1.2 Related Work

The worst-group risk minimization is closely related to the group DRO problem.
In [SKH+19], the authors consider solving the empirical objective in the
offline setting and propose an online algorithm based on the stochastic mirror
descent (SMD) method from [NJL+09]. The convergence rate achieved in [SKH+19]
is suboptimal because of the high variance of the gradient estimators. On the
other hands, several works [HJZ22, SGJ22, ZZY+23] has studied the group DRO
problem in the stochastic oracle setting and achieves an excess worst-group
population risk of $\tilde{O}\left(\sqrt{\frac{p}{K}}\right)$ The basic idea
behind the methods used in these works is to cast the objective into a zero-
sum game based on the observation that the optimality gap depends on the
expected regret of the max and min players. The authors in [SGJ22] demonstrate
the tightness of this rate by proving a matching lower bound result.

The worst-group risk minimization problem is also extensively studied under
the notion of min-max group fairness. Reference [DGK+21] studies learning with
min-max group fairness and propose a multiplicative reweighting based method.
However, their method assumes the access to a weighted empirical risk
minimization oracle which may not be realistic in practice. Meanwhile,
reference [AAK+22] studies a similar problem and present more efficient
gradient based methods to achieve the min-max group fairness based on the idea
of active sampling. The problem of min-max group fairness is also studied in
[MSS19] under the federated learning setting. However, all these works do not
provide any privacy guarantees.

Our work is also related to the line of works on differentially private
stochastic saddle point (DP-SSP) problem. References [YHL+22, ZTO+22] have
presented algorithms with the optimal rate for the weak duality gap, while the
optimal rate for the strong duality gap is achieved in [BGM23]. However, these
works only consider the objective with $L_{2}/L_{2}$ geometry, directly
applying the results from existing DP-SSP works leads to a suboptimal
convergence rate due to the polynomial dependence of $p$ on the $L_{2}$
Lipschtiz constant for the model parameters. Moreover, extending the recursive
regularization method in [BGM23] to the $L_{2}/L_{1}$ setting is not
straightforward because the given analysis explicitly requires both primal and
dual parameters lie in Hilbert spaces. In a concurrent and independent work
[GGP24], the authors study DP-SSP problem in the $L_{1}/L_{1}$ geometry over
polyhedral feasible sets. They propose a method based on a combination of
stochastic mirror descent and the exponential mechanism, and show that it
attains nearly dimension-independent convergence rate for the expected duality
gap. We note that their problem setting is different from the $L_{2}/L_{1}$
setting considered in this work. In particular, their method takes advantage
of the polyhedral geometry under $L_{1}$ constraints. Consequently, their
construction and results are incomparable to ours.

##  2 Preliminaries

We consider $p$ groups, where each group $i\in[p]$ corresponds to a
distributions $D_{i}$. Given a parameter space $\mathcal{W}\in\mathcal{R}^{d}$
and a loss function $\ell$, we let $\ell(w,z)$ be the loss incurred by a
weight vector $w$ on a data point $z$. We assume the $L_{2}$ diameter of
$\mathcal{W}$, $\left\|\mathcal{W}\right\|_{2}$, is bounded by $M$. Throughout
this paper, we assume that the loss function $\ell$ is convex, $L$-Lipschitz
and bounded by $[0,B]$ unless stated otherwise . The population loss of
distribution $D_{i}$ is written as $L_{D_{i}}(w)=\mathbb{E}_{z\sim
D_{i}}\ell(w,z)$. Given a dataset $S_{i}$, we also denote
$L_{S_{i}}(w)=\frac{1}{|S_{i}|}\sum_{z\in S_{i}}\ell(w,z)$ as the empirical
loss evaluated on $S_{i}$.

#### Sample oracle:

A sample oracle $\mathcal{C}_{i}$ w.r.t distribution $D_{i},$ $i\in[p]$
returns an i.i.d sample $z$ drawn from $D_{i}$. We denote the collection of
sample oracles from all groups as
$\tilde{\mathcal{C}}=\\{\mathcal{C}_{1},\dots\mathcal{C}_{p}\\}$.

####  $\alpha$-saddle point:

We say $(\tilde{x},\tilde{y})$ is an $\alpha$-saddle point of a minimax
problem $\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\phi(x,y)$ if
$\phi(\tilde{x},y)-\phi(x,\tilde{y})\leq\alpha$ for any $x\in\mathcal{X}$ and
$y\in\mathcal{Y}$. When $\alpha=0$, we simply call $(\tilde{x},\tilde{y})$ a
saddle point of $\phi$.

#### Worst-group population risk minimization

: Given $p$ groups that each of them is with a distribution $D_{i}$, we define
the expected (population) worst-group risk of model $w$ as the maximal
population loss of $w$ across all group distributions written as

$R(w)=\max_{i\in[p]}L_{D_{i}}(w)$

Our objective of minimizing the worst-group risk is therefore written as

$\min_{w\in\mathcal{W}}\max_{i\in[p]}L_{D_{i}}(w)$ (3)

Denote $\Delta_{p}=\\{\lambda\in[0,1]^{p}:\left\|\lambda\right\|_{1}=1\\}$ as
the probability simplex over $p$ dimensions and
$\phi(w,\lambda)=\sum_{i=1}^{p}\lambda_{i}L_{D_{i}}(w)$.

Then the objective in (3) can be equivalently written as

$\min_{w\in\mathcal{W}}\max_{\lambda\in\Delta_{p}}\phi(w,\lambda)$ (4)

The equivalence is based on the fact that for any $w\in\mathcal{W}$,
$\phi(w,\lambda)$ is maximized by a $\lambda$ with all dimensions being zero
except the one with the highest $L_{D_{i}}(w)$. We also define the _excess
worst-group population risk_ of $w\in\mathcal{W}$ as

$\mathcal{E}(w;\\{D_{i}\\}_{i=1}^{p})\triangleq\max_{i\in[p]}L_{D_{i}}(w)-\min_{\tilde{w}\in\mathcal{W}}\max_{i\in[p]}L_{D_{i}}(\tilde{w})$

#### Differential Privacy [DMN+06]:

A mechanism $\mathcal{M}$ is $(\epsilon,\delta)$-DP if for any two neighboring
datasets $S$ and $S^{\prime}$ that differ on single _data point_ and any
output set $\mathcal{O}$, we have

$P\left(M(S)\in\mathcal{O}\right)\leq
e^{\epsilon}P\left(M(S^{\prime})\in\mathcal{O}\right)+\delta$

We focus on record-level privacy throughout the paper. We say that a pair of
sequences of sampled data points $\\{z_{1},\dots z_{T}\\}$ and
$\\{z_{1}^{\prime},\dots z^{\prime}_{T}\\}$ are neighbors if, for some
$j\in[p]$, $z_{i}=z^{\prime}_{i}$ for all $i\in[T]\setminus\\{j\\}$ and
$z_{j}\neq z^{\prime}_{j}$.

#### Stability:

Our analysis depends on the notion of uniform argument stability defined as
follows

######  Definition 1.

A randomized algorithm $\mathcal{A}$ that takes data collections $\tilde{S}$
as input and outputs
$(\mathcal{A}_{w}(\tilde{S}),\mathcal{A}_{\lambda}(\tilde{S}))$ is said to
attain $\Delta$-uniform argument stability with respect to $w$ if for any
pairs of adjacent $\tilde{S}$ and $\tilde{S}^{\prime}$ that differs in a
single data point, we have

$\mathbb{E}_{\mathcal{A}}\left[\left\|\mathcal{A}_{w}(\tilde{S})-\mathcal{A}_{w}(\tilde{S^{\prime}})\right\|\right]\leq\Delta$

##  3 Minimax Phased ERM

In this section, we propose an algorithm attaining an excess worst-group
population risk of
$\tilde{O}\left(\sqrt{\frac{p}{K}}+\frac{p\sqrt{d}}{K\epsilon}\right)$, where
$p$ and $K$ denote the number of groups and the total number of samples drawn
from all groups, respectively. Our algorithm involves iteratively solving a
sequence of regularized minimax objectives. In iteration $t$, given the
previous iterate $w_{t-1}$ and a dataset collection
$\\{S_{i}^{t}\\}_{i=1}^{p}$ where $S_{i}^{t}$ is the dataset formed by the
data points drawn from the sample oracle $\mathcal{C}_{i}$ at current
iteration, we find an approximate saddle point
$(\tilde{w}_{t},\tilde{\lambda}_{t})$ of the regularized objective
$F_{t}(w,\lambda)=\sum_{i=1}^{p}\lambda_{i}L_{S^{t}_{i}}(w)+\mu_{w}^{t}\left\|w-w_{t-1}\right\|_{2}^{2}-\mu_{\lambda}^{t}\sum_{j=1}^{p}\lambda_{j}\log\lambda_{j}$
and output $\tilde{w}_{t}$. We can show that $\tilde{w}_{t}$ has low
sensitivity w.r.t. the collection of samples drawn from all groups. , and
hence, we can use the standard Gaussian mechanism to to ensure that the
computation of $\tilde{w}_{t}$ is differentially private.

Proving the utility guarantee of our algorithm involves new stability based
argument. First, given a dataset collection $\tilde{S}=\\{S_{1},\dots
S_{p}\\}$ where each $S_{i}\sim D_{i}^{n}$ is a dataset formed by $n$ samples
drawn from the sample oracle $\mathcal{C}_{i}$. we show that an algorithm that
outputs an approximate saddle point $(\tilde{w},\tilde{\lambda})$ for the
regularized objective
$F(w,\lambda)=\sum_{i=1}^{p}\lambda_{i}L_{S_{i}}(w)+\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}-\mu_{\lambda}\sum_{j=1}^{p}\lambda_{j}\log\lambda_{j}$
has uniform argument stability of
$O\left(\frac{L}{n\mu_{w}}+\frac{B}{n\sqrt{\mu_{w}\mu_{\lambda}}}\right)$ with
respect to $\tilde{w}$. Then we prove that $\Delta$-uniform argument stability
of $\tilde{w}$ leads to a $\tilde{O}\left(\Delta+\frac{B}{\sqrt{n}}\right)$
generalization error bound.

Our stability-based generalization argument is distinct from existing
generalization analysis based on uniform convergence [MSS19, AAK+22], which
leads to sub-optimal excess worst-group risk for general convex losses even in
the non-private regime. On the other hand, our result circumvents a known
bottleneck in the relationship between stability and generalization in
stochastic minmax optimization (also, known as Stochastic Saddle Point (SSP)
problems). In particular, in the $L_{2}/L_{2}$ setting of the SSP problem, the
best known generalization guarantee using a $\Delta$-argument stable algorithm
is $\sqrt{\Delta}$ generalization error based on the analysis of the strong
duality gap [OPZ+22].

###  3.1 Algorithm description

Our algorithm relies on a non-private subroutine to solve a regularized
minimax problem. More concretely, let $\tilde{S}=\\{S_{1},\dots S_{p}\\}$ be a
collection of datasets. Let $\mu_{w}$, $\mu_{\lambda}>0$ and
$w^{\prime}\in\mathcal{W}$. Let
$\mathcal{A}_{emp}(\tilde{S},\mu_{w},\mu_{\lambda},w^{\prime},\alpha)$ be an
empirical minimax solver that computes an $\alpha$-saddle point
$(\tilde{w},\tilde{\lambda})$ of

$\min_{w\in\mathcal{W}}\max_{\lambda\in\Delta_{p}}\Bigg{\\{}F(w,\lambda)\coloneqq\sum_{i=1}^{p}\lambda_{i}L_{S_{i}}(w)+\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}-\mu_{\lambda}\sum_{j=1}^{p}\lambda_{j}\log\lambda_{j}\Bigg{\\}}$
(5)

and outputs $\tilde{w}$.

The formal description of our algorithm is given in Algorithm 1. Our algorithm
is inspired by the Phased ERM approach of [FKT20], which was used to attain
the optimal rate for the simpler problem of differentially private stochastic
convex optimization. We repurpose the Phased ERM approach for the stochastic
minimax problem. Our algorithm involves several modifications to this approach
that enable us to attain strong guarantees for the worst-group population risk
minimization problem. Crucially, we provide a new analysis for our algorithm
that utilizes the argument uniform stability of the regularized minimax
problems (see, Lemma 4).

In Algorithm 1, a sequence of regularized empirical minimax problems are
defined and solved iteratively using the non-private minimax solver
$\mathcal{A}_{emp}$ (defined earlier in this section). The total number of
such problems (the number of rounds in the algorithm) $T$ is logarithmic in
$K/p$. In round $t\in[T]$, we first sample a dataset of size $n_{t}$ from each
distribution to construct a new dataset collection $\tilde{S}_{t}$. The center
of the regularization term is chosen to be $w^{\prime}=w_{t-1}$, i.e., the
previous iterate. The settings of the regularization parameters in each round
are carefully chosen to ensure convergence to a nearly optimal rate. The
regularization parameter $\mu_{\lambda}$ is fixed across all rounds whereas
$\mu_{w}$ is doubled with every round. Our main result is stated below.

Algorithm 1 Minimax Phased ERM

Input Sample oracles $\\{\mathcal{C}_{1},\dots\mathcal{C}_{p}\\}$, step size
$\eta$, $D=\max\\{L,B\\}$, total number of samples drawn from all groups $K$,
non-private empirical solver $A_{emp}$.

Initialize $w_{0}$ arbitrary parameter vector in $\mathcal{W}$.

Set $n=K/p$ and $T=\log_{2}(n)$.

for $t=1,\dots,T$ do

Let $n_{t}=n/T,$ $\eta_{t}=\eta 2^{-t}$, $\mu_{w}^{t}=1/(\eta_{t}n_{t})$,
$\mu_{\lambda}^{t}=1/(\eta n)$.

For each $i\in[p]$, sample $S_{i}^{t}\sim D_{i}^{n_{t}}$ using the sample
oracle $\mathcal{C}_{i}$. Denote $\tilde{S}^{t}=\\{S_{1}^{t},\dots
S_{p}^{t}\\}$.

Let
$\alpha_{t}=\frac{L^{2}}{8n_{t}^{2}\mu_{w}^{t}}+\frac{B^{2}}{8n_{t}^{2}\mu_{\lambda}^{t}}$
.

Let
$\tilde{w}_{t}=\mathcal{A}_{emp}(\tilde{S}^{t},\mu_{w}^{t},\mu_{\lambda}^{t},w_{t-1},\alpha_{t})$.

Set $w_{t}=\tilde{w_{t}}+\xi_{t}$ where
$\xi_{t}\sim\mathcal{N}(0,\sigma_{t}I_{d})$ and
$\sigma_{t}=6D\sqrt{2\log_{2}(n)\log(1/\delta)\eta\eta_{t}}/\epsilon$.

end for

Output: $w_{T}$.

######  Theorem 2.

Let
$\eta=\frac{M}{D}\min\left\\{\frac{\epsilon}{\sqrt{72d\log(\frac{K}{p})\log(\frac{1}{\delta})}},\frac{\sqrt{p}}{\log^{\frac{3}{4}}(K)\sqrt{K}}\right\\}$.
Algorithm 1 is $(\epsilon,\delta)$-differentially private and we have

$\displaystyle\mathbb{E}\left[\max_{i\in[p]}L_{D_{i}}(w_{T})\right]-\min_{w\in\mathcal{W}}\max_{i\in[p]}L_{D_{i}}(w)$
$\displaystyle=O\left(MD\left(\log^{\frac{11}{4}}(K)\sqrt{\frac{p}{K}}+\frac{\log^{\frac{5}{2}}(K)p\sqrt{d\log(1/\delta)}}{K\epsilon}\right)\right),$

where $w_{T}$ is the output of Algorithm 1 and the expectation is taken over
the sampled data points and the algorithm’s inner randomness.

#### Remarks:

  * •

One can show that the rate in Theorem 2 is nearly optimal in the offline
setting considered in Section 5, where each distribution is observed by a
fixed-size dataset of size $K/p$. A lower bound instance of
$\Omega\left(\frac{p\sqrt{d}}{K\epsilon}+\sqrt{\frac{p}{K}}\right)$ can be
constructed in this case. More details are given in Appendix D. Also, note
that when $d=O(K/p)$, the rate in Theorem 2 matches the the non-private lower
bound $\Omega\left(\sqrt{\frac{p}{K}}\right)$ up to logarithmic factors.

  * •

In Appendix A.1, we give an instantiation of $\mathcal{A}_{emp}$, which is an
iterative algorithm for solving the regularized minimax problem in (5) with a
convergence rate of $\tilde{O}(1/N)$, where $N$ is the number of iterations.

The privacy and utility guarantees in Theorem 2 rely on a stability-based
result of the saddle point of the regularized objective (5), which we present
in the following lemma.

######  Lemma 3.

Consider two neighboring dataset collections $\tilde{S}=\\{S_{1},\dots
S_{p}\\}\in\mathcal{Z}^{n\times p}$ and
$\tilde{S}^{\prime}=\\{S^{\prime}_{1},\dots
S^{\prime}_{p}\\}\in\mathcal{Z}^{n\times p}$ that differs in a single data
point. Let $(\tilde{w},\tilde{\lambda})$ and
$(\tilde{w}^{\prime},\tilde{\lambda}^{\prime})$ be an $\alpha$-saddle point of
$F(w,\lambda)$ in (5) when the dataset collections are $\tilde{S}$ and
$\tilde{S}^{\prime},$ respectively. By letting
$\alpha\leq\frac{L^{2}}{8n^{2}\mu_{w}}+\frac{B^{2}}{8n^{2}\mu_{\lambda}}$, we
have

$\left\|\tilde{w}-\tilde{w}^{\prime}\right\|_{2}\leq\frac{3}{n}\left(\frac{L}{\mu_{w}}+\frac{B}{\sqrt{\mu_{w}\mu_{\lambda}}}\right)$

The proof of Lemma 3 follows from Lemma 2 in [ZHW+21] as well as the
observation that $F(w,\lambda)$ can be equivalently written in the finite-sum
form composed with regularization terms. We give full details in Appendix A.3.

Now we are ready to present our main technical lemma, which shows that an
approximate saddle point of the regularized objective $F(w,\lambda)$ in (5)
gives a good solution to the worst-group population risk minimization problem.
We will sketch the proof of this lemma and defer the full proof to Appendix
A.4.

######  Lemma 4.

Let $(\tilde{w},\tilde{\lambda})$ be an $\alpha$-saddle point of
$F(w,\lambda)$ in (5) with
$\alpha\leq\frac{L^{2}}{8n^{2}\mu_{w}}+\frac{B^{2}}{8n^{2}\mu_{\lambda}}$. For
any $w\in\mathcal{W}$,

$\displaystyle\mathbb{E}\left[\max_{i\in[p]}L_{D_{i}}(\tilde{w})\right]-\max_{i\in[p]}L_{D_{i}}(w)$
$\displaystyle=O\bigg{(}\mu_{w}\left\|w-w^{\prime}\right\|_{2}^{2}+\mu_{\lambda}\log
p+\left(\frac{L^{2}}{n\mu_{w}}+\frac{LB}{n\sqrt{\mu_{w}\mu_{\lambda}}}\right)\log(n)\log(np)+\frac{B\sqrt{\log(pn)}}{\sqrt{n}}\bigg{)},$

where the expectation is taken over the randomness in the datasets
$\tilde{S}$.

###### Proof.

(sketch) For simplicity, we let $\alpha=0$, which means
$(\tilde{w},\tilde{\lambda})$ is the exact saddle point of $F(w,\lambda)$. In
particular, by the definition of saddle point, one can show that for any
$w\in\mathcal{W}$

$\max_{i\in[p]}L_{S_{i}}(\tilde{w})-\hat{\phi}(w,\tilde{\lambda})\leq\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}+\mu_{\lambda}\log
p$

where $\hat{\phi}(w,\lambda)=\sum_{i=1}^{p}\lambda_{i}L_{S_{i}}(w)$.

By Lemma 3 and Lipschitzness, for any given $i\in[p]$, computing $\tilde{w}$
has a uniform stability of
$\gamma=\frac{3}{n}\left(\frac{L^{2}}{\mu_{w}}+\frac{LB}{\sqrt{\mu_{w}\mu_{\lambda}}}\right)$
with respect to the change of datapoint in $S_{i}$. By Theorem 1.1 in [FV19],
we have with high probability over the sampling of $\tilde{S}$,

$|L_{S_{i}}(\tilde{w})-L_{D_{i}}(\tilde{w})|=\tilde{O}\left(\gamma+\frac{B}{\sqrt{n}}\right)$

Then we can use union bound across all $i\in[p]$ and obtain with high
probability

$|L_{S_{i}}(\tilde{w})-L_{D_{i}}(\tilde{w})|=\tilde{O}\left(\gamma+\frac{B}{\sqrt{n}}\right)\quad\forall
i\in[p]$

In particular, we have with high probability

$|\max_{i\in[p]}L_{D_{i}}(\tilde{w})-\max_{i\in[p]}L_{S_{i}}(\tilde{w})|=\tilde{O}\left(\gamma+\frac{B}{\sqrt{n}}\right)$

Meanwhile, we can show that with high probability,
$|\phi(w,\tilde{\lambda})-\hat{\phi}(w,\tilde{\lambda})|=\tilde{O}\left(\frac{B}{\sqrt{n}}\right)$
for any given $w\in\mathcal{W}$. Finally, we put everything together and have
with high probability

$\displaystyle\max_{i\in[p]}L_{D_{i}}(\tilde{w})-\max_{i\in[p]}L_{D_{i}}(w)$
$\displaystyle\leq\max_{i\in[p]}L_{D_{i}}(\tilde{w})-\phi(w,\tilde{\lambda})$
$\displaystyle\leq\max_{i\in[p]}L_{S_{i}}(\tilde{w})-\hat{\phi}(w,\tilde{\lambda})+\tilde{O}\left(\gamma+\frac{B}{\sqrt{n}}\right)$
$\displaystyle=\tilde{O}\left(\mu_{w}\left\|w-w^{\prime}\right\|_{2}^{2}+\mu_{\lambda}+\gamma+\frac{B}{\sqrt{n}}\right)$

Replacing $\gamma$ with
$\frac{3}{n}\left(\frac{L^{2}}{\mu_{w}}+\frac{LB}{\sqrt{\mu_{w}\mu_{\lambda}}}\right)$
and we obtain the desired result. ∎

#### Remark:

As a side product of Lemma 4, we can sample a new dataset collection
$\tilde{S}=\\{S_{1},\dots S_{p}\\}$ where $S_{i}\sim D_{i}^{K/p}$. By letting
$\mu_{w}=\frac{D}{M}\sqrt{\frac{p}{K}}\sqrt{\log(K/p)\log(K)}$,
$\mu_{\lambda}=D\sqrt{\frac{p\log(K/p)\log(K)}{K\log p}}$ and $w^{\prime}$ be
any arbitrary parameter in $\mathcal{W}$, solving the regularized objective
(5) with $\tilde{S}$ gives an excess worst-group population risk of
$\tilde{O}\left(\sqrt{\frac{p}{K}}\right)$, which matches the non-private
lower bound in [SGJ22] up to logarithmic factors. Prior methods (nearly)
matching the non-private lower bound depend on making one pass over the
sampled data points to directly optimize the population objective, our
regularization-based method however does not require such one pass structure.

Now, we are ready to give a proof sketch of Theorem 2. The full proof is
deferred to Appendix A.5.

###### Proof.

(Proof Sketch of Theorem 2)

#### Privacy:

At iteration $t$, by the stability argument in Lemma 3, we have

$\displaystyle\left\|\tilde{w_{t}}-\tilde{w_{t}}^{\prime}\right\|_{2}\leq\frac{3L}{n_{t}\mu_{w}^{t}}+\frac{3B}{n_{t}\sqrt{\mu_{w}^{t}\mu_{\lambda}^{t}}}$
$\displaystyle=3L\eta_{t}+\frac{3B\sqrt{n_{t}n\eta_{t}\eta}}{n_{t}}\leq
6D\sqrt{(\log_{2}n)\eta_{t}\eta}$

where $\tilde{w_{t}}$ and $\tilde{w_{t}}^{\prime}$ are outputs from
neighboring dataset collections $\tilde{S}^{t}$ and $\tilde{S}^{t^{\prime}}$
that differ in one datapoint. The privacy follows from the privacy guarantee
of Gaussian mechanism.

#### Utility:

Recall that $R(w)=\max_{i\in[p]}L_{D_{i}}(w)$. By Lemma 4, we have

$\displaystyle\mathbb{E}[R(\tilde{w_{t}})-R(\tilde{w}_{t-1})]=\tilde{O}\left(\frac{\mathbb{E}[\left\|\xi_{t-1}\right\|_{2}^{2}]}{n_{t}\eta_{t}}+\frac{1}{\eta
n}+D^{2}\sqrt{\eta\eta_{t}}+\frac{B}{\sqrt{n_{t}}}\right)$

.

Also, we have

$\mathbb{E}\left\|\xi_{t}\right\|_{2}^{2}=d\sigma_{t}^{2}=72dD^{2}\log
n\log(1/\delta)2^{-t}\eta^{2}/\epsilon^{2}$

Therefore, as long as

$\eta\leq\frac{M\epsilon}{D\sqrt{72d\log n\log(1/\delta)}}$

We will have

$\mathbb{E}\left\|\xi_{t}\right\|_{2}^{2}\leq 2^{-t}M^{2}\text{ and
}\mathbb{E}\left\|\xi_{t}\right\|_{2}\leq\sqrt{2}^{-t}M$

Let $\tilde{w}_{0}=w^{*}$ and $\xi_{0}=w_{0}-w^{*}$. Then
$\left\|\xi_{0}\right\|_{2}\leq M$. Hence,

$\displaystyle\mathbb{E}[R(w_{T})]-R(w^{*})$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}[R(\tilde{w}_{t})-R(\tilde{w}_{t-1})]+\mathbb{E}[R(w_{T})-R(\hat{w}_{T})]$
$\displaystyle\leq\sum_{t=1}^{T}\tilde{O}\left(\frac{\mathbb{E}[\left\|\xi_{t-1}\right\|_{2}^{2}]}{n\eta_{t}}+\frac{1}{\eta
n}+D^{2}\sqrt{\eta\eta_{t}}+\frac{B}{\sqrt{n}}\right)+L\mathbb{E}[\left\|\xi_{T}\right\|_{2}]$

The inequality holds since $R(\cdot)$ is $L$-Lipschitz and
$n_{t}=n/\log_{2}(n)$.

We have

$\frac{\mathbb{E}[\left\|\xi_{t-1}\right\|_{2}^{2}]}{n_{t}\eta_{t}}\leq\frac{2^{-(t-1)}M^{2}\log_{2}n}{n2^{-t}\eta}=\frac{2(\log_{2}n)M^{2}}{\eta
n}$

and $\mathbb{E}[\left\|\xi_{T}\right\|_{2}]\leq
M\sqrt{2}^{-\log_{2}n}=\frac{M}{\sqrt{n}}$.

Therefore,

$\displaystyle\mathbb{E}[R(w_{T})]-R(w^{*})$
$\displaystyle\leq\sum_{t=1}^{T}\tilde{O}\left(\frac{M^{2}}{\eta
n}+D^{2}\eta+\frac{B}{\sqrt{n}}\right)+\frac{ML}{\sqrt{n}}$
$\displaystyle=\tilde{O}\left(\frac{MD}{\sqrt{n}}+\frac{MD\sqrt{d}}{n\epsilon}\right)$

Replace $n$ with $K/p$ and we get the desired result. ∎

##  4 Worst-group Risk Minimization using DP OCO Algorithm

In this section, we give a framework to directly minimize the expected worst-
group loss in (4) using any DP online convex optimization (OCO) algorithm as a
subroutine.

Our framework leverages the idea from [HJZ22, SGJ22, ZZY+23] of casting the
objective into a two-player zero-sum game. One can show that the excess
expected worst-group risk is bounded by the sum of the expected regret bounds
of the min-player (the $w$-player) and max-player (the $\lambda$-player) using
stochastic gradient estimation. Therefore, given any DP-OCO algorithm
$\mathcal{Q}_{-}$, our frameworks proceed by letting the $w$-player run
$\mathcal{Q}_{-}$ with an estimate of the loss function $\phi(w,\lambda_{t})$.
Meanwhile, we instantiate the $\lambda$-player as a standard EXP3 multi-arm
bandit algorithm and feed it with a privatized estimator of
$\nabla_{\lambda}\phi(w_{t},\lambda_{t})$.

An online convex optimization algorithm interacts with an adversary for $T$
rounds. In each round, the algorithm picks a vector $w_{t}$ and then the
adversary chooses a convex loss function $\ell_{t}$. The performance of an OCO
algorithm $\mathcal{Q}$ is therefore measured by the regret defined as

$r_{\mathcal{Q}}(T)=\frac{1}{T}\,\mathbb{E}\left[\sum_{t=1}^{T}\ell_{t}(w_{t})-\min_{w^{*}\in\mathcal{W}}\sum_{t=1}^{T}\ell_{t}(w^{*})\right]$

######  Definition 5.

An online algorithm $\mathcal{M}$ is $(\epsilon,\delta)$-DP if for any two
sequence of loss functions $S=(\ell_{1},\dots\ell_{T})$ and
$S^{\prime}=(\ell^{\prime}_{1},\dots\ell^{\prime}_{T})$ that differs in one
loss function, we have

$P(\mathcal{M}(S)\in O)\leq e^{\epsilon}P(\mathcal{M}(S^{\prime})\in
O)+\delta$

Suppose we have a DP OCO algorithm $\mathcal{Q}_{-}$ with regret
$r_{\mathcal{Q}_{-}}(T)$ that observes $l_{t}=\ell(\cdot,x_{t})$ for some data
point $x_{t}$ in each iteration, the formal description of our framework is
given in Algorithm 2. We give the privacy and utility guarantee of Algorithm 2
in the following theorems.

Algorithm 2 Worst-group risk minimization using DP-OCO algorithm

Input Sample oracles $\\{\mathcal{C}_{1},\dots\mathcal{C}_{p}\\}$, DP OCO
algorithm $\mathcal{Q}_{-}$, learning rate $\eta$, privacy parameters
$\epsilon,\delta$.

Initialize $w_{1}\in\mathcal{W}$ and $\lambda_{1}=\left(1/p,\dots
1/p\right)\in[0,1]^{p}$.

Set $U=B+\frac{2B}{\epsilon}\log(T)$.

for $t=1,\dots,T-1$ do

Sample $i_{t}\sim\lambda_{t}$.

Sample $x_{t}^{-},x_{t}^{+}\sim D_{i_{t}}$ using the sample oracle
$\mathcal{C}_{i_{t}}$.

Update $w_{t+1}=\mathcal{Q}_{-}(w_{1:t},x_{t}^{-})$.

Compute $\tilde{\ell}_{t}=U-\ell(w_{t},x_{t}^{+})+y_{t},$
$y_{t}\sim\text{Lap}(B/\epsilon)$.

Update
$\lambda_{t+1,i_{t}}=\lambda_{t,i_{t}}\text{exp}\left(\frac{-\eta\tilde{\ell}_{t}}{\lambda_{t,i_{t}}}\right)$.

Normalize
$\lambda_{t+1}=\frac{\lambda_{t+1}}{\left\|\lambda_{t+1}\right\|_{1}}$.

end for

Output $\bar{w}_{T}=\frac{1}{T}\sum_{t=1}^{T}w_{t}$,
$\bar{\lambda}_{T}=\frac{1}{T}\sum_{t=1}^{T}\lambda_{t}$.

######  Theorem 6.

(Privacy Guarantee) Algorithm 2 is $(\epsilon,\delta)$-differentially private.

###### Proof.

The sampled dataset can be divided into two disjoint sets.
$S=\\{S_{-},S_{+}\\}$ where $S_{-}=\\{x_{1}^{-},\dots x_{T}^{-}\\}$ and
$S_{+}=\\{x_{1}^{+},\dots x_{T}^{+}\\}$. Now, we proceed inductively. When
$t=1$, it is easy to see that the generation of $(w_{1},\lambda_{1})$ is
$(\epsilon,\delta)$-DP.

Now we assume that the generation of $\\{(w_{i},\lambda_{i})\\}_{i=1}^{t}$ is
$(\epsilon,\delta)$-DP for iteration $t$. At iteration $t+1$, we observe that
the computation of $w_{t+1}$ only depends on $S_{-}$ and
$\\{w_{i}\\}_{i=1}^{t}$, hence $w_{t+1}$ can be generated under
$(\epsilon,\delta)$-DP constraint due to the privacy guarantee of
$\mathcal{Q}_{-}$.

Furthermore, since $\ell$ is uniformly bounded by $B$, then clearly the
sensitivity of $\ell(w_{t},\cdot)$ w.r.t. replacing one data point in the
input sequence is bounded by $B$. Hence, by the properties of the Laplace
mechanism, $\tilde{\ell}_{t}$ is also generated in $(\epsilon,0)$-DP manner.
Given that $\lambda_{t+1}$ depends on only $\tilde{\ell}_{t}$ and
$\lambda_{t}$ and since DP is closed under postprocessing, computing
$\lambda_{t+1}$ is $(\epsilon,\delta)$-DP. Since in iteration $t$, two
different data points (namely, $x_{t}^{-}$ and $x_{t}^{+}$) are used to
generate $w_{t+1}$ and $\lambda_{t+1}$, then by parallel composition (and
given the induction hypothesis), generating $(w_{t+1},\lambda_{t+1})$ is
$(\epsilon,\delta)$-DP. ∎

######  Theorem 7.

(Utility Guarantee) Suppose the regret of $\mathcal{Q}_{-}$ is denoted as
$r_{\mathcal{Q}_{-}}(\cdot)$. By setting $\eta=\sqrt{\frac{\ln(p)}{pTU^{2}}}$,
we have

$\displaystyle\mathbb{E}\left[\max_{i\in[p]}L_{D_{i}}(\bar{w}_{T})\right]-\min_{w\in\mathcal{W}}\max_{i\in[p]}L_{D_{i}}(w)=r_{\mathcal{Q}_{-}}(K/2)+O\left(\frac{B\log(K)}{\epsilon}\sqrt{\frac{p\log(p)}{K}}\right)$

where $\bar{w}_{T}$ is the output of Algorithm 2 and the expectation is over
the sampling of data points and the algorithm’s randomness.

The proof of Theorem 7 can be found in Appendix B.1. In particular, by
instantiating the DP OCO algorithm $\mathcal{Q}_{-}$ with the DP-FTRL
algorithm [KMS+21], we have the following corollary.

######  Corollary 8.

Let $\mathcal{Q}_{-}$ in Algorithm 2 be DP-FTRL algorithm from [KMS+21]. By
plugging the regret bound of DP-FTRL into Theorem 7, we have

$\displaystyle\mathbb{E}\left[\max_{i\in[p]}L_{D_{i}}(\bar{w}_{T})\right]-\min_{w\in\mathcal{W}}\max_{i\in[p]}L_{D_{i}}(w)$
$\displaystyle=O\left(ML\sqrt{\frac{d^{\frac{1}{2}}\log^{2}(1/\delta)\log(K)}{\epsilon
K}}+\frac{B\log(K)}{\epsilon}\sqrt{\frac{p\log(p)}{K}}\right),$

where the expectation is over the sampling of data points and the algorithm’s
randomness.

#### Remark:

Corollary 8 demonstrates an excess expected worst-group risk of
$\tilde{O}\left(\sqrt{\frac{d^{1/2}}{\epsilon
K}}+\sqrt{\frac{p}{K\epsilon^{2}}}\right)$. For the common case of
$\epsilon=\Theta(1)$, the rate in Corollary 8 matches the lower bound of
$\Omega\left(\sqrt{\frac{p}{K}}\right)$ shown in [SGJ22] up to logarithmic
factors in the regime of $d=\tilde{O}\left(p^{2}\right)$.

##  5 Private Worst-group Empirical Risk Minimization

In this section, we consider the _offline setting_ where each distribution
$D_{i}$ is observed by a fixed-size dataset $S_{i}$ with i.i.d samples drawn
from $D_{i}$. In the offline setting, the learner will take the dataset
collection $\tilde{S}=\\{S_{1},\dots S_{p}\\}$ as input instead of querying
the sample oracles directly. This setting captures scenarios where each group
is represented by a dataset whose size is fixed beforehand.

In particular, we denote the dataset collection as $\tilde{S}=\\{S_{1},\dots
S_{p}\\}$. Without loss of generality, we assume all datasets $S_{i}$ have
same size, namely $|S_{i}|=n$ for all $i\in[p]$. Note that $n$ can also be
written as $n=K/p$ in this case. We first define the worst-group empirical
risk minimization problem as follows.

#### Worst-group empirical risk minimization

: Given a dataset collection $\tilde{S}=\\{S_{1},\dots
S_{p}\\}\in\mathcal{Z}^{n\times p}$, we denote
$\hat{\phi}(w,\lambda)=\sum_{i=1}^{p}\lambda_{i}L_{S_{i}}(w)$. The worst-group
empirical loss can be expressed as
$\max_{i\in[p]}L_{S_{i}}(w)=\max_{\lambda\in\Delta_{p}}\hat{\phi}(w,\lambda)$.
The empirical objective is hence written as

$\min_{w\in\mathcal{W}}\max_{\lambda\in\Delta_{p}}\hat{\phi}(w,\lambda)$ (6)

We define the _excess worst-group empirical risk_ of $w\in\mathcal{W}$ as

$\hat{\mathcal{E}}(w;\\{S_{i}\\}_{i=1}^{p})\triangleq\max_{i\in[p]}L_{S_{i}}(w)-\min_{\tilde{w}\in\mathcal{W}}\max_{i\in[p]}L_{S_{i}}(\tilde{w}).$

Next, we will present a method described in Algorithm 3 to solve the empirical
objective (6) under the differential privacy constraint. Algorithm 3 is based
on a private version of the multiplicative reweighting scheme [AAK+22, DGK+21]
and attains nearly optimal excess empirical worst-group risk.

###  5.1 Private Multiplicative Group Reweighting

Here, we provide the details of our algorithm described formally in Algorithm
3. In this algorithm, we maintain a sampling weight vector
$\lambda\in[0,1]^{p}$ for all datasets $\\{S_{i}\\}_{i=1}^{p}$. In each
iteration, we first sample a dataset according to $\lambda$. Next, we sample a
mini-batch from this dataset and update the model parameters using Noisy-SGD.
We then update the group weight vector $\lambda$ using the multiplicative
weights approach based on privatized loss values computed over the datasets at
the model parameters. We present the privacy and utility guarantee of
Algorithm 3 in the following theorems.

Algorithm 3 Noisy SGD with Multiplicative Group Reweighting (Noisy-SGD-MGR)

Input: Collection of datasets $\tilde{S}=\\{S_{1},\dots
S_{p}\\}\in\mathcal{Z}^{n\times p}$, mini-batch size $m$, $\\#$ iterations
$T$, learning rates $\eta_{w}$ and $\eta_{\lambda}$, privacy parameters
$\epsilon,\delta$, and noise scales $\sigma^{2},\tau$.

Initialize $w_{1}\in\mathcal{W}$ and
$\lambda_{1}=\left(\frac{1}{p},\dots\frac{1}{p}\right)\in[0,1]^{p}$.

for $t=1,\dots,T-1$ do

Sample $i_{t}\sim\lambda_{t}$.

Sample $B_{t}=\\{z_{1},\dots z_{m}\\}$ from $S_{i_{t}}$ uniformly with
replacement.

Update the model as follows
$w_{t+1}=\text{Proj}_{\mathcal{W}}\left(w_{t}-\eta_{w}\cdot\left(\frac{1}{m}\sum_{z\in
B_{t}}\nabla\ell(w_{t},z)+G_{t}\right)\right),$ where
$G_{t}\sim\mathcal{N}(0,\sigma^{2}I_{d})$.

Compute $L_{t}=[-L_{S_{i}}(w_{t})+y_{i,t}]_{i=1}^{q},$
$y_{i,t}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\text{Lap}(\tau)$.

Update the weights
$\tilde{\lambda}_{t+1}^{i}=\lambda_{t}^{i}\exp(-\eta_{\lambda}L_{t}^{i}),$
$\forall\leavevmode\nobreak\ i\in[p]$.

Normalize
$\lambda_{t+1}=\frac{\tilde{\lambda}_{t+1}}{\left\|\tilde{\lambda}_{t+1}\right\|_{1}}$.

end for

Output: $\bar{w}_{T}=\frac{1}{T}\sum_{t=1}^{T}w_{t}$,
$\bar{\lambda}_{T}=\frac{1}{T}\sum_{t=1}^{T}\lambda_{t}$.

######  Theorem 9.

(Privacy guarantee) In Algorithm 3, let
$\tau=\frac{cBp}{K\epsilon}\sqrt{T\log(1/\delta)}$ and
$\sigma^{2}=\frac{cTp^{2}L^{2}\log(T/\delta)\log(1/\delta)}{K^{2}\epsilon^{2}}$
for some universal constant $c$. Then, Algorithm 3 is $(\epsilon,\delta)$-DP.

######  Theorem 10.

(Convergence guarantee) There exist settings of
$T=O\left(\frac{(ML+B\sqrt{\log(p)})K^{2}\epsilon^{2}}{GBdp^{2}\log(1/\delta)}\right)$,
$\eta_{w}=O\left(\frac{M^{2}}{T(G^{2}+d\sigma^{2})}\right)$ and
$\eta_{\lambda}=O\left(\sqrt{\frac{\log(p)}{U^{2}T}}\right),$ where
$U=O\left(B+\frac{Bp}{K\epsilon}\sqrt{T\log(1/\delta)}\log(KT)\right)$ such
that

$\displaystyle\mathbb{E}\left[\max_{i\in[p]}L_{S_{i}}(\bar{w}_{T})\right]-\min_{w\in\mathcal{W}}\max_{i\in[p]}L_{S_{i}}(w)$
$\displaystyle=O\bigg{(}\frac{MLp\sqrt{d\log(1/\delta)\log(K/\delta)}}{K\epsilon}+\frac{Bp\sqrt{\log(p)\log(1/\delta)}\log(\frac{K\epsilon}{d\log(1/\delta)})}{K\epsilon}\bigg{)},$

where the expectation is over the algorithm’s randomness.

Remarks:

  * •

The convergence rate in Theorem 10 is nearly optimal up to logarithmic
factors. A lower bound instance can be created to reduce the original problem
to a DP-ERM problem with single dataset, which leads to a lower bound of
$\Omega\left(\frac{p\sqrt{d}}{K\epsilon}\right)$[BST14]. A more detailed
argument for the lower bound instance can be found in Appendix D.

  * •

[AAK+22] proposes a gradient method based on the active group selection
scheme. One can also design a private algorithm based on this scheme and
achieve a suboptimal rate of
$\tilde{O}\left(\sqrt{\frac{MLBp}{K\epsilon}}+\frac{MLp\sqrt{d}}{K\epsilon}\right)$.
We defer the details to Appendix C.2.

##  6 Conclusion

We presented differentially private algorithms for solving the worst-group
risk minimization problem. In particular, we gave two upper bounds on the
excess worst-group population risk, one of them is tight in the offline
setting and we established the optimal rate for the excess worst-group
empirical risk. Establishing the optimal rate for the worst-group population
risk in general is left as an interesting open problem for future work.

## Acknowledgements

This work is supported by NSF Award 2112471 and NSF CAREER Award 2144532.

## References

  * [AAK+22] Jacob D Abernethy et al.  “Active Sampling for Min-Max Fairness.”  In _International Conference on Machine Learning_ 162, 2022
  * [BFT+19] Raef Bassily, Vitaly Feldman, Kunal Talwar and Abhradeep Guha Thakurta  “Private stochastic convex optimization with optimal rates”  In _Advances in neural information processing systems_ 32, 2019
  * [BGM23] Raef Bassily, Cristóbal Guzmán and Michael Menart  “Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap”  In _arXiv preprint arXiv:2302.12909_ , 2023
  * [BHP+17] Avrim Blum, Nika Haghtalab, Ariel D Procaccia and Mingda Qiao  “Collaborative PAC learning”  In _Advances in Neural Information Processing Systems_ 30, 2017
  * [BST14] Raef Bassily, Adam Smith and Abhradeep Thakurta  “Private empirical risk minimization: Efficient algorithms and tight error bounds”  In _2014 IEEE 55th annual symposium on foundations of computer science_ , 2014, pp. 464–473  IEEE
  * [DGK+21] Emily Diana et al.  “Minimax group fairness: Algorithms and experiments”  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ , 2021, pp. 66–76
  * [DMN+06] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith  “Calibrating noise to sensitivity in private data analysis”  In _Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3_ , 2006, pp. 265–284  Springer
  * [FKT20] Vitaly Feldman, Tomer Koren and Kunal Talwar  “Private stochastic convex optimization: optimal rates in linear time”  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , 2020, pp. 439–449
  * [FV19] Vitaly Feldman and Jan Vondrak  “High probability generalization bounds for uniformly stable algorithms with nearly optimal rate”  In _Conference on Learning Theory_ , 2019, pp. 1270–1279  PMLR
  * [GGP24] Tomás González, Cristóbal Guzmán and Courtney Paquette  “Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems” Unpublished manuscript, 2024
  * [HJZ22] Nika Haghtalab, Michael Jordan and Eric Zhao  “On-demand sampling: Learning optimally from multiple distributions”  In _Advances in Neural Information Processing Systems_ 35, 2022, pp. 406–419
  * [KMS+21] Peter Kairouz et al.  “Practical and private (deep) learning without sampling or shuffling”  In _International Conference on Machine Learning_ , 2021, pp. 5213–5225  PMLR
  * [MSS19] Mehryar Mohri, Gary Sivek and Ananda Theertha Suresh  “Agnostic federated learning”  In _International Conference on Machine Learning_ , 2019, pp. 4615–4625  PMLR
  * [NJL+09] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan and Alexander Shapiro  “Robust stochastic approximation approach to stochastic programming”  In _SIAM Journal on optimization_ 19.4 SIAM, 2009, pp. 1574–1609
  * [OPZ+22] Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang and Kaiqing Zhang  “What is a Good Metric to Study Generalization of Minimax Learners?”  In _Advances in Neural Information Processing Systems_ 35, 2022, pp. 38190–38203
  * [Ora19] Francesco Orabona  “A modern introduction to online learning”  In _arXiv preprint arXiv:1912.13213_ , 2019
  * [PMB+22] Afroditi Papadaki et al.  “Minimax demographic group fairness in federated learning”  In _2022 ACM Conference on Fairness, Accountability, and Transparency_ , 2022, pp. 142–159
  * [SGJ22] Tasuku Soma, Khashayar Gatmiry and Stefanie Jegelka  “Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems”  In _arXiv preprint arXiv:2212.13669_ , 2022
  * [SKH+19] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto and Percy Liang  “Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization”  In _arXiv preprint arXiv:1911.08731_ , 2019
  * [YHL+22] Zhenhuan Yang et al.  “Differentially private sgda for minimax problems”  In _Uncertainty in Artificial Intelligence_ , 2022, pp. 2192–2202  PMLR
  * [ZHW+21] Junyu Zhang, Mingyi Hong, Mengdi Wang and Shuzhong Zhang  “Generalization bounds for stochastic saddle point problems”  In _International Conference on Artificial Intelligence and Statistics_ , 2021, pp. 568–576  PMLR
  * [ZTO+22] Liang Zhang, Kiran K Thekumparampil, Sewoong Oh and Niao He  “Bring your own algorithm for optimal differentially private stochastic minimax optimization”  In _Advances in Neural Information Processing Systems_ 35, 2022, pp. 35174–35187
  * [ZZY+23] Lijun Zhang, Peng Zhao, Tianbao Yang and Zhi-Hua Zhou  “Stochastic Approximation Approaches to Group Distributionally Robust Optimization”  In _arXiv preprint arXiv:2302.09267_ , 2023

##  Appendix A Missing Proofs in Section 3

###  A.1 Non-private algorithm for the regularized objective

Here, we provide an non-private algorithm in solving the regularized minimax
problem in (5) written as

$\min_{w\in\mathcal{W}}\max_{\lambda\in\Delta_{p}}F(w,\lambda)\coloneqq\sum_{i=1}^{p}\lambda_{i}L_{S_{i}}(w)+\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|^{2}-\mu_{\lambda}\sum_{j=1}^{p}\lambda_{j}\log\lambda_{j}$

with an convergence rate of $\tilde{O}\left(1/N\right)$ where $N$ is the
number of iterations.

Algorithm 4 Minimax Optimization for SC-SC Objective

Input: Collection of datasets $S=\\{S_{1},\dots S_{p}\\}$, regularization
parameters $\mu_{w}$, $\mu_{\lambda}>0$.

Init: $w_{1}\in\mathcal{W}$.

for $t=1,\dots,N-1$ do

Compute
$\tilde{\lambda}_{t}=\left[\exp(L_{S_{1}}(w_{t})/\mu_{\lambda}),\dots\exp(L_{S_{p}}(w_{t})/\mu_{\lambda})\right]$.

Let $\lambda_{t}=\frac{\tilde{\lambda_{t}}}{\left\|\lambda_{t}\right\|_{1}}$.

Compute $\nabla_{t}=\sum_{i=1}^{p}\lambda_{t}^{i}\nabla
L_{S_{i}}(w_{t})+\mu_{w}(w_{t}-w^{\prime})$ .

Update $w_{t+1}=\text{Proj}_{\mathcal{W}}(w_{t}-\eta_{t}\nabla_{t})$.

end for

Output: $\bar{w}_{N}=\frac{1}{N}\sum_{t=1}^{N}w_{t}$ and
$\bar{\lambda}_{N}=\frac{1}{N}\sum_{t=1}^{N}\lambda_{t}$ .

We now provide the convergence guarantee on Algorithm 4.

######  Theorem 11.

Let $\eta_{t}=\frac{1}{\mu_{w}t}$, we have

$\max_{\lambda\in\Delta_{p}}F(\bar{w}_{N},\lambda)-\min_{w\in\mathcal{W}}F(w,\bar{\lambda}_{N})=O\left(\frac{\ln
N}{N}\left(\frac{L^{2}}{\mu_{w}}+M^{2}\mu_{w}\right)\right)$

###### Proof.

An important observation here is that in $\lambda_{t}$ is the best response of
function $F(w_{t},\cdot)$, that is,

$\lambda_{t}=\operatorname*{arg\,min}_{\lambda\in\Delta_{p}}F(w_{t},\lambda)$

Then by Corollary 11.16 in [Ora19], we have

$\max_{\lambda\in\Delta_{p}}F(\bar{w}_{N},\lambda)-\min_{w\in\mathcal{W}}F(w,\bar{\lambda}_{N})\leq\frac{\text{Regret}_{N}^{w}}{N}$
(7)

where
$\text{Regret}_{N}^{w}=\sum_{t=1}^{N}l_{t}(w_{t})-\min_{w\in\mathcal{W}}\sum_{t=1}^{N}l_{t}(w)$
and $l_{t}(w)=F(w,\lambda_{t})$. Since $w$ is updated using online gradient
descent and $l_{t}(w)$ is strongly convex, by Corollary 4.9 in [Ora19] and
$\left\|\nabla_{t}\right\|_{2}\leq G+\mu_{w}B$, we have

$\text{Regret}_{N}^{w}=O\left(\frac{(L+\mu_{w}M)^{2}}{\mu_{w}}(1+\ln
N)\right)=O\left(\ln N\left(\frac{L^{2}}{\mu_{w}}+M^{2}\mu_{w}\right)\right)$
(8)

Combining equations (7) and (8), we get the desired result. ∎

###  A.2 Auxiliary Lemma

######  Lemma 12.

Let $(\hat{w},\hat{\lambda})$ be the exact saddle point of (5) and
$(\tilde{w},\tilde{\lambda})$ be an $\alpha$-saddle point of (5). Then we have

$\left\|\hat{w}-\tilde{w}\right\|_{2}\leq\sqrt{\frac{2\alpha}{\mu_{w}}}$

###### Proof.

Since $(\tilde{w},\tilde{\lambda})$ is an $\alpha$-saddle point of
$F(w,\lambda)$, then

$\displaystyle F(\tilde{w},\hat{\lambda})-F(\hat{w},\tilde{\lambda})$
$\displaystyle\leq\alpha$ $\displaystyle\implies
F(\tilde{w},\hat{\lambda})-F(\hat{w},\hat{\lambda})+F(\hat{w},\hat{\lambda})-F(\hat{w},\tilde{\lambda})$
$\displaystyle\leq\alpha$

Since $(\hat{w},\hat{\lambda})$ is the saddle point, then

$F(\hat{w},\hat{\lambda})-F(\hat{w},\tilde{\lambda})\geq 0$

Therefore,

$F(\tilde{w},\hat{\lambda})-F(\hat{w},\hat{\lambda})\leq\alpha$

Also we have
$\hat{w}=\operatorname*{arg\,min}_{w\in\mathcal{W}}F(w,\hat{\lambda})$ and
$F(\cdot,\hat{\lambda})$ is a $\mu_{w}$-strongly convex function, then

$\displaystyle\mu_{w}/2\left\|\hat{w}-\tilde{w}\right\|_{2}^{2}\leq
F(\tilde{w},\hat{\lambda})-F(\hat{w},\hat{\lambda})\leq\alpha$
$\displaystyle\implies\left\|\hat{w}-\tilde{w}\right\|_{2}\leq\sqrt{\frac{2\alpha}{\mu_{w}}}$

∎

###  A.3 Proof of Lemma 3

###### Proof.

Note that the empirical objective
$\hat{\phi}(w,\lambda)=\sum_{i=1}^{p}\lambda_{i}L_{S_{i}}(w)$ can also be
written in a finite sum form. For any $i\in[p]$, we denote $z_{i}^{j}$ be the
$j_{th}$ datapoint of dataset $S_{i}$ and define batched node
$\xi^{j}=(z_{1}^{j},\dots z_{p}^{j})$. Hence $\tilde{S}$ can be expressed as
$\tilde{S}=\\{\xi^{1},\dots\xi^{n}\\}$. We also define a new loss function
$f(w,\lambda,\xi)$ where $\xi=\\{z_{1},\dots z_{p}\\}$ as

$f(w,\lambda,\xi)=\sum_{i=1}^{p}\lambda_{i}\ell(w,z_{i})$

Then it is easy to show that

$\hat{\phi}(w,\lambda)=\frac{1}{n}\sum_{j=1}^{n}f(w,\lambda,\xi^{j})$ (9)

Suppose $\tilde{S}=\\{\xi_{1},\dots\xi_{i},\dots\xi_{n}\\}$ and
$\tilde{S}^{\prime}=\\{\xi_{1},\dots\xi^{\prime}_{i},\dots\xi_{n}\\}$ where
$\xi_{i}$ and $\xi^{\prime}_{i}$ differ with single datapoint $z_{i}^{j}$ for
some $j\in[n]$. By equation $\eqref{eq: finite sume form}$, we have

$\displaystyle\hat{\phi}(w,\lambda)$
$\displaystyle=\frac{1}{n}\sum_{\xi\in\tilde{S}}f(w,\lambda,\xi)$
$\displaystyle\hat{\phi}^{\prime}(w,\lambda)$
$\displaystyle=\frac{1}{n}\sum_{\xi\in\tilde{S}^{\prime}}f(w,\lambda,\xi)$

We also let
$\Psi(w,\lambda)=\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}-\mu_{\lambda}\sum_{j=1}^{p}\lambda_{j}\log\lambda_{j}$.

Let $(\hat{w},\hat{\lambda})$ and $(\hat{w}^{\prime},\hat{\lambda}^{\prime})$
be the exact saddle point of $\hat{\phi}(w,\lambda)+\Psi(w,\lambda)$ and
$\hat{\phi}^{\prime}(w,\lambda)+\Psi(w,\lambda)$ respectively.

It is easy to show that $\left\|\nabla_{w}f(w,\lambda,\xi)\right\|_{2}\leq L$
and $\left\|\nabla_{\lambda}f(w,\lambda,\xi)\right\|_{\infty}\leq B$ for any
$\xi$. Also, $\hat{\phi}(w,\lambda)+\Psi(w,\lambda)$ is $\mu_{w}$-strongly
convex w.r.t $\left\|\cdot\right\|_{2}$ and $\mu_{\lambda}$-strongly concave
w.r.t $\left\|\cdot\right\|_{1}$. Then using Lemma 2 from [ZHW+21], we obtain

$\sqrt{\mu_{w}\left\|\hat{w}-\hat{w}^{\prime}\right\|_{2}^{2}+\mu_{\lambda}\left\|\hat{\lambda}-\hat{\lambda}^{\prime}\right\|_{1}^{2}}\leq\frac{2}{n}\sqrt{\frac{L^{2}}{\mu_{w}}+\frac{B^{2}}{\mu_{\lambda}}}$

Furthermore, we have

$\displaystyle\left\|\hat{w}-\hat{w}^{\prime}\right\|_{2}\leq\sqrt{\mu_{w}\left\|\hat{w}-\hat{w}^{\prime}\right\|_{2}^{2}+\mu_{\lambda}\left\|\hat{\lambda}-\hat{\lambda}^{\prime}\right\|_{1}^{2}}/\sqrt{\mu_{w}}$
$\displaystyle\leq\frac{1}{n}\sqrt{\frac{4L^{2}}{\mu_{w}^{2}}+\frac{4B^{2}}{\mu_{\lambda}\mu_{w}}}\leq\frac{2}{n}\left(\frac{L}{\mu_{w}}+\frac{B}{\sqrt{\mu_{w}\mu_{\lambda}}}\right)$

Meanwhile, by Lemma 12, we also have

$\left\|\tilde{w}-\hat{w}\right\|_{2}\leq\sqrt{\frac{2\alpha}{\mu_{w}}}\leq\frac{1}{2n}\left(\frac{L}{\mu_{w}}+\frac{B}{\sqrt{\mu_{w}\mu_{\lambda}}}\right)$

and

$\left\|\tilde{w}^{\prime}-\hat{w}^{\prime}\right\|_{2}\leq\sqrt{\frac{2\alpha}{\mu_{w}}}\leq\frac{1}{2n}\left(\frac{L}{\mu_{w}}+\frac{B}{\sqrt{\mu_{w}\mu_{\lambda}}}\right)$

Putting every thing together, we have

$\left\|\tilde{w}-\tilde{w}^{\prime}\right\|_{2}\leq\frac{3}{n}\left(\frac{L}{\mu_{w}}+\frac{B}{\sqrt{\mu_{w}\mu_{\lambda}}}\right)$

∎

###  A.4 Proof of Lemma 4

###### Proof.

Let $R(w)=\max_{i\in[p]}L_{D_{i}}(w)$ and
$\hat{\phi}(w,\lambda)=\sum_{i\in[p]}\lambda_{i}L_{S_{i}}(w)$. Denote
$(\hat{w},\hat{\lambda})$ the exact saddle point of $F(w,\lambda)$. By the
definition of saddle point, we have for any $w\in\mathcal{W}$ and
$\lambda\in\Delta_{p}$,

$\displaystyle\hat{\phi}(\hat{w},\lambda)+\frac{\mu_{w}}{2}\left\|\hat{w}-w^{\prime}\right\|_{2}^{2}-\mu_{\lambda}\sum_{j=1}^{p}\lambda_{j}\log\lambda_{j}$
$\displaystyle-\left(\hat{\phi}(w,\hat{\lambda})+\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}-\mu_{\lambda}\sum_{j=1}^{p}\hat{\lambda}_{j}\log\hat{\lambda}_{j}\right)\leq
0$
$\displaystyle\implies\hat{\phi}(\hat{w},\lambda)-\hat{\phi}(w,\hat{\lambda})\leq$
$\displaystyle\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}-\mu_{\lambda}\sum_{j=1}^{p}\hat{\lambda}_{j}\log\hat{\lambda}_{j}-\left(\frac{\mu_{w}}{2}\left\|\hat{w}-w^{\prime}\right\|_{2}^{2}-\mu_{\lambda}\sum_{j=1}^{p}\lambda_{j}\log\lambda_{j}\right)$
$\displaystyle\leq\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}-\mu_{\lambda}\sum_{j=1}^{p}\hat{\lambda}_{j}\log\hat{\lambda}_{j}$
$\displaystyle\leq\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}+\mu_{\lambda}\log
p$

In particular, we have for any $w\in\mathcal{W}$

$\max_{i\in[p]}L_{S_{i}}(\hat{w})-\hat{\Phi}(w,\hat{\lambda})\leq\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}+\mu_{\lambda}\log
p$

By Lemma 3, for any fixed $i\in[p]$, computing $\hat{w}$ has a uniform
stability of
$\gamma=\frac{2L^{2}}{n\mu_{w}}+\frac{2LB}{n\sqrt{\mu_{w}\mu_{\lambda}}}$ with
respect to the change of datapoint in dataset $S_{i}$. Therefore, by fixing
the randomness of $\tilde{S}_{-i}=\\{S_{1},\dots S_{i-1},S_{i+1},\dots
S_{p}\\}$ and Theorem 1.1 from [FV19], we have

$P_{S_{i}\sim D_{i}^{n}}\left(|L_{S_{i}}(\hat{w})-L_{D_{i}}(\hat{w})|\geq
c\left(\gamma\log(n)\log(n/\beta)+\frac{B\sqrt{\log
1/\beta}}{\sqrt{n}}\right)\right)\leq\beta$

Then we can release the randomness of $\tilde{S}_{-i}$ and obtain

$P_{\tilde{S}}\left(|L_{S_{i}}(\hat{w})-L_{D_{i}}(\hat{w})|\geq
c\left(\gamma\log(n)\log(n/\beta)+\frac{B\sqrt{\log
1/\beta}}{\sqrt{n}}\right)\right)\leq\beta$

Using union bound across all $i\in[p]$, we obtain with probability over
$1-\beta$, for all $i\in[p]$

$|L_{S_{i}}(\hat{w})-L_{D_{i}}(\hat{w})|=O\left(\left(\frac{L^{2}}{n\mu_{w}}+\frac{LB}{n\sqrt{\mu_{w}\mu_{\lambda}}}\right)\log(n)\log(np/\beta)+\frac{B\sqrt{\log(p/\beta)}}{\sqrt{n}}\right)$

Therefore, with probability $1-\beta$, we have

$\displaystyle|\max_{i\in[p]}L_{D_{i}}(\hat{w})-\max_{i\in[p]}L_{S_{i}}(\hat{w})|$
$\displaystyle=O\left(\left(\frac{L^{2}}{n\mu_{w}}+\frac{LB}{n\sqrt{\mu_{w}\mu_{\lambda}}}\right)\log(n)\log(np/\beta)+\frac{B\sqrt{\log(p/\beta)}}{\sqrt{n}}\right)$

Also, since $w$ is independent of the dataset, with probability over $1-\beta$

$|L_{S_{i}}(w)-L_{D_{i}}(w)|=O\left(\frac{B\log(p/\beta)}{\sqrt{n}}\right)\quad\forall
i\in[p]$

and

$|\Phi(w,\hat{\lambda})-\hat{\Phi}(w,\hat{\lambda})|=O\left(\frac{B\log(p/\beta)}{\sqrt{n}}\right)$

After putting everything together, we obtain with probability over $1-2\beta$

$\displaystyle
R(\hat{w})-R(w)=\max_{i\in[p]}L_{D_{i}}(\hat{w})-\max_{i\in[p]}L_{D_{i}}(w)$
$\displaystyle\leq\max_{i\in[p]}L_{D_{i}}(\hat{w})-\phi(w,\hat{\lambda})$
$\displaystyle\leq\max_{i\in[p]}L_{S_{i}}(\hat{w})-\hat{\phi}(w,\hat{\lambda})+O\left(\left(\frac{L^{2}}{n\mu_{w}}+\frac{LB}{n\sqrt{\mu_{w}\mu_{\lambda}}}\right)\log(n)\log(np/\beta)+\frac{B\sqrt{\log(p/\beta)}}{\sqrt{n}}\right)$
$\displaystyle=O\left(\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}+\mu_{\lambda}\log
p+\left(\frac{L^{2}}{n\mu_{w}}+\frac{LB}{n\sqrt{\mu_{w}\mu_{\lambda}}}\right)\log(n)\log(np/\beta)+\frac{B\sqrt{\log(p/\beta)}}{\sqrt{n}}\right)$

Choosing $\beta=1/n$ and taking expectation over the dataset collection
$\tilde{S}$, we obtain

$\displaystyle\mathbb{E}\left[R(\hat{w})\right]-R(w)$ (10)
$\displaystyle=O\left(\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}+\mu_{\lambda}\log
p+\left(\frac{L^{2}}{n\mu_{w}}+\frac{LB}{n\sqrt{\mu_{w}\mu_{\lambda}}}\right)\log(n)\log(np)+\frac{B\sqrt{\log(pn)}}{\sqrt{n}}\right)$

By Lemma 12, we have

$\left\|\tilde{w}-\hat{w}\right\|_{2}\leq\sqrt{\frac{2\alpha}{\mu_{w}}}\leq\frac{1}{2n}\left(\frac{L}{\mu_{w}}+\frac{B}{\sqrt{\mu_{w}\mu_{\lambda}}}\right)$

Given the fact that $R(\cdot)$ is $L$-Lipschitz, we have

$|R(\tilde{w})-R(\hat{w})|\leq
L\left\|\tilde{w}-\hat{w}\right\|_{2}=O\left(\frac{L^{2}}{n\mu_{w}}+\frac{LB}{n\sqrt{\mu_{w}\mu_{\lambda}}}\right)$
(11)

Combining equations (10) and (11), we have

$\displaystyle\mathbb{E}\left[R(\tilde{w})\right]-R(w)$
$\displaystyle=O\left(\frac{\mu_{w}}{2}\left\|w-w^{\prime}\right\|_{2}^{2}+\mu_{\lambda}\log
p+\left(\frac{L^{2}}{n\mu_{w}}+\frac{LB}{n\sqrt{\mu_{w}\mu_{\lambda}}}\right)\log(n)\log(np)+\frac{B\sqrt{\log(pn)}}{\sqrt{n}}\right)$

∎

###  A.5 Proof of Theorem 2

###### Proof.

Privacy: At iteration $t$, by the stability argument in Lemma 3, we have

$\displaystyle\left\|\tilde{w_{t}}-\tilde{w_{t}}^{\prime}\right\|_{2}$
$\displaystyle\leq\frac{3L}{n_{t}\mu_{w}^{t}}+\frac{3B}{n_{t}\sqrt{\mu_{w}^{t}\mu_{\lambda}^{t}}}$
$\displaystyle=3L\eta_{t}+\frac{3B\sqrt{n_{t}n\eta_{t}\eta}}{n_{t}}$
$\displaystyle\leq 6D\sqrt{(\log_{2}n)\eta_{t}\eta}$

where $\tilde{w_{t}}$ and $\tilde{w_{t}}^{\prime}$ are outputs from
neighboring dataset collections $\tilde{S}^{t}$ and $\tilde{S}^{t^{\prime}}$
that differ in one datapoint. The privacy follows from the privacy guarantee
of Gaussian mechanism.

Utility: By Lemma 4, we have

$\displaystyle\mathbb{E}[R(\tilde{w_{t}})-R(\tilde{w}_{t-1})]$
$\displaystyle=O\left(\frac{\mathbb{E}[\left\|\xi_{t-1}\right\|_{2}^{2}]}{n_{t}\eta_{t}}+\frac{\log
p}{\eta
n}+D^{2}\sqrt{\eta\eta_{t}}\log^{1.5}n\log(np)+\frac{B\sqrt{\log(pn)}}{\sqrt{n_{t}}}\right)$

where $R(w)=\max_{i\in[p]}L_{D_{i}}(w)$.

Also, we have

$\mathbb{E}\left\|\xi_{t}\right\|_{2}^{2}=d\sigma_{t}^{2}=72dD^{2}\log(n)\log(1/\delta)2^{-t}\eta^{2}/\epsilon^{2}$

Therefore, as long as

$\eta\leq\frac{M\epsilon}{D\sqrt{72d\log(n)\log(1/\delta)}}$

We will have

$\mathbb{E}\left\|\xi_{t}\right\|_{2}^{2}\leq 2^{-t}M^{2}\text{ and
}\mathbb{E}\left\|\xi_{t}\right\|_{2}\leq\sqrt{2}^{-t}M$

Let $\tilde{w}_{0}=w^{*}$ and $\xi_{0}=w_{0}-w^{*}$. Then
$\left\|\xi_{0}\right\|_{2}\leq M$. Hence

$\displaystyle\mathbb{E}[R(w_{T})]-R(w^{*})=\sum_{t=1}^{T}\mathbb{E}[R(\tilde{w}_{t})-R(\tilde{w}_{t-1})]+\mathbb{E}[R(w_{T})-R(\hat{w}_{T})]$
$\displaystyle\leq\sum_{t=1}^{T}O\left(\frac{\mathbb{E}[\left\|\xi_{t-1}\right\|_{2}^{2}]}{n_{t}\eta_{t}}+\frac{\log
p}{\eta
n}+D^{2}\sqrt{\eta\eta_{t}}\log^{1.5}n\log(np)+\frac{B\sqrt{\log(n)\log(pn)}}{\sqrt{n}}\right)$
$\displaystyle\quad+L\mathbb{E}[\left\|\xi_{T}\right\|_{2}]\quad\text{($R(\cdot)$
is $L$-Lipschitz.)}$

We have

$\frac{\mathbb{E}[\left\|\xi_{t-1}\right\|_{2}^{2}]}{n_{t}\eta_{t}}\leq\frac{2^{-(t-1)}M^{2}\log_{2}n}{n2^{-t}\eta}=\frac{2(\log_{2}n)M^{2}}{\eta
n}$

and $\mathbb{E}[\left\|\xi_{T}\right\|_{2}]\leq
M\sqrt{2}^{-\log_{2}n}=\frac{M}{\sqrt{n}}$.

Therefore,

$\displaystyle\mathbb{E}[R(w_{T})]-R(w^{*})$
$\displaystyle\leq\sum_{t=1}^{T}O\left(\frac{\log(n)M^{2}}{\eta
n}+\frac{\log(p)}{\eta
n}+D^{2}\eta\log^{1.5}(n)\log(np)+\frac{B\sqrt{\log(n)\log(pn)}}{\sqrt{n}}\right)$
$\displaystyle\quad+\frac{ML}{\sqrt{n}}$ $\displaystyle=\log n\cdot
O\left(\frac{(\log(np))M^{2}}{\eta
n}+D^{2}\eta\log^{2.5}(np)+\frac{B\sqrt{\log(n)\log(np)}}{\sqrt{n}}\right)$
$\displaystyle\quad+\frac{ML}{\sqrt{n}}$
$\displaystyle=O\left(\frac{MD\log^{11/4}(np)}{\sqrt{n}}+(MD\log^{5/2}(np))\frac{\sqrt{d\log(1/\delta)}}{n\epsilon}\right)$

Replacing $n$ with $K/p$ gives the desired result. ∎

##  Appendix B Missing Proofs in Section 4

###  B.1 Proof of Theorem 7

###### Proof.

It is easy to see that the objective in (3) is equivalent to

$\min_{w\in\mathcal{W}}\max_{\lambda\in\Delta_{p}}\sum_{i\in[p]}\lambda_{i}L_{D_{i}}(w)$

where $\Delta_{p}=\\{\lambda\in[0,1]^{p}:\left\|\lambda\right\|_{1}=1\\}$ the
probability simplex over $p$ users. Recall
$\phi(w,\lambda)=\sum_{i\in[p]}\lambda_{i}L_{D_{i}}(w)$, then we have

$\displaystyle\max_{\lambda\in\Delta_{p}}\phi(\bar{w}_{T},\lambda)-\min_{w\in\mathcal{W}}\max_{\lambda\in\Delta_{p}}\phi(w,\lambda)$
$\displaystyle=\max_{\lambda\in\Delta_{p}}\phi(\bar{w}_{T},\lambda)-\max_{\lambda\in\Delta_{p}}\min_{w\in\mathcal{W}}\phi(w,\lambda)$
$\displaystyle\leq\frac{1}{T}\max_{w\in\mathcal{W},\lambda\in\Delta_{p}}\left\\{\sum_{t=1}^{T}\phi(w_{t},\lambda)-\phi(w,\lambda_{t})\right\\}$
$\displaystyle=\frac{1}{T}\max_{w\in\mathcal{W},\lambda\in\Delta_{p}}\left\\{\sum_{t=1}^{T}\left(\phi(w_{t},\lambda)-\phi(w_{t},\lambda_{t})+\phi(w_{t},\lambda_{t})-\phi(w,\lambda_{t})\right)\right\\}$
$\displaystyle=\frac{1}{T}\left[\sum_{t=1}^{T}\phi(w_{t},\lambda_{t})-\min_{w\in\mathcal{W}}\sum_{t=1}^{T}\phi(w,\lambda_{t})\right]\quad(A)$
$\displaystyle\quad+\frac{1}{T}\left[\sum_{t=1}^{T}-\phi(w_{t},\lambda_{t})-\min_{\lambda\in\Delta_{p}}\sum_{t=1}^{T}(-\phi(w_{t},\lambda))\right]\quad(B)$

We address the term A first. By fixing the randomness of $w_{t}$ and
$\lambda_{t}$ for some iteration $t$, we have
$\mathbf{E}_{x_{t}^{-}}\ell(w_{t},x_{t}^{-})=\phi(w_{t},\lambda_{t})$. By
extending the same argument to all $t\in[T]$, we obtain for any $w$,

$\frac{1}{T}\mathbf{E}\left[\sum_{t=1}^{T}\left(\phi(w_{t},\lambda_{t})-\phi(w,\lambda_{t})\right)\right]=\frac{1}{T}\mathbf{E}\left[\sum_{t=1}^{T}\ell(w_{t},x_{t}^{-})-\ell(w,x_{t}^{-})\right]$

By the regret guarantee of $\mathcal{Q}_{-}$, we have for any sequence
$x_{1}^{-},\dots x_{T}^{-}$

$\frac{1}{T}\mathbf{E}\left[\sum_{t=1}^{T}\ell(w_{t},x_{t}^{-})-\ell(w,x_{t}^{-})\right]\leq
r_{Q_{-}}(T)$

where the expectation is taken from the randomness over the algorithm.
Therefore, we have

$\mathbf{E}[A]\leq r_{Q_{-}}(T)$ (12)

We then address the term $B$. We first define $\ell^{\prime}(w,x)$ as the
difference between some fixed constant $U$ and the original loss function
$\ell(w,x)$, that is, $\ell^{\prime}(w,x)=U-\ell(w,x)$. Similarly the vector
of $p$ population risks over the new loss function $\ell^{\prime}$ is
therefore written as $g(w)=[L^{\prime}_{D_{1}}(w),\dots
L^{\prime}_{D_{p}}(w)]$. Therefore, the term $B$ can be equivalently written
as

$B=\frac{1}{T}\left[\sum_{t=1}^{T}\langle
g(w_{t}),\lambda_{t}\rangle-\min_{\lambda\in\Delta^{p}}\sum_{t=1}^{T}\langle
g(w_{t}),\lambda\rangle\right]$

Notice that at each iteration $t$, we have

$\nabla_{\lambda}\langle g(w_{t}),\lambda\rangle=g(w_{t})$

We construct a unbiased estimator of $g(w_{t})$ as

$g^{\prime}(w_{t})=\begin{cases}\frac{\tilde{\ell}_{t}}{\lambda_{t}^{i}}\quad
i=j_{t}\\\ 0\quad o.w.\end{cases}$

By letting $U=B+\frac{2B}{\epsilon}\log(T)$, we have we have w.p. over
$1-\frac{1}{T}$, $\max_{t\in[T]}|y_{t}|\leq\frac{2B}{\epsilon}\log(T)$, which
we denote as event $E$. Conditioned on $E$, we have $\tilde{l}_{t}\in[0,2U]$
for any $t\in[T]$.

Observing that for any fixed $w_{t}$, since $x_{t}^{+}\sim D_{i_{t}}$, we
obtain

$\mathbf{E}[g^{\prime}(w_{t})|E]=g(w_{t})$

We now establish the bound on term B

$\displaystyle\mathbf{E}\left[\sum_{t=1}^{T}\langle
g(w_{t}),\lambda_{t}\rangle-\sum_{t=1}^{T}\langle
g(w_{t}),\lambda\rangle\right]$
$\displaystyle=\mathbf{E}\left[\sum_{t=1}^{T}\langle
g^{\prime}(w_{t}),\lambda_{t}\rangle-\sum_{t=1}^{T}\langle
g^{\prime}(w_{t}),\lambda\rangle\right]$

Since $\left\|g^{\prime}(w_{t})\right\|_{\infty}\leq 2U$ conditioned on event
$E$, by setting $\eta=\sqrt{\frac{\ln(p)}{pTU^{2}}}$ and invoking the regret
bound of EXP3, we obtain

$\displaystyle\mathbf{E}[B|E]$
$\displaystyle=\frac{1}{T}\mathbf{E}\left[\sum_{t=1}^{T}\langle
g(w_{t}),\lambda_{t}\rangle-\sum_{t=1}^{T}\langle
g(w_{t}),\lambda\rangle\right]$
$\displaystyle=O\left(U\sqrt{\frac{p\log(p)}{T}}\right)$

Then we take the expectation on $E$ and obtain

$\mathbf{E}[B]=P(E)\mathbf{E}[B|E]+(1-P(E))\mathbf{E}[B|E^{c}]=O\left(U\sqrt{\frac{p\log(p)}{T}}\right)$

Finally we plug in the value of $U$,

$\mathbf{E}[B]=O\left(\frac{B\log(T)}{\epsilon}\sqrt{\frac{p\log(p)}{T}}\right)$
(13)

We combine equations (12) and (13) to get the desired result. ∎

##  Appendix C Missing Proofs from Section 5

###  C.1 Proof of Theorem 9 and 10

###### Proof.

(Proofs of Theorem 9) Note that given two neighboring data collections
$\tilde{S}=\\{S_{1},\dots S_{p}\\}$ and
$\tilde{S}^{\prime}=\\{S^{\prime}_{1},\dots S^{\prime}_{p}\\}$ that differ in
one datapoint of $j_{th}$ dataset for some $j\in[p]$. In iteration $t$, if
$i_{t}\neq j$, then the output distribution of $w_{t+1}$ is same for
$\tilde{S}$ and $\tilde{S}^{\prime}$. Otherwise, generating $w_{t+1}$
satisfies $(\frac{\epsilon}{c\sqrt{T\log(1/\delta)}},\frac{\delta}{2T})$-DP
based on the property of Gaussian mechanism and privacy amplification by
subsampling. Therefore, overall generating $w_{t+1}$ is
$(\frac{\epsilon}{c\sqrt{T\log(1/\delta)}},\frac{\delta}{2T})$-DP.

Meanwhile, generating $\lambda_{t+1}$ is
$(\frac{\epsilon}{c\sqrt{T\log(1/\delta)}},0)$-DP based on the property of
Laplace mechanism. Using basic composition, we have generating the pair
$(w_{t+1},\lambda_{t+1})$ is
$(\frac{2\epsilon}{c\sqrt{T\log(1/\delta)}},\frac{\delta}{2T})$-DP. Hence, by
strong composition for $t\in[T]$, we obtain the algorithm is
$(\epsilon,\delta)$-DP. ∎

###### Proof.

(Proof of Theorem 10) Recall that $n=K/p$. We have

$\displaystyle\max_{\lambda\in\Delta_{p}}\hat{\phi}(\bar{w}_{T},\lambda)-\min_{w\in\mathcal{W}}\max_{\lambda\in\Delta_{p}}\hat{\phi}(w,\lambda)$
$\displaystyle\leq\max_{\lambda\in\Delta_{p}}\hat{\phi}(\bar{w}_{T},\lambda)-\min_{w\in\mathcal{W}}\hat{\phi}(w,\bar{\lambda}_{T})$
$\displaystyle\leq\max_{\lambda\in\Delta_{p},w\in\mathcal{W}}\left\\{\frac{1}{T}\sum_{t=1}^{T}\left(\hat{\phi}(w_{t},\lambda)-\hat{\phi}(w,\lambda_{t})\right)\right\\}$
$\displaystyle=\max_{\lambda\in\Delta_{p},w\in\mathcal{W}}\left\\{\frac{1}{T}\sum_{t=1}^{T}\left(\hat{\phi}(w_{t},\lambda)+\hat{\phi}(w_{t},\lambda_{t})-\hat{\phi}(w_{t},\lambda_{t})-\hat{\phi}(w,\lambda_{t})\right)\right\\}$
$\displaystyle=\frac{1}{T}\left[\sum_{t=1}^{T}\hat{\phi}(w_{t},\lambda_{t})-\min_{w\in\mathcal{W}}\sum_{t=1}^{T}\hat{\phi}(w,\lambda_{t})\right]\quad(A)$
$\displaystyle\quad+\frac{1}{T}\left[\sum_{t=1}^{T}-\hat{\phi}(w_{t},\lambda_{t})-\min_{\lambda\in\Delta_{p}}\sum_{t=1}^{T}(-\hat{\phi}(w_{t},\lambda))\right]\quad(B)$

Next, we will bound the terms $A$ and $B$ separately. We address term $A$
first. In particular, for any $w\in\mathcal{W}$, we can rewrite the
expectation of term $A$ as

$\displaystyle\mathbb{E}[A]=\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\left(\hat{\phi}(w_{t},\lambda_{t})-\hat{\phi}(w,\lambda_{t})\right)\right]$
$\displaystyle\leq\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla\hat{\phi}(w_{t},\lambda_{t}),w_{t}-w\rangle\right]$

For any iteration $t$, by fixing the randomness up to $w_{t}$ and
$\lambda_{t}$ and letting $\nabla_{t}=\frac{1}{m}\sum_{z\in
B_{t}}\nabla\ell(w_{t},z)+G_{t}$ be the gradient update in step 6 in Algorithm
3, we have

$\mathbb{E}[\nabla_{t}]=\nabla\hat{\phi}(w_{t},\lambda_{t})$

We can extend the same augment for all $t\in[T]$ and obtain

$\displaystyle\mathbb{E}[A]\leq\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla\hat{\phi}(w_{t},\lambda_{t}),w_{t}-w\rangle\right]$
$\displaystyle=\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla_{t},w_{t}-w\rangle\right]$
$\displaystyle\leq\frac{M^{2}}{2T\eta}+\frac{\eta}{2T}\sum_{t=1}^{T}\mathbb{E}\left[\left\|\nabla_{t}\right\|^{2}\right]$
$\displaystyle\leq\frac{\eta
L^{2}}{2}+\frac{M^{2}}{2T\eta}+\frac{d\sigma^{2}\eta}{2}$

where the first equality holds by standard convex analysis.

Meanwhile, we let $U=B+\frac{8B}{n\epsilon}\sqrt{T\log(1/\delta)}\log(pnT/2)$,
and denote $L^{\prime}_{t}=[U-L_{S_{i}}(w_{t})+y_{i,t}]_{i=1}^{p}$. By using a
union bound, we have $\left\|L^{\prime}(t)\right\|_{\infty}\leq 2U$ for all
$t\in[T]$ with probability over $1-\frac{1}{n}$, which we denote as event E.
Conditioned on event E, our update rule for $\lambda$ can be seen as applying
the Hedge algorithm with $L^{\prime}_{t}$ as the loss input and the term $B$
is formulated as its corresponding regret bound. Therefore, by the regret
bound of Hedge , we obtain

$\mathbb{E}[B|E]=O\left(\left\|L_{t}\right\|_{\infty}\sqrt{\frac{\log(p)}{T}}\right)=O\left(B\sqrt{\frac{\log(p)}{T}}+\frac{B\sqrt{\log(p)\log(1/\delta)}\log(pnT)}{n\epsilon}\right)$

Then we can take the expectation over $E$ and have

$\mathbb{E}[B]=P(E)\mathbb{E}[B|E]+P(E^{c})\mathbb{E}[B|E^{c}]=O\left(B\sqrt{\frac{\log(p)}{T}}+\frac{B\sqrt{\log(p)\log(1/\delta)}\log(pnT)}{n\epsilon}\right)$

By combining the bounds of $\mathbb{E}[A]$ and $\mathbb{E}[B]$ and plugging
into the values of $T$, $\eta_{w}$ and $\eta_{\lambda}$, we obtain the desired
result. ∎

###  C.2 Private Active Group Selection

Here we present another algorithm built upon the active group selection scheme
described in Algorithm 5. Algorithm 5 is different from Algorithm 3 on the
group selection method. Instead of maintaining a weight vector to sample the
dataset as in Algorithm 3, we select the dataset with highest loss in each
iteration. To maintain privacy, we resort to the report-noisy-max mechanism
for the group selection. After such (approximately) worst-off group is
selected, we sample a mini-batch from it and use Noisy-SGD to update the model
parameters.

Algorithm 5 Noisy SGD with active group selection (Noisy-SGD-AGS)

InputCollection of datasets $S=\\{S_{1},\dots S_{p}\\}\in\mathcal{Z}^{n\times
p}$, mini-batch size $m$, $\\#$ iterations $T$, learning rate $\eta$

for $t=1,\dots,T-1$ do

Compute $i_{t}=\operatorname*{arg\,max}_{i\in[p]}L_{S_{i}}(w_{t})+y_{i,t}$
where $y_{i,t}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\text{Lap}(\tau)$.

Sample $B_{t}=\\{z_{1},\dots z_{m}\\}$ from $S_{i_{t}}$ uniformly with
replacement.

Update the model by
$w_{t+1}=\text{Proj}_{\mathcal{W}}\left(w_{t}-\eta\cdot\left(\frac{1}{m}\sum_{z\in
B_{t}}\nabla\ell(w_{t},z)+G_{t}\right)\right).$

where $G_{t}\sim\mathcal{N}(0,\sigma^{2}I_{d})$.

end for

Output $\bar{w}_{T}=\frac{1}{T}\sum_{t=1}^{T}w_{t}$

######  Theorem 13.

(Privacy guarantee) Algorithm 5 is $(\epsilon,\delta)$-DP with
$\tau=\frac{cBp}{K\epsilon}\sqrt{T\log(1/\delta)}$ and
$\sigma^{2}=\frac{cTL^{2}q^{2}\log(K/\delta)\log(1/\delta)}{K^{2}\epsilon^{2}}$
for some universal constant $c$.

.

######  Theorem 14.

(Convergence rate) with probability over $1-\kappa$, by letting
$T=\frac{MLK\epsilon}{16Bp\sqrt{\log(1/\delta)}}$ and
$\eta=\frac{M}{\sqrt{T(G^{2}+d\sigma^{2})}}$, we have

$\displaystyle\mathbb{E}[\max_{i\in[p]}L_{S_{i}}(\bar{w}_{T})]-\min_{w\in\mathcal{W}}\max_{i\in[p]}L_{S_{i}}(w)=$
$\displaystyle
O\left(\left(\sqrt{\frac{MLBp}{K\epsilon}}+\frac{MLp\sqrt{d}}{K\epsilon}\right)\cdot\operatorname{polylog}(p,\delta,\kappa,n)\right).$

###### Proof.

By the union bound, we have with probability over $1-\kappa$

$|y_{i,t}|\leq\frac{8B}{n\epsilon}\sqrt{T\log(1/\delta)}\log(pT/2\kappa)$

for all $i\in[p]$ and $t\in[T]$. We denote this as event $A$ and condition on
$A$. By denoting
$R(\kappa,T)=\frac{8B}{n\epsilon}\sqrt{T\log(1/\delta)}\log(pT/2\kappa)$, we
have

$\displaystyle\mathbb{E}[\max_{i\in[q]}L_{S_{i}}(\bar{w}_{T})]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}\max_{i\in[q]}L_{S_{i}}(w_{t})\right]\quad(\text{convexity
of }\max_{i}L_{S_{i}})$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}L_{S_{i_{t}}}(w_{t})\right]+R(\kappa,T)\quad(\text{Event
A})$

For any fixed $w^{*}$, by the convexity of the loss function, we obtain

$\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}(L_{S_{i_{t}}}(w_{t})-L_{S_{i_{t}}}(w^{*}))\right]\leq\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla
L_{S_{i_{t}}}(w_{t}),w_{t}-w^{*}\rangle\right]$

Denote $\nabla_{t}=\frac{1}{m}\sum_{z\in B_{t}}\nabla\ell(w_{t},z)+G_{t}$
where $B_{t}$ is the mini-batch uniformly sampled from $S_{i_{t}}$ and
$G_{t}\sim\mathcal{N}(0,\sigma^{2}I_{d})$. If we fix the randomness of $w_{t}$
and $i_{t}$, it is easy to see that

$\mathbb{E}[\nabla_{t}]=\nabla L_{S_{i_{t}}}(w_{t})$

where the randomness comes from the datapoint sampling and added Gaussian
noise.

By releasing the randomness of $w_{t}$ and $i_{t}$ and extending the same
analysis to all $t\in[T]$, we obtain

$\displaystyle\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}\left(L_{S_{i_{t}}}(w_{t})-L_{S_{i_{t}}}(w^{*})\right)\right]$
$\displaystyle\leq\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla
L_{S_{i_{t}}}(w_{t}),w_{t}-w^{*}\rangle\right]$
$\displaystyle=\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla_{t},w_{t}-w^{*}\rangle\right]$
$\displaystyle\leq\frac{M^{2}}{2T\eta}+\frac{\eta}{2T}\sum_{t=1}^{T}\mathbb{E}\left[\left\|\nabla_{t}\right\|^{2}\right]$
$\displaystyle\leq\frac{\eta
L^{2}}{2}+\frac{M^{2}}{2T\eta}+\frac{d\sigma^{2}\eta}{2}$

Therefore, we have

$\displaystyle\mathbb{E}[\max_{i\in[q]}L_{S_{i}}(\bar{w}_{T})]$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}L_{S_{i_{t}}}(w_{t})\right]+R(\kappa,T)\quad(\text{Event
A})$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}L_{S_{i_{t}}}(w^{*})\right]+\frac{\eta
L^{2}}{2}+\frac{M^{2}}{2T\eta}+\frac{d\sigma^{2}\eta}{2}+R(\kappa,T)$
$\displaystyle\leq\max_{i\in[q]}L_{S_{i}}(w^{*})+\frac{\eta
L^{2}}{2}+\frac{M^{2}}{2T\eta}+\frac{d\sigma^{2}\eta}{2}+R(\kappa,T)$

By plugging into the value of $\eta$, $\sigma^{2}$ and $T$ and replacing $n$
with $K/p$, we get the desired result. ∎

##  Appendix D Lower Bounds for the Offline Setting

Consider a $L$-Lipschitz convex loss function $\ell(w,z)$ bounded by $[0,B]$
for any $w\in\mathcal{W}$ and $z\in\mathcal{Z}$. We create a new loss function
$\ell^{\prime}(w,(z,y))=\ell(w,z)+y$ where $y\in[0,B]$. It is easy to see that
$\ell^{\prime}(\cdot,(z,y))$ is also convex and $L$-Lipschitz.

#### Empirical case

We let $y=B$ for all datapoints in
$S_{1}=\\{(z_{1},y_{1}),\dots(z_{n},y_{n})\\}$ and $y=0$ for all datapoints in
$S_{i}$ with $i\neq 1$. Therefore, it is easy to see that for any
$w\in\mathcal{W}$ and $i\in[p]$

$L^{\prime}_{S_{1}}(w)\geq L^{\prime}_{S_{i}}(w)$

where $L^{\prime}_{S_{i}}(w)=\frac{1}{n}\sum_{(z,y)\in
S_{i}}\ell^{\prime}(w,(z,y))$.

Then we have

$\min_{w\in\mathcal{W}}\max_{i\in[p]}L^{\prime}_{S_{1}}(w)=\min_{w\in\mathcal{W}}L^{\prime}_{S_{1}}(w)$

Then the original worst-group empirical risk minimization problem is reduced
to single-distribution DP-ERM problem which is known to be lower bounded by
$\Omega\left(\frac{\sqrt{d}}{n\epsilon}\right)$ for Lipschitz convex loss
[BST14]. Therefore, a lower bound of the excess worst-group empirical risk is
also $\Omega\left(\frac{\sqrt{d}}{n\epsilon}\right)$. Since $n=K/p$, this
lower bound can also be written as
$\Omega\left(\frac{p\sqrt{d}}{K\epsilon}\right)$.

#### Population case

We let $y=B$ when $(z,y)\sim D_{1}$ and $y=0$ when $(z,y)\sim D_{i}$ with
$i\neq 1$. The distribution of $z$ is arbitrary. Therefore, we have for any
$w\in\mathcal{W}$ and $i\in[p]$

$L^{\prime}_{D_{1}}(w)\geq L^{\prime}_{D_{i}}(w)$

and

$\min_{w\in\mathcal{W}}\max_{i\in[p]}L^{\prime}_{D_{i}}(w)=\min_{w\in\mathcal{W}}L^{\prime}_{D_{1}}(w)$

Similar to the empirical case, we can reduce the worst-group population risk
minimization problem to single-distribution DP-SCO problem which is lower
bounded by $\Omega\left(\frac{\sqrt{d}}{n\epsilon}+\frac{1}{\sqrt{n}}\right)$
[BFT+19]. Therefore a lower bound of the population excess worst-group risk is
also $\Omega\left(\frac{\sqrt{d}}{n\epsilon}+\frac{1}{\sqrt{n}}\right)$. Since
$n=K/p$, this lower bound can be also written as
$\Omega\left(\frac{p\sqrt{d}}{K\epsilon}+\sqrt{\frac{p}{K}}\right)$.