# Private Domain Adaptation from a Public Source

Raef Bassily The Ohio State University & Google Research NY.
<EMAIL_ADDRESS><EMAIL_ADDRESS>Mehryar Mohri Google Research & Courant
Institute of Mathematical Sciences, NY<EMAIL_ADDRESS>Ananda Theertha
Suresh Google Research, NY<EMAIL_ADDRESS>
###### Abstract

A key problem in a variety of applications is that of domain adaptation from a
public source domain, for which a relatively large amount of labeled data with
no privacy constraints is at one’s disposal, to a private target domain, for
which a private sample is available with very few or no labeled data. In
regression problems with no privacy constraints on the source or target data,
a _discrepancy minimization_ algorithm based on several theoretical guarantees
was shown to outperform a number of other adaptation algorithm baselines.
Building on that approach, we design differentially private discrepancy-based
algorithms for adaptation from a source domain with public labeled data to a
target domain with unlabeled private data. The design and analysis of our
private algorithms critically hinge upon several key properties we prove for a
smooth approximation of the weighted discrepancy, such as its smoothness with
respect to the $\ell_{1}$-norm and the sensitivity of its gradient. Our
solutions are based on private variants of Frank-Wolfe and Mirror-Descent
algorithms. We show that our adaptation algorithms benefit from strong
generalization and privacy guarantees and report the results of experiments
demonstrating their effectiveness.

##  1 Introduction

In a variety of applications in practice, the amount of labeled data available
from the domain of interest is too modest to train an accurate model. Instead,
the learner must resort to using labeled samples from an alternative source
domain, whose distribution is expected to be close to that of the target
domain. Additionally, typically a large amount of _unlabeled data_ from the
target domain is also at one’s disposal.

The problem of generalizing from that distinct source domain to a target
domain for which few or no labeled data is available is a fundamental
challenge in learning theory and algorithmic design known as the _domain
adaptation problem_. We study a privacy-constrained and thus even more
demanding scenario of domain adaptation, motivated by the critical data
restrictions in modern applications: in practice, often the labeled data
available from the source domain is public with no privacy constraints, but
the unlabeled data from the target domain is subject to privacy constraints.

Differential privacy has become the gold standard of privacy-preserving data
analysis as it offers formal and quantitative privacy guarantees and enjoys
many attractive properties from an algorithmic design perspective [DR14].
Despite the remarkable progress in the field of differentially private machine
learning, the problem of differentially private domain adaptation is still not
well-understood. In this work, we present several new differentially private
adaptation algorithms for the scenario described above that we show benefit
from strong generalization guarantees. We also report the results of
experiments demonstrating their effectiveness. Note that there has been a
sequence of publications that provide formal differentially private learning
guarantees assuming access to public data [CH11, BNS13, BTT18, ABM19, NB20,
BCM+20]. However, their results are not applicable to the adaptation problem
we study, since they assume that the source and target domains coincide.

The design of our algorithms and their guarantees benefit from the theoretical
analysis of domain adaptation by a series of prior publications, starting with
the introduction of a _$d_{A}$ -distance_ between distributions by [KBG04] and
[BBCP06]. These authors used this notion to derive learning bounds for the
zero-one loss, (see also the follow-up publications [BCK+08, BDBC+10]) in
terms of a quantity denoted by $\lambda_{{\mathscr{H}}}$ that depends on the
hypothesis set ${\mathscr{H}}$ and the distribution and that cannot be
estimated from observations. Later, [*]MansourMohriRostamizadeh2009 and [CM14]
introduced the notion of _discrepancy_ , which they used to give a general
analysis of single-source adaptation for arbitrary loss functions. The notion
of discrepancy is a divergence measure tailored to domain adaptation that
coincides with the $d_{A}$-distance in the special case of the zero-one loss.
Unlike other divergence measures between distributions such as an
$\ell_{1}$-distance, discrepancy takes into account the loss function and the
hypothesis set and, crucially, can be estimated from finite samples. The
authors presented Rademacher complexity learning bounds in terms of the
discrepancy for arbitrary hypothesis sets and loss functions, as well as
pointwise learning bounds for kernel-based hypothesis sets.

For regression problems with no privacy constraints on the source or target
data, [CM14] gave a _discrepancy minimization algorithm_ based on a
reweighting of the losses of sample points. They further presented a series of
experimental results demonstrating that their algorithm outperformed all other
baselines in a series of tasks. Building on that approach, we design new
differentially private discrepancy-based algorithms for adaptation from a
source domain with public labeled data to a target domain with unlabeled
private data. In Section 3, we briefly present some background material on the
discrepancy analysis of adaptation motivating that approach.

The design and analysis of our private algorithms crucially hinge upon several
key properties we prove for a smooth approximation of the weighted
discrepancy, such as its smoothness with respect to the $\ell_{1}$-norm and
the sensitivity of its gradient (Section 4). In Section 5, we present new two-
stage adaptation algorithms that can be viewed as private counterparts of the
discrepancy minimization algorithm of [CM14]. As with that algorithm, the
first stage consists of finding a reweighting of the source sample that
minimizes the discrepancy, the second stage of minimizing a regularized
weighted empirical loss based on the reweighting found in the first stage.
Since the second stage does not involve private data, only the first stage
requires a private solution. Our solutions are based on private variants of
Frank-Wolfe and Mirror-Descent algorithms, and they are computationally
efficient. We describe these solutions in detail and prove privacy and
generalization guarantees for both algorithms. We further compare the benefits
of these algorithms as a function of the sample sizes.

In Section 6, we present a new, computationally efficient, _single-stage_
differentially private adaptation algorithm seeking to directly minimize the
sum of the weighted empirical loss and the discrepancy. Since attaining the
minimum in this case is generally intractable due to non-convexity of the
objective, instead, our algorithm finds an approximate stationary point of
this objective. Our algorithm is comprised of a sequence of Frank-Wolfe
updates, where each update consists of a differentially private update of the
weights and a non-private update of the predictor. In fact, our algorithm can
be used in much more general settings of private non-convex optimization over
(a Cartesian product of) domains with different geometries. We formally prove
the privacy and convergence guarantees of our algorithm in a general problem
setting, and then derive its generalization guarantees in the context of
adaptation. Finally, in Section 7, we report our experimental results.

We start with the introduction of preliminary concepts and definitions
relevant to our analysis.

##  2 Preliminaries

Let ${\mathscr{X}}\subset\mathbb{R}^{d}$ denote the input space and
${\mathscr{Y}}$ the output space, which we assume to be a measurable subset of
$\mathbb{R}$. We assume that ${\mathscr{X}}$ is included in the $\ell_{2}$
ball of radius $r$, $\operatorname{\mathbb{B}}^{d}(r)$. We will also assume
that ${\mathscr{Y}}$ is included in a bounded interval of diameter $Y>0$. Let
${\mathscr{H}}$ be a family of hypotheses mapping from ${\mathscr{X}}$ to
${\mathscr{Y}}$. We focus on the family of linear hypotheses
${\mathscr{H}}=\left\\{x\mapsto w\cdot x\colon\|w\|\leq\Lambda\right\\}$. We
will be mainly interested in the regression setting, though some of our
results can be extended to other contexts. For any $h\in{\mathscr{H}}$, we
denote by $\ell(h(x),y)=(h(x)-y)^{2}$ the familiar squared loss of $h$ for the
labeled point $(x,y)\in{\mathscr{X}}\times{\mathscr{Y}}$. We denote by $M>0$
an upper bound on the loss: $\ell(h(x),y)\leq M$, for all $(x,y)$.

#### Learning scenario:

We identify a domain with a distribution over
${\mathscr{X}}\times{\mathscr{Y}}$ and refer to the source domain as the one
corresponding to a distribution ${\mathscr{Q}}$ and the target domain, the one
corresponding to a distribution ${\mathscr{P}}$. We assume that the learner
receives a sample $S=\left((x_{1},y_{1}),\ldots,(x_{m},y_{m})\right)$ of $m$
labeled points drawn i.i.d. from a distribution ${\mathscr{Q}}$ over
${\mathscr{X}}\times{\mathscr{Y}}$ and it also has access to a large sample
$T$ of $n$ unlabeled points drawn i.i.d. from ${\mathscr{P}}_{\mathscr{X}}$,
the input marginal distribution associated to ${\mathscr{P}}$. We view the
data from ${\mathscr{Q}}$, that is sample $S$, as _public data_ , and the data
from ${\mathscr{P}}$, sample $T$, as _private data_.

The objective of the learner is to use the samples $S$ and $T$ to select a
hypothesis $h\in{\mathscr{H}}$ with small expected loss with respect to the
target domain:
$\mathcal{L}({\mathscr{P}},h)=\operatorname*{\mathbb{E}}_{(x,y)\sim{\mathscr{P}}}[\ell(h(x),y)]$.
In the absence of any constraints, this coincides with the standard problem of
single-source domain adaptation, studied in a very broad recent literature,
starting with the theoretical studies of [BBCP06, MMR09, CM14].

#### Discrepancy notions:

Clearly, the success of adaptation depends on the closeness of the
distributions ${\mathscr{P}}$ and ${\mathscr{Q}}$, which can be measured
according to various divergences. The notion of _discrepancy_ has been shown
to be appropriate measure of divergence between distributions in the context
of domain adaptation. We will distinguish the so-called _${\mathscr{Y}}$
-discrepancy_ $\mathrm{dis}_{\mathscr{Y}}({\mathscr{P}},{\mathscr{Q}})$, which
can only be estimated when sufficient labeled data is available from both
distributions, and the standard discrepancy
$\mathrm{dis}({\mathscr{P}},{\mathscr{Q}})$, which can be estimated from
finite unlabeled samples from both distributions:

$\displaystyle\mathrm{Dis}_{\mathscr{Y}}({\mathscr{P}},{\mathscr{Q}})$
$\displaystyle=\max_{h\in{\mathscr{H}}}\left\\{\mathcal{L}({\mathscr{P}},h)-\mathcal{L}({\mathscr{Q}},h)\right\\}$
$\displaystyle\mathrm{Dis}({\mathscr{P}},{\mathscr{Q}})$
$\displaystyle=\max_{h,h^{\prime}\in{\mathscr{H}}}\left[\operatorname*{\mathbb{E}}_{x\sim{\mathscr{P}}_{\mathscr{X}}}[\ell(h(x),h^{\prime}(x))]-\operatorname*{\mathbb{E}}_{x\sim{\mathscr{Q}}_{\mathscr{X}}}[\ell(h(x),h^{\prime}(x))]\right].$

We will be using the two-sided versions of these expressions. For example, we
will use

$\mathrm{dis}({\mathscr{P}},{\mathscr{Q}})\triangleq\max\left\\{\mathrm{Dis}({\mathscr{P}},{\mathscr{Q}}),\mathrm{Dis}({\mathscr{Q}},{\mathscr{P}})\right\\}$

though part of our analysis holds with one-sided definitions too.

#### Matrix definitions:

We will adopt the following matrix definitions and notation. We denote by
$\mathbb{M}_{d}$ the set of real-valued $d\times d$ matrices and by
$\mathbb{S}_{d}$ the subset of $\mathbb{M}_{d}$ formed by symmetric matrices.
We will denote by $\langle\cdot,\cdot\rangle$ the Frobenius product defined
for all ${\mathbf{M}},{\mathbf{M}}^{\prime}\in\mathbb{M}_{d}$ by
$\langle{\mathbf{M}},{\mathbf{M}}^{\prime}\rangle=\sum_{i,j=1}^{d}{\mathbf{M}}_{ij}{\mathbf{M}}^{\prime}_{ij}=\operatorname{Tr}({\mathbf{M}}^{\top}{\mathbf{M}}^{\prime})$.
For any matrix ${\mathbf{M}}\in\mathbb{S}_{d}$, we denote by
$\lambda_{i}({\mathbf{M}})$ the $i$th eigenvalue of ${\mathbf{M}}$ in
decreasing order and will also denote by
$\lambda_{\max}({\mathbf{M}})=\lambda_{1}({\mathbf{M}})$ its largest
eigenvalue, and by $\lambda_{\min}({\mathbf{M}})=\lambda_{d}({\mathbf{M}})$
its smallest eigenvalue. We also denote by $\lambda({\mathbf{M}})$ the vector
of eigenvalues of ${\mathbf{M}}$. For any $p\in[1,+\infty]$, we will denote by
$\|{\mathbf{M}}\|_{(p)}$ the $p$-Schatten norm of ${\mathbf{M}}$ defined by
$\|{\mathbf{M}}\|_{(p)}=\|\lambda({\mathbf{M}})\|_{p}=\left[\sum_{i=1}^{d}\lvert\lambda_{i}({\mathbf{M}})\rvert^{p}\right]^{\frac{1}{p}}$.
Note that $p=+\infty$ corresponds to the spectral norm:
$\|{\mathbf{M}}\|_{(\infty)}=\|\lambda({\mathbf{M}})\|_{\infty}$, which we
also denote by $\|{\mathbf{M}}\|_{2}$.

#### Smoothness:

We will say that a continuously differentiable function $f$ defined over a
vector space ${\mathscr{E}}$ is $\gamma$-smooth for norm $\|\cdot\|$ if
$\forall x,x^{\prime}\in{\mathscr{E}},\|\nabla f(x)-\nabla
f(x^{\prime})\|_{*}\leq\gamma\|x-x^{\prime}\|$, where $\|\cdot\|_{*}$ is the
dual norm associated to $\|\cdot\|$. When $f$ is twice differentiable, it is
known that the condition on the Hessian $\forall
x,z\in{\mathscr{E}},\left\lvert
z^{\top}\nabla^{2}f(x)z\right\rvert\leq\gamma\|z\|^{2}$, implies that $f$ is
$\|\cdot\|$-$\gamma$-smooth [Sid19][Chapter 5; lemma 8].

#### Differential Privacy [DMNS06, DKM+06]:

Let $\varepsilon,\delta>0$. A (randomized) algorithm
$\mathcal{A}\colon\mathcal{Z}^{n}\rightarrow\mathcal{R}$ is
$(\varepsilon,\delta)$-differentially private if for all pairs of datasets
$T,T^{\prime}\in\mathcal{Z}$ that differ in exactly one entry, and every
measurable $\mathcal{O}\subseteq\mathcal{R}$, we have:
$\operatorname*{\mathbb{P}}\left(\mathcal{A}(T)\in\mathcal{O}\right)\leq
e^{\varepsilon}\cdot\operatorname*{\mathbb{P}}\left(\mathcal{A}(T^{\prime})\in\mathcal{O}\right)+\delta.$
We consider differentially private algorithms that have access to an auxiliary
public dataset $S$ in addition to their input private dataset $T$. In such
case, we view the public set $S$ as being “hardwired” to the algorithm, and
the constraint of differential privacy is imposed only w.r.t. the private
dataset.

##  3 Background on discrepancy-based generalization bounds

In this section, we briefly present some background material on discrepancy-
based generalization guarantees. A more detailed discussion is presented in
Appendix A. Let the _output label-discrepancy_
$\eta_{\mathscr{H}}(S,\widetilde{T})$ be defined as follows:

$\eta_{\mathscr{H}}(S,\widetilde{T})=\min_{h_{0}\in{\mathscr{H}}}\left\\{\sup_{(x,y)\in
S}|y-h_{0}(x)|+\sup_{(x,y)\in\widetilde{T}}|y-h_{0}(x)|\right\\},$

where $\widetilde{T}$ is the labeled version of $T$ (i.e., $\widetilde{T}$ is
$T$ associated with its true (hidden) labels). Note that
$\mathrm{dis}({\mathscr{P}}_{\mathscr{X}},{\mathsf{q}})$ measures the
difference of the distributions on the input domain. In contrast,
$\eta_{\mathscr{H}}(S,\widetilde{T})$ accounts for the difference of the
output labels in $S$ and $T$. Note that under the covariate-shift and
separability assumption, we have $\eta_{\mathscr{H}}(S,\widetilde{T})=0$. In
general, adaptation is not possible when $\eta_{\mathscr{H}}(S,\widetilde{T})$
is large since the labels received on the training sample would then be very
different from the target ones. Thus, we will assume, as in previous work,
that we have $\eta_{\mathscr{H}}(S,\widetilde{T})\ll 1$. Then, the following
learning bound, expressed in terms of the empirical unlabeled discrepancy
$\mathrm{dis}\left(\widehat{\mathscr{P}}_{\mathscr{X}},{\mathsf{q}}\right)$,
$\eta_{\mathscr{H}}(S,\widetilde{T})$, and the Rademacher complexity of
${\mathscr{H}}$, holds with probability at least $1-\beta$ for all
$h\in{\mathscr{H}}$ and all distributions ${\mathsf{q}}$ over $S$ [CM14,
CMMM19]:

$\mathcal{L}({\mathscr{P}},h)\leq\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h(x_{i}),y_{i})+\mathrm{dis}\left(\widehat{\mathscr{P}}_{\mathscr{X}},{\mathsf{q}}\right)+\eta_{\mathscr{H}}(S,\widetilde{T})+2M\mathcal{R}_{n}({\mathscr{H}})+M\sqrt{\frac{\log\frac{1}{\beta}}{2n}}.$
(1)

The following more explicit upper bound on the Rademacher complexity holds
when ${\mathscr{H}}$ is the class of linear predictors and the support of
${\mathscr{P}}_{\mathscr{X}}$ is included in the $\ell_{2}$-ball of radius
$r$: $\mathcal{R}_{n}({\mathscr{H}})\leq\sqrt{\frac{r^{2}\Lambda^{2}}{n}}$
[MRT18]. [CM14] proposed an adaptation algorithm motivated by these learning
bounds and other pointwise guarantees expressed in terms of discrepancy. Their
algorithm can be viewed as a two-stage method seeking to minimize the first
two terms of this learning bound. It consists of first finding a minimizer
${\mathsf{q}}$ of the weighted discrepancy (second term) and then minimizing
(a regularized) ${\mathsf{q}}$-weighted empirical loss (first term) w.r.t. $h$
for that value of ${\mathsf{q}}$.

We will design private adaptation algorithms for a similar two-stage approach,
as well as a single-stage approach seeking to choose $h$ and ${\mathsf{q}}$ to
directly minimize the first two terms of the bound. The privacy and accuracy
guarantees of our algorithms crucially rely on a careful analysis of a smooth
approximation of the discrepancy term, which we present in the following
section.

##  4 Discrepancy analysis and smooth approximation

###  4.1 Analysis

For the squared loss and ${\mathscr{H}}=\left\\{x\mapsto w\cdot
x\colon\|w\|\leq\Lambda\right\\}$, the weighted discrepancy term of the
learning bound (1) can be expressed in terms of the spectral norm of a matrix
that is an affine function of ${\mathsf{q}}$.

######  Lemma 1 ([MMR09]).

For any distribution ${\mathsf{q}}$ over $S_{\mathscr{X}}$, the following
inequality holds:

$\displaystyle\mathrm{dis}(\widehat{P},{\mathsf{q}})$
$\displaystyle=4\Lambda^{2}\|{\mathbf{M}}({\mathsf{q}})\|_{2}=4\Lambda^{2}\max\big{\\{}\lambda_{\max}\left({\mathbf{M}}({\mathsf{q}})\right),\lambda_{\max}\left(-{\mathbf{M}}({\mathsf{q}})\right)\big{\\}},$

where
${\mathbf{M}}({\mathsf{q}})={\mathbf{M}}_{0}-\sum_{i=1}^{m}q_{i}{\mathbf{M}}_{i}$
and where
${\mathbf{M}}_{0}=\sum_{x\in{\mathscr{X}}}\widehat{\mathscr{P}}_{\mathscr{X}}(x)xx^{\top}$,
and ${\mathbf{M}}_{i}=x_{i}x_{i}^{\top}$, $i\in[m]$.

For completeness, the short proof is given in Appendix B. In view of that, the
learning bound (1) suggests seeking $h\in{\mathscr{H}}$ and
${\mathsf{q}}\in\Delta_{m}$ to minimize the first two terms:

$\displaystyle\mspace{-10.0mu}\min_{\begin{subarray}{c}h\in{\mathscr{H}}\\\
{\mathsf{q}}\in\Delta_{m}\end{subarray}}\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h(x_{i}),y_{i})+4\Lambda^{2}\|{\mathbf{M}}({\mathsf{q}})\|_{2}.$
(2)

Note that the second term of the bound is sub-differentiable but it is not
differentiable both because of the underlying maximum operator and because the
maximum eigenvalue is not differentiable at points where its multiplicity is
more than one. Furthermore, the first term of the objective function is convex
with respect to $h$ and convex with respect to ${\mathsf{q}}$, but it is not
jointly convex.

The private algorithms we design require both the smoothness of objective,
which would not hold given the first issue mentioned, and the sensitivity of
the gradients. Thus, instead, we will use a uniform $\alpha$-smooth
approximation of the second term, for which we analyze in detail the
smoothness and gradient sensitivity.

###  4.2 Softmax smooth approximation

A natural approximation of $\lambda_{\max}({\mathsf{q}})$ is based on the
softmax approximation:

$F({\mathsf{q}})=\frac{1}{\mu}\log\left[\sum_{i=1}^{d}e^{\mu\lambda_{i}({\mathbf{M}}({\mathsf{q}}))}\right].$

Note that while $F$ is a function of the eigenvalues, which are not
differentiable everywhere, it is in fact infinitely differentiable since it
can be expressed in terms of the trace of the exponential matrix or the trace
of powers of ${\mathbf{M}}({\mathsf{q}})$:
$F({\mathsf{q}})=\frac{1}{\mu}\log\Big{[}\operatorname{Tr}\big{[}\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\big{]}\Big{]}$.
The matrix exponential can be computed in $O(d^{3})$, using an SVD of matrix
${\mathbf{M}}({\mathsf{q}})$. The following inequalities follow directly the
properties of the softmax:

$\displaystyle\mspace{-15.0mu}\lambda_{\max}({\mathbf{M}}({\mathsf{q}}))$
$\displaystyle\mspace{-3.0mu}\leq\mspace{-3.0mu}F({\mathsf{q}})\mspace{-3.0mu}\leq\mspace{-3.0mu}\lambda_{\max}({\mathbf{M}}({\mathsf{q}}))\mspace{-3.0mu}+\mspace{-3.0mu}\tfrac{\log(\operatorname{rank}({\mathbf{M}}({\mathsf{q}})))}{\mu}.\mspace{-10.0mu}$
(3)

Note that we have
$\operatorname{rank}({\mathbf{M}}({\mathsf{q}}))\leq\min\left(m+n,d\right)$.
Thus, for $\mu=\frac{\log(m+n)}{\alpha}$, $F({\mathsf{q}})$ gives a uniform
$\alpha$-approximation of $\lambda_{\max}({\mathbf{M}}({\mathsf{q}}))$. Note
that the components of the gradient of $F$ are given by

$\displaystyle\left[\nabla F({\mathsf{q}})\right]_{j}$
$\displaystyle=-\frac{\langle\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right),{\mathbf{M}}_{j}\rangle}{\operatorname{Tr}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)},\qquad
j\in[m]$ (4)

where $\langle\cdot,\cdot\rangle$ denotes the Frobenius inner product. Both
the smoothness and sensitivity of $\nabla F$ will be needed for the derivation
of our algorithm. We now analyze these properties of function $F$, using
function $f$ which is defined for any symmetric matrix
${\mathbf{M}}\in\mathbb{S}_{d}$ as follows:

$\displaystyle
f({\mathbf{M}})=\frac{1}{\mu}\log\left[\sum_{k=0}^{+\infty}\frac{\mu^{k}}{k!}\left\langle{\mathbf{M}}^{k},{\mathbf{I}}\right\rangle\right].$

The following result provides the desired smoothness result needed for $F$,
which we prove by using the $\mu$-smoothness of $f$.

######  Theorem 1.

The softmax approximation $F$ is
$\mu\left(\max_{i\in[m]}\|x_{i}\|_{2}^{4}\right)$-smooth for
$\|\,\cdot\,\|_{1}$.

The proof is given in Appendix C.1. Next, we analyze the _sensitivity of
$\nabla F$_, that is the maximum variation in $\ell_{\infty}$-norm of $\nabla
F({\mathsf{q}})$ when a single point $x$ in the sample of size $n$ drawn from
$\widehat{\mathscr{P}}_{\mathscr{X}}$ is changed to another one $x^{\prime}$.

######  Theorem 2.

The gradient of the softmax approximation $F$ is $\frac{2\mu
r^{2}}{n}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}$-sensitive.

The proof is given in Appendix C.1.

Note that the softmax function $f$ is known to be convex [BV14]. Since
${\mathbf{M}}({\mathsf{q}})$ is an affine function of ${\mathsf{q}}$ and that
composition with affine functions preserves convexity, this shows that $F$ is
also a convex function. The following further shows that $F$ is
$\max_{i\in[m]}\|x_{i}\|^{2}_{2}$-Lipschitz.

######  Theorem 3.

For any ${\mathsf{q}}\in\Delta_{m}$, the gradient of $F$ is bounded as
follows: $\|\nabla
F({\mathsf{q}})\|_{\infty}\leq\max_{i\in[m]}\|x_{i}\|^{2}_{2}$.

The proof is given in Appendix C.1. In view of the expression of the weighted
discrepancy
$\mathrm{dis}(\widehat{\mathscr{P}},{\mathsf{q}})=\max\left\\{\lambda_{\max}({\mathbf{M}}({\mathsf{q}})),\lambda_{\max}(-{\mathbf{M}}({\mathsf{q}}))\right\\}$,
the smooth approximation $F({\mathsf{q}})$ of the maximum eigenvalue of
${\mathbf{M}}({\mathsf{q}})$ leads immediately to a smooth approximation
$\widetilde{F}({\mathsf{q}})=f(\widetilde{\mathbf{M}}({\mathsf{q}}))$ of
$\mathrm{dis}(\widehat{\mathscr{P}},{\mathsf{q}})$, with

$\widetilde{\mathbf{M}}({\mathsf{q}})=\begin{bmatrix}{\mathbf{M}}({\mathsf{q}})&{\mathbf{0}}\\\
{\mathbf{0}}&-{\mathbf{M}}({\mathsf{q}})\end{bmatrix}.$

Thus, $\widetilde{F}$ inherits the key properties of $F$ gathered in the
following corollary.

######  Corollary 1.

The following properties holds for $\widetilde{F}$:

  1. 1.

$\widetilde{F}$ is convex and is a uniform
$\frac{\log(2\min\left\\{m+n,d\right\\})}{\mu}$-approximation of
${\mathsf{q}}\mapsto\mathrm{dis}(\widehat{P},{\mathsf{q}})$.

  2. 2.

$\widetilde{F}$ is $\mu\left(\max_{i\in[m]}\|x_{i}\|_{2}^{4}\right)$-smooth
for $\|\,\cdot\,\|_{1}$.

  3. 3.

$\|\nabla\widetilde{F}\|_{\infty}$ is $\frac{2\mu
r^{2}}{n}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}$-sensitive.

  4. 4.

for any ${\mathsf{q}}\in\Delta_{m}$,
$\|\nabla\widetilde{F}({\mathsf{q}})\|_{\infty}\leq\max_{i\in[m]}\|x_{i}\|^{2}_{2}$.

The proof is given in Appendix C.2. In Appendix C.3, we also present and
analyze a $p$-norm smooth approximation of the discrepancy. This approximation
can be used to design private adaptation algorithms with a relative deviation
guarantee that can be more favorable in some contexts.

##  5 Two-stage private adaptation algorithms

Here, we discuss private solutions for a two-stage approach that consists of
first finding ${\mathsf{q}}$ that minimizes the empirical discrepancy and next
fixing ${\mathsf{q}}$ to that value and minimizing the empirical
${\mathsf{q}}$-weighted loss over $h\in{\mathscr{H}}$. In the absence of
privacy constraints, this coincides with the two-stage algorithm of [CM14].
The first stage consists of seeking ${\mathsf{q}}\in\Delta_{m}$ to minimize an
$\ell_{2}$-regularized version of the discrepancy, the second stage simply
consists of fixing the solution ${\mathsf{q}}$ obtained in the first stage and
seeking $h\in{\mathscr{H}}$ minimizing the ${\mathsf{q}}$-weighted empirical
loss:

$\displaystyle\min_{{\mathsf{q}}\in\Delta_{m}}\|{\mathbf{M}}({\mathsf{q}})\|_{2}+\frac{\lambda}{2}\|{\mathsf{q}}\|_{2}^{2}\qquad\quad\min_{w\in\mathbb{B}_{2}^{d}(\Lambda)}\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(\langle
w,x_{i}\rangle,y_{i}),$ (5)

where $\mathbb{B}_{2}^{d}(\Lambda)$ is the Euclidean ball in $\mathbb{R}$ of
radius $\Lambda$. Equivalently, we can define an $\ell_{2}$-regularized
version of the weighted empirical loss and minimize it over $\mathbb{R}^{d}$;
namely, solve

$\min_{w\in\mathbb{R}^{d}}\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(\langle
w,x_{i}\rangle,y_{i})+\widetilde{\lambda}\|w\|^{2}_{2},$

where $\widetilde{\lambda}>0$ is a hyperparameter. Regularization in the first
stage is done to ensure that the resulting weights ${\mathsf{q}}$ are not too
sparse since sparse solutions can lead to poor output model in the second
stage of the adaptation algorithm.

In the second stage, no private data is involved. Thus, in this section, we
give two private algorithms for the first stage of discrepancy minimization.
Our private algorithms aim at minimizing an $\ell_{2}$-regularized version of
the smooth approximation, $\widetilde{F}$, of the discrepancy discussed in
Section 4.2. To emphasize its dependence on the private unlabeled dataset $T$,
we will use the notation $\widetilde{F}_{T}$. Namely, our algorithms aim at
privately minimizing an $\ell_{2}$-regularized version of $\widetilde{F}_{T}$:

$\widetilde{F}_{T}^{\lambda}\triangleq\widetilde{F}_{T}({\mathsf{q}})+\frac{\lambda}{2}\|{\mathsf{q}}\|_{2}^{2}.$

As mentioned earlier, the regularization term is used to avoid sparse
solutions ${\mathsf{q}}$ that may impact the accuracy of the output model in
the second stage of the adaptation algorithm. Our algorithms are based on
private variants of the Frank-Wolfe algorithm and the Mirror Descent
algorithm. The general structure of these algorithms follow known private
constructions devised in the context of differenitally private empirical risk
minimization [TGTZ15, BGN21, AFKT21]. However, we note that the guarantees of
both algorithms crucially rely on the smoothness and sensitivity properties of
the approximation proved in the previous section. Solving the optimization
with respect to the smooth approximation of the discrepancy enables us to
bound the sensitivity of the gradients (see Theorem 2), which helps us devise
private solutions for this problem.

We defer the description of these algorithms to Appendix D. We state below
their formal guarantees.

######  Theorem 4.

The Noisy Frank-Wolfe algorithm (Algorithm 2 in Appendix D.1) is
$(\varepsilon,\delta)$-differentially private. Let
${\mathsf{q}}^{\ast}\in\operatorname*{argmin}_{{\mathsf{q}}\in\Delta_{m}}\mathrm{dis}(\widehat{P},{\mathsf{q}})$.
There exists a choice of the parameters of Algorithm 2 such that with high
probability over the algorithm’s internal randomness, the output
$\widehat{{\mathsf{q}}}$ satisfies

$\displaystyle\mathrm{dis}(\widehat{P},\widehat{{\mathsf{q}}})\leq$
$\displaystyle\mathrm{dis}(\widehat{P},{\mathsf{q}}^{\ast})+\frac{\lambda}{2}\|{\mathsf{q}}^{\ast}\|_{2}^{2}+\widetilde{O}\left(\frac{1}{(\varepsilon
n)^{1/3}}\right).$

The smoothness we created in $\widetilde{F}_{T}$ also enables us to use a
private variant of the Frank-Wolfe algorithm, whose optimization error scales
only logarithmically with $m$.

######  Theorem 5.

The Noisy Mirror Descent algorithm (Algorithm 3 in Appendix D.2) is
$(\varepsilon,\delta)$-differentially private. Let
${\mathsf{q}}^{\ast}\in\operatorname*{argmin}_{{\mathsf{q}}\in\Delta_{m}}\mathrm{dis}(\widehat{P},{\mathsf{q}})$.
There exists a choice of the parameters of Algorithm 3 such that with high
probability over the algorithm’s randomness, the output
$\widehat{{\mathsf{q}}}$ satisfies

$\displaystyle\mathrm{dis}(\widehat{P},\widehat{{\mathsf{q}}})\leq$
$\displaystyle\mathrm{dis}(\widehat{P},{\mathsf{q}}^{\ast})+\frac{\lambda}{2}\|{\mathsf{q}}^{\ast}\|_{2}^{2}+\widetilde{O}\left(\frac{m^{1/4}}{\sqrt{\varepsilon
n}}\right).$

Note that compared to the guarantees of the private Frank-Wolfe algorithm in
Theorem 4, the optimization error of the Noisy Mirror Descent algorithm
(Theorem 5) exhibits a better dependence on $n$ at the expense of worse
dependence on $m$. In Appendix D, we give full proofs of these theorems.

Note that by standard stability arguments, the minimum weighted empirical loss
of the second stage when training with ${\mathsf{q}}^{\ast}$ is close to the
minimum weighted empirical loss when training with $\widehat{\mathsf{q}}$ when
the discrepancy between $\widehat{\mathsf{q}}$ and ${\mathsf{q}}^{*}$ is small
[MMR09]. Theorems 4 and 5 precisely supply guarantees for that closeness in
discrepancy via the inequality
$\mathrm{dis}(\widehat{\mathsf{q}},{\mathsf{q}}^{\ast})\leq\mathrm{dis}(\widehat{\mathscr{P}},\widehat{\mathsf{q}})-\mathrm{dis}(\widehat{\mathscr{P}},{\mathsf{q}}^{\ast})$,
thereby guaranteeing the closeness of the loss of our private predictor
(output of the second stage) to the minimum ${\mathsf{q}}^{\ast}$-weighted
empirical loss. This together with the learning bound (1) immediately provide
a bound on the expected loss of our private predictor.

##  6 Single-stage private adaptation algorithm

In this section, we give a novel private algorithm for that outputs an
approximate stationary point of the smooth approximation of the learning
bound: $L_{T}({\mathsf{q}},w)\triangleq\sum_{i=1}^{m}{\mathsf{q}}_{i}(\langle
w,x_{i}\rangle-y_{i})^{2}+4\Lambda^{2}\widetilde{F}_{T}({\mathsf{q}}).$ Here,
$\widetilde{F}_{T}({\mathsf{q}}),~{}{\mathsf{q}}\in\Delta_{m},$ is the smooth
approximation of the discrepancy discussed in Section 4.2 (where the subscript
$T$ in $L_{T}$ and $\widetilde{F}_{T}$ is used to emphasize the dependence on
the private dataset $T$).

As discussed earlier, the function $L_{T}$ is generally non-convex in
${\mathsf{q}},w$. Since attaining a global minimizer of $L_{T}$ is generally
intractable, a reasonable alternative is to find (an approximate) stationary
point of $L_{T}$. Note that $L_{T}({\mathsf{q}},w)$ is smooth in
${\mathsf{q}}$ w.r.t. $\|\cdot\|_{1}$ (as discussed in Section 4.2) and smooth
in $w$ w.r.t. $\|\cdot\|_{2}$ (due to the nature of the squared loss). These
smoothness properties allow us to design our private solution. Given the
approximation guarantee (3), the data-dependent terms in the learning bound
(1) can thus be approximated by $L_{T}({\mathsf{q}},w)$. Hence, our strategy
here is to find an approximate stationary point
$(\widehat{{\mathsf{q}}},\widehat{w})$ of $L_{T}$ via our private algorithm,
and then derive a learning bound in terms of
$L_{T}(\widehat{{\mathsf{q}}},\widehat{w})$. The formal definition of an
approximate stationary point is given next.

######  Definition 1 ($\alpha$-approximate stationary point).

Let $f:\mathcal{C}\rightarrow\mathbb{R}$ be a differentiable function over a
convex and compact subset $\mathcal{C}$ of a normed vector space. Let
$\alpha\geq 0$. We say that $u\in\mathcal{C}$ is an $\alpha$-approximate
stationary point of $f$ if the stationarity gap of $f$ at $u$, defined as
$\operatorname{Gap}_{f}(u)\triangleq\max\limits_{v\in\mathcal{C}}\langle-\nabla
f(u),v-u\rangle$ is at most $\alpha$.

First, we will give a generic differentially-private algorithm for
approximating a stationary point of smooth non-convex objectives
$f_{T}:\mathcal{Q}\times\mathcal{W}\rightarrow\mathbb{R}$ (defined by a
private dataset $T$) that satisfy certain smoothness and Lipschitzness
conditions. We give formal definitions of these conditions below.

######  Definition 2
($\left((\gamma_{\mathsf{q}},\|\cdot\|_{p_{1}}),(\gamma_{w},\|\cdot\|_{p_{2}})\right)$-Lipschitz
function).

Consider a function
$f\colon\mathcal{Q}\times\mathcal{W}\rightarrow\mathbb{R}$, where
$\mathcal{Q}$ is a convex set whose $\|\cdot\|_{p_{1}}$-diameter is bounded by
$D_{\mathsf{q}}$ (we refer to $\mathcal{Q}$ as
$(D_{\mathsf{q}},\|\cdot\|_{p_{1}})$-bounded set), and $\mathcal{W}$ is a
convex $(D_{w},\|\cdot\|_{p_{2}})$-bounded set. Let
$\gamma_{\mathsf{q}},\gamma_{w}\geq 0$. We say that $f$ is
$\left(\left(\gamma_{\mathsf{q}},\|\cdot\|_{p_{1}}\right),\left(\gamma_{w},\|\cdot\|_{p_{2}}\right)\right)$-Lipschitz
if for any $w\in\mathcal{W}$, $f(\cdot,w)$ is $\gamma_{\mathsf{q}}$-Lipschitz
w.r.t. $\|\cdot\|_{p_{1}}$ over $\mathcal{Q}$, and for every
${\mathsf{q}}\in\mathcal{Q}$, $f({\mathsf{q}},\cdot)$ is
$\gamma_{w}$-Lipschitz w.r.t. $\|\cdot\|_{p_{2}}$ over $\mathcal{W}$.

######  Definition 3
($\left((\mu_{\mathsf{q}},\|\cdot\|_{p_{1}}),(\mu_{w},\|\cdot\|_{p_{2}})\right)$-smooth
function).

This notion is defined analogously. We say that $f$ is
$\left((\mu_{\mathsf{q}},\|\cdot\|_{p_{1}}),(\mu_{w},\|\cdot\|_{p_{2}})\right)$-Lipschitz
if for any $w\in\mathcal{W}$, $f(\cdot,w)$ is $\mu_{\mathsf{q}}$-smooth w.r.t.
$\|\cdot\|_{p_{1}}$ over $\mathcal{Q}$, and for every
${\mathsf{q}}\in\mathcal{Q}$, $f({\mathsf{q}},\cdot)$ is $\mu_{w}$-Lipschitz
w.r.t. $\|\cdot\|_{p_{2}}$ over $\mathcal{W}$.

Our private algorithm (Algorithm 1 below) takes as input an objective
$f_{T}:\mathcal{Q}\times\mathcal{W}\rightarrow\mathbb{R}$, where $\mathcal{Q}$
is a convex polyhedral set with bounded $\|\cdot\|_{1}$-diameter and
$\mathcal{W}$ is a convex set with bounded $\|\cdot\|_{2}$-diameter. Hence,
our objective $L_{T}$ mentioned earlier is a special case. The algorithm is
comprised of a number rounds, where in each round, two private Frank-Wolfe
update steps are performed; one for ${\mathsf{q}}$ and another for $w$. The
privacy mechanism for each is different due to the different geometries of
$\mathcal{Q}$ and $\mathcal{W}$. We note that in the special case where
$f_{T}=L_{T}$, there is no need to privatize the Frank-Wolfe step for $w$ due
to the fact that such update step depends only on the ${\mathsf{q}}$-weighted
empirical loss over the public data and the fact that differential privacy is
closed under post-processing (the previous update step for ${\mathsf{q}}$ is
carried out in a differentially private manner).

When $f_{T}$ satisfies the Lipschitzness and smoothness properties defined
above w.r.t. $\|\cdot\|_{1}$ and $\|\cdot\|_{2}$, we give formal convergence
guarantees to a stationary point in terms of a high-probability bound on the
_stationarity gap_ of the output (see Definition 1). Despite the different
geometries of $\mathcal{Q}$ and $\mathcal{W}$, our final bound is roughly the
sum of the bounds we would obtain if we ran two separate Frank-Wolfe
algorithms (one over $\mathcal{Q}$ and the other over $\mathcal{W})$. This is
mainly due to the hybrid Lipschitzness and smoothness conditions
($\|\cdot\|_{1}$ for ${\mathsf{q}}$ and $\|\cdot\|_{2}$ for $w$), which enable
us to decompose the bound on the convergence rate over ${\mathsf{q}}$ and $w$.

0: Private dataset: $T=(z_{1},\ldots,z_{n})\in\mathcal{Z}^{n}$, privacy
parameters $(\varepsilon,\delta)$, a convex
$(D_{\mathsf{q}},\|\cdot\|_{1})$-bounded polyhedral set:
$\mathcal{Q}\subset\mathbb{R}^{m}$ with $J$ vertices
$\mathcal{V}=(v_{1},\ldots,v_{J})$, a convex $(D_{w},\|\cdot\|_{2})$-bounded
set $\mathcal{W}\subset\mathbb{R}^{d}$, a function
$f_{T}({\mathsf{q}},w),~{}{\mathsf{q}}\in\mathcal{Q},w\in\mathcal{W}$ (defined
via the dataset $T$), bound on the global $\|\cdot\|_{\infty}$-sensitivity of
$\nabla_{\mathsf{q}}f_{T}({\mathsf{q}},w):~{}\tau_{\mathsf{q}}>0$, bound on
the global $\|\cdot\|_{2}$-sensitivity of
$\nabla_{w}f_{T}({\mathsf{q}},w):~{}\tau_{w}\geq 0$, step size: $\eta$, number
of iterations: $K$.

1: Set
$\sigma_{\mathsf{q}}:=\frac{4\tau_{\mathsf{q}}\sqrt{2K\log(\frac{1}{\delta})}}{\varepsilon}$.

2: Set
$\sigma_{w}:=\frac{4\tau_{w}\sqrt{2K\log(\frac{1}{\delta})}}{\varepsilon}$.

3: Choose arbitrarily
$({\mathsf{q}}^{0},w^{0})\in\mathcal{Q}\times\mathcal{W}$.

4: for $k=0$ to $K-1$ do

5:
$\nabla_{\mathsf{q}}^{k}:=\nabla_{\mathsf{q}}f_{T}({\mathsf{q}}^{k},w^{k})$.

6: Draw $\left(b_{v}^{k}:v\in\mathcal{V}\right)$ independently
$\sim\mathsf{Lap}(\sigma_{\mathsf{q}})$.

7:
$v_{\mathsf{q}}^{k}:=\operatorname*{argmin}\limits_{v\in\mathcal{V}}\Big{\\{}\langle\nabla_{\mathsf{q}}^{k},v\rangle+b_{v}^{k}\Big{\\}}$.

8:
$G_{\mathsf{q}}^{k}:=-\left(\langle\nabla_{\mathsf{q}}^{k},v_{\mathsf{q}}^{k}-{\mathsf{q}}^{k}\rangle+b_{v}^{k}\right)$.

9: ${\mathsf{q}}^{k+1}:=(1-\eta){\mathsf{q}}^{k}+\eta v_{\mathsf{q}}^{k}.$

10: $\nabla_{w}^{k}:=\nabla_{w}f_{T}({\mathsf{q}}^{k},w^{k})$.

11: $\widehat{\nabla}_{w}^{k}:=\nabla_{w}^{k}+{\mathbf{g}}^{k}$, where
${\mathbf{g}}^{k}\sim\mathcal{N}(\mathbf{0},\sigma_{w}^{2}\mathbb{I}_{d})$.

12:
$u_{w}^{k}:=\operatorname*{argmin}\limits_{u\in\mathcal{W}}\langle\widehat{\nabla}_{w}^{k},u\rangle$.

13: $G_{w}^{k}:=-\langle\widehat{\nabla}_{w}^{k},u_{w}^{k}-w^{k}\rangle.$

14: $w^{k+1}:=(1-\eta)w^{k}+\eta u_{w}^{k}.$

15: end for

16: return
$(\widehat{{\mathsf{q}}},\widehat{w})=({\mathsf{q}}^{k^{\ast}},w^{k^{\ast}})$,
where
$k^{\ast}=\operatorname*{argmin}\limits_{k\in[K]}(G_{\mathsf{q}}^{k}+G_{w}^{k}).$

Algorithm 1 Private Frank-Wolfe for approximating stationary points of
$f_{T}:\mathcal{Q}\times\mathcal{W}\rightarrow\mathbb{R}$

######  Theorem 6.

Algorithm 1 is $(\varepsilon,\delta)$-differentially private. Assume that the
objective $f_{T}\colon\mathcal{Q}\times\mathcal{W}\rightarrow\mathbb{R}$ is
$\left((\gamma_{\mathsf{q}},\|\cdot\|_{1}),(\gamma_{w},\|\cdot\|_{2})\right)$-Lipschitz
and
$\left((\mu_{\mathsf{q}},\|\cdot\|_{1}),(\mu_{w},\|\cdot\|_{2})\right)$-smooth.
Assume further that for all ${\mathsf{q}}\in\mathcal{Q},$ and
$w,w^{\prime}\in\mathcal{W}$,
$\|\nabla_{\mathsf{q}}f_{T}({\mathsf{q}},w)-\nabla_{\mathsf{q}}f_{T}({\mathsf{q}},w^{\prime})\|_{\infty}\leq\gamma_{{\mathsf{q}},w}\|w-w^{\prime}\|_{2}$.
Then, for any $\beta\in(0,1)$, there exists a choice of $K$ and $\mu$ such
that with probability at least $1-\beta$ (over the algorithm’s randomness),
the stationarity gap of the output $\widehat{w}$ is upper bounded by

$\displaystyle\operatorname{Gap}_{f_{T}}(\widehat{{\mathsf{q}}},\widehat{w})$
$\displaystyle\leq
5\sqrt{\bar{D}\left(\sigma^{0}_{\mathsf{q}}\log\left(\tfrac{\bar{D}J}{\sigma^{0}_{\mathsf{q}}\beta}\right)+D_{w}\sigma^{0}_{w}\sqrt{d\log\left(\tfrac{\bar{D}}{D_{w}\sigma^{0}_{w}\beta}\right)}\right)}.$

The proof is given in Appendix E. We note that our adaptation objective
$L_{T}({\mathsf{q}},w)$ satisfies all the conditions in Theorem 6. In Appendix
E.1, we give a detailed discussion regarding instantiating Algorithm 1 with
$L_{T}({\mathsf{q}},w)$ and the specific settings of all the parameters in
this special case. As a result, we immediately reach the following corollary.

######  Corollary 2.

Let $L_{T}({\mathsf{q}},w)=\sum_{i=1}^{m}{\mathsf{q}}_{i}(\langle
w,x_{i}\rangle-y_{i})^{2}+4\Lambda^{2}\widetilde{F}_{T}({\mathsf{q}})$ be the
input to Algorithm 1. Let $\beta\in(0,1)$. There exists a choice of $K$ and
$\eta$ fow which, with probability at least $1-\beta$, the output of the
algorithm is an approximate stationary point of $L_{T}$ with stationarity gap
upper bounded as

$\operatorname{Gap}_{L_{T}}(\widehat{{\mathsf{q}}},\widehat{w})\leq\widetilde{O}\left(\frac{\mu^{3/4}}{\sqrt{\varepsilon
n}}\right).$

Hence, bound (1) implies that w.p. $\geq 1-2\beta$ over the choice of the
public and private datasets and the algorithm’s internal randomness, the
expected loss of the predictor $h_{\widehat{w}}$ (defined by the output
$\widehat{w}$) w.r.t. the target domain is bounded as

$\displaystyle\mathcal{L}({\mathscr{P}},h_{\widehat{w}})\leq$ $\displaystyle
L_{T}(\widehat{{\mathsf{q}}},\widehat{w})+\widetilde{O}\left(\frac{1}{\mu}+\frac{1}{\sqrt{n}}\right)+\eta_{\mathscr{H}}(S,\widetilde{T}).$

######  Remark.

Note that $(\widehat{{\mathsf{q}}},\widehat{w})$ is an approximate stationary
point of $L_{T}$. In practice, $(\widehat{{\mathsf{q}}},\widehat{w})$ can be
an approximation of a good local minimum of $L_{T}$ as demonstrated by our
experiments. In such situations, the above bound implies a good prediction
accuracy for the output predictor. Note also that the bound above is given in
terms of the soft-max approximation parameter $\mu$. In general, this
parameter should be treated as a hyper-parameter and tuned appropriately to
minimize the above bound. One reasonable choice of $\mu$ can be obtained by
balancing the bound on the stationarity gap with the error term
$\log(m+n)/\mu$ due to the soft-max approximation. In such case,
$\mu=\widetilde{O}((\varepsilon n)^{2/7})$.

##  7 Experiments

|
---|---
(a) | (b)
Figure 1: (a) Value of the spectral norm $\|{\mathbf{M}}({\mathsf{q}})\|_{2}$
for the output of noisy Frank-Wolfe (solid lines) and noisy Mirror descent
(dotted lines) discrepancy minimization as a function of the number of samples
from the private dataset $n$. (b) Test error as a function of the number of
samples from the private dataset $n$. The solid lines correspond to the
single-stage algorithm, the dotted lines to the two-stage mirror decent
algorithm, and dashed lines to the two-stage Frank Wolfe algorithm.

The objective of this section is to provide proof-of-concept experiments to
demonstrate that reasonable privacy guarantees could be achieved, when using
our private domain adaptation algorithms. We use a setting similar to that of
[CM14, Section 7.1] and demonstrate that the utility of private adaptation
degrades gracefully with increased privacy guarantees and that the single-
stage Frank-Wolfe algorithm performs best in most scenarios.

We carried out experiments with the following synthetic dataset. Let $d=10$
and $\sigma^{2}=1/(9d)$. Let $P_{\mathscr{X}}$ be a spherical Gaussian
centered around $(-1/\sqrt{2d},1/\sqrt{2d},\ldots,-1/\sqrt{2d},1/\sqrt{2d})$
and with variance $\sigma^{2}$ in all directions. Let $Q_{\mathscr{X}}$ be a
Gaussian distribution with mean $(1/\sqrt{2d},\ldots,1/\sqrt{2d})$ and with
variance $\sigma^{2}$ in all directions. We defined the labeling function via
$f(x)=x\cdot\bar{1}$ if $\bar{1}\cdot x>0$,
$\left(\frac{1}{2}x\cdot\bar{1}\right)$ otherwise, where
$\bar{1}=(1/\sqrt{d},\ldots,1/\sqrt{d})$. We chose the target distribution to
be $P_{{\mathscr{X}}}$ and the source distribution as a mixture of
$P_{{\mathscr{X}}}$ and $Q_{{\mathscr{X}}}$ with the weight of
$P_{{\mathscr{X}}}$ set to $25\%$. We fixed the number of source samples to be
$1\mathord{,}000$ and varied the number of unlabeled target samples from
$1\mathord{,}000$ to $8\mathord{,}000$. All experiments were repeated ten
times for statistical consistency. We set $K=1\mathord{,}000$,
$\lambda=0.001$, the privacy parameter $\delta=1/8\mathord{,}000$, and varied
$\epsilon$ in experiments. The standard deviations were calculated over $10$
runs in experiments.

In this setup, we first ran differentially private discrepancy minimization
using Algorithms 2 and 3. We plotted $\|{\mathbf{M}}({\mathsf{q}})\|_{2}$ for
different values of $\epsilon$ in Figure 1(a). The performance of the noisy
Frank-Wolfe algorithm degrades smoothly with $\epsilon$ and improves with $n$.
However the performance of the noisy mirror decent algorithm is much worse.
This is in line with the theoretical guarantees as $m=\Omega(n^{2/3})$ in
these experiments and noisy Frank-Wolfe algorithm has a better convergence
guarantee in this regime. We expect mirror descent to perform better with much
larger values of $n$. Furthermore, observe that the noisy mirror descent has a
high standard deviation compared to Frank-Wolfe algorithm as the noise added
in mirror descent scales polynomially in $m$, whereas it scales only
logarithmically in $m$ for the Frank-Wolfe algorithm.

We next compared our single-stage (Algorithm 1) and the two-stage
differentially private algorithms with the model trained only with the public
dataset (Figure 1(b)). As an oracle baseline, we also plotted the model
trained with the labeled private dataset. Note that this model uses extra
information that is not available during training and is plotted for
illustration purposes only. The single-stage Frank-Wolfe algorithm without
privacy admits the same performance as the model trained on the labeled
private dataset. It performs better than the two-stage Frank-Wolfe algorithm,
however the gap decreases as the privacy guarantee $\epsilon$ improves. The
performance of the mirror descent algorithm without differential privacy is
similar to that of Frank-Wolfe algorithm, however as theory indicates, the
performance degrades quickly with the privacy parameter. Similar to Figure
1(a), the performance of the noisy mirror descent algorithm is much worse and
has a high standard deviation.

##  8 Conclusion

We presented new differentially private adaptation algorithms benefitting from
strong theoretical guarantees. Our analysis can form the basis for the study
of privacy for other related adaptation scenarios, including scenarios where a
small amount of (private) labeled data is also available from the target
domain and those with multiple sources. Our single-stage private algorithm is
further likely to be of independent interest for private optimization of other
similar objective functions.

## Acknowledgements

This work was done while RB was visiting Google, NY. RB’s research at OSU is
supported by NSF Award AF-1908281, NSF Award 2112471, Google Faculty Research
Award, and NSF CAREER Award 2144532.

## References

  * [ABM19] Noga Alon, Raef Bassily, and Shay Moran.  Limits of private learning with access to public data.  NeuRIPS 2019, also available at arXiv:1910.11519 [cs.LG], 2019.
  * [ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016.
  * [AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar.  Private stochastic convex optimization: Optimal rates in L1 geometry.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 393–403. PMLR, 2021.
  * [BBCP06] Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira.  Analysis of representations for domain adaptation.  In Bernhard Schölkopf, John C. Platt, and Thomas Hofmann, editors, Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, pages 137–144. MIT Press, 2006.
  * [BCK+08] John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman.  Learning bounds for domain adaptation.  In Advances in neural information processing systems, pages 129–136, 2008.
  * [BCM+20] Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu.  Private query release assisted by public data.  In International Conference on Machine Learning, pages 695–703. PMLR, 2020.
  * [BDBC+10] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  Machine learning, 79(1-2):151–175, 2010.
  * [BGM21] Raef Bassily, Cristóbal Guzmán, and Michael Menart.  Differentially private stochastic optimization: New results in convex and non-convex settings.  Advances in Neural Information Processing Systems, 34, 2021.
  * [BGN21] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi.  Non-euclidean differentially private stochastic convex optimization.  arXiv preprint arXiv:2103.01278, 2021.
  * [BLST10] Raghav Bhaskar, Srivatsan Laxman, Adam Smith, and Abhradeep Thakurta.  Discovering frequent patterns in sensitive data.  In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 503–512, 2010.
  * [BNS13] Amos Beimel, Kobbi Nissim, and Uri Stemmer.  Private learning and sanitization: Pure vs. approximate differential privacy.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 363–378. Springer, 2013.
  * [BTT18] Raef Bassily, Abhradeep Thakurta, and Om Thakkar.  Model-agnostic private learning.  In Advances in Neural Information Processing Systems 31, pages 7102–7112. Curran Associates, Inc., 2018.
  * [BV14] Stephen P. Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge University Press, 2014.
  * [CH11] Kamalika Chaudhuri and Daniel Hsu.  Sample complexity bounds for differentially private learning.  In Proceedings of the 24th Annual Conference on Learning Theory, pages 155–186, 2011.
  * [CM14] Corinna Cortes and Mehryar Mohri.  Domain adaptation and sample bias correction theory and algorithm for regression.  Theor. Comput. Sci., 519:103–126, 2014.
  * [CMMM19] Corinna Cortes, Mehryar Mohri, and Andrés Muñoz Medina.  Adaptation based on generalized discrepancy.  J. Mach. Learn. Res., 20:1:1–1:30, 2019.
  * [DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486–503. Springer, 2006.
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of cryptography conference, pages 265–284. Springer, 2006\.
  * [DR14] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [JN08] Anatoli Juditsky and Arkadi Nemirovski.  Large deviations of vector-valued martingales in 2-smooth normed spaces.  Rapport de recherche hal-00318071, HAL, 2008.
  * [KBG04] Daniel Kifer, Shai Ben-David, and Johannes Gehrke.  Detecting change in data streams.  In Mario A. Nascimento, M. Tamer Özsu, Donald Kossmann, Renée J. Miller, José A. Blakeley, and K. Bernhard Schiefer, editors, (e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB 2004, Toronto, Canada, August 31 - September 3 2004, pages 180–191. Morgan Kaufmann, 2004.
  * [MMR09] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  In COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
  * [MRT18] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of Machine Learning.  Adaptive computation and machine learning. MIT Press, 2018.  Second edition.
  * [NB20] Anupama Nandi and Raef Bassily.  Privately answering classification queries in the agnostic pac model.  In Algorithmic Learning Theory, pages 687–703, 2020.
  * [Nes07] Yurii Nesterov.  Smoothing technique and its applications in semidefinite optimization.  Math. Program., 110:245–259, 2007.
  * [NJLS09] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro.  Robust stochastic approximation approach to stochastic programming.  SIAM Journal on optimization, 19(4):1574–1609, 2009.
  * [NY83] A.S. Nemirovsky and D.B. Yudin.  Problem Complexity and Method Efficiency in Optimization.  A Wiley-Interscience publication. Wiley, 1983.
  * [Sid19] Aaron Sidford.  Introduction to optimization theory - MS&E213 / CS269O.  Stanford Course Notes, 2019.  https://web.stanford.edu/~sidford/courses/19fa_opt_theory/.
  * [TGTZ15] Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang.  Nearly optimal private lasso.  Advances in Neural Information Processing Systems, 28:3025–3033, 2015.

###### Contents of Appendix

  1. A Background on discrepancy-based generalization bounds
  2. B Discrepancy analysis and bounds
  3. C Smooth approximations
  4. D Private Two-Stage Algorithms for Discrepancy Minimization
  5. E Proof of Theorem 6

##  Appendix A Background on discrepancy-based generalization bounds

In this section, we briefly present some background material on discrepancy-
based generalization guarantees.

The following learning bound was given by [CMMM19]: for any $\beta>0$, with
probably at least $1-\beta$ over the draw of a sample
$S\sim{\mathscr{Q}}^{m}$, for any distribution ${\mathsf{q}}$ over
$S_{\mathscr{X}}$, for all $h\in{\mathscr{H}}$, the following inequality
holds:

$\displaystyle\mathcal{L}({\mathscr{P}},h)$
$\displaystyle\leq\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h(x_{i}),y_{i})+\mathrm{dis}_{\mathscr{Y}}\left(\widehat{\mathscr{P}},{\mathsf{q}}\right)+2\mathcal{R}_{n}(\ell\circ{\mathscr{H}})+M\sqrt{\frac{\log\frac{1}{\beta}}{2n}}.$
(6)

This bound is tight in the sense that for the hypothesis reaching the maximum
in the definition of the ${\mathscr{Y}}$-discrepancy, the bound coincides with
the standard Rademacher complexity bound on $\widehat{\mathscr{P}}$ [CMMM19].
The bound suggests choosing $h\in{\mathscr{H}}$ and the distribution
${\mathsf{q}}$ to minimize the right-hand side. The first term of the bound is
not jointly convex with respect to $h$ and ${\mathsf{q}}$. Instead, the
algorithm suggested by [CM14] (see also [MMR09]) consists of a two-stage
procedure: first choose ${\mathsf{q}}$ to minimize the ${\mathsf{q}}$-weighted
empirical discrepancy, next fix ${\mathsf{q}}$ and choose $h$ to minimize the
${\mathsf{q}}$-weighted empirical loss
$\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h(x_{i}),y_{i})$.

In practice, we do not have labeled data from ${\mathscr{P}}$ or too few to be
able to accurately minimize the ${\mathscr{Y}}$-discrepancy, since otherwise
adaptation would not be even necessary and we could directly use labeled data
from ${\mathscr{P}}$ for training. Instead, we upper bound the
${\mathscr{Y}}$-discrepancy in terms of the discrepancy
$\mathrm{dis}({\mathscr{P}}_{\mathscr{X}},{\mathsf{q}})$ and the _output
label-discrepancy_ $\eta_{\mathscr{H}}(S,\widetilde{T})$ defined as follows:

$\eta_{\mathscr{H}}(S,\widetilde{T})=\min_{h_{0}\in{\mathscr{H}}}\left\\{\sup_{(x,y)\in
S}|y-h_{0}(x)|+\sup_{(x,y)\in\widetilde{T}}|y-h_{0}(x)|\right\\},$

where $\widetilde{T}$ is the labeled version of $T$ (i.e., $\widetilde{T}$ is
$T$ associated with its true (hidden) labels). Note that
$\mathrm{dis}({\mathscr{P}}_{\mathscr{X}},{\mathsf{q}})$ measures the
difference of the distributions on the input domain. In contrast,
$\eta_{\mathscr{H}}(S,\widetilde{T})$ accounts for the difference of the
output labels in $S$ and $T$. We will assume that
$\eta_{\mathscr{H}}(S,\widetilde{T})\ll 1$. Note that under the covariate
shift assumption and separable case, we have
$\eta_{\mathscr{H}}(S,\widetilde{T})=0$. In general, adaptation is not
possible when $\eta_{\mathscr{H}}(S,\widetilde{T})$ can be large since the
labels received on the training sample can be different from the target ones.

We will say that a loss function $\ell$ is _$\gamma$ -admissible_ if
$\left\lvert\ell(h(x),y)-\ell(h^{\prime}(x),y)\right\rvert\leq\gamma\left\lvert
h(x)-h^{\prime}(x)\right\rvert$ for all
$(x,y)\in{\mathscr{X}}\times{\mathscr{Y}}$ and $h\in{\mathscr{H}}$ [CMMM19].
Note that this is a slightly weaker condition than that of
$\gamma$-Lipschitzness of the loss with respect to its first argument.

######  Theorem 7.

Let $\ell$ be a $\gamma$-admissible loss. Then, the following upper bound
holds:

$\mathrm{dis}_{\mathscr{Y}}({\mathscr{P}},{\mathscr{Q}})\leq\mathrm{dis}({\mathscr{P}}_{\mathscr{X}},{\mathsf{q}})+\gamma\,\eta_{\mathscr{H}}(\operatorname{supp}({\mathscr{P}}),\operatorname{supp}({\mathscr{Q}})).$

The proof is given in Appendix B. Note that the squared loss is
$2M$-admissible: since the function $x\mapsto x^{2}$ is 2-Lipschitz on
$[0,1]$, we have
$\left\lvert\ell(h(x),y)-\ell(h^{\prime}(x),y)\right\rvert=M\left\lvert\frac{\ell(h(x),y)}{M}-\frac{\ell(h^{\prime}(x),y)}{M}\right\rvert\leq
2M\left\lvert h(x)-h^{\prime}(x)\right\rvert$. Thus, the learning bound (6)
can be expressed in terms of the discrepancy and the Rademacher complexity of
${\mathscr{H}}$ as follows, using the fact
$\mathcal{R}_{n}(\ell\circ{\mathscr{H}})\leq 2M\mathcal{R}_{n}({\mathscr{H}})$
[MRT18][Prop. 11.2]:

$\displaystyle\mathcal{L}({\mathscr{P}},h)$
$\displaystyle\leq\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h(x_{i}),y_{i})+\mathrm{dis}\left(\widehat{\mathscr{P}}_{\mathscr{X}},{\mathsf{q}}\right)+\eta_{\mathscr{H}}(S,S^{\prime})+2M\mathcal{R}_{n}({\mathscr{H}})+M\sqrt{\frac{\log\frac{1}{\beta}}{2n}}.$

We will be considering a family of linear hypotheses
${\mathscr{H}}=\left\\{x\mapsto w\cdot x\colon\|w\|\leq\Lambda\right\\}$ and
will be assuming that the support of ${\mathscr{P}}_{\mathscr{X}}$ is included
in the $\ell_{2}$ ball of radius $r$. The following more explicit upper bound
on the Rademacher complexity then holds when the support of
${\mathscr{P}}_{\mathscr{X}}$ is included in the $\ell_{2}$-ball of radius
$r$: $\mathcal{R}_{n}({\mathscr{H}})\leq\sqrt{\frac{r^{2}\Lambda^{2}}{n}}$
[MRT18].

##  Appendix B Discrepancy analysis and bounds

See 7

###### Proof.

For any hypothesis $h_{0}$ in ${\mathscr{H}}$, we can write

$\displaystyle\mathrm{dis}_{\mathscr{Y}}(\widehat{\mathscr{P}},{\mathsf{q}})$
$\displaystyle=\sup_{h\in{\mathscr{H}}}\,\left\lvert\operatorname*{\mathbb{E}}_{(x,y)\sim\widehat{\mathscr{P}}}[\ell(h(x),y)]-\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h(x_{i}),y_{i})\right\rvert$
$\displaystyle\leq\sup_{h\in{\mathscr{H}}}\,\left\lvert\operatorname*{\mathbb{E}}_{x\sim\widehat{\mathscr{P}}}[\ell(h(x),h_{0}(x))]-\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h(x_{i}),h_{0}(x_{i}))\right\rvert$
$\displaystyle\quad+\sup_{h\in{\mathscr{H}}}\,\left\lvert\operatorname*{\mathbb{E}}_{(x,y)\sim\widehat{\mathscr{P}}}[\ell(h(x),y)]-\operatorname*{\mathbb{E}}_{x\sim\widehat{\mathscr{P}}}[\ell(h(x),h_{0}(x))]\right\rvert$
$\displaystyle\quad+\sup_{h\in{\mathscr{H}}}\,\left\lvert\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h(x_{i}),h_{0}(x_{i}))-\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h(x_{i}),y_{i})\right\rvert$
$\displaystyle\leq\mathrm{dis}(\widehat{\mathscr{P}}_{\mathscr{X}},{\mathsf{q}})+\gamma\operatorname*{\mathbb{E}}_{(x,y)\sim\widehat{\mathscr{P}}}\left[|y-h_{0}(x)|\right]+\gamma\sum_{i=1}^{m}{\mathsf{q}}_{i}|y_{i}-h_{0}(x_{i})|$
$\displaystyle\leq\mathrm{dis}(\widehat{\mathscr{P}}_{\mathscr{X}},{\mathsf{q}})+\gamma\left\\{\sup_{(x,y)\in\operatorname{supp}(\widehat{\mathscr{P}})}|y-h_{0}(x)|+\sup_{(x,y)\in\operatorname{supp}(\widehat{\mathscr{Q}})}|y-h_{0}(x)|\right\\}$
$\displaystyle=\mathrm{dis}(\widehat{\mathscr{P}}_{\mathscr{X}},{\mathsf{q}})+\gamma\eta_{\mathscr{H}}(\operatorname{supp}({\mathscr{P}}),\operatorname{supp}({\mathscr{Q}})),$

which completes the proof. ∎

See 1

###### Proof.

$\displaystyle\mathrm{dis}(\widehat{P},{\mathsf{q}})$
$\displaystyle=\max_{\|w\|,\|w^{\prime}\|\leq\Lambda}\operatorname*{\mathbb{E}}_{x\sim{\mathsf{q}}}\left\lvert\left[\left[(w-w^{\prime})\cdot
x\right]^{2}\right]-\operatorname*{\mathbb{E}}_{x\sim\widehat{\mathscr{P}}_{X}}\left[\left[(w-w^{\prime})\cdot
x\right]^{2}\right]\right\rvert$
$\displaystyle=\max_{\|w\|,\|w^{\prime}\|\leq\Lambda}\left\lvert\sum_{x\in{\mathscr{X}}}\left[\widehat{P}(x)-{\mathsf{q}}(x)\right]\left[(w-w^{\prime})\cdot
x\right]^{2}\right\rvert$ $\displaystyle=\max_{\|u\|\leq
2\Lambda}\left\lvert\sum_{x\in{\mathscr{X}}}\left[\widehat{P}(x)-{\mathsf{q}}(x)\right]\left[u\cdot
x\right]^{2}\right\rvert$ $\displaystyle=\max_{\|u\|\leq 2\Lambda}\left\lvert
u^{\top}\left[\sum_{x\in{\mathscr{X}}}\left(\widehat{P}(x)-{\mathsf{q}}(x)\right)xx^{\top}\right]u\right\rvert$
$\displaystyle=4\Lambda^{2}\max_{\|u\|\leq 1}\left\lvert
u^{\top}\left[{\mathbf{M}}_{0}-\sum_{i=1}^{m}{\mathsf{q}}_{i}{\mathbf{M}}_{i}\right]u\right\rvert$
$\displaystyle=4\Lambda^{2}\max_{\|u\|\leq 1}\left\lvert
u^{\top}{\mathbf{M}}({\mathsf{q}})u\right\rvert$
$\displaystyle=4\Lambda^{2}\max_{\|u\|=1}\left\lvert
u^{\top}{\mathbf{M}}({\mathsf{q}})u\right\rvert$
$\displaystyle=4\Lambda^{2}\max\big{\\{}\lambda_{\max}\left({\mathbf{M}}({\mathsf{q}})\right),\lambda_{\max}\left(-{\mathbf{M}}({\mathsf{q}})\right)\big{\\}}.$

This completes the proof. ∎

##  Appendix C Smooth approximations

###  C.1 Softmax approximation

######  Proposition 1.

Assume that $f$ is $\gamma$-smooth w.r.t. $\|\,\cdot\,\|_{2}$, then $F$ is
$\gamma\left(\max_{i\in[m]}\|x_{i}\|_{2}^{4}\right)$-smooth w.r.t.
$\|\,\cdot\,\|_{1}$.

###### Proof.

For any ${\mathsf{q}},{\mathsf{q}}^{\prime}\in\Delta(m)$, the following upper
bound on the spectral norm of
${\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})$ holds:

$\displaystyle\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\|_{2}$
$\displaystyle=\left\|\sum_{i=1}^{m}({\mathsf{q}}_{i}-{\mathsf{q}}^{\prime}_{i})x_{i}x_{i}^{\top}\right\|_{2}$
(7)
$\displaystyle\leq\sum_{i=1}^{m}\left\lvert{\mathsf{q}}_{i}-{\mathsf{q}}^{\prime}_{i}\right\rvert\left\|x_{i}x_{i}^{\top}\right\|_{2}$
$\displaystyle\leq\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}\max_{i\in[m]}\left\|x_{i}x_{i}^{\top}\right\|_{2}$
$\displaystyle=\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}.$

We have $F({\mathsf{q}})=f({\mathbf{M}}({\mathsf{q}}))$, thus the gradient of
$F$ can be expressed as follows:

$\nabla F({\mathsf{q}})=-[\langle\nabla
f({\mathbf{M}}({\mathsf{q}})),{\mathbf{M}}_{i}\rangle]_{i\in[m]}.$

Thus, for any ${\mathsf{q}},{\mathsf{q}}^{\prime}\in\Delta(m)$, we have:

$\displaystyle\|\nabla F({\mathsf{q}})-\nabla
F({\mathsf{q}}^{\prime})\|_{\infty}$
$\displaystyle=\max_{i\in[m]}\,\left\lvert\langle\nabla
f({\mathbf{M}}({\mathsf{q}}))-\nabla
f({\mathbf{M}}({\mathsf{q}}^{\prime})),{\mathbf{M}}_{i}\rangle\right\rvert$
$\displaystyle\leq\max_{i\in[m]}\,\left\|\nabla
f({\mathbf{M}}({\mathsf{q}}))-\nabla
f({\mathbf{M}}({\mathsf{q}}^{\prime}))\right\|_{(1)}\left\|{\mathbf{M}}_{i}\right\|_{(\infty)}$
(Hölder’s ineq.)
$\displaystyle\leq\gamma\max_{i\in[m]}\,\left\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{(\infty)}\left\|{\mathbf{M}}_{i}\right\|_{(\infty)}$
($\gamma$-smoothness of $f$)
$\displaystyle=\gamma\max_{i\in[m]}\,\left\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{2}\left\|{\mathbf{M}}_{i}\right\|_{2}$
(definition of $\|\,\cdot\,\|_{(\infty)}$)
$\displaystyle\leq\gamma\max_{i\in[m]}\left\\{\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}\right\\}\left\|x_{i}\right\|^{2}_{2}$
(inequality (7))
$\displaystyle=\gamma\left(\max_{i\in[m]}\left\|x_{i}\right\|^{4}_{2}\right)\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}.$

This completes the proof. ∎

We will use the following bound for the Hessian of $f$.

######  Lemma 2 ([Nes07]).

The following upper bound holds for the Hessian of $f$ for any two symmetric
matrices ${\mathbf{M}},{\mathbf{U}}\in\mathbb{S}_{d}$:

$\left\langle\nabla^{2}\\!f({\mathbf{M}})\,{\mathbf{U}},{\mathbf{U}}\right\rangle\leq\mu\left\|{\mathbf{U}}\right\|^{2}_{2},$

where $\left\|{\mathbf{U}}\right\|_{2}=\|\lambda({\mathbf{U}})\|_{\infty}$
denotes the spectral norm of ${\mathbf{U}}$.

See 1

###### Proof.

In view of Lemma 2, $f$ is $\|\,\cdot\,\|_{2}$-$\mu$-smooth. The result thus
follows by Proposition 1. ∎

See 2

###### Proof.

For ${\mathbf{M}}({\mathsf{q}}))$ and ${\mathbf{M}}^{\prime}({\mathsf{q}}))$
differing only by point $x$ and $x^{\prime}$ in
$\widehat{\mathscr{P}}_{\mathscr{X}}$, we have:

$\displaystyle\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}^{\prime}({\mathsf{q}})\|_{2}$
$\displaystyle=\left\|\frac{1}{n}\left[xx^{\top}-x^{\prime}x^{\prime\top}\right]\right\|_{2}\leq\frac{2r^{2}}{n}.$
(8)

Thus, following the proof of Proposition 1, the sensitivity is bounded by

$\displaystyle\max_{i\in[m]}\,\left\lvert\langle\nabla
f({\mathbf{M}}({\mathsf{q}}))-\nabla
f({\mathbf{M}}^{\prime}({\mathsf{q}})),{\mathbf{M}}_{i}\rangle\right\rvert$
$\displaystyle\leq\max_{i\in[m]}\,\left\|\nabla
f({\mathbf{M}}({\mathsf{q}}))-\nabla
f({\mathbf{M}}^{\prime}({\mathsf{q}}))\right\|_{(1)}\left\|{\mathbf{M}}_{i}\right\|_{(\infty)}$
(Hölder’s ineq.)
$\displaystyle\leq\mu\max_{i\in[m]}\,\left\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{(\infty)}\left\|{\mathbf{M}}_{i}\right\|_{(\infty)}$
($\mu$-smoothness of $f$)
$\displaystyle=\mu\max_{i\in[m]}\,\left\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{2}\left\|{\mathbf{M}}_{i}\right\|_{2}$
(definition of $\|\,\cdot\,\|_{(\infty)}$) $\displaystyle\leq\frac{2\mu
r^{2}}{n}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}.$

This completes the proof. ∎

######  Proposition 2.

The following inequality holds for the spectral norm of the Hessian of $F$:

$\|\nabla^{2}F\|_{2}\leq\mu\left\|\sum_{i=1}^{m}x_{i}x_{i}^{\top}\right\|_{2}\leq\mu\left[\sum_{i=1}^{m}\|x_{i}\|_{2}^{2}\right].$

###### Proof.

The second-partial derivatives of $F({\mathsf{q}})$ can be expressed as
follows:

$\displaystyle\frac{\partial^{2}S}{\partial{\mathsf{q}}_{i}\partial{\mathsf{q}}_{j}}$
$\displaystyle=-\left\langle\frac{\partial}{\partial{\mathsf{q}}_{j}}\nabla
f({\mathbf{M}}({\mathsf{q}})),{\mathbf{M}}_{i}\right\rangle$
$\displaystyle=+\langle\nabla^{2}\\!f({\mathbf{M}}({\mathsf{q}}))\,{\mathbf{M}}_{j},{\mathbf{M}}_{i}\rangle.$

Thus, using the shorthand
$\overline{\mathbf{M}}=\sum_{i=1}^{m}{\mathbf{X}}_{i}{\mathbf{M}}_{i}$, for
any ${\mathbf{X}}\in\mathbb{R}^{m}$, we can write:

$\displaystyle{\mathbf{X}}^{\top}\nabla^{2}F{\mathbf{X}}$
$\displaystyle=\sum_{i,j=1}^{d}{\mathbf{X}}_{i}{\mathbf{X}}_{j}\left\langle\nabla^{2}\\!f({\mathbf{M}}({\mathsf{q}}))\,{\mathbf{M}}_{j},{\mathbf{M}}_{i}\right\rangle$
$\displaystyle=\left\langle\nabla^{2}\\!f({\mathbf{M}}({\mathsf{q}}))\,\bigg{(}\sum_{j=1}^{d}{\mathbf{X}}_{j}{\mathbf{M}}_{j}\bigg{)},\left(\sum_{i=1}^{d}{\mathbf{X}}_{i}{\mathbf{M}}_{i}\right)\right\rangle$
$\displaystyle=\left\langle\nabla^{2}\\!f({\mathbf{M}}({\mathsf{q}}))\,\left(\overline{\mathbf{M}}\right),\left(\overline{\mathbf{M}}\right)\right\rangle$
$\displaystyle\leq\mu\|\overline{\mathbf{M}}\|^{2}_{2}$ (Lemma 2)
$\displaystyle=\mu\left(\left\|\sum_{i=1}^{m}{\mathbf{X}}_{i}x_{i}x_{i}^{\top}\right\|_{2}\right)^{2}$
$\displaystyle=\mu\left(\max_{\|u\|\leq
1}\left\lvert\sum_{i=1}^{m}{\mathbf{X}}_{i}u^{\top}x_{i}x_{i}^{\top}u\right\rvert\right)^{2}$
(def. of spectral norm) $\displaystyle=\mu\left(\max_{\|u\|\leq
1}\left\lvert\sum_{i=1}^{m}{\mathbf{X}}_{i}(u^{\top}x_{i})^{2}\right\rvert\right)^{2}$
$\displaystyle\leq\mu\left(\max_{\|u\|\leq
1}\|{\mathbf{X}}\|\sqrt{\sum_{i=1}^{m}(u^{\top}x_{i})^{2}}\right)^{2}$
(Cauchy-Schwarz ineq.)
$\displaystyle=\mu\left(\|{\mathbf{X}}\|\sqrt{\max_{\|u\|\leq
1}\sum_{i=1}^{m}(u^{\top}x_{i})^{2}}\right)^{2}$
$\displaystyle=\mu\left\|\sum_{i=1}^{m}x_{i}x_{i}^{\top}\right\|_{2}\|{\mathbf{X}}\|^{2}.$

This completes the proof. ∎

See 3

###### Proof.

By inequality (4), for any $i\in[m]$, we have

$\displaystyle\left\lvert\left[\nabla F({\mathsf{q}})\right]_{i}\right\rvert$
$\displaystyle=\left\lvert\frac{\left\langle\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right),{\mathbf{M}}_{i}\right\rangle}{\operatorname{Tr}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)}\right\rvert$
$\displaystyle=\frac{x_{i}^{\top}\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)x_{i}}{\operatorname{Tr}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)}$
$\displaystyle\leq\|x_{i}\|^{2}_{2}\frac{\max_{\|u\|_{2}=1}u^{\top}\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)u}{\operatorname{Tr}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)}$
$\displaystyle=\|x_{i}\|^{2}_{2}\frac{\lambda_{\max}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)}{\operatorname{Tr}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)}\leq\|x_{i}\|^{2}_{2}.$

This completes the proof. ∎

###  C.2 Properties of $\widetilde{F}$

See 1

###### Proof.

The results follow directly the definition of $\widetilde{F}$ and Theorems 1,
2, 3 and the discussion above. In particular, since
$\widetilde{F}({\mathsf{q}})=f(\widetilde{\mathbf{M}}({\mathsf{q}}))$, the
gradient of $\widetilde{F}$ can be expressed as follows in terms of $f$:

$\nabla\widetilde{F}({\mathsf{q}})=-\left\langle\nabla
f(\widetilde{\mathbf{M}}({\mathsf{q}})),\operatorname{\mathrm{diag}}({\mathbf{M}}_{i},-{\mathbf{M}}_{i})\right\rangle.$

Thus, for any $i\in[m]$, we have:

$\displaystyle\left[\nabla\widetilde{F}({\mathsf{q}})\right]_{i}$
$\displaystyle=-\frac{\left\langle\exp\left(\mu\widetilde{\mathbf{M}}({\mathsf{q}})\right),\operatorname{\mathrm{diag}}({\mathbf{M}}_{i},-{\mathbf{M}}_{i})\right\rangle}{\operatorname{Tr}\left(\exp\left(\mu\widetilde{\mathbf{M}}({\mathsf{q}})\right)\right)}.$

In particular, we can write:

$\displaystyle\left\lvert\left[\nabla\widetilde{F}({\mathsf{q}})\right]_{i}\right\rvert$
$\displaystyle=-\frac{x_{i}^{\top}\left[\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)-\exp\left(-\mu{\mathbf{M}}({\mathsf{q}})\right)\right]x_{i}}{\operatorname{Tr}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)+\operatorname{Tr}\left(\exp\left(-\mu{\mathbf{M}}({\mathsf{q}})\right)\right)}$
$\displaystyle\leq\|x_{i}\|^{2}_{2}\max_{\|u\|^{2}_{2}=1}\left\lvert\frac{u^{\top}\left[\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)-\exp\left(-\mu{\mathbf{M}}({\mathsf{q}})\right)\right]u}{\operatorname{Tr}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)+\operatorname{Tr}\left(\exp\left(-\mu{\mathbf{M}}({\mathsf{q}})\right)\right)}\right\rvert$
$\displaystyle\leq\|x_{i}\|^{2}_{2}\frac{\lambda_{\max}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)+\lambda_{\max}\left(\exp\left(-\mu{\mathbf{M}}({\mathsf{q}})\right)\right)}{\operatorname{Tr}\left(\exp\left(\mu{\mathbf{M}}({\mathsf{q}})\right)\right)+\operatorname{Tr}\left(\exp\left(-\mu{\mathbf{M}}({\mathsf{q}})\right)\right)}$
$\displaystyle\leq\|x_{i}\|^{2}_{2}.$

This completes the proof. ∎

In the following, we further give explicit proofs of some of these statements.

######  Proposition 3.

Assume that $f$ is $\gamma$-smooth w.r.t. $\|\,\cdot\,\|_{2}$, then
$\widetilde{F}$ is $\gamma\left(\max_{i\in[m]}\|x_{i}\|_{2}^{4}\right)$-smooth
w.r.t. $\|\,\cdot\,\|_{1}$.

###### Proof.

For any ${\mathsf{q}},{\mathsf{q}}^{\prime}\in\Delta(m)$, the following upper
bound on the spectral norm of
${\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})$ holds:

$\displaystyle\|\widetilde{\mathbf{M}}({\mathsf{q}})-\widetilde{\mathbf{M}}({\mathsf{q}}^{\prime})\|_{2}$
$\displaystyle=\|\operatorname{\mathrm{diag}}({\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime}),-\left[\operatorname{\mathrm{diag}}({\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime}))\right]\|_{2}$
(9)
$\displaystyle=\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\|_{2}$
(10)
$\displaystyle=\left\|\sum_{i=1}^{m}({\mathsf{q}}_{i}-{\mathsf{q}}^{\prime}_{i})x_{i}x_{i}^{\top}\right\|_{2}$
(11)
$\displaystyle\leq\sum_{i=1}^{m}\left\lvert{\mathsf{q}}_{i}-{\mathsf{q}}^{\prime}_{i}\right\rvert\left\|x_{i}x_{i}^{\top}\right\|_{2}$
$\displaystyle\leq\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}\max_{i\in[m]}\left\|x_{i}x_{i}^{\top}\right\|_{2}$
$\displaystyle=\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}.$

We have $F({\mathsf{q}})=f({\mathbf{M}}({\mathsf{q}}))$, thus the gradient of
$F$ can be expressed as follows:

$\nabla F({\mathsf{q}})=-[\langle\nabla
f({\mathbf{M}}({\mathsf{q}})),{\mathbf{M}}_{i}\rangle]_{i\in[m]}.$

Thus, for any ${\mathsf{q}},{\mathsf{q}}^{\prime}\in\Delta(m)$, we have:

$\displaystyle\|\nabla\widetilde{F}({\mathsf{q}})-\nabla\widetilde{F}({\mathsf{q}}^{\prime})\|_{\infty}$
$\displaystyle=\max_{i\in[m]}\,\left\lvert\langle\nabla
f(\widetilde{\mathbf{M}}({\mathsf{q}}))-\nabla
f(\widetilde{\mathbf{M}}({\mathsf{q}}^{\prime})),\operatorname{\mathrm{diag}}({\mathbf{M}}_{i},-{\mathbf{M}}_{i})\rangle\right\rvert$
$\displaystyle\leq\max_{i\in[m]}\,\left\|\nabla
f(\widetilde{\mathbf{M}}({\mathsf{q}}))-\nabla
f(\widetilde{\mathbf{M}}({\mathsf{q}}^{\prime}))\right\|_{(1)}\left\|\operatorname{\mathrm{diag}}({\mathbf{M}}_{i},-{\mathbf{M}}_{i})\right\|_{(\infty)}$
(Hölder’s ineq.)
$\displaystyle\leq\gamma\max_{i\in[m]}\,\left\|\widetilde{\mathbf{M}}({\mathsf{q}})-\widetilde{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{(\infty)}\left\|{\mathbf{M}}_{i}\right\|_{(\infty)}$
($\gamma$-smoothness of $f$)
$\displaystyle=\gamma\max_{i\in[m]}\,\left\|\widetilde{\mathbf{M}}({\mathsf{q}})-\widetilde{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{2}\left\|{\mathbf{M}}_{i}\right\|_{2}$
(definition of $\|\,\cdot\,\|_{(\infty)}$)
$\displaystyle\leq\gamma\max_{i\in[m]}\left\\{\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}\right\\}\left\|x_{i}\right\|^{2}_{2}$
(inequality (9))
$\displaystyle=\gamma\left(\max_{i\in[m]}\left\|x_{i}\right\|^{4}_{2}\right)\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}.$

This completes the proof. ∎

###### Proof.

For ${\mathbf{M}}({\mathsf{q}}))$ and ${\mathbf{M}}^{\prime}({\mathsf{q}}))$
differing only by point $x$ and $x^{\prime}$ in
$\widehat{\mathscr{P}}_{\mathscr{X}}$, we have:

$\displaystyle\|\widetilde{\mathbf{M}}({\mathsf{q}})-\widetilde{\mathbf{M}}^{\prime}({\mathsf{q}})\|_{2}$
$\displaystyle=\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}^{\prime}({\mathsf{q}})\|_{2}$
(12)
$\displaystyle=\left\|\frac{1}{n}\left[xx^{\top}-x^{\prime}x^{\prime\top}\right]\right\|_{2}\leq\frac{2r^{2}}{n}.$
(13)

Thus, following the proof of Proposition 3, the sensitivity is bounded by

$\displaystyle\max_{i\in[m]}\,\left\lvert\langle\nabla
f(\widetilde{\mathbf{M}}({\mathsf{q}}))-\nabla
f(\widetilde{\mathbf{M}}^{\prime}({\mathsf{q}})),\operatorname{\mathrm{diag}}({\mathbf{M}}_{i},-{\mathbf{M}}_{i})\rangle\right\rvert$
$\displaystyle\leq\max_{i\in[m]}\,\left\|\nabla
f(\widetilde{\mathbf{M}}({\mathsf{q}}))-\nabla
f(\widetilde{\mathbf{M}}^{\prime}({\mathsf{q}}))\right\|_{(1)}\left\|\operatorname{\mathrm{diag}}({\mathbf{M}}_{i},-{\mathbf{M}}_{i})\right\|_{(\infty)}$
(Hölder’s ineq.)
$\displaystyle\leq\mu\max_{i\in[m]}\,\left\|\widetilde{\mathbf{M}}({\mathsf{q}})-\widetilde{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{(\infty)}\left\|{\mathbf{M}}_{i}\right\|_{(\infty)}$
($\mu$-smoothness of $f$)
$\displaystyle=\mu\max_{i\in[m]}\,\left\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{2}\left\|{\mathbf{M}}_{i}\right\|_{2}$
(definition of $\|\,\cdot\,\|_{(\infty)}$) $\displaystyle\leq\frac{2\mu
r^{2}}{n}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}.$

This completes the proof. ∎

###  C.3 $p$-norm approximation

A smooth approximation of
$\left\|{\mathbf{M}}({\mathsf{q}})\right\|^{2}_{2}=\left\|\lambda\big{(}{\mathbf{M}}({\mathsf{q}})\big{)}\right\|_{\infty}^{2}$
can be defined as follows:

$G({\mathsf{q}})=\operatorname{Tr}\left[{\mathbf{M}}({\mathsf{q}})^{2p}\right]^{\frac{1}{p}}=\left[\sum_{i=1}^{d}\lambda_{i}({\mathbf{M}}({\mathsf{q}}))^{2p}\right]^{\frac{1}{p}},$

for $p$ sufficiently large. The following inequalities hold for this
approximation:

$\left\|\lambda\big{(}{\mathbf{M}}({\mathsf{q}})\big{)}\right\|_{\infty}^{2}\leq
G({\mathsf{q}})\leq\left[\operatorname{rank}({\mathbf{M}}({\mathsf{q}}))\right]^{\frac{1}{p}}\left\|\lambda\big{(}{\mathbf{M}}({\mathsf{q}})\big{)}\right\|_{\infty}^{2}.$

The gradient of the smooth approximation is given for all $i\in[1,m]$ by:

$\mspace{-3.0mu}[\nabla
G({\mathbf{M}}({\mathsf{q}}))]_{i}=-2\left\langle{\mathbf{M}}^{2p-1}({\mathsf{q}}),{\mathbf{M}}_{i}\right\rangle\operatorname{Tr}[{\mathbf{M}}^{2p}({\mathsf{q}})]^{\frac{1}{p}-1}.\mspace{-12.0mu}$
(14)

We can write $G({\mathsf{q}})=g({\mathbf{M}}({\mathsf{q}}))$ where $g$ is
defined for all ${\mathbf{M}}\in\mathbb{S}_{d}$ by

$g({\mathbf{M}})=\operatorname{Tr}\left[{\mathbf{M}}^{2p}\right]^{\frac{1}{p}}=\left\langle{\mathbf{M}}^{2p},{\mathbf{I}}\right\rangle^{\frac{1}{p}}.$

The following result provides the desired smoothness result needed for $G$,
which we prove by using the smoothness property of $g$.

######  Theorem 8.

The $p$-norm approximation function $G$ is
$(2p-1)\left(\max_{i\in[m]}\|x_{i}\|_{2}^{4}\right)$-smooth for
$\|\,\cdot\,\|_{1}$.

The proof is given in Appendix C.3. Next, we present a sensitivity bounds for
$G$.

######  Theorem 9.

Assume that the support of ${\mathscr{P}}$ is included in the $\ell_{2}$ ball
of radius $r$. Then, the gradient of the $p$-norm approximation $G$ is
$\frac{2(2p-1)r^{2}}{n}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}$-sensitive.

The proof is given in Appendix C.3.

######  Proposition 4.

Assume that $g$ is $\gamma$-smooth with respect to the norm
$\|\,\cdot\,\|_{(2p)}$:

$\forall{\mathbf{M}},{\mathbf{M}}^{\prime}\in\mathbb{S}_{d},\quad\|\nabla
g({\mathbf{M}})-\nabla g({\mathbf{M}}^{\prime})\|_{(r)}\leq\gamma\|\nabla
g({\mathbf{M}})-\nabla g({\mathbf{M}}^{\prime})\|_{(2p)},$

with $\frac{1}{r}+\frac{1}{2p}=1$. Then, $G$ is
$\gamma\left(\max_{i\in[m]}\|x_{i}\|_{2}^{4}\right)$-smooth:

$\forall{\mathsf{q}},{\mathsf{q}}^{\prime}\in\mathbb{R}^{d},\quad\|\nabla
G({\mathsf{q}})-\nabla
G({\mathsf{q}}^{\prime})\|_{\infty}\leq\gamma\left(\max_{i\in[m]}\left\|x_{i}\right\|^{4}_{2}\right)\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\|_{1}.$

###### Proof.

The proof is similar to that of Proposition 1. For any
${\mathsf{q}},{\mathsf{q}}^{\prime}\in\Delta(m)$, the following upper bound on
the norm-$(2p)$ of
${\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})$ holds:

$\displaystyle\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\|_{(2p)}$
$\displaystyle=\left\|\sum_{i=1}^{m}({\mathsf{q}}_{i}-{\mathsf{q}}^{\prime}_{i})x_{i}x_{i}^{\top}\right\|_{(2p)}$
(15)
$\displaystyle\leq\sum_{i=1}^{m}\left\lvert{\mathsf{q}}_{i}-{\mathsf{q}}^{\prime}_{i}\right\rvert\left\|x_{i}x_{i}^{\top}\right\|_{(2p)}$
$\displaystyle\leq\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}\max_{i\in[m]}\left\|x_{i}x_{i}^{\top}\right\|_{(2p)}$
$\displaystyle=\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}.$

We have $G({\mathsf{q}})=g({\mathbf{M}}({\mathsf{q}}))$, thus the gradient of
$G$ can be expressed as follows:

$\nabla G({\mathsf{q}})=-[\langle\nabla
g({\mathbf{M}}({\mathsf{q}})),{\mathbf{M}}_{i}\rangle]_{i\in[m]}.$

Thus, for any ${\mathsf{q}},{\mathsf{q}}^{\prime}\in\Delta(m)$, we have:

$\displaystyle\|\nabla G({\mathbf{M}}({\mathsf{q}}))-\nabla
G({\mathbf{M}}({\mathsf{q}}^{\prime}))\|_{\infty}$
$\displaystyle=\max_{i\in[m]}\,\left\lvert\langle\nabla
g({\mathbf{M}}({\mathsf{q}}))-\nabla
g({\mathbf{M}}({\mathsf{q}}^{\prime})),{\mathbf{M}}_{i}\rangle\right\rvert$
$\displaystyle\leq\max_{i\in[m]}\,\left\|\nabla
g({\mathbf{M}}({\mathsf{q}}))-\nabla
g({\mathbf{M}}({\mathsf{q}}^{\prime}))\right\|_{(r)}\left\|{\mathbf{M}}_{i}\right\|_{(2p)}$
(Hölder’s ineq.)
$\displaystyle\leq\gamma\max_{i\in[m]}\,\left\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{(2p)}\left\|{\mathbf{M}}_{i}\right\|_{(2p)}$
($\gamma$-smoothness of $f$)
$\displaystyle\leq\gamma\max_{i\in[m]}\left\\{\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}\right\\}\left\|x_{i}\right\|^{2}_{2}$
(inequality (15))
$\displaystyle=\gamma\left(\max_{i\in[m]}\left\|x_{i}\right\|^{4}_{2}\right)\left\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\right\|_{1}.$

This completes the proof. ∎

We will use the following bound for the Hessian of $g$.

######  Lemma 3 ([Nes07]).

The following upper bound holds for the Hessian of $f$ for any two symmetric
matrices ${\mathbf{M}},{\mathbf{U}}\in\mathbb{S}_{d}$:

$\left\langle\nabla^{2}\\!g({\mathbf{M}})\,{\mathbf{U}},{\mathbf{U}}\right\rangle\leq(2p-1)\left\|\lambda({\mathbf{U}})\right\|^{2}_{2p},$

where
$\left\|\lambda({\mathbf{U}})\right\|^{2}_{2p}=\left(\operatorname{Tr}\left[{\mathbf{U}}^{2p}\right]\right)^{\frac{1}{p}}$.

See 8

###### Proof.

In view of Lemma 3, $g$ is $\|\,\cdot\,\|_{(2p)}$-$(2p-1)$-smooth. The result
thus follows by Proposition 4. ∎

See 9

###### Proof.

For ${\mathbf{M}}({\mathsf{q}}))$ and ${\mathbf{M}}^{\prime}({\mathsf{q}}))$
differing only by point $x$ and $x^{\prime}$ in
$\widehat{\mathscr{P}}_{\mathscr{X}}$, we have:

$\displaystyle\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}^{\prime}({\mathsf{q}})\|_{2}$
$\displaystyle=\left\|\frac{1}{n}\left[xx^{\top}-x^{\prime}x^{\prime\top}\right]\right\|_{2}\leq\frac{2r^{2}}{n}.$
(16)

Thus, following the proof of Proposition 4, the sensitivity is bounded by

$\displaystyle\max_{i\in[m]}\,\left\lvert\langle\nabla
g({\mathbf{M}}({\mathsf{q}}))-\nabla
g({\mathbf{M}}^{\prime}({\mathsf{q}})),{\mathbf{M}}_{i}\rangle\right\rvert$
$\displaystyle\leq\max_{i\in[m]}\,\left\|\nabla
g({\mathbf{M}}({\mathsf{q}}))-\nabla
g({\mathbf{M}}^{\prime}({\mathsf{q}}))\right\|_{(r)}\left\|{\mathbf{M}}_{i}\right\|_{(2p)}$
(Hölder’s ineq.)
$\displaystyle\leq(2p-1)\max_{i\in[m]}\,\left\|{\mathbf{M}}({\mathsf{q}})-{\mathbf{M}}({\mathsf{q}}^{\prime})\right\|_{(2p)}\left\|{\mathbf{M}}_{i}\right\|_{(2p)}$
($\gamma$-smoothness of $f$)
$\displaystyle\leq\frac{2(2p-1)r^{2}}{n}\max_{i\in[m]}\left\|x_{i}\right\|^{2}_{2}.$
(inequality (16))

This completes the proof. ∎

######  Proposition 5.

The following inequality holds for the spectral norm of the Hessian of $F$:

$\|\nabla^{2}G\|_{2}\leq(2p-1)\left[\sum_{i=1}^{m}\|x_{i}\|_{2}^{2}\right].$

###### Proof.

As in the proof of Proposition 2, we have:

$\displaystyle\frac{\partial^{2}G}{\partial{\mathsf{q}}_{i}\partial{\mathsf{q}}_{j}}$
$\displaystyle=-\left\langle\frac{\partial}{\partial{\mathsf{q}}_{j}}\nabla
f({\mathbf{M}}({\mathsf{q}})),{\mathbf{M}}_{i}\right\rangle$
$\displaystyle=+\langle\nabla^{2}\\!g({\mathbf{M}}({\mathsf{q}}))\,{\mathbf{M}}_{j},{\mathbf{M}}_{i}\rangle.$

Thus, using the shorthand
$\overline{\mathbf{M}}=\sum_{i=1}^{m}{\mathbf{X}}_{i}{\mathbf{M}}_{i}$, for
any ${\mathbf{X}}\in\mathbb{R}^{m}$, we can write:

$\displaystyle{\mathbf{X}}^{\top}\nabla^{2}G{\mathbf{X}}$
$\displaystyle=\sum_{i,j=1}^{d}{\mathbf{X}}_{i}{\mathbf{X}}_{j}\left\langle\nabla^{2}\\!g({\mathbf{M}}({\mathsf{q}}))\,{\mathbf{M}}_{j},{\mathbf{M}}_{i}\right\rangle$
$\displaystyle=\left\langle\nabla^{2}\\!f({\mathbf{M}}({\mathsf{q}}))\,\bigg{(}\sum_{j=1}^{d}{\mathbf{X}}_{j}{\mathbf{M}}_{j}\bigg{)},\left(\sum_{i=1}^{d}{\mathbf{X}}_{i}{\mathbf{M}}_{i}\right)\right\rangle$
$\displaystyle=\left\langle\nabla^{2}\\!f({\mathbf{M}}({\mathsf{q}}))\,\left(\overline{\mathbf{M}}\right),\left(\overline{\mathbf{M}}\right)\right\rangle$
$\displaystyle\leq(2p-1)\|\overline{\mathbf{M}}\|^{2}_{(2p)}$ (Lemma 3)
$\displaystyle=(2p-1)\left(\left\|\sum_{i=1}^{m}{\mathbf{X}}_{i}x_{i}x_{i}^{\top}\right\|_{(2p)}\right)^{2}$
$\displaystyle=(2p-1)\left(\operatorname{Tr}\left(\left[\sum_{i=1}^{m}{\mathbf{X}}_{i}x_{i}x_{i}^{\top}\right]^{2p}\right)\right)^{\frac{1}{p}}$
$\displaystyle\leq(2p-1)\left(\sum_{i=1}^{m}|{\mathbf{X}}_{i}|\left\|x_{i}x_{i}^{\top}\right\|_{(2p)}\right)^{2}$
$\displaystyle\leq(2p-1)\|{\mathbf{X}}\|_{2}^{2}\sum_{i=1}^{m}\left\|x_{i}x_{i}^{\top}\right\|^{2}_{(2p)}$
$\displaystyle=(2p-1)\|{\mathbf{X}}\|_{2}^{2}\sum_{i=1}^{m}\left\|x_{i}\right\|^{2}_{2}.$

This completes the proof.

∎

##  Appendix D Private Two-Stage Algorithms for Discrepancy Minimization

###  D.1 The Noisy Frank-Wolfe Algorithm and its Guarantees

We first start with our noisy Frank-Wolfe algorithm. The algorithm is formally
described in Algorithm 2 below.

0: Private unlabeled dataset
$T=(\widetilde{x}_{1},\ldots,\widetilde{x}_{n})\in\mathcal{X}^{n}$, public
unlabeled dataset $S_{\mathcal{X}}=(x_{1},\ldots,x_{m})\in\mathcal{X}^{m}$,
privacy parameters $(\varepsilon,\delta)$, smooth-approximation parameter
$\mu$, regularization parameter $\lambda$, $\\#$ of iterations $K$.

1: Let $r=\max_{x\in\mathcal{X}}\|x\|_{2}$.

2: Let $\hat{r}=\max_{i\in[m]}\|x_{i}\|_{2}$.

3: Let $\Delta_{m}$ be the $(m-1)$-dimensional probability simplex.

4: Define
$\widetilde{F}_{T}^{\lambda}({\mathsf{q}})\triangleq\widetilde{F}_{T}({\mathsf{q}})+\frac{\lambda}{2}\|{\mathsf{q}}\|_{2}^{2},~{}{\mathsf{q}}\in\Delta_{m}.$

5: Choose an arbitrary point ${\mathsf{q}}_{1}\in\Delta_{m}$.

6: Set $\sigma=\frac{4\mu
r^{2}\hat{r}^{2}\sqrt{2K\log(\frac{1}{\delta})}}{{n\varepsilon}}.$

7: for $k=1$ to $K$ do

8: Compute
$\nabla\widetilde{F}_{T}^{\lambda}({\mathsf{q}}_{k})=\nabla\widetilde{F}_{T}({\mathsf{q}}_{k})+\lambda{\mathsf{q}}_{k},$
where $\nabla\widetilde{F}_{T}({\mathsf{q}}_{k})$ is computed as described in
Section 4.2.

9: Draw $\\{b_{i,k}\\}_{i\in[m]}$ i.i.d. from $\mathsf{Lap}(\sigma).$

10: Find
$j_{k}=\operatorname*{argmin}\limits_{i\in[m]}\\{\langle{\mathbf{e}}_{i},\nabla\widetilde{F}_{T}^{\lambda}({\mathsf{q}}_{k})\rangle+b_{i,k}\\},$
where $\\{{\mathbf{e}}_{i}\\}_{i\in[m]}$ are the standard unit vectors in
$\mathbb{R}^{m}.$

11: Update
${\mathsf{q}}_{k+1}=(1-\eta_{k}){\mathsf{q}}_{k}+\eta_{k}{\mathbf{e}}_{j_{k}}$,
where $\eta_{k}=\frac{3}{k+2}.$

12: end for

13: return $\widehat{{\mathsf{q}}}={\mathsf{q}}_{K}.$

Algorithm 2 Noisy Frank-Wolfe for minimizing (regularized) smoothed
discrepancy

See 4

The above theorem follows as a corollary of the following theorem.

######  Theorem 10.

Algorithm 2 is $(\varepsilon,\delta)$-differentially private. Let
$\beta\in(0,1)$. With probability $1-\beta$ over the algorithm’s randomness
(the Laplace noise), the output $\widehat{{\mathsf{q}}}$ satisfies

$\displaystyle\widetilde{F}_{T}^{\lambda}(\widehat{\mathsf{q}})\leq$
$\displaystyle\min_{{\mathsf{q}}\in\Delta_{m}}\widetilde{F}_{T}^{\lambda}({\mathsf{q}})+\frac{2(\mu\hat{r}^{4}+\lambda)}{K}+\frac{8\mu
r^{2}\hat{r}^{2}\sqrt{2K\log(\frac{1}{\delta})}\log(K)\log(\frac{mK}{\beta})}{\varepsilon
n}.$

The proof relies on the smoothness property of $\widetilde{F}_{T}^{\lambda}$
and the sensitivity bound on $\nabla\widetilde{F}_{T}({\mathsf{q}})$. Using
the approximation guarantee of $\widetilde{F}_{T}$ given in Corollary 1
together with Theorem 10 above, we reach the result of Theorem 4, which can be
more precisely stated as the following corollary.

######  Corollary 3.

Let
${\mathsf{q}}^{\ast}\in\operatorname*{argmin}\limits_{{\mathsf{q}}\in\Delta_{m}}\mathrm{dis}(\widehat{P},{\mathsf{q}})$.
Let $\beta\in(0,1)$. There exists a choice of $K$ and $\mu$ in Algorithm 2 for
which the following holds: assuming w.l.o.g. that $\lambda\leq\mu\hat{r}^{4}$,
w.p. at least $1-\beta$, the output $\widehat{{\mathsf{q}}}$ satisfies

$\displaystyle\mathrm{dis}(\widehat{P},\widehat{{\mathsf{q}}})\leq$
$\displaystyle\mathrm{dis}(\widehat{P},{\mathsf{q}}^{\ast})+\frac{\lambda}{2}\|{\mathsf{q}}^{\ast}\|_{2}^{2}+\widetilde{O}\left(\frac{\Lambda^{4}\hat{r}^{4/3}r^{2/3}}{(\varepsilon
n)^{1/3}}\right),$

where $\Lambda$ is the $\|\cdot\|_{2}$-bound on the predictors in
${\mathscr{H}}$.

Proof of Theorem 10 For the privacy guarantee of Algorithm 2, first note that
the global $\|\cdot\|_{\infty}$-sensitivity of
$\nabla\widetilde{F}_{T}^{\lambda}$ (w.r.t. replacing any data point in the
private dataset) is the same as that of $\nabla\widetilde{F}_{T}$, which is
bounded by $\frac{2\mu r^{2}\hat{r}^{2}}{n}$ as established in Corollary 1
(Part 3). Hence, by the setting of the scale of the Laplace noise and the
privacy guarantee of the Report-Noisy-Max mechanism [DR14, BLST10], it follows
that a single iteration of Algorithm 2 is
$\left(\frac{\varepsilon}{\sqrt{8K\log(\frac{1}{\delta})}},0\right)$-differentially
private. The advanced composition theorem of differential privacy [DR14] thus
implies that the algorithm is $(\varepsilon,\delta)$-differentially private.

We now prove the convergence guarantee. Let
$\tilde{{\mathsf{q}}}\in\operatorname*{argmin}\limits_{{\mathsf{q}}\in\Delta_{m}}S_{\lambda}({\mathsf{q}})$.
First, by Corollary 1 (Part 2), $\widetilde{F}_{T}$ is $\mu\hat{r}^{4}$-smooth
w.r.t. $\|\cdot\|_{1}$. Note also that
$\frac{\lambda}{2}\|{\mathsf{q}}\|_{2}^{2}$ is $\lambda$-smooth over
${\mathsf{q}}\in\Delta_{m}$ w.r.t. $\|\cdot\|_{1}$. This follows from the fact
that for any ${\mathsf{q}},{\mathsf{q}}^{\prime}\in\Delta_{m},$

$\|\nabla\big{(}\frac{\lambda}{2}\|{\mathsf{q}}\|_{2}^{2}\big{)}-\nabla\big{(}\frac{\lambda}{2}\|{\mathsf{q}}^{\prime}\|_{2}^{2}\big{)}\|_{\infty}=\lambda\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\|_{\infty}\leq\lambda\|{\mathsf{q}}-{\mathsf{q}}^{\prime}\|_{1}.$

Hence, we get that the objective $\widetilde{F}_{T}^{\lambda}$ is
$(\mu\hat{r}^{4}+\lambda)$-smooth w.r.t. $\|\cdot\|_{1}$ over $\Delta_{m}$.
Thus, by standard analysis of the Noisy Frank-Wolfe algorithm (see, e.g.,
[TGTZ15, BGM21]), we have

$\displaystyle\widetilde{F}_{T}^{\lambda}(\widehat{{\mathsf{q}}})-\widetilde{F}_{T}^{\lambda}(\tilde{{\mathsf{q}}})$
$\displaystyle\leq\frac{2(\mu\hat{r}^{4}+\lambda)}{K}+\sum_{k=1}^{K}\eta_{k}\alpha_{k},$

where
$\alpha_{k}\triangleq\langle\nabla\widetilde{F}_{T}^{\lambda}({\mathsf{q}}_{k}),{\mathbf{e}}_{j_{k}}\rangle-\min\limits_{i\in[m]}\langle\nabla\widetilde{F}_{T}^{\lambda}({\mathsf{q}}_{k}),{\mathbf{e}}_{i}\rangle$.
By the tail properties of the Laplace distribution together with the union
bound, we get that w.p. $\geq 1-\beta$, for all $k\in[K],$
$\alpha_{k}\leq\sigma\log(Km/\beta)=\frac{4\mu
r^{2}\hat{r}^{2}\sqrt{2K\log(\frac{1}{\delta})}\log(Km/\beta)}{{n\varepsilon}}$.
Hence, given the setting of $\eta_{k}$, w.p. $\geq 1-\beta,$ the above bound
simplifies to

$\displaystyle\widetilde{F}_{T}^{\lambda}(\widehat{{\mathsf{q}}})-\widetilde{F}_{T}^{\lambda}(\tilde{{\mathsf{q}}})$
$\displaystyle\leq\frac{2(\mu\hat{r}^{4}+\lambda)}{K}+\frac{8\mu
r^{2}\hat{r}^{2}\sqrt{2K\log(\frac{1}{\delta})}\log(K)\log(Km/\beta)}{{n\varepsilon}},$

which completes the proof.

Proof of Corollary 3. The result can be obtained with the following choices of
$K$ and $\mu$:

$\displaystyle K$ $\displaystyle=\frac{\hat{r}^{4/3}(\varepsilon
n)^{2/3}}{3r^{4/3}\log^{1/3}(\frac{1}{\delta})\log^{2/3}(n)\log^{2/3}(\frac{mn}{\beta})}\qquad\mu=\sqrt{\frac{K\log(m+n)}{8\hat{r}^{4}}}.$

###  D.2 The Noisy Mirror-Descent Algorithm and its Guarantees

Next, we give an alternative private algorithm for minimizing the regularized
smooth approximation of the discrepancy, $\widetilde{F}_{T}^{\lambda}$. Our
algorithm is described in Algorithm 3 below. Compared to the guarantees of the
private Frank-Wolfe algorithm, the optimization error of this algorithm
exhibits a better dependence on $n$ at the expense of worse dependence on $m$.
In particular, the excess error with respect to the minimum discrepancy scales
as $\widetilde{O}\left(\frac{m^{1/4}}{\sqrt{n}}\right)$ (see Corollary 4).
When $m=\widetilde{O}\left(n^{2/3}\right)$, Algorithm 3 below benefits from
more favorable generalization error guarantees than Algorithm 2.

0: Private unlabeled dataset
$T=(\widetilde{x}_{1},\ldots,\widetilde{x}_{n})\in\mathcal{X}^{n}$, public
unlabeled dataset $S_{\mathcal{X}}=(x_{1},\ldots,x_{m})\in\mathcal{X}^{m}$,
privacy parameters $(\varepsilon,\delta)$, smooth-approximation parameter
$\mu$, number of iterations $K$.

1: Let $r=\max_{x\in\mathcal{X}}\|x\|_{2}$.

2: Let $\hat{r}=\max_{i\in[m]}\|x_{i}\|_{2}$.

3: Let $\Delta_{m}$ be the $(m-1)$-dimensional probability simplex.

4: Let $p=1+\frac{1}{\log(m)}$.

5: Set $\sigma=\frac{4\mu
r^{2}\hat{r}^{2}\sqrt{2Km\log(\frac{1}{\delta})}}{{n\varepsilon}}$

6: Set $\eta=\frac{2}{(\hat{r}^{2}+\lambda)}\sqrt{\frac{\log(m)}{K}}.$

7: Choose an arbitrary point ${\mathsf{q}}_{1}\in\Delta_{m}$.

8: for $k=1$ to $K$ do

9: Compute
$\widehat{\nabla}_{k}=\nabla\widetilde{F}_{T}({\mathsf{q}}_{k})+\lambda{\mathsf{q}}_{k}+Z_{k},$
where $Z_{k}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\mathbb{I}_{m})$.

10: Update
${\mathsf{q}}_{k+1}=\arg\min\limits_{{\mathsf{q}}\in\Delta_{m}}\bigg{\\{}\langle\widehat{\nabla}_{k},{\mathsf{q}}-{\mathsf{q}}_{k}\rangle+\frac{\|{\mathsf{q}}-{\mathsf{q}}_{k}\|_{p}^{2}}{\eta(p-1)}\bigg{\\}}.$

11: end for

12: return $\widehat{{\mathsf{q}}}=\frac{1}{K}\sum_{k=1}^{K}{\mathsf{q}}_{k}$

Algorithm 3 Noisy Mirror-Descent for minimizing $\widetilde{F}_{T}^{\lambda}$

See 5

The above theorem follows as a corollary of the following theorem.

######  Theorem 11.

Algorithm 3 is $(\varepsilon,\delta)$-differentially private. Let
$\beta\in(0,1)$. If we set

$K=\frac{(\hat{r}^{2}+\lambda)^{2}\varepsilon^{2}n^{2}}{128\mu^{2}\hat{r}^{4}r^{4}m\log(\frac{2m}{\beta})\log(\frac{1}{\delta})}.$

then with probability at least $1-\beta$ over the algorithm’s randomness
(Gaussian noise), the output $\widehat{{\mathsf{q}}}$ satisfies

$\displaystyle\widetilde{F}_{T}^{\lambda}(\widehat{\mathsf{q}})$
$\displaystyle\leq\min_{{\mathsf{q}}\in\Delta_{m}}\widetilde{F}_{T}^{\lambda}({\mathsf{q}})+\frac{46(\lambda+\hat{r}^{2})\mu
r^{2}\hat{r}^{2}\log(\frac{2m}{\beta})\sqrt{m\log(\frac{1}{\delta})}}{\varepsilon
n}.$

Using the approximation guarantee of $\widetilde{F}_{T}$ given in Corollary 1
together with Theorem 11 above, we reach the result of Theorem 5, which can be
more precisely stated as the following corollary.

######  Corollary 4.

Let
${\mathsf{q}}^{\ast}\in\arg\min\limits_{{\mathsf{q}}\in\Delta_{m}}\mathrm{dis}(\widehat{P},{\mathsf{q}})$.
Let $\beta\in(0,1)$. In Algorithm 3, set $K$ as in Theorem 11. Then, there
exists a choice of $\mu$ such that the following holds: assuming w.l.o.g. that
$\lambda=O(\hat{r}^{2})$, w.p. at least $1-\beta$, the output
$\widehat{{\mathsf{q}}}$ satisfies

$\displaystyle\mathrm{dis}(\widehat{P},\widehat{{\mathsf{q}}})$
$\displaystyle\leq\mathrm{dis}(\widehat{P},{\mathsf{q}}^{\ast}))+\frac{\lambda}{2}\|{\mathsf{q}}^{\ast}\|_{2}^{2}+\widetilde{O}\left(\frac{\Lambda^{2}r\hat{r}^{2}m^{1/4}}{\sqrt{\varepsilon
n}}\right),$

where $\Lambda$ is the $\|\cdot\|_{2}$-bound on the predictors in
${\mathscr{H}}$.

Proof of Theorem 11 First, we show that Algorithm 3 is
$(\varepsilon,\delta)$-differentially private. Note that for any
${\mathsf{q}}\in\Delta_{m}$ the $\|\cdot\|_{2}$-sensitivity of
$\nabla\widetilde{F}_{T}^{\lambda}$ can be upper bounded as
$\|\nabla\widetilde{F}_{T}^{\lambda}({\mathsf{q}})-\nabla\widetilde{F}_{T^{\prime}}^{\lambda}({\mathsf{q}})\|_{2}=\|\nabla\widetilde{F}_{T}({\mathsf{q}})-\nabla\widetilde{F}_{T^{\prime}}({\mathsf{q}})\|_{2}\leq\sqrt{m}\|\nabla\widetilde{F}_{T}({\mathsf{q}})-\nabla\widetilde{F}_{T^{\prime}}({\mathsf{q}})\|_{\infty}\leq\frac{2\mu
r^{2}\hat{r}^{2}\sqrt{m}}{n}$, where the last inequality follows from the
sensitivity bound in Corollary 1. Thus, given the setting of the Gaussian
noise in the algorithm, the privacy guarantee of the Gaussian mechanism
[DKM+06, DR14] together with the Moments Accountant technique [ACG+16] show
the claimed privacy guarantee.

Next, we prove the convergence guarantee. The analysis here is similar to the
analysis of noisy mirror descent in [BGN21, AFKT21]. First, it is known that
$\Phi({\mathsf{q}})\triangleq\frac{\|{\mathsf{q}}\|^{2}_{p}}{p-1}$, where
$p=1+\frac{1}{\log(m)},$ is $1$-strongly convex w.r.t. $\|\cdot\|_{1}$ (see,
e.g., [NY83]). Moreover,
$D_{\Phi}\triangleq\max\limits_{{\mathsf{q}},{\mathsf{q}}^{\prime}}\lvert\Phi({\mathsf{q}})-\Phi({\mathsf{q}}^{\prime})\rvert\leq
2\log(m)$. Note also that $\widetilde{F}_{T}^{\lambda}$ is
$\gamma\triangleq(\hat{r}^{2}+\lambda)$-Lipschitz w.r.t $\|\cdot\|_{1}$, which
follows from the Lipschitz property of $\widetilde{F}_{T}$ (Corollary 1) and
the fact that $\frac{\lambda}{2}\|{\mathsf{q}}\|_{2}^{2}$ is
$\lambda$-Lipschitz w.r.t. $\|\cdot\|_{1}$ over $\Delta_{m}$. Hence, by
standard analysis of (noisy) mirror descent [NY83, NJLS09], we have (letting
$\tilde{{\mathsf{q}}}=\operatorname*{argmin}\limits_{{\mathsf{q}}\in\Delta_{m}}\widetilde{F}_{T}^{\lambda}({\mathsf{q}})$)

$\displaystyle\widetilde{F}_{T}^{\lambda}(\widehat{{\mathsf{q}}})-\widetilde{F}_{T}^{\lambda}(\tilde{{\mathsf{q}}})\leq$
$\displaystyle\frac{D_{\Phi}}{2\eta
K}+\frac{\eta\gamma^{2}}{2}+\frac{\eta}{2K}\sum_{k=1}^{K}\|Z_{k}\|^{2}_{\infty}$
$\displaystyle\leq$ $\displaystyle\frac{2\log(m)}{\eta
K}+\frac{\eta(\lambda+\hat{r}^{2})^{2}}{2}+\frac{\eta}{2K}\sum_{k=1}^{K}\|Z_{k}\|^{2}_{\infty}$

where $\\{Z_{k}:k\in[K]\\}$ are i.i.d. from
$\mathcal{N}(\mathbf{0},\sigma^{2}\mathbb{I}_{m})$. By a concentration
argument in non-Euclidean norms [JN08, Theorem 2.1], w.p. $\geq 1-\beta$, we
have $\frac{1}{K}\sum_{k=1}^{K}\|Z_{k}\|^{2}_{\infty}\leq
4\sigma^{2}\log(\frac{2m}{\beta})$. Hence, w.p. $\geq 1-\beta$, we have

$\displaystyle\widetilde{F}_{T}^{\lambda}(\widehat{{\mathsf{q}}})-\widetilde{F}_{T}^{\lambda}(\tilde{{\mathsf{q}}})\leq$
$\displaystyle\frac{2\log(m)}{\eta
K}+\frac{\eta(\lambda+\hat{r}^{2})^{2}}{2}+2\eta\sigma^{2}\log(\frac{2m}{\beta})$

Thus, given the setting of $\sigma$ (Step 5 of Algorithm 3), optimizing the
bound above in $\eta$ and $K$ yields
$\eta=\frac{2}{(\hat{r}^{2}+\lambda)}\sqrt{\frac{\log(m)}{K}}$ and
$K=\frac{(\hat{r}^{2}+\lambda)^{2}\varepsilon^{2}n^{2}}{128\mu^{2}\hat{r}^{4}r^{4}m\log(\frac{2m}{\beta})\log(\frac{1}{\delta})}$.
Plugging these values in the above bound yields the claimed bound.

Proof of Corollary 4. The following is the choice of $\mu$ yielding the
statement of the corollary:

$\mu=\frac{\sqrt{\varepsilon
n}\log^{1/4}(m+n)}{4r\hat{r}\sqrt{(\lambda+\hat{r}^{2})\log(\frac{2m}{\beta})}\left[m\log(\frac{1}{\delta})\right]^{1/4}}.$

##  Appendix E Proof of Theorem 6

See 6

The statement holds with the following choice of $K$ and $\mu$:

$\displaystyle K$
$\displaystyle=\frac{\sqrt{2}\bar{D}}{\sigma^{0}_{\mathsf{q}}\log\left(\frac{\bar{D}J}{\sigma^{0}_{\mathsf{q}}\beta}\right)+D_{w}\sigma^{0}_{w}\sqrt{d\log\left(\frac{\bar{D}}{D_{w}\sigma^{0}_{w}\beta}\right)}}\qquad\eta=\sqrt{\frac{2(D_{\mathsf{q}}\gamma_{\mathsf{q}}+D_{w}\gamma_{w})}{(D_{\mathsf{q}}^{2}\mu_{\mathsf{q}}+D_{w}^{2}\mu_{w}+2\gamma_{{\mathsf{q}},w}D_{\mathsf{q}}D_{w})K}},$

where
$\bar{D}=\sqrt{(D_{\mathsf{q}}\gamma_{\mathsf{q}}+D_{w}\gamma_{w})(D_{\mathsf{q}}^{2}\mu_{\mathsf{q}}+D_{w}^{2}\mu_{w}+2\gamma_{{\mathsf{q}},w}D_{\mathsf{q}}D_{w})}$,
$\sigma^{0}_{\mathsf{q}}=\frac{\sigma_{\mathsf{q}}}{\sqrt{K}}$, and
$\sigma^{0}_{w}=\frac{\sigma_{w}}{\sqrt{K}}$ (where
$\sigma_{\mathsf{q}},\sigma_{w}$ are as given in steps 1 and 2).

###### Proof.

The privacy proof follows by combining the guarantees of the Report-Noisy-Min
mechanism (steps 1, 7, and 8) and the Gaussian mechanism (steps 2 and 11)
together with the application of the advanced composition theorem of
differential privacy over the $K$ rounds of the algorithm.

We now prove the convergence (stationarity gap) guarantee. By the smoothness
of $f_{T}$, we have

$\displaystyle f_{T}({\mathsf{q}}^{k+1},w^{k+1})$ $\displaystyle\leq
f_{T}({\mathsf{q}}^{k},w^{k+1})+\langle\nabla_{\mathsf{q}}^{k},{\mathsf{q}}^{k+1}-{\mathsf{q}}^{k}\rangle+\langle\nabla_{\mathsf{q}}f_{T}({\mathsf{q}}^{k},w^{k+1})-\nabla_{\mathsf{q}}f_{T}({\mathsf{q}}^{k},w^{k}),{\mathsf{q}}^{k+1}-{\mathsf{q}}^{k}\rangle+\frac{\mu_{\mathsf{q}}}{2}\|{\mathsf{q}}^{k+1}-{\mathsf{q}}^{k}\|_{1}^{2}$
$\displaystyle\leq
f_{T}({\mathsf{q}}^{k},w^{k+1})+\langle\nabla_{\mathsf{q}}^{k},{\mathsf{q}}^{k+1}-{\mathsf{q}}^{k}\rangle+\gamma_{{\mathsf{q}},w}\|w^{k+1}-w^{k}\|_{2}\|{\mathsf{q}}^{k+1}-{\mathsf{q}}^{k}\|_{1}+\frac{\mu_{\mathsf{q}}}{2}\|{\mathsf{q}}^{k+1}-{\mathsf{q}}^{k}\|_{1}^{2}$
$\displaystyle\leq
f_{T}({\mathsf{q}}^{k},w^{k})+\langle\nabla_{\mathsf{q}}^{k},{\mathsf{q}}^{k+1}-{\mathsf{q}}^{k}\rangle+\langle\nabla_{w}^{k},w^{k+1}-w^{k}\rangle+\gamma_{{\mathsf{q}},w}\|w^{k+1}-w^{k}\|_{2}\|{\mathsf{q}}^{k+1}-{\mathsf{q}}^{k}\|_{1}+\frac{\mu_{\mathsf{q}}}{2}\|{\mathsf{q}}^{k+1}-{\mathsf{q}}^{k}\|_{1}^{2}$
$\displaystyle~{}~{}~{}~{}+\frac{\mu_{w}}{2}\|w^{k+1}-w^{k}\|_{2}^{2}$
$\displaystyle\leq
f_{T}({\mathsf{q}}^{k},w^{k})+\eta\langle\nabla_{\mathsf{q}}^{k},v_{\mathsf{q}}^{k}-{\mathsf{q}}^{k}\rangle+\eta\langle\nabla_{w}^{k},u_{w}^{k}-w^{k}\rangle+\gamma_{{\mathsf{q}},w}\eta^{2}D_{\mathsf{q}}D_{w}+\frac{\eta^{2}\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}}{2}+\frac{\eta^{2}\mu_{w}D^{2}_{w}}{2}$
$\displaystyle\leq
f_{T}({\mathsf{q}}^{k},w^{k})+\eta\langle\nabla_{\mathsf{q}}^{k},v_{\mathsf{q}}^{k}-{\mathsf{q}}^{k}\rangle+\eta\langle\widehat{\nabla}_{w}^{k},u_{w}^{k}-w^{k}\rangle+\eta\langle\nabla_{w}^{k}-\widehat{\nabla}_{w}^{k},u_{w}^{k}-w^{k}\rangle+\gamma_{{\mathsf{q}},w}\eta^{2}D_{\mathsf{q}}D_{w}$
$\displaystyle~{}~{}~{}~{}+\frac{\eta^{2}\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}}{2}+\frac{\eta^{2}\mu_{w}D^{2}_{w}}{2}$

Define
$v_{\ast}^{k}\triangleq\operatorname*{argmin}\limits_{v\in\mathcal{V}}\langle\nabla_{\mathsf{q}}^{k},v\rangle$
and
$\alpha^{k}\triangleq\langle\nabla_{\mathsf{q}}^{k},v_{\mathsf{q}}^{k}-v_{\ast}^{k}\rangle$.
Also, define
$u_{\ast}^{k}\triangleq\operatorname*{argmin}\limits_{u\in\mathcal{W}}\langle\nabla_{w}^{k},u\rangle$.
Hence, noting that
$\langle\widehat{\nabla}_{w}^{k},u_{w}^{k}-w^{k}\rangle\leq\langle\widehat{\nabla}_{w}^{k},u_{\ast}^{k}-w^{k}\rangle$
(which follows from the definition of $u_{w}^{k}$ in Step 12 in Algorithm 1),
the bound on $f_{T}({\mathsf{q}}^{k+1},w^{k+1})$ above can be further upper
bounded as

$\displaystyle
f_{T}({\mathsf{q}}^{k},w^{k})+\eta\langle\nabla_{\mathsf{q}}^{k},v_{\mathsf{q}}^{k}-{\mathsf{q}}^{k}\rangle+\eta\left[\langle\widehat{\nabla}_{w}^{k},u_{\ast}^{k}-w^{k}\rangle+\langle\nabla_{w}^{k}-\widehat{\nabla}_{w}^{k},u_{w}^{k}-w^{k}\rangle\right]+\gamma_{{\mathsf{q}},w}\eta^{2}D_{\mathsf{q}}D_{w}$
$\displaystyle~{}~{}~{}+\frac{\eta^{2}\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}}{2}+\frac{\eta^{2}\mu_{w}D^{2}_{w}}{2}$
$\displaystyle\leq$ $\displaystyle
f_{T}({\mathsf{q}}^{k},w^{k})+\eta\langle\nabla_{\mathsf{q}}^{k},v_{\mathsf{q}}^{k}-{\mathsf{q}}^{k}\rangle+\eta\left[\langle\nabla_{w}^{k},u_{\ast}^{k}-w^{k}\rangle+\langle\widehat{\nabla}_{w}^{k}-\nabla_{w}^{k},u_{\ast}^{k}-w^{k}\rangle+\langle\nabla_{w}^{k}-\widehat{\nabla}_{w}^{k},u_{w}^{k}-w^{k}\rangle\right]$
$\displaystyle+\gamma_{{\mathsf{q}},w}\eta^{2}D_{\mathsf{q}}D_{w}+\frac{\eta^{2}\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}}{2}+\frac{\eta^{2}\mu_{w}D^{2}_{w}}{2}$
$\displaystyle\leq$ $\displaystyle
f_{T}({\mathsf{q}}^{k},w^{k})+\eta\langle\nabla_{\mathsf{q}}^{k},v_{\mathsf{q}}^{k}-{\mathsf{q}}^{k}\rangle++\eta\left[\langle\nabla_{w}^{k},u_{\ast}^{k}-w^{k}\rangle+\langle\widehat{\nabla}_{w}^{k}-\nabla_{w}^{k},u_{\ast}^{k}-u_{w}^{k}\rangle\right]+\gamma_{{\mathsf{q}},w}\eta^{2}D_{\mathsf{q}}D_{w}$
$\displaystyle~{}~{}~{}+\frac{\eta^{2}\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}}{2}+\frac{\eta^{2}\mu_{w}D^{2}_{w}}{2}$
$\displaystyle\leq$ $\displaystyle
f_{T}({\mathsf{q}}^{k},w^{k})+\eta\left[\langle\nabla_{\mathsf{q}}^{k},v_{\ast}^{k}-{\mathsf{q}}^{k}\rangle+\alpha^{k}\right]+\eta\left[\langle\nabla_{w}^{k},u_{\ast}^{k}-w^{k}\rangle+\langle\widehat{\nabla}_{w}^{k}-\nabla_{w}^{k},u_{\ast}^{k}-u_{w}^{k}\rangle\right]+\gamma_{{\mathsf{q}},w}\eta^{2}D_{\mathsf{q}}D_{w}$
$\displaystyle~{}~{}~{}+\frac{\eta^{2}\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}}{2}+\frac{\eta^{2}\mu_{w}D^{2}_{w}}{2}$
$\displaystyle\leq$ $\displaystyle
f_{T}({\mathsf{q}}^{k},w^{k})+\eta\left[\langle\nabla_{\mathsf{q}}^{k},v_{\ast}^{k}-{\mathsf{q}}^{k}\rangle+\langle\nabla_{w}^{k},u_{\ast}^{k}-w^{k}\rangle\right]+\eta\alpha^{k}+\eta
D_{w}\|\widehat{\nabla}_{w}^{k}-\nabla_{w}^{k}\|_{2}+\gamma_{{\mathsf{q}},w}\eta^{2}D_{\mathsf{q}}D_{w}$
$\displaystyle~{}~{}~{}+\frac{\eta^{2}\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}}{2}+\frac{\eta^{2}\mu_{w}D^{2}_{w}}{2}$

Note
$\langle\nabla_{\mathsf{q}}^{k},v_{\ast}^{k}-{\mathsf{q}}^{k}\rangle+\langle\nabla_{w}^{k},u_{\ast}^{k}-w^{k}\rangle=-\operatorname{Gap}_{f_{T}}({\mathsf{q}}^{k},w^{k})$.
Moreover, with standard bounds on then tail of Laplacian and Gaussian random
variables, with probability at least $1-\beta$, for all $k\in[K]$,
$\alpha^{k}\leq\sigma_{\mathsf{q}}\log(2JK/\beta)$ and
$\|\widehat{\nabla}_{w}^{k}-\nabla_{w}^{k}\|_{2}\leq\sigma_{w}\sqrt{d\log(2K/\beta)}$.
We will condition on this event for the rest of the proof. Hence, the bound
becomes:

$\displaystyle
f_{T}({\mathsf{q}}^{k},w^{k})-\eta\operatorname{Gap}_{f_{T}}({\mathsf{q}}^{k},w^{k})+\eta\sigma_{\mathsf{q}}\log\left(\frac{2JK}{\beta}\right)+\eta
D_{w}\sigma_{w}\sqrt{d\log\left(\frac{2K}{\beta}\right)}+\gamma_{{\mathsf{q}},w}\eta^{2}D_{\mathsf{q}}D_{w}$
$\displaystyle~{}+\frac{\eta^{2}\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}}{2}+\frac{\eta^{2}\mu_{w}D^{2}_{w}}{2}$

Rearranging terms, and then averaging over $k\in[K]$, we get

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\operatorname{Gap}_{f_{T}}({\mathsf{q}}^{k},w^{k})$
$\displaystyle\leq\frac{f_{T}({\mathsf{q}}^{0},w^{0})-f_{T}({\mathsf{q}}^{K+1},w^{K+1})}{\eta
K}+\eta\left[\gamma_{{\mathsf{q}},w}D_{\mathsf{q}}D_{w}+\frac{\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}}{2}+\frac{\mu_{w}D^{2}_{w}}{2}\right]$
(17)
$\displaystyle\quad+\sigma_{\mathsf{q}}\log\left(\frac{2JK}{\beta}\right)+D_{w}\sigma_{w}\sqrt{d\log\left(\frac{2K}{\beta}\right)}$
$\displaystyle\leq\frac{D_{\mathsf{q}}\gamma_{\mathsf{q}}+D_{w}\gamma_{w}}{\eta
K}+\eta\left[\gamma_{{\mathsf{q}},w}D_{\mathsf{q}}D_{w}+\frac{\mu_{\mathsf{q}}D^{2}_{\mathsf{q}}+\mu_{w}D^{2}_{w}}{2}\right]$
(18)
$\displaystyle\quad+\sqrt{K}\left[\sigma^{0}_{\mathsf{q}}\log\left(\frac{2JK}{\beta}\right)+D_{w}\sigma^{0}_{w}\sqrt{d\log\left(\frac{2K}{\beta}\right)}\right].$
(19)

Optimizing this bound in $\eta$ and $K$ results in the settings of $K$ and
$\eta$ in the theorem statement. Substituting with these settings and
simplifying, we get that the average gap is upper bounded by $\mathsf{A}/2$,
where $\mathsf{A}$ is the bound in the theorem; namely,
$\mathsf{A}=5\sqrt{\bar{D}\left(\sigma^{0}_{\mathsf{q}}\log\left(\tfrac{\bar{D}J}{\sigma^{0}_{\mathsf{q}}\beta}\right)+D_{w}\sigma^{0}_{w}\sqrt{d\log\left(\tfrac{\bar{D}}{D_{w}\sigma^{0}_{w}\beta}\right)}\right)}.$

Now, to conclude the proof, we show that
$\operatorname{Gap}_{f_{T}}(\widehat{{\mathsf{q}}},\widehat{w})\leq\frac{1}{K}\sum_{k=1}^{K}\operatorname{Gap}_{f_{T}}({\mathsf{q}}^{k},w^{k})+\mathsf{A}/2$.
By the definition of $\widehat{{\mathsf{q}}},\widehat{w}$ and using a similar
analysis as above (and using the tail bounds on the Gaussian and Laplace r.v.s
as before), observe that
$\operatorname{Gap}_{f_{T}}(\widehat{{\mathsf{q}}},\widehat{w})$ can be upper
bounded as

$\displaystyle\operatorname{Gap}_{f_{T}}(\widehat{{\mathsf{q}}},\widehat{w})$
$\displaystyle=\operatorname{Gap}_{f_{T}}({\mathsf{q}}^{k^{\ast}},w^{k^{\ast}})$
$\displaystyle\leq\min\limits_{k\in[K]}\operatorname{Gap}_{f_{T}}({\mathsf{q}}^{k},w^{k})+\sigma_{\mathsf{q}}\log\left(\frac{2JK}{\beta}\right)+D_{w}\sigma_{w}\sqrt{d\log\left(\frac{2K}{\beta}\right)}$
$\displaystyle\leq\frac{1}{K}\sum_{k=1}^{K}\operatorname{Gap}_{f_{T}}({\mathsf{q}}^{k},w^{k})+\sqrt{K}\left[\sigma^{0}_{\mathsf{q}}\log\left(\frac{2JK}{\beta}\right)+D_{w}\sigma^{0}_{w}\sqrt{d\log\left(\frac{2K}{\beta}\right)}\right].$

Observe that the term
$\sqrt{K}\left[\sigma^{0}_{\mathsf{q}}\log(\frac{2JK}{\beta})+D_{w}\sigma^{0}_{w}\sqrt{d\log(\frac{2K}{\beta})}\right]$
above is the last term in (19). Hence, by substituting with the values of $K$
and $\eta$, we can show that this term is upper bounded by $\mathsf{A}/2$.
This leads to the following:

$\displaystyle\operatorname{Gap}_{f_{T}}(\widehat{{\mathsf{q}}},\widehat{w})$
$\displaystyle\leq\frac{1}{K}\sum_{k=1}^{K}\operatorname{Gap}_{f_{T}}({\mathsf{q}}^{k},w^{k})+\mathsf{A}/2,$

which completes the proof. ∎

Proof of Corollary 2.

See 2

More precisely, the stationarity gap is bounded as

$\operatorname{Gap}_{L_{T}}(\widehat{{\mathsf{q}}},\widehat{w})\leq\frac{32(1+2\mu\hat{r}^{2})^{\frac{1}{4}}(\Lambda\hat{r})^{\frac{3}{2}}r\sqrt{(\Lambda\hat{r}+Y)\mu\log(\frac{mn}{\beta})}\log^{\frac{1}{4}}(1/\delta)}{\sqrt{\varepsilon
n}}.$

This is done by choosing $K$ and $\eta$ as follows:

$\displaystyle K=\frac{\varepsilon
n(\Lambda\hat{r}+Y)\sqrt{1+2\mu\hat{r}^{2}}}{4\Lambda\hat{r}r^{2}\mu\log\left(\frac{mn}{\beta}\right)\sqrt{\log(\frac{1}{\delta})}}\qquad\eta=\frac{\sqrt{2}(\Lambda\hat{r}+Y)}{\Lambda\hat{r}\sqrt{(1+2\mu\hat{r}^{2})K}}.$

Hence, bound (1) implies that w.p. $\geq 1-2\beta$ over the choice of the
public and private datasets and the algorithm’s internal randomness, the
expected loss of the predictor $h_{\widehat{w}}$ (defined by the output
$\widehat{w}$) w.r.t. the target domain is bounded as

$\displaystyle\mathcal{L}({\mathscr{P}},h_{\widehat{w}})\leq$ $\displaystyle
L_{T}(\widehat{{\mathsf{q}}},\widehat{w})+\frac{2\log(m+n)}{\mu}+\frac{2\Lambda
r(\Lambda r+Y)^{2}}{\sqrt{n}}+(\Lambda
r+Y)^{2}\sqrt{\frac{\log\frac{1}{\beta}}{2n}}+\eta_{\mathscr{H}}(S,\widetilde{T}).$

###  E.1 Instantiating Algorithm 1 with $L_{T}({\mathsf{q}},w)$

We now show that the smooth approximation of our adaptation objective function
$L_{T}({\mathsf{q}},w)=\sum_{i=1}^{m}{\mathsf{q}}_{i}\ell(h_{w}(x_{i}),y_{i})+4\Lambda^{2}\widetilde{F}_{T}({\mathsf{q}})$
(where $\ell(h_{w}(x_{i}),y_{i})=(\langle w,x_{i}\rangle-y_{i})^{2}$ is the
squared loss) is an instance of the family of functions $f_{T}$ in Theorem 6.

Recall that we assume that $\mathcal{W}\subseteq\mathbb{B}_{2}^{d}(\Lambda)$
(the $\|\cdot\|_{2}$ ball of radius $\Lambda$ in $\mathbb{R}^{d}$),
$\mathcal{X}\subset\mathbb{B}_{2}^{d}(r)$, and $\mathcal{Y}\subseteq[-Y,Y]$
for some $Y>0$. Also, recall that we denote the maximum norm of the feature
vectors in the public dataset, $\max\limits_{i\in[m]}\|x_{i}\|_{2}$, by
$\hat{r}$.

First, note that $\mathcal{Q}$ in Algorithm 1 is instantiated with the simplex
$\Delta_{m}$ and hence, $\mathcal{V}$ is
$\\{{\mathbf{e}}_{1},\ldots,{\mathbf{e}}_{m}\\}$.

Second, since the private dataset $T$ only appears in $\widetilde{F}_{T}$,
note that $\nabla_{w}L_{T}({\mathsf{q}},w)$ does not involve $T$. Thus,
$\sigma_{w}$ in Algorithm 1 can be set to zero. That is, we do not need to
privatize the Frank-Wolfe steps over $w$.

Third, note that the global $\|\cdot\|_{\infty}$-sensitivity of
$\nabla_{\mathsf{q}}L_{T}({\mathsf{q}},w),\tau_{\mathsf{q}}$, is the same as
that of $4\Lambda^{2}\nabla_{\mathsf{q}}\widetilde{F}$, which follows from
Corollary 1 (Part 3), namely, $\tau_{\mathsf{q}}=\frac{8\Lambda^{2}\mu
r^{2}\hat{r}^{2}}{n}$, where $\mu$ is the approximation parameter of the soft-
max and $\hat{r}=\max\limits_{i\in[m]}\|x_{i}\|_{2}$.

Fourth, note that $L_{T}(\cdot,\cdot)$ is
$\Big{(}(\gamma_{\mathsf{q}},\|\cdot\|_{1}),(\gamma_{w},\|\cdot\|_{2})\Big{)}$-Lipschitz,
where $\gamma_{\mathsf{q}}=(\Lambda\hat{r}+Y)^{2}+4\Lambda^{2}\hat{r}^{2}$,
which follows from
$\|\nabla_{\mathsf{q}}L_{T}({\mathsf{q}},w)\|_{\infty}\leq\max\limits_{i\in[m]}\ell(h_{w}(x_{i}),y_{i})+4\Lambda^{2}\|\nabla_{\mathsf{q}}\widetilde{F}({\mathsf{q}})\|_{\infty}$
together with Corollary 1 (Part 4), and
$\gamma_{w}=2(\Lambda\hat{r}+Y)\hat{r}$, which follows directly from the
$\|\cdot\|_{2}$-bound on the gradient of the squared loss over
$\mathbb{B}_{2}^{d}(\Lambda)$.

Moreover, $L_{T}(\cdot,\cdot)$ is
$\Big{(}(\mu_{\mathsf{q}},\|\cdot\|_{1}),(\mu_{w},\|\cdot\|_{2})\Big{)}$-smooth,
where $\mu_{\mathsf{q}}=4\Lambda^{2}\mu\hat{r}^{4}$, which follows from the
fact that the smoothness of $L_{T}$ w.r.t. ${\mathsf{q}}$ is given by the
smoothness of $4\Lambda^{2}\widetilde{F}_{T}$, which follows from Corollary 1
(Part 2), and $\mu_{w}=\hat{r}^{2}$, which follows from the fact that the
squared loss $\ell(h_{w}(x),y)$ is $\|x\|_{2}^{2}$-smooth w.r.t.
$\|\cdot\|_{2}$.

Additionally, the condition on
$\|\nabla_{\mathsf{q}}L_{T}({\mathsf{q}},w)-\nabla_{\mathsf{q}}L_{T}({\mathsf{q}},w^{\prime})\|_{\infty}$
in Theorem 6 is satisfied in our case with
$\gamma_{{\mathsf{q}},w}=2\hat{r}(\Lambda\hat{r}+Y)$, which follows from the
fact that
$\|\nabla_{\mathsf{q}}L_{T}({\mathsf{q}},w)-\nabla_{\mathsf{q}}L_{T}({\mathsf{q}},w^{\prime})\|_{\infty}=\max_{i\in[m]}\lvert\ell(h_{w}(x_{i}),y_{i})-\ell(h_{w^{\prime}}(x_{i}),y_{i})\rvert$
together with the Lipschitzness property of the squared loss over
$\mathbb{B}_{2}^{d}(\Lambda)$.

Finally, note that $D_{\mathsf{q}}=2$ and $D_{w}=2\Lambda$.