# Large-vocabulary Audio-visual Speech Recognition in Noisy Environments
††thanks: This project has received funding from the German Research
Foundation DFG under grant number KO3434/4-2.

Wentao Yu, Steffen Zeiler, Dorothea Kolossa  Institute of Communication
AcousticsRuhr University Bochum Germany
{wentao.yu, steffen.zeiler<EMAIL_ADDRESS>
###### Abstract

Audio-visual speech recognition (AVSR) can effectively and significantly
improve the recognition rates of small-vocabulary systems, compared to their
audio-only counterparts. For large-vocabulary systems, however, there are
still many difficulties, such as unsatisfactory video recognition accuracies,
that make it hard to improve over audio-only baselines. In this paper, we
specifically consider such scenarios, focusing on the large-vocabulary task of
the LRS2 database, where audio-only performance is far superior to video-only
accuracies, making this an interesting and challenging setup for multi-modal
integration.

To address the inherent difficulties, we propose a new fusion strategy: a
recurrent integration network is trained to fuse the state posteriors of
multiple single-modality models, guided by a set of model-based and signal-
based stream reliability measures. During decoding, this network is used for
stream integration within a hybrid recognizer, where it can thus cope with the
time-variant reliability and information content of its multiple feature
inputs.

We compare the results with end-to-end AVSR systems as well as with
competitive hybrid baseline models, finding that the new fusion strategy shows
superior results, on average even outperforming oracle dynamic stream
weighting, which has so far marked the—realistically unachievable—upper bound
for standard stream weighting. Even though the pure lipreading performance is
low, audio-visual integration is helpful under all—clean, noisy, and
reverberant—conditions. On average, the new system achieves a relative word
error rate reduction of 42.18% compared to the audio-only model, pointing at a
high effectiveness of the proposed integration approach.

††publicationid: pubid: 978-1-6654-3288-7/21/$31.00 ©2021 European Union

##  I Introduction

Audio-visual speech recognition (AVSR) is motivated by the natural ability of
humans to integrate cross-modal information. When people are listening to
speech in a noisy environment, they often unconsciously focus on the speaker's
lips, which is of great benefit to human listening and comprehension [1]. Even
in clean speech, seeing the lips of the speaker influences perception, as
demonstrated by the McGurk effect [2]. It has been shown in many studies [3,
4, 5] that machine AVSR systems can also successfully improve performance on
small-vocabulary tasks, when compared to their audio-only speech recognition
(ASR) counterparts with otherwise equivalent setups. However, large-vocabulary
tasks are still difficult for lipreading, because many phoneme pairs
correspond to identical visemes, which makes certain words virtually
indistinguishable to a vision-only system, as for example ”do” and ”to”.

This problem also leads to an inherent difficulty of AVSR on large-vocabulary
tasks [6, 7], which is acerbated by the fact that many multi-stream fusion
approaches perform badly, when the performance of the streams varies widely.
In this work, we address this shortcoming by introducing a new stream fusion
strategy that is impervious to such disparate single-stream recognition rates
and can still benefit from low-quality streams in improving the results of
highly reliable, clean audio data. To evaluate it in a realistic manner, we
use a large-vocabulary dataset—the Lip Reading Sentences (LRS2) corpus [8]—for
all experiments, which we further augment by adding realistic noise and
reverberation.

An effective fusion strategy for AVSR is decision fusion, which combines the
decisions of multiple classifiers into a common decision. Decision fusion
comes in different forms, such as dynamic stream-weighting [9], or state-based
decision fusion (SBDF), e.g. in [10, 11, 12, 13]. An alternative fusion
approach is the idea of fusing _representations_ rather than decisions, e.g.
via multi-modal attentions [14]. Another example in this direction is that of
gating, e.g. in [15] or in [16], where a newly designed _Gated Multimodal
Unit_ is used for dynamically fusing feature streams within each cell of a
network.

In this work, we argue that the ideas of representation fusion and decision
fusion can be unified in a different fashion, namely, by using the posterior
probabilities $p(\textbf{s}|\textbf{o}_{t}^{\mathrm{i}})$ of $i=1\ldots M$
single-modality hybrid models as our representation of the uni-modal streams.

This viewpoint opens up a range of new possibilities, centered around these
single-modality representations. On the one hand, we can base the multi-modal
model on pre-trained hybrid ASR models. On the other hand, we can learn
recurrent and dynamic fusion networks, which can benefit from the reliability
information that is inherent in the posterior probabilities, such as
instantaneous entropy and dispersion [5], as well as from temporal context.

Overall, in the following, we compare our new approach with the performance of
4 baseline and oracle fusion strategies, which are detailed in Section II. The
proposed fusion strategy is introduced in Section III. Section IV describes
the set of reliability measures that are employed in all of the dynamic fusion
approaches. The experiments are presented in Section V, while Section VI
introduces and analyzes the results. Finally, in Section VII, we discuss the
lessons learned and give an outlook on future work.

##  II Related work

There are many different fusion strategies in AVSR research. In this section,
we give a brief introduction to the fusion strategies that are considered as
baseline models in this work. In these baselines as well as in our own model,
M = 3 single-modality models are combined, one acoustic and two visual, where
$\textbf{{o}}_{t}^{\mathrm{A}}$ are our audio features, and
$\textbf{{o}}_{t}^{\mathrm{VS}}$ and $\textbf{{o}}_{t}^{\mathrm{VA}}$ are
shape-based and appearance-based video features; see Section V-B for details.

###  II-A Early integration

Early integration simply fuses the audio and visual information at the level
of the input features via

$\textbf{{o}}_{t}=[(\textbf{{o}}_{t}^{\mathrm{A}})^{T},(\textbf{{o}}_{t}^{\mathrm{VS}})^{T},(\textbf{{o}}_{t}^{\mathrm{VA}})^{T}]^{T}.$
(1)

Superscript $T$ denotes the transpose.

###  II-B Dynamic stream weighting

Stream weighting is an effective method to fuse different streams. It is a
solution to the problem that the various streams may be reliable and
informative in very different ways. Hence, a number of works employ the
strategy of weighting different modalities [5, 17, 13]. Many utilize static
weights; for example in [18], audio and video speech recognition models are
trained separately and the DNN state posteriors of all modalities are combined
by constant stream weights $\lambda^{i}$ according to

$\textnormal{log
}\widetilde{p}(s|\textbf{o}_{t})=\sum_{i}\lambda^{i}\cdot\textrm{log
}{p}(s|\textbf{o}_{t}^{i}).$ (2)

Here, $\textrm{log }{p}(s|\textbf{{o}}_{t}^{i})$ is the log-posterior of state
$s$ in stream $i$ at time $t$ and
$\textnormal{log}\,\widetilde{p}(s|\textbf{{o}}_{t})$ is its estimated
combined log-posterior.

The problem of weight determination, however, cannot be neglected [19]. It is
clear that in good lighting conditions, the visual information may be more
useful, while audio information is most beneficial in frames with a
sufficiently high SNR. Therefore, the weight should be dynamically estimated
to obtain optimal fusion results. As a baseline approach, we therefore
consider _dynamic_ stream weighting, which implements this idea. Specifically,
we use dynamic stream weighting as described in [20] as the baseline. Here,
the DNN state posteriors of all modalities are combined by estimated dynamic
weights according to

$\textnormal{log
}\widetilde{p}(s|\textbf{o}_{t})=\sum_{i}\lambda_{t}^{i}\cdot\textrm{log
}{p}(s|\textbf{o}_{t}^{i}).$ (3)

The stream weights $\lambda_{t}^{i}$ are estimated by a feedforward network
from a set of reliability measures, introduced in detail in Sec. IV.

Reliability information has proven beneficial for multi-modal integration in
many studies [4, 5, 21], where it is used to inform the integration model
about the degree of uncertainty in all information streams over time. In [20],
the authors also consider different criteria to train the integration model.
In this paper, we use two of them as our baselines, namely the mean squared
error (MSE) and the cross-entropy (CE).

This learning-based approach to weighted stream integration can effectively
and significantly improve the recognition rates in lower SNR conditions. Also,
in contrast to many other stream integration strategies, such as [22, 9, 23],
it does not suffer from a loss of performance relative to the best single
modality when the modalities differ widely in their performance, but it rather
gains accuracy even from the inclusion of less informative streams. This is a
feature of great importance for the case at hand, as we need to design a
system that will even allow for the inclusion of the visual modality under
clean conditions, where audio is far more informative than video data, without
loosing—or, ideally, even still gaining—performance.

###  II-C Oracle weighting

We also compute optimal, or _oracle_ stream weights, as described in [20].
These optimal dynamic stream weights are computed in such a way as to minimize
the cross-entropy with respect to the ground-truth forced alignment
information. Since a known text transcription of the test set is therefore
needed in this method, it is only useful to obtain a theoretical upper
performance bound for standard stream-weighting approaches. To minimize the
cross-entropy, we use convex optimization via CVX [24].

The obtained oracle stream weights $\lambda_{t}^{i}$ are then used to
calculate the estimated log-posterior through Equation (3). As oracle stream
weights yield the minimum cross-entropy between the fused posteriors and the
ground-truth one-hot posteriors of the reference transcription computed by
forced alignment, the corresponding results can be considered as the best
achievable word error rate (WER) of a stream-weighting-based hybrid
recognition system.

###  II-D End-to-end model

In recent years, end-to-end speech recognition has quickly gained widespread
popularity. The end-to-end model predicts character sequences directly from
the audio signal. Comparing the end-to-end model and the hybrid speech
recognition model, the end-to-end model has a lower complexity and is more
easily amenable to multi-lingual ASR. But there are also some advantages to
using a hybrid model. For example, the hybrid model can be learned from and
adapted to comparatively little data and it can easily integrate with task-
specific WFST language models [25]. Importantly for this work, hybrid models
allow for integration at the level of the pseudo-posteriors, which is a place
for interpretable stream integration.

Hence, in this work, we use the hybrid approach to train the single modality
models. To compare the performance of our proposed system to that of end-to-
end AVSR, we consider the end-to-end “Watch, Listen, Attend and Spell” model
(WLAS) [26] as a baseline. In this model, the audio and video encoders are
LSTM networks. The decoder is an LSTM transducer, which fuses the encoded
audio and video sequences through a dual attention mechanism.

##  III System overview

In the following, we propose an architecture that centers around a decision
fusion net (DFN), which learns to combine all modalities dynamically.

As shown in Fig. 1, it bases on the state posteriors of each modality, derived
from one hybrid recognition model per stream, which we consider as our
representation of instantaneous feature inputs. In addition, we provide the
DFN with multiple reliability indicators as auxiliary inputs, which help in
estimating the multi-modal log-posteriors $\textnormal{log
}\widetilde{p}(\textbf{s}|\textbf{o}_{t})$ for the decoder. As mentioned
above, we consider $M=3$ single-modality models, one acoustic and two visual.
The fused posterior $\textnormal{log
}\widetilde{p}(\textbf{s}|\textbf{o}_{t})$ is computed via

$\textnormal{log
}\widetilde{p}(\textbf{s}|\textbf{o}_{t})=\textrm{DFN}([{p}(\textbf{s}|\textbf{o}_{t}^{\mathrm{A}})^{T},{p}(\textbf{s}|\textbf{o}_{t}^{\mathrm{VA}})^{T},\\\
{p}(\textbf{s}|\textbf{o}_{t}^{\mathrm{VS}})^{T},\textbf{R}_{t}^{T}]^{T}).$
(4)

Here, ${p}(\textbf{s}|\textbf{o}_{t}^{\mathrm{A}})$,
${p}(\textbf{s}|\textbf{o}_{t}^{\mathrm{VA}})$ and
${p}(\textbf{s}|\textbf{o}_{t}^{\mathrm{VS}})$ are the state posteriors of the
audio model, and of the appearance-based, and a shape-based video model,
respectively. $\textbf{R}_{t}$ is a vector composed of the reliability
measures at time $t$, which we describe in Sec. IV. As an alternative to the
posteriors of each stream, we have also considered a fusion of the log
posteriors $\textnormal{log}\;{p}(\textbf{s}|\textbf{o}_{t}^{\mathrm{i}})$,
but settled on the linear posteriors due to a better model convergence.

Figure 1: Audio-visual fusion via the DFN, applied to one stream of audio and
two streams of video features

DFN training is then performed with the cross-entropy loss

$\mathcal{L}_{\textnormal{CE}}=-\frac{1}{T}\sum_{t=1}^{T}\sum_{s=1}^{S}p^{*}(s|\textbf{{o}}_{t})\cdot\textnormal{log
}\widetilde{p}(s|\textbf{{o}}_{t}).$ (5)

Here, $p^{*}(s|\textbf{{o}}_{t})$ is the target state probability of state
$s$, obtained by the forced alignment for the clean acoustic training data.
The estimated vector of log-posteriors $\textnormal{log
}\widetilde{p}(\textbf{s}|\textbf{o}_{t})$ is obtained from Eq. (4). Finally,
the decoder uses these estimated log-posteriors to find the optimum word
sequence by a graph search through the decoding graph [27].

##  IV Reliability measures

To support the estimation of the dynamic stream weights, we extract a range of
model-based and signal-based reliability measures (see Tab. I), generally
computed as in [20]. All of these reliability indicators are used in the
dynamic stream weighting baseline as well as in our proposed model.

TABLE I: Overview of reliability measures Model-based | Signal-based
---|---
Audio-based | Video-based
|  • Entropy
---
• Dispersion
• Posterior difference
• Temporal divergence
• Entropy and
dispersion ratio
|  • MFCC
---
• $\Delta$MFCC
• SNR
• $f_{0}$
• $\Delta f_{0}$
• voicing probability
|  • Confidence
---
• IDCT
• Image
distortion

The model-based measures are entropy, dispersion, posterior difference,
temporal divergence, entropy- and dispersion-ratio. All model-based measures
are computed from the log-posterior outputs of their respective single-
modality models, $\textnormal{log }{p}(\textbf{s}|\textbf{o}_{t})$.

Signal-based reliability measures for the audio data comprise the first 5 MFCC
coefficients with their temporal derivatives $\Delta$MFCC, again as in [20].
The SNR is strongly related to the intelligibility of an audio signal.
However, due to the realistic, highly non-stationary environmental noises
(discussed in Sec. V) used in data augmentation and testing, conventional SNR
estimation algorithms are not showing a robust performance. Instead,
therefore, the deep learning approach DeepXi [28] is used to estimate the
frame-wise SNR.

The pitch $f_{0}$ and its temporal derivative, $\Delta f_{0}$, are also used
as reliability indicators. It has been shown that high pitch of a speech
signal negatively affects the MFCC coefficients [29], due to insufficient
smoothing of the pitch harmonics in the speech spectrum by the filterbank.

The probability of voicing [30] is used as an additional cue. It is computed
from the Normalized Cross-Correlation Function (NCCF) values for each frame.

OpenFace [31] is used for face detection and facial landmark extraction. This
allows us to use the confidence of the face detector in each frame as an
indicator of the visual feature quality. The other signal-based video
reliability measures, the Inverse Discrete Cosine Transform (IDCT), and the
image distortion estimates, are the same as in [20].

##  V Experimental Setup

###  V-A Dataset

The Oxford-BBC Lip Reading Sentences (LRS2) corpus is used for all
experiments. It contains more than 144k sentences from British television.
Table II gives an overview of the dataset size and partitioning. The pre-train
set is usually used in AVSR tasks for video or audio-visual model pretraining.
In this work, we combine the pre-train and training set to train all acoustic,
visual, and AV models.

TABLE II: Size of subsets within the LRS2 Corpus Subset | Utterances | Vocabulary |  | Duration
---
[hh:mm]
pre-train set | 96,000 | 41,000 | 196:25
training set | 45,839 | 17,660 | 28:33
validation set | 1,082 | 1,984 | 00:40
test set | 1,243 | 1,698 | 00:35

For the AVSR task, the results are often dominated by the acoustic model. To
analyze the performance in different noisy environments and to counter the
audio-visual model imbalance, we add acoustic noise to the LRS2 database. The
ambient subset of the MUSAN corpus [32] is used as the noise source. It
contains noises such as wind, footsteps, paper rustling, rain, as well as
indistinct crowd noises. Seven different SNRs are selected randomly, from -9
dB to 9 dB in steps of 3 dB. We also generated data for a far-field AVSR
scenario. As the LRS2 database does not contain highly reverberant data, we
artificially reverberate the acoustic data by convolutions with measured
impulse responses. These impulse responses also come from the MUSAN corpus.
Both types of augmentation use Kaldi’s Voxceleb example recipe.

###  V-B Feature extraction

The audio model uses 40 log Mel features together with two pitch features
($f_{0}$, $\Delta f_{0}$) and the probability of voicing, yielding
43-dimensional feature vectors. The audio features are extracted with 25 ms
frame size and 10 ms frameshift. The video features are extracted per frame,
i.e., every 40 ms. The video appearance model (VA) uses 43-dimensional IDCT
coefficients of the grayscale mouth region of interest (ROI) as features. The
video shape model (VS) is based on the 34-dimensional non-rigid shape
parameters described in [31].

Since the audio and video features have different frame rates, Bresenham's
algorithm [33] is used to align the video features before training the visual
models. This algorithm gives the best first-order approximation for aligning
audio and video frames given only a difference in frame rates.

###  V-C Implementation details

All our experiments are based on the Kaldi toolkit [25]. As mentioned in
Section V-A, both pre-train and training sets are used together to train the
acoustic and visual models. The initial HMM-GMM training follows the standard
Kaldi AMI recipe, namely, monophone training followed by triphone training. A
linear discriminant analysis (LDA) is applied to a stacked context of features
to obtain discriminative short-term features. Finally, speaker adaptive
training (SAT) is used to compensate for speaker variability. Each step
produces a better forced alignment for later network training. HMM-DNN
training uses the nnet2 p-norm network [34] recipe, which is efficiently
parallelizable.

Once HMM-DNN training has been performed, the acoustic model DNN and two
visual observation models are available. They output estimated log-posteriors
$\textrm{log }{p}(\textbf{s}|\textbf{{o}}_{t}^{i})$ for each stream, which are
then used in our proposed DFN. Its input consists of all stream-wise state-
posteriors ${p}(\textbf{s}|\textbf{{o}}_{t}^{i})$ and the reliability
measures.

As mentioned in Section III, the decoder obtains the best word sequence by
graph search through a decoding graph using the estimated log-pseudo-
posteriors $\textnormal{log }\widetilde{p}(\textbf{s}|\textbf{o}_{t})$. To
ensure that all experiments and modalities search through the same decoding
graph, we share the phonetic decision tree between all single modalities.
Thus, the number of states for each modality is identical, specifically 3,856.

In addition, there are 41 reliability indicators, which leads to an overall
input dimension of $(3\times 3856+41)=$11,609. The first three hidden layers
have 8,192, 4,096, and 1,024 units, respectively, each using the ReLU
activation function, layer normalization (LN), and a dropout rate of 0.15.
They are followed by 3 BLSTM layers with 1,024 memory cells for each
direction, using tanh as the activation function. Finally, a fully connected
(FC) layer projects the data to the output dimension of 3,856. A log-softmax
function is applied to obtain the estimated log-posteriors.

Early stopping is used to avoid overfitting. We check for early stopping every
7,900 iterations, using the validation set. The training process is stopped if
the validation loss does not decrease for 23,700 iterations. Finally, the
performance is evaluated on the test set. We performed two experiments with
the proposed DFN strategy. The first uses the BLSTM-DFN, exactly as described
above, while the second is an LSTM-DFN, replacing the BLSTM layers by purely
feed-forward LSTMs.

The learning rate is initialized to $5\times 10^{-4}$ and reduced by 20%
whenever the validation loss does not decrease in early stopping checking. The
batch size is set to 10. DNN training utilizes the PyTorch library [35] with
the ADAM optimizer.

##  VI Results

In this section, we compare the performance of all baseline models and fusion
strategies. Figure 2 gives an overview of the results of the audio-only model
and compares the results of all baselines and our proposed BLSTM-DFN.

Figure 2: WER (%) on the test set of the LRS2 corpus.

Comparing the audio-only model and the BLSTM-DFN integration, our fusion
strategy is able to reduce the Word Error Rate (WER) for every SNR, even for
clean acoustic data. For lower SNRs, the DFN can improve the absolute WER by
over 10%. Our proposed BLSTM-DFN is also capable of achieving better results
in many cases than the–realistically unachievable—oracle weighting (OW), that
is based on ground-truth transcription information of the test set and can be
considered as the upper limit for the dynamic stream-weighting approach of
Equation (3). The end-to-end WLAS model is not able to improve the recognition
rates comparing to the audio-only model, which may in part be due to the fact
that it does not employ an explicit language model.

Table III lists all the results of our experiments under additive noise. As
expected, the audio-only model (AO) has a much better performance than the
video-appearance (VA) and video-shape (VS) models. The average WERs of the
visual models are over 80%, which illustrates that lipreading is still hard in
large-vocabulary tasks. We have also employed the pre-trained spatio-temporal
visual front-end from [36] to extract high-level visual features, without
seeing improvements. We assume that this is due to insufficient training data
as well as to insufficient generalization across speakers and recording
conditions.

TABLE III:  Word error rate (%) on the LRS2 test set under additive noise. OW describes the realistically unachievable performance bound for dynamic, instantaneous stream weighting. SNR | -9 | -6 | -3 | 0 | 3 | 6 | 9 | clean | avg.
---|---|---|---|---|---|---|---|---|---
AO | 48.96 | 41.44 | 33.07 | 30.81 | 22.85 | 18.89 | 16.49 | 10.12 | 27.83
VA | 85.83 | 87.00 | 85.26 | 88.10 | 87.03 | 88.44 | 88.25 | 88.10 | 87.25
VS | 88.11 | 90.27 | 87.29 | 88.88 | 85.88 | 85.33 | 88.58 | 87.10 | 87.68
EI | 40.14 | 32.47 | 23.96 | 26.59 | 20.67 | 16.68 | 14.76 | 10.02 | 23.16
MSE | 46.48 | 37.79 | 27.45 | 27.47 | 19.52 | 16.58 | 15.09 | 9.42 | 24.98
CE | 45.79 | 37.14 | 26.32 | 28.03 | 19.40 | 16.68 | 14.76 | 9.42 | 24.65
OW | 30.33 | 26.47 | 15.41 | 21.25 | 13.66 | 11.66 | 10.45 | 7.54 | 17.10
WLAS | 64.74 | 59.87 | 49.03 | 50.60 | 41.17 | 39.89 | 43.72 | 29.32 | 47.29
LSTM-DFN | 33.30 | 27.22 | 21.26 | 21.25 | 19.17 | 13.97 | 15.84 | 10.32 | 20.29
BLSTM-DFN | 27.55 | 23.11 | 17.89 | 16.35 | 14.93 | 10.25 | 10.78 | 7.84 | 16.09

Early integration (EI) can also improve the results, but the improvement is
not as significant as that of the proposed DFN approach. Comparing the BLSTM-
DFN and the LSTM-DFN, the former shows a notable advantage in accuracy, albeit
at the price of non-real-time performance. Both the LSTM-DFN and the BLSTM-DFN
use recurrent layers with 1024 memory cells. As the number of parameters in a
BLSTM layer are almost double that of the LSTM layer, we also trained a BLSTM-
DFN using 512 memory cells per layer. The average WER of this model is 16.14%,
still better than that of the LSTM-DFN with a similar number of parameters. If
we increase the number of cells for the LSTM-DFN to 2048, with the same
learning rate, the model suffers from convergence issues.

The dynamic stream weighting results, using the MSE or CE loss, are better
than shown in [20] for three reasons. Firstly, improved reliability measures
are used in this work. Secondly, [20] trains acoustic and visual models only
on the training set, whereas here, they are trained on both the pre-train and
training data. This gives a significant performance boost to the single-
modality systems and also to early integration, but is not of as much added
benefit to the dynamic stream-weight estimation, though the weight estimator
from [20] was trained on the validation set, whereas here, it is also trained
on the pre-train and training sets. We assume that its relatively small
performance gain is due to the limited flexibility of the composition function
in dynamic stream weighting.

Comparing the average WER over all acoustic conditions, the proposed BLSTM-DFN
is greatly beneficial, outperforming the not realistically achievable OW
system, and surpassing all feasible stream integration approaches by a clear
margin. Thus, our proposed method outperforms even optimal dynamic stream
weighting and therefore provides a fundamentally superior architecture
compared to instantaneous stream weighting.

[] Far-field AVSR WER (%) on LRS2. AO EI MSE CE OW WLAS LSTM- DFN BLSTM- DFN
23.61 19.15 19.54 19.44 12.70 44.24 15.67 15.28

We also checked the case of far-field AVSR by using data augmentation to
produce artificially reverberated speech, see Table VI for the results. The
BLSTM-DFN still outperforms the other fusion strategies, but it is not as
close to the OW. We suspect the reason is an insufficient amount of
reverberant acoustic training signals.

Overall, it can be concluded that the introduced DFN is generally superior to
instantaneous dynamic stream weighting. The latter can be considered as fusion
at the _frame level_. Frame-by-frame, it sums log-posteriors of each stream in
a weighted fashion. Hence, its estimated combined log-posterior is a linear
transformation of the single-modality log-posteriors. In contrast, the DFN can
be considered as a cross-temporal fusion strategy at the _state level_ , as
the combined log-posterior is estimated through a non-linear transformation
with memory. This allows for a more accurate estimation, in which the BLSTM-
DFN gives an added advantage to the LSTM-DFN, since it has access to both past
and future contextual information. In this work, the BLSTM-DFN shows a
relative WER reduction of 42.18% compared to the audio-only system, while the
LSTM-DFN yields a relative WER improvement of 27.09%, showing the benefit of
being able to lipread even for noisy LVCSR.

##  VII Conclusion

There are still many difficulties for large-vocabulary speech recognition
under adverse conditions, but the fusion of acoustic and visual information
can bring a significant benefit to these challenging and interesting tasks. In
this paper, we propose a new architecture, the decision fusion net (DFN), in
which we consider state posteriors of acoustic and visual models as
appropriate stream representations for fusion. These are combined by the DFN,
which uses stream reliability indicators to estimate the optimal state-
posteriors for hybrid speech recognition. It comes in two flavors, a BLSTM-DFN
with optimal performance, as well as an LSTM-DFN, which provides the option of
real-time decoding.

We compare the performance of our proposed model to early integration as well
as to conventional dynamic stream weighting models. In experimental results on
noisy as well as on reverberant data, our proposed model shows significant
improvements, with the BLSTM version giving a relative word-error-rate
reduction of 42.18% over audio-only recognition, and outperforming all
baseline models. The hybrid architecture with the proposed DFN clearly
outperforms the end-to-end WLAS model, which we attribute to its factorization
of stream evaluation, stream integration, and subsequent, language-model-
supported, search. It is worth mentioning that, on average, the hybrid DFN
model is even superior to a hybrid model with _oracle_ stream weighting, which
is an interesting result on its own, given that the latter provides a
theoretical upper bound for instantaneous stream weighting approaches.

The natural next goal of our work is to focus on end-to-end audio-visual
speech recognition models. Here, we are specifically interested in
investigating reliability-supported fusion within the attention mechanism in
CTC and transformer systems and in the possibilities that come with
probabilistic intermediate representations for these architectures.

## References

  * [1] M. J. Crosse, G. M. Di Liberto, and E. C. Lalor, “Eye can hear clearly now: inverse effectiveness in natural audiovisual speech processing relies on long-term crossmodal temporal integration,” _Journal of Neuroscience_ , vol. 36, no. 38, pp. 9888–9895, 2016.
  * [2] H. McGurk and J. MacDonald, “Hearing lips and seeing voices,” _Nature_ , vol. 264, no. 5588, pp. 746–748, 1976.
  * [3] M. Wand and J. Schmidhuber, “Improving speaker-independent lipreading with domain-adversarial training,” in _Proc. Interspeech_ , 2017.
  * [4] H. Meutzner, N. Ma, R. Nickel, C. Schymura, and D. Kolossa, “Improving audio-visual speech recognition using deep neural networks with dynamic stream reliability estimates,” in _Proc. ICASSP_ , 2017, pp. 5320–5324.
  * [5] M. Gurban, J. Thiran, T. Drugman, and T. Dutoit, “Dynamic modality weighting for multi-stream HMMs in audio-visual speech recognition,” in _Proc. ICMI_ , 2008, pp. 237–240.
  * [6] K. Thangthai and R. Harvey, “Building large-vocabulary speaker-independent lipreading systems,” in _Proc. Interspeech_ , 2018.
  * [7] G. Sterpu, C. Saam, and N. Harte, “How to teach DNNs to pay attention to the visual modality in speech recognition,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 28, pp. 1052–1064, 2020.
  * [8] T. Afouras, J. Chung, A. Senior, O. Vinyals, and A. Zisserman, “Deep audio-visual speech recognition,” _arXiv:1809.02108_ , 2018.
  * [9] D. Stewart, R. Seymour, A. Pass, and J. Ming, “Robust audio-visual speech recognition under noisy audio-video conditions,” _IEEE Transactions on Cybernetics_ , vol. 44, no. 2, pp. 175–184, 2013.
  * [10] A. Abdelaziz, S. Zeiler, and D. Kolossa, “Learning dynamic stream weights for coupled-HMM-based audio-visual speech recognition,” _Audio, Speech, and Language Processing, IEEE/ACM Transactions on_ , vol. 23, no. 5, pp. 863–876, 2015.
  * [11] G. Potamianos, C. Neti, G. Gravier, A. Garg, and A. Senior, “Recent advances in the automatic recognition of audiovisual speech,” _Proceedings of the IEEE_ , vol. 91, no. 9, pp. 1306–1326, 2003.
  * [12] J. Luettin, G. Potamianos, and C. Neti, “Asynchronous stream modeling for large vocabulary audio-visual speech recognition,” vol. 1. IEEE, 2001, pp. 169–172.
  * [13] A. Nefian, L. Liang, X. Pi, X. Liu, and K. Murphy, “Dynamic Bayesian networks for audio-visual speech recognition,” _EURASIP Journal on Advances in Signal Processing_ , vol. 2002, no. 11, pp. 1–15, 2002.
  * [14] P. Zhou, W. Yang, W. Chen, Y. Wang, and J. Jia, “Modality attention for end-to-end audio-visual speech recognition,” in _Proc. ICASSP_ , 2019. [Online]. Available: http://arxiv.org/abs/1811.05250
  * [15] J. Yu, S. Zhang, J. Wu, S. Ghorbani, B. Wu, S. Kang, S. Liu, X. Liu, H. Meng, and D. Yu, “Audio-visual recognition of overlapped speech for the LRS2 dataset,” in _Proc. ICASSP_ , 2020a, pp. 6984–6988.
  * [16] J. Arevalo, T. Solorio, M. Montes-y Gomez, and F. González, “Gated multimodal networks,” _Neural Computing and Applications_ , pp. 1–20, 2020\.
  * [17] M. Heckmann, F. Berthommier, and K. Kroschel, “Noise adaptive stream weighting in audio-visual speech recognition,” _EURASIP Journal on Advances in Signal Processing_ , vol. 2002, no. 11, pp. 1–14, 2002.
  * [18] M. Yang, S. Wang, and Y. Lin, “A multimodal fusion system for people detection and tracking,” _Int. J. Imaging Syst. Technol._ , vol. 15, pp. 131–142, 2005\.
  * [19] M. Kankanhalli, J. Wang, and R. Jain, “Experiential sampling in multimedia systems,” _IEEE Transactions on Multimedia_ , vol. 8, no. 5, pp. 937–946, 2006.
  * [20] W. Yu, S. Zeiler, and D. Kolossa, “Multimodal integration for large-vocabulary audio-visual speech recognition,” in _Proc. EUSIPCO_ , 2020b, pp. 341–345.
  * [21] H. Hermansky, “Multistream recognition of speech: Dealing with unknown unknowns,” _Proceedings of the IEEE_ , vol. 101, no. 5, pp. 1076–1088, 2013\.
  * [22] R. Seymour, J. Ming, and D. Stewart, “A new posterior based audio-visual integration method for robust speech recognition,” in _Proc. Interspeech_ , 2005.
  * [23] S. Receveur, R. Weiß, and T. Fingscheidt, “Turbo automatic speech recognition,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 24, no. 5, pp. 846–862, 2016.
  * [24] M. Grant and S. Boyd, “CVX: Matlab Software for Disciplined Convex Programming, version 2.1,” http://cvxr.com/cvx, Mar. 2014.
  * [25] D. Povey, A. Ghoshal, G. Boulianne, L. Burget, O. Glembek, N. Goel, M. Hannemann, P. Motlicek, Y. Qian, P. Schwarz _et al._ , “The Kaldi speech recognition toolkit,” in _Proc. IEEE_. IEEE Signal Processing Society, 2011.
  * [26] J. S. Chung, A. Senior, O. Vinyals, and A. Zisserman, “Lip reading sentences in the wild,” in _IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 6447–6456.
  * [27] M. Mohri, F. Pereira, and M. Riley, “Speech recognition with weighted finite-state transducers,” in _Springer Handbook of Speech Processing_. Springer, 2008, pp. 559–584.
  * [28] A. Nicolson and K. Paliwal, “Deep learning for minimum mean-square error approaches to speech enhancement,” _Speech Communication_ , vol. 111, pp. 44–55, 2019.
  * [29] S. Dharanipragada, U. Yapanel, and B. Rao, “Robust feature extraction for continuous speech recognition using the MVDR spectrum estimation method,” _IEEE Transactions on Audio, Speech, and Language Processing_ , vol. 15, no. 1, pp. 224–234, 2006.
  * [30] P. Ghahremani, B. BabaAli, D. Povey, K. Riedhammer, J. Trmal, and S. Khudanpur, “A pitch extraction algorithm tuned for automatic speech recognition,” in _Proc. ICASSP_ , 2014, pp. 2494–2498.
  * [31] B. Amos, L. Bartosz, and M. Satyanarayanan, “OpenFace: A general-purpose face recognition library with mobile applications,” CMU-CS-16-118, CMU School of Computer Science, Tech. Rep., 2016.
  * [32] D. Snyder, G. Chen, and D. Povey, “MUSAN: A Music, Speech, and Noise Corpus,” 2015, arXiv:1510.08484v1.
  * [33] R. Sproull, “Using program transformations to derive line-drawing algorithms,” _ACM Transactions on Graphics (TOG)_ , vol. 1, no. 4, pp. 259–273, 1982.
  * [34] X. Zhang, J. Trmal, D. Povey, and S. Khudanpur, “Improving deep neural network acoustic models using generalized maxout networks,” in _Proc. ICASSP_ , 2014, pp. 215–219.
  * [35] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” in _Advances in neural information processing systems_ , 2019, pp. 8026–8037.
  * [36] T. Stafylakis and G. Tzimiropoulos, “Combining residual networks with LSTMs for lipreading,” _arXiv preprint arXiv:1703.04105_ , 2017.


or gender), $y_{i}\in\mathcal{Y}$ is the label. Using constrained group-
objective optimization, the chosen hypothesis $h$ need not have access to nor
knowledge of the protected attribute $A$ during testing or deployment.

######  Definition 8.4 (Equalized Odds (Hardt et al., 2016)).

A classifier $h$ satisfies Equalized Odds under a distribution over
$(\text{{x}},a,y)$ if $h(X)$, its prediction, is conditionally independent of
the protected attribute $A$ given the label $Y$.

In notation, we have that for all
$a\in\mathcal{A},\hat{y}\in\mathcal{Y},x\in\mathcal{X}$

$\mathbb{P}_{(\text{{x}},a,y)\sim\mu}\left[h(\text{{x}})=\hat{y}|A=a,Y=y\right]=\mathbb{P}\left[h(\text{{x}})=\hat{y}|Y=y\right].$

######  Definition 8.5 (Demographic Parity (Agarwal et al., 2018)).

A classifier $h$ satisfies Demographic Parity under a distribution over
$(\text{{x}},a,y)$ if $h(X)$, its prediction, is statistically independent of
the protected attribute $A$.

In notation, we have that for all $a\in\mathcal{A},\hat{y}\in\mathcal{Y}$

$\mathbb{P}_{(\text{{x}},a,y)\sim\mu}\left[h(\text{{x}})=\hat{y}|A=a\right]=\mathbb{P}\left[h(\text{{x}})=\hat{y}\right].$

For optimization purposes, we often cannot satisfy either equalized odds or
demographic parity exactly so we must instead pursue relaxations of equalized
odds and demographic parity. For example, Jagielski et al. (2018) pursue
$\gamma$ Equalized Odds which is defined in Definition 8.7, stated in terms of
false positives and false negatives of a hypothesis $h$.

######  Definition 8.6 (Gini Index of Inequality (Busa-Fekete et al., 2017)).

Suppose there are $K$ subgroups in a population of individuals earning income.
The Gini Index of Inequality is given by

$I(l)=\frac{\sum_{i,j}|l_{i}-l_{j}|}{2n\sum_{i}l_{i}}\in[0,1],$

where $l\in[0,1]^{K}$ and $l_{i}$ could represent the percentile average
income of individuals in subgroup $i$.

The Gini index is not convex but quasi-convex which means that its level sets
are convex. For any given $\theta\in[0,1]$, $I(l)\leq\theta$ is equivalent to

$\sum_{i,j}|l_{i}-l_{j}|-2n\theta\sum l_{i}\leq 0,$

which is a convex constraint (Alabi et al., 2018).

Definition 8.6 makes no distributional assumptions on the loss vector
$l\in[0,1]^{K}$.

Agarwal et al. (2018) show how to convert the empirical risk minimization
problem for satisfying either demographic parity or equalized odds into the
following problem:

$\min_{h\in\Delta}\hat{err}(h)\,\,\text{ s.t. }\,\,M\hat{\mu}(h)\leq\hat{c}$
(11)

where the matrix $M\in{\mathbb{R}}^{|\mathcal{K}|\times|\mathcal{J}|}$ and the
vector $\hat{c}\in{\mathbb{R}}^{|\mathcal{K}|}$ specify linear constraints for
the problem and $\hat{\mu}(h)\in{\mathbb{R}}^{|\mathcal{J}|}$ is a vector of
conditional moments taken over the the distribution on
$(\mathcal{X},A,\mathcal{Y})$.

To convert into the form of constrained group-objective optimization, we set
$f(\ell(h,D))=\hat{err}(h)$ and
$g(\ell(h,D))=(M\hat{\mu}(h)-\hat{c})\cdot\textbf{1}$ where 1 is the all-ones
vector or $g(\ell(h,D))=\max_{i\in[\mathcal{K}]}(M\hat{\mu}(h)-\hat{c})_{i}$.
We leave out details of how to convert the definition of Demographic Parity
and Equalized Odds into Equation 11 as this is already done in Section 2
(termed “Problem Formulation”) in (Agarwal et al., 2018). Last, for the Gini
index of inequality, we can convert into constrained group-objective
optimization by setting the constraint function $g$ to
$g(l)=\sum_{i,j}|l_{i}-l_{j}|-2n\theta\sum l_{i}\leq 0$ for some
$\theta\in[0,1]$ and setting $f(l)=-\sum_{i}l_{i}$ for all $l\in[0,1]^{K}$.

We note here that $K$, the number of groups, is not a constant and could vary
depending on the context, application, and matters of intersectionality
(Buolamwini and Gebru, 2018; Hébert-Johnson et al., 2018).

####  8.2.1 Satisfying Equalized Odds

Now, we show how to satisfy approximate notions of equalized odds while
respecting differential privacy constraints.

######  Definition 8.7 ($\alpha$-Equalized Odds (Jagielski et al., 2018)).

Let $X,A,Y$ be random variables representing the non-sensitive features, the
sensitive attribute, and the label assigned to an individual, respectively.

Given a dataset of examples
$D=\\{(\text{{x}}_{i},a_{i},y_{i})\\}_{i=1}^{n}\in(\mathcal{X},\mathcal{A},\\{0,1\\})^{n}$
of size $n$, we say a classifier $c\in\mathcal{C}_{P}$ satisfies $\alpha$
Equalized Odds if

$\max_{a,a^{\prime}\in\mathcal{A}}\\{\max(|\hat{FP}_{a}-\hat{FP}_{a^{\prime}}|,|\hat{TP}_{a}-\hat{TP}_{a^{\prime}}|)\\}\leq\alpha$
(12)

where $\hat{FP}_{a},\hat{TP}_{a}$ are empirical estimates of
$FP_{a}(c)=\mathbb{P}_{(x,y,a)}[c(\text{{x}})=1|A=a,y=0]$,
$TP_{a}(c)=\mathbb{P}_{(x,y,a)}[c(\text{{x}})=1|A=a,y=1]$ respectively on
dataset $D$. 181818 $FP_{a}(c)$ is usually referred to as the false positive
rate on attribute $A=a$. Likewise, $FN_{a}(c)$ and $TP_{a}(c)$ are the false
negative and true positive rates on attribute $A=a$ respectively.

We say a classifier satisfies $\alpha$-Smoothed Equalized Odds if the smoothed
version of Equation 13 is satisfied (i.e., when the maximum and absolute
functions in Equation 13 are replaced with smoothed versions 191919 For
example, the smooth maximum function is a smooth approximation to the maximum
function.  or using the Moreau-Yosida regularization technique).

For concreteness, we provide a specific smoothed version of $\alpha$-equalized
odds in Definition 8.8.

######  Definition 8.8 ($(\alpha,\eta)$-Smoothed Equalized Odds).

Let $X,A,Y$ be random variables representing the non-sensitive features, the
sensitive attribute, and the label assigned to an individual, respectively.

Given a dataset of examples
$D=\\{(\text{{x}}_{i},a_{i},y_{i})\\}_{i=1}^{n}\in(\mathcal{X},\mathcal{A},\\{0,1\\})^{n}$
of size $n$, we say a classifier $c\in\mathcal{C}_{P}$ satisfies
$(\alpha,\eta)$ Equalized Odds if the constraint function

$g(\hat{FP},\hat{FN},\hat{TP})=\operatorname*{smax}^{\eta}_{a,a^{\prime}\in\mathcal{A}}\\{\max(|\hat{FP}_{a}-\hat{FP}_{a^{\prime}}|,|\hat{TP}_{a}-\hat{TP}_{a^{\prime}}|)\\}-\alpha$
(13)

is less than or equal to 0. $(\hat{FP},\hat{FN},\hat{TP})$ corresponds to the
$3|\mathcal{A}|$ empirical estimates of the false positives, false negatives,
and true positives for the $|\mathcal{A}|$ groups. $(\hat{FP},\hat{TP})$ are
used to enforce the equalized odds constraint while $(\hat{FP},\hat{FN})$ are
used to compute the error of the classifier. We use the smooth maximum
function
$\operatorname*{smax}^{\eta}(y_{1},\ldots,y_{n})=\frac{\sum_{i=1}^{n}y_{i}e^{\eta
y_{i}}}{\sum_{i=1}^{n}e^{\eta y_{i}}}$ (Lange et al., 2014). As
$\eta\rightarrow\infty$, $\operatorname*{smax}^{\eta}\rightarrow\max$.

######  Corollary 8.9.

For any privacy parameters $\epsilon,\delta\in(0,1]$, suppose we have a
dataset of examples $D=\\{(\text{{x}}_{i},a_{i},y_{i})\\}_{i=1}^{n}$ of size
$n$ where $\text{{x}}_{i}\in\mathcal{X},y_{i}\in\\{0,1\\}$,
$a_{i}\in\mathcal{A}$, for all $i\in[n]$. Assume that there exists at least
one decision in $\mathcal{C}_{P}$ (with VC dimension
$\operatorname*{VC}(\mathcal{C}_{P})$ in parametric space ${\mathbb{R}}^{P}$)
that satisfies $(\alpha,\eta)$-Smoothed Equalized Odds (by Definition 8.7) for
some $\eta>0$.

Then there exists
$n_{0}=\tilde{O}\left(\frac{|\mathcal{A}|^{4}\cdot\operatorname*{VC}(\mathcal{C}_{P})}{\epsilon\alpha^{3}}\right)$
such that for all $n\geq n_{0}$, with probability at least $9/10$, we can
obtain a decision $\tilde{c}\in\mathcal{C}_{P}$ satisfying
$(\alpha,\eta)$-smoothed equalized odds and that is within $\alpha$ away from
the most accurate classifier.

###### Proof.

For any classifier $c\in\mathcal{C}_{P}$ we set the loss vector of $c$ on $D$
to

$\ell(c,D)=(\ell_{1}(c,D),\ldots,\ell_{K}(c,D)),$

with $K=3|\mathcal{A}|$ where

$\ell_{1}(c,D)=\hat{FP}_{1},\ldots,\ell_{|A|}(c,D)=\hat{FP}_{|\mathcal{A}|},$
$\ell_{|\mathcal{A}|+1}(c,D)=\hat{TP}_{1},\ldots,\ell_{2|A|}(c,D)=\hat{TP}_{|\mathcal{A}|},$

and

$\ell_{2|\mathcal{A}|+1}(c,D)=\hat{FN}_{1},\ldots,\ell_{3|A|}(c,D)=\hat{FN}_{|\mathcal{A}|}.$

Then the empirical error of any classifier $c\in\mathcal{C}_{P}$ is
$f(\ell(c,D))=\sum_{a\in\mathcal{A}}\hat{FP}_{a}+\hat{FN}_{a}$ (the sum of the
false positives and false negatives) and the $\alpha$-equalized odds is
enforced via

$g(\ell(c,D))=\max_{a,a^{\prime}\in\mathcal{A}}\\{\max(|\hat{FP}_{a}-\hat{FP}_{a^{\prime}}|,|\hat{TP}_{a}-\hat{TP}_{a^{\prime}}|)\\}-\alpha,$

so that $g(\ell(c,D))\leq 0$ for all classifiers $c\in\mathcal{C}_{P}$ that
satisfy $\alpha$-equalized odds. We use a smoothed version of $g(\ell(c,D))$
(i.e., replace the maximum and absolute functions in that equation with the
smooth approximations of those functions or using the Moreau-Yosida
regularization technique).

Now, assuming there exists at least one choice $c\in\mathcal{C}_{P}$ such that
$g(\ell(c,D))\leq 0$, we can just directly apply Corollary 5.11 to $f,g$ to
obtain the desired corollary. ∎

Corollary 8.9 results in sample size
$\tilde{O}\left(\frac{|\mathcal{A}|^{4}\cdot\operatorname*{VC}(\mathcal{C}_{P})}{\epsilon\alpha^{3}}\right)$.
As a result, the linear optimization based algorithm for Theorem 5.9 performs
better (in terms of asymptotic sample complexity) than the DP-oracle-learner
of Jagielski et al. (2018) which requires sample size
$\tilde{O}\left(\frac{|\mathcal{A}|^{3}\operatorname*{VC}(\mathcal{C}_{P})}{\epsilon\alpha^{3+r}}\right)$
for any $r>0$ provided that $\min_{a,y}\\{\hat{q}_{ay}\\}\leq\alpha^{(1+r)/2}$
where $\hat{q}_{ay}$ is the empirical estimate of $\mathbb{P}[A=a,Y=y]$.

Example 8.10 shows how to use Corollary 8.9 on specific smooth approximations
to the absolute value and maximum functions. Note that this is one of many
ways to apply smoothing and this specific version might not apply optimal
smoothing. Smoothing of non-smooth functions for specific tasks is an entire
research agenda (e.g., see (Bach et al., 2012; Lange et al., 2014) for smooth
approximations to the max and absolute value functions) and not the focus of
this research paper.

######  Example 8.10.

Suppose we have two groups and can obtain empirical estimates of the false
positive, false negative, and true positive rates of these groups for any
$c\in\mathcal{C}_{P}$ and fixed dataset of labeled examples
$D=\\{(\text{{x}}_{i},a_{i},y_{i})\\}_{i=1}^{n}\in(\mathcal{X}\times\\{1,2\\}\times\\{0,1\\})^{n}$.
The goal is to perform binary classification under $(\alpha,\eta)$ equalized
odds constraints. We let $\mathcal{C}_{P}$ be the set of single-parametric
threshold classifiers over the reals so that
$\operatorname*{VC}(\mathcal{C}_{P})=1$. The loss vector is

$\ell(c,D)=(\hat{FP}_{1}(c,D),\hat{FP}_{2}(c,D),\hat{FN}_{1}(c,D),\hat{FN}_{2}(c,D),\hat{TP}_{1}(c,D),\hat{TP}_{2}(c,D)).$

The “error” function $f$ can be computed as the linear function
$f(\ell(c,D))=\hat{FP}_{1}(c,D)+\hat{FP}_{2}(c,D)+\hat{FN}_{1}(c,D)+\hat{FN}_{2}(c,D)$
and so is Lipschitz, smooth.

Now, define a smooth approximation to the max function as
$\operatorname*{smax}^{\eta}(y_{1},\ldots,y_{n})=\frac{\sum_{i=1}^{n}y_{i}e^{\eta
y_{i}}}{\sum_{i=1}^{n}e^{\eta y_{i}}}$. Then if for all decisions
$c\in\mathcal{C}_{P}$ and for a fixed $\eta,D$,
$\operatorname*{smax}^{\eta}(|\hat{FP}_{1}(c,D)-\hat{FP}_{2}(c,D)|),|\hat{TP}_{1}(c,D)-\hat{TP}_{2}(c,D)|)$
is 1-Lipschitz, we can apply Corollary 8.9 to obtain the desired guarantees.

More generally, the possible empirical rates for any given dataset depends on
how complex the decision set $\mathcal{C}_{P}$ is. The decision set
$\mathcal{C}_{P}$ could represent all possible parameterizations of a specific
neural network architecture, all possible weights for a polynomial threshold
function to be used for classification, or a constant separator threshold
defined over the reals.

######  Remark 8.11.

We have shown how to apply our methods to satisfy certain statistical
definitions of algorithmic fairness and some convex performance measures of
the confusion matrix. There are potentially other use cases we have not
explored that we leave for future work.

##  9 Conclusion

In this paper, we have explored the problem of private fair optimization via a
reductions approach. We provided an $(\epsilon,0)$-differentially private
exponential sampling algorithm and an $(\epsilon,\delta)$-differentially
private linear optimization based algorithm as a solution. As a side-effect
perhaps, we introduce a class of bounded divergence linear optimizers, which
could be useful for solving more general (Lipschitz-continuous) multi-
objective problems. We also provide a lower bound on the excess risk (or
equivalently, on the sample complexity) for any $\epsilon$ or
$(\epsilon,\delta)$-differentially private algorithm that solves the
constrained group-objective optimization problem.

Our framework can also be used to solve model projection (Alghamdi et al.,
2020) for certain constraint sets constructed via linear inequalities.
Constructively showing connections between the model projection problem (for
certain $f$-divergences) and linear optimizers with divergence constraints is
left to future work. Furthermore, linear optimizers share the same form as a
Rectified Linear Unit (ReLU) used in deep learning. Showing constructive
equivalences, especially by delineating time/accuracy tradeoffs (Goel et al.,
2019), is left to future work.

##  10 Acknowledgements

Thanks to Salil Vadhan for providing detailed comments on this paper at
various stages of the project and to Cynthia Dwork, Adam Smith, and other
members of the Boston-Area Data Privacy group for comments that improved the
writing of this work. We are grateful to Shahab Asoodeh, Boaz Barak, Flavio du
Pin Calmon, Nicole Immorlica, Adam Tauman Kalai, Sanmi Koyejo, Ankur Moitra,
Jelani Nelson, and Chris Wiggins for illuminating discussions related to this
work. The Computational Social Science group at Facebook AI Research and
participants of the “Recent Themes in Resource Tradeoffs: Privacy, Fairness,
and Robustness” workshop at the University of Minnesota provided many helpful
comments and suggestions that improved the writing of this work. Finally, we
appreciate the guidance of the anonymous referees who helped to improve the
presentation of this work.

## References

  * Abowd [2018] John M. Abowd.  The u.s. census bureau adopts differential privacy.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’18, page 2867, New York, NY, USA, 2018. Association for Computing Machinery.  ISBN 9781450355520.  URL https://doi.org/10.1145/3219819.3226070.
  * Agarwal et al. [2018] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna M. Wallach.  A reductions approach to fair classification.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pages 60–69, 2018.
  * Agarwal et al. [2019] Alekh Agarwal, Miroslav Dudík, and Zhiwei Steven Wu.  Fair regression: Quantitative definitions and reduction-based algorithms.  In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , pages 120–129, 2019.  URL http://proceedings.mlr.press/v97/agarwal19d.html.
  * Alabi et al. [2018] Daniel Alabi, Nicole Immorlica, and Adam Tauman Kalai.  Unleashing linear optimizers for group-fair learning and optimization.  In _Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018._ , pages 2043–2066, 2018.  URL http://proceedings.mlr.press/v75/alabi18a.html.
  * Alghamdi et al. [2020] Wael Alghamdi, Shahab Asoodeh, Hao Wang, Flávio P. Calmon, Dennis Wei, and Karthikeyan Natesan Ramamurthy.  Model projection: Theory and applications to fair machine learning.  In _IEEE International Symposium on Information Theory, ISIT 2020, Los Angeles, CA, USA, June 21-26, 2020_ , pages 2711–2716. IEEE, 2020\.
  * Bach et al. [2012] Francis R. Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski.  Optimization with sparsity-inducing penalties.  _Foundations and Trends in Machine Learning_ , 4(1):1–106, 2012.  URL https://doi.org/10.1561/2200000015.
  * Ball et al. [2020] Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan.  Cryptography from information loss.  In _11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA_ , pages 81:1–81:27, 2020.
  * Bartlett et al. [2006] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe.  Convexity, classification, and risk bounds.  _Journal of the American Statistical Association_ , 101(473):138–156, 2006.  doi: 10.1198/016214505000000907.
  * Bassily et al. [2014] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014_ , pages 464–473, 2014.
  * Bennett et al. [1995] Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Ueli M. Maurer.  Generalized privacy amplification.  _IEEE Trans. Inf. Theory_ , 41(6):1915–1923, 1995.  URL https://doi.org/10.1109/18.476316.
  * Beygelzimer et al. [2009] Alina Beygelzimer, John Langford, and Bianca Zadrozny.  Tutorial summary: Reductions in machine learning.  In Andrea Pohoreckyj Danyluk, Léon Bottou, and Michael L. Littman, editors, _Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, Montreal, Quebec, Canada, June 14-18, 2009_ , volume 382 of _ACM International Conference Proceeding Series_ , page 12. ACM, 2009.
  * Blackwell [1956] David Blackwell.  An analog of the minimax theorem for vector payoffs.  _Pacific Journal of Mathematics_ , 6(1):1–8, 1956\.
  * Blumer et al. [1989] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth.  Learnability and the vapnik-chervonenkis dimension.  _J. ACM_ , 36(4):929–965, 1989.  URL https://doi.org/10.1145/76359.76371.
  * Bousquet and Elisseeff [2000] Olivier Bousquet and André Elisseeff.  Algorithmic stability and generalization performance.  In _Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS) 2000, Denver, CO, USA_ , pages 196–202, 2000.  URL https://proceedings.neurips.cc/paper/2000/hash/49ad23d1ec9fa4bd8d77d02681df5cfa-Abstract.html.
  * Brassard et al. [1986] Gilles Brassard, Claude Crépeau, and Jean-Marc Robert.  Information theoretic reductions among disclosure problems.  In _27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986_ , pages 168–173. IEEE Computer Society, 1986.  URL https://doi.org/10.1109/SFCS.1986.26.
  * Bubeck [2015] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Foundations and Trends in Machine Learning_ , 8(3-4):231–357, 2015.
  * Buolamwini and Gebru [2018] Joy Buolamwini and Timnit Gebru.  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In _Conference on Fairness, Accountability and Transparency, FAT 2018, 23-24 February 2018, New York, NY, USA_ , pages 77–91, 2018.  URL http://proceedings.mlr.press/v81/buolamwini18a.html.
  * Busa-Fekete et al. [2017] Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor.  Multi-objective bandits: Optimizing the generalized gini index.  In _Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017_ , pages 625–634, 2017.  URL http://proceedings.mlr.press/v70/busa-fekete17a.html.
  * Canonne et al. [2019] Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam D. Smith, and Jonathan Ullman.  The structure of optimal private tests for simple hypotheses.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019_ , pages 310–321, 2019.
  * Carlini et al. [2019] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In Nadia Heninger and Patrick Traynor, editors, _28th USENIX Security Symposium, USENIX Security 2019, Santa Clara, CA, USA, August 14-16, 2019_ , pages 267–284. USENIX Association, 2019.  URL https://www.usenix.org/conference/usenixsecurity19/presentation/carlini.
  * Cesa-Bianchi and Lugosi [2006] Nicolò Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge University Press, 2006.
  * Chaudhuri and Hsu [2011] Kamalika Chaudhuri and Daniel J. Hsu.  Sample complexity bounds for differentially private learning.  In _COLT 2011 - The 24th Annual Conference on Learning Theory, June 9-11, 2011, Budapest, Hungary_ , pages 155–186, 2011.  URL http://proceedings.mlr.press/v19/chaudhuri11a/chaudhuri11a.pdf.
  * Chaudhuri et al. [2011] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate.  Differentially private empirical risk minimization.  _Journal of Machine Learning Research_ , 12:1069–1109, 2011\.
  * Chervonenkis and Vapnik [1971] A. Ya. Chervonenkis and V. N. Vapnik.  On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities, 1971.  ISSN 0040-585X.
  * Choromanski and Malkin [2012] Krzysztof Choromanski and Tal Malkin.  The power of the dinur-nissim algorithm: breaking privacy of statistical and graph databases.  In _Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012_ , pages 65–76, 2012.  URL https://doi.org/10.1145/2213556.2213570.
  * Consortium et al. [2009] P3G Consortium, George Church, Catherine Heeney, Naomi Hawkins, Jantina de Vries, Paula Boddington, Jane Kaye, Martin Bobrow, and Bruce Weir.  Public access to genome-wide data: Five views on balancing research with privacy and protection.  _PLOS Genetics_ , 5(10):1–4, 10 2009.  URL https://doi.org/10.1371/journal.pgen.1000665.
  * Cormode et al. [2018] Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang.  Privacy at scale: Local differential privacy in practice.  In _Proceedings of the 2018 International Conference on Management of Data_ , SIGMOD ’18, page 1655–1658, New York, NY, USA, 2018. Association for Computing Machinery.  ISBN 9781450347037.  URL https://doi.org/10.1145/3183713.3197390.
  * Cuff and Yu [2016] Paul Cuff and Lanqing Yu.  Differential privacy as a mutual information constraint.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016_ , pages 43–54, 2016.
  * De [2012] Anindya De.  Lower bounds in differential privacy.  In Ronald Cramer, editor, _Theory of Cryptography_ , pages 321–338, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.  ISBN 978-3-642-28914-9.
  * Dinur and Nissim [2003] Irit Dinur and Kobbi Nissim.  Revealing information while preserving privacy.  In _Proceedings of the Twenty-second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems_ , PODS ’03, pages 202–210, New York, NY, USA, 2003. ACM.  ISBN 1-58113-670-6.
  * Donoho [2006] D.L. Donoho.  Compressed sensing.  _IEEE Transactions on Information Theory_ , 52(4):1289–1306, 2006.  doi: 10.1109/TIT.2006.871582.
  * Dwork and Lei [2009] Cynthia Dwork and Jing Lei.  Differential privacy and robust statistics.  In _Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009_ , pages 371–380, 2009.
  * Dwork and Roth [2014] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3-4):211–407, 2014.
  * Dwork et al. [2006] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings_ , pages 265–284, 2006.
  * Dwork et al. [2010] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan.  Boosting and differential privacy.  In _51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA_ , pages 51–60, 2010.
  * Dwork et al. [2012] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel.  Fairness through awareness.  In _Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012_ , pages 214–226, 2012.
  * Dwork et al. [2015] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth.  Preserving statistical validity in adaptive data analysis.  In _Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015_ , pages 117–126, 2015.
  * Ehrenfeucht et al. [1989] Andrzej Ehrenfeucht, David Haussler, Michael J. Kearns, and Leslie G. Valiant.  A general lower bound on the number of examples needed for learning.  _Inf. Comput._ , 82(3):247–261, 1989.  URL https://doi.org/10.1016/0890-5401(89)90002-3.
  * Ekstrand et al. [2018] Michael D. Ekstrand, Rezvan Joshaghani, and Hoda Mehrpouyan.  Privacy for all: Ensuring fair and equitable privacy protections.  In _Conference on Fairness, Accountability and Transparency, FAT 2018, 23-24 February 2018, New York, NY, USA_ , pages 35–47, 2018.  URL http://proceedings.mlr.press/v81/ekstrand18a.html.
  * Feldman and Vondrák [2019] Vitaly Feldman and Jan Vondrák.  High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.  In Alina Beygelzimer and Daniel Hsu, editors, _Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA_ , volume 99 of _Proceedings of Machine Learning Research_ , pages 1270–1279. PMLR, 2019\.  URL http://proceedings.mlr.press/v99/feldman19a.html.
  * Freund and Schapire [1997] Yoav Freund and Robert E. Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _J. Comput. Syst. Sci._ , 55(1):119–139, 1997\.  URL https://doi.org/10.1006/jcss.1997.1504.
  * Friedler et al. [2021] Sorelle A. Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian.  The (im)possibility of fairness: Different value systems require different mechanisms for fair decision making.  _Commun. ACM_ , 64(4):136–143, March 2021.  ISSN 0001-0782.  doi: 10.1145/3433949.  URL https://doi.org/10.1145/3433949.
  * Garfinkel et al. [2018] Simson L. Garfinkel, John M. Abowd, and Christian Martindale.  Understanding database reconstruction attacks on public data.  _ACM Queue_ , 16(5):50, 2018.  URL https://doi.org/10.1145/3291276.3295691.
  * Goel et al. [2019] Surbhi Goel, Sushrut Karmalkar, and Adam R. Klivans.  Time/accuracy tradeoffs for learning a relu with respect to gaussian marginals.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 8582–8591, 2019.
  * Hannan [1957] James Hannan.  Approximation to bayes risk in repeated play.  _Contributions to the Theory of Games, III, Ann. Math. Study Number 39_ , pages 97–139, 1957.
  * Hardt et al. [2016] Moritz Hardt, Eric Price, and Nati Srebro.  Equality of opportunity in supervised learning.  In _Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain_ , pages 3315–3323, 2016.  URL http://papers.nips.cc/paper/6374-equality-of-opportunity-in-supervised-learning.
  * Hazan [2016] Elad Hazan.  Introduction to online convex optimization.  _Found. Trends Optim._ , 2(3-4):157–325, 2016\.
  * Hébert-Johnson et al. [2018] Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum.  Multicalibration: Calibration for the (computationally-identifiable) masses.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pages 1944–1953, 2018.  URL http://proceedings.mlr.press/v80/hebert-johnson18a.html.
  * Hiranandani et al. [2019] Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, and Oluwasanmi O Koyejo.  Multiclass performance metric elicitation.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 9356–9365. Curran Associates, Inc., 2019.  URL http://papers.nips.cc/paper/9133-multiclass-performance-metric-elicitation.pdf.
  * Iyengar et al. [2019] R. Iyengar, J. P. Near, D. Song, O. Thakkar, A. Thakurta, and L. Wang.  Towards practical differentially private convex optimization.  In _2019 2019 IEEE Symposium on Security and Privacy (SP)_ , Los Alamitos, CA, USA, may 2019. IEEE Computer Society.  doi: 10.1109/SP.2019.00001.  URL https://doi.ieeecomputersociety.org/10.1109/SP.2019.00001.
  * Jaggi [2013] Martin Jaggi.  Revisiting frank-wolfe: Projection-free sparse convex optimization.  In _Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013_ , pages 427–435, 2013\.  URL http://jmlr.org/proceedings/papers/v28/jaggi13.html.
  * Jagielski et al. [2018] Matthew Jagielski, Michael J. Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi-Malvajerdi, and Jonathan Ullman.  Differentially private fair learning.  _CoRR_ , abs/1812.02696, 2018.  URL http://arxiv.org/abs/1812.02696.
  * Kairouz et al. [2017] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  The composition theorem for differential privacy.  _IEEE Trans. Inf. Theory_ , 63(6):4037–4049, 2017.  URL https://doi.org/10.1109/TIT.2017.2685505.
  * Kakade et al. [2009] Sham M. Kakade, Adam Tauman Kalai, and Katrina Ligett.  Playing games with approximation algorithms.  _SIAM J. Comput._ , 39(3):1088–1106, 2009.
  * Kalai and Vempala [2003] Adam Kalai and Santosh S. Vempala.  Efficient algorithms for online decision problems.  In _Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings_ , pages 26–40, 2003.
  * Karp [1972] Richard M. Karp.  _Reducibility among Combinatorial Problems_ , pages 85–103.  Springer US, Boston, MA, 1972.  URL https://doi.org/10.1007/978-1-4684-2001-2_9.
  * Kearns [1998] Michael J. Kearns.  Efficient noise-tolerant learning from statistical queries.  _J. ACM_ , 45(6):983–1006, 1998.  URL https://doi.org/10.1145/293347.293351.
  * Keener [2010] R.W. Keener.  _Theoretical Statistics: Topics for a Core Course_.  Springer Texts in Statistics. Springer New York, 2010.  ISBN 9780387938394.
  * Kifer et al. [2012] Daniel Kifer, Adam D. Smith, and Abhradeep Thakurta.  Private convex optimization for empirical risk minimization with applications to high-dimensional regression.  In _COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland_ , pages 25.1–25.40, 2012.  URL http://www.jmlr.org/proceedings/papers/v23/kifer12/kifer12.pdf.
  * Kilbertus et al. [2018] Niki Kilbertus, Adria Gascon, Matt Kusner, Michael Veale, Krishna Gummadi, and Adrian Weller.  Blind justice: Fairness with encrypted sensitive attributes.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 2630–2639, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.  URL http://proceedings.mlr.press/v80/kilbertus18a.html.
  * Kleinberg et al. [2017] Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan.  Inherent trade-offs in the fair determination of risk scores.  In Christos H. Papadimitriou, editor, _8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA_ , volume 67 of _LIPIcs_ , pages 43:1–43:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  URL https://doi.org/10.4230/LIPIcs.ITCS.2017.43.
  * Kleinberg et al. [2020] Jon M. Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Cass R. Sunstein.  Algorithms as discrimination detectors.  _Proc. Natl. Acad. Sci. USA_ , 117(48):30096–30100, 2020.  URL https://doi.org/10.1073/pnas.1912790117.
  * Koltchinskii and Panchenko [2000] Vladimir Koltchinskii and Dmitriy Panchenko.  Rademacher processes and bounding the risk of function learning.  In Evarist Giné, David M. Mason, and Jon A. Wellner, editors, _High Dimensional Probability II_ , pages 443–457, Boston, MA, 2000. Birkhäuser Boston.  ISBN 978-1-4612-1358-1.
  * Komarova and Nekipelov [2020] Tatiana Komarova and Denis Nekipelov.  Identification and formal privacy guarantees, 2020.
  * Lange et al. [2014] Mandy Lange, Dietlind Zühlke, Olaf Holz, and Thomas Villmann.  Applications of lp-norms and their smooth approximations for gradient based learning vector quantization.  In _22th European Symposium on Artificial Neural Networks, ESANN 2014, Bruges, Belgium, April 23-25, 2014_ , 2014.  URL http://www.elen.ucl.ac.be/Proceedings/esann/esannpdf/es2014-153.pdf.
  * Langford et al. [2006] John Langford, Roberto Oliveira, and Bianca Zadrozny.  Predicting conditional quantiles via reduction to classification.  In _UAI ’06, Proceedings of the 22nd Conference in Uncertainty in Artificial Intelligence, Cambridge, MA, USA, July 13-16, 2006_ , 2006.
  * Linial et al. [1991] Nathan Linial, Yishay Mansour, and Ronald L. Rivest.  Results on learnability and the vapnik-chervonenkis dimension.  _Inf. Comput._ , 90(1):33–49, 1991.  URL https://doi.org/10.1016/0890-5401(91)90058-A.
  * Littlestone [1987] Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  _Mach. Learn._ , 2(4):285–318, 1987.  URL https://doi.org/10.1007/BF00116827.
  * Manning et al. [2008] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze.  _Introduction to information retrieval_.  Cambridge University Press, 2008.
  * Marler and Arora [2004] R.T. Marler and J.S. Arora.  Survey of multi-objective optimization methods for engineering.  _Structural and Multidisciplinary Optimization_ , 26(6):369–395, Apr 2004.  ISSN 1615-1488.  doi: 10.1007/s00158-003-0368-6.  URL https://doi.org/10.1007/s00158-003-0368-6.
  * McAllester [1999] David A. McAllester.  Pac-bayesian model averaging.  In _Proceedings of the Twelfth Annual Conference on Computational Learning Theory, COLT 1999, Santa Cruz, CA, USA, July 7-9, 1999_ , pages 164–170, 1999.
  * McAllester [2003] David A. McAllester.  Simplified pac-bayesian margin bounds.  In _Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings_ , pages 203–215, 2003.
  * McSherry and Talwar [2007] Frank McSherry and Kunal Talwar.  Mechanism design via differential privacy.  In _48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings_ , pages 94–103, 2007.
  * Mironov [2017] Ilya Mironov.  Rényi differential privacy.  In _30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017_ , pages 263–275, 2017.
  * Narasimhan [2018] Harikrishna Narasimhan.  Learning with complex loss functions and constraints.  In _International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain_ , pages 1646–1654, 2018.  URL http://proceedings.mlr.press/v84/narasimhan18a.html.
  * Narasimhan et al. [2015] Harikrishna Narasimhan, Harish G. Ramaswamy, Aadirupa Saha, and Shivani Agarwal.  Consistent multiclass algorithms for complex performance measures.  In _Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015_ , pages 2398–2407, 2015\.  URL http://jmlr.org/proceedings/papers/v37/narasimhanb15.html.
  * Nesterov [2005] Yurii Nesterov.  Smooth minimization of non-smooth functions.  _Math. Program._ , 103(1):127–152, 2005.
  * Neyman et al. [1933] Jerzy Neyman, Egon Sharpe Pearson, and Karl Pearson.  Ix. on the problem of the most efficient tests of statistical hypotheses.  _Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character_ , 231(694-706):289–337, 1933.  doi: 10.1098/rsta.1933.0009.  URL https://royalsocietypublishing.org/doi/abs/10.1098/rsta.1933.0009.
  * Nguyen et al. [2005] XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan.  On divergences, surrogate loss functions, and decentralized detection.  _CoRR_ , abs/math/0510521, 2005.  URL http://arxiv.org/abs/math/0510521.
  * Nguyen et al. [2009] XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan.  On surrogate loss functions and f-divergences.  _The Annals of Statistics_ , 37(2):876 – 904, 2009.  doi: 10.1214/08-AOS595.  URL https://doi.org/10.1214/08-AOS595.
  * Rennie and Srebro [2005] Jason Rennie and Nathan Srebro.  Loss functions for preference levels: Regression with discrete ordered labels.  _Proceedings of the IJCAI Multidisciplinary Workshop on Advances in Preference Handling_ , 01 2005.
  * Sason and Verdú [2016] Igal Sason and Sergio Verdú.  f-divergence inequalities.  _IEEE Trans. Inf. Theory_ , 62(11):5973–6006, 2016.  doi: 10.1109/TIT.2016.2603151.  URL https://doi.org/10.1109/TIT.2016.2603151.
  * Shalev-Shwartz and Ben-David [2014] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press, 2014.
  * Shamir and Zhang [2013] Ohad Shamir and Tong Zhang.  Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes.  In _Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013_ , pages 71–79, 2013\.  URL http://jmlr.org/proceedings/papers/v28/shamir13.html.
  * Sheffet [2019] Or Sheffet.  Differentially private ordinary least squares.  _J. Priv. Confidentiality_ , 9(1), 2019.  URL https://doi.org/10.29012/jpc.654.
  * Shokri et al. [2017] R. Shokri, M. Stronati, C. Song, and V. Shmatikov.  Membership inference attacks against machine learning models.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , pages 3–18, 2017.  doi: 10.1109/SP.2017.41.
  * Steinke and Ullman [2015] Thomas Steinke and Jonathan Ullman.  Between pure and approximate differential privacy.  _CoRR_ , abs/1501.06095, 2015.  URL http://arxiv.org/abs/1501.06095.
  * Talwar et al. [2014] Kunal Talwar, Abhradeep Thakurta, and Li Zhang.  Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry.  _CoRR_ , abs/1411.5417, 2014.  URL http://arxiv.org/abs/1411.5417.
  * Talwar et al. [2015] Kunal Talwar, Abhradeep Thakurta, and Li Zhang.  Nearly optimal private LASSO.  In _Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada_ , pages 3025–3033, 2015.
  * Vadhan [2017] Salil P. Vadhan.  The complexity of differential privacy.  In _Tutorials on the Foundations of Cryptography._ , pages 347–450. 2017.
  * Valiant [1984] Leslie G. Valiant.  A theory of the learnable.  _Commun. ACM_ , 27(11):1134–1142, 1984.
  * Vapnik [2000] Vladimir Vapnik.  _The Nature of Statistical Learning Theory_.  Statistics for Engineering and Information Science. Springer, 2000.
  * Wang et al. [2018] Di Wang, Minwei Ye, and Jinhui Xu.  Differentially private empirical risk minimization revisited: Faster and more general.  _CoRR_ , abs/1802.05251, 2018.  URL http://arxiv.org/abs/1802.05251.
  * Wang et al. [2015] Hong Wang, Wei Xing, Kaiser Asif, and Brian Ziebart.  Adversarial prediction games for multivariate losses.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015.  URL https://proceedings.neurips.cc/paper/2015/file/dfa92d8f817e5b08fcaafb50d03763cf-Paper.pdf.
  * Wipf and Rao [2004] David P. Wipf and Bhaskar D. Rao.  L_0-norm minimization for basis selection.  In _Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, NIPS 2004, December 13-18, 2004, Vancouver, British Columbia, Canada]_ , pages 1513–1520, 2004.  URL https://proceedings.neurips.cc/paper/2004/hash/b1c00bcd4b5183705c134b3365f8c45e-Abstract.html.
  * Zhang [2006] Tong Zhang.  Information-theoretic upper and lower bounds for statistical estimation.  _IEEE Trans. Inf. Theory_ , 52(4):1307–1321, 2006.

##  Appendix A Some Inequalities and Advanced Composition Result

######  Lemma A.1 (Markov’s Inequality).

Let $Z$ be a non-negative random variable. Then for all $a\geq 0$,

$\mathbb{P}[Z\geq a]\leq\frac{\mathbb{E}[Z]}{a},$

where $\mathbb{E}[Z]=\int_{x=0}^{\infty}\mathbb{P}[Z\geq x]dx$.

######  Lemma A.2 (Cauchy-Schwarz Inequality).

For any two vectors $\mathbf{u},\mathbf{v}$ of an inner product space we have
that

$|\langle\mathbf{u},\mathbf{v}\rangle|\leq\mathopen{\|}\mathbf{u}\mathclose{\|}\mathopen{\|}\mathbf{v}\mathclose{\|}.$

######  Lemma A.3 (Jensen’s Inequality).

For any $t\in[0,1]$ and convex function
$f:\mathcal{X}\rightarrow{\mathbb{R}}$, the following holds:

$f(t\text{{x}}_{1}+(1-t)\text{{x}}_{2})\leq
tf(\text{{x}}_{1})+(1-t)f(\text{{x}}_{2}),$

for any $\text{{x}}_{1},\text{{x}}_{2}\in\mathcal{X}$.

######  Lemma A.4 (Advanced Composition (Dwork et al. [2010])).

For all $\epsilon,\delta,\bar{\delta}\geq 0$, the class of
$(\epsilon,\delta)$-differentially private mechanisms results in
$(\bar{\epsilon},k\delta+\bar{\delta})$-differential privacy under $k$-fold
adaptive composition for:

$\bar{\epsilon}=\epsilon\sqrt{2k\log(1/\bar{\delta})}+k\epsilon(e^{\epsilon}-1).$

A corollary of Lemma A.4 states that we can set
$\epsilon=\frac{\bar{\epsilon}}{2\sqrt{2k\log(1/\bar{\delta})}}$ to ensure
$(\bar{\epsilon},k\delta+\bar{\delta})$ differential privacy overall for
target privacy parameters $\bar{\epsilon}\in(0,1),\bar{\delta}\in(0,1]$.

##  Appendix B Projection-Free Convex Optimization using Frank-Wolfe

In previous sections, we presented linear optimization based algorithms to
solve the constrained group-objective optimization problem with and without
privacy. In this section, we present another linear optimization based
algorithm that is an adaptation of the Frank-Wolfe projection-free algorithm.
Algorithm 3 is the Frank-Wolfe algorithm presented in [Jaggi, 2013] which
allows for use of approximate linear optimizers to solve the subproblems in
each iteration $t\in[T]$. The original version of Frank-Wolfe only allowed for
exact linear optimizers.

Lemma B.2 presents the convergence guarantees of the algorithm after $k$
iterations in terms of the curvature constant of the function
$h:{\mathbb{R}}^{K}\rightarrow{\mathbb{R}}$ to be optimized (see Definition
B.1) and the accuracy of the linear optimizer oracle. We will rely on a
modified version of Algorithm 3 to solve the constrained group-objective
optimization problem (Definition 1.2).

The execution of Algorithm 3 in each iteration relies on the availability of
an approximate linear oracle of the form
$\min_{\hat{s}\in\mathcal{C}}\langle\hat{s},\nabla h(y^{(t)})\rangle$. In
[Alabi et al., 2018], the authors provide an algorithm that can optimize any
Lipschitz-continuous function $h:{\mathbb{R}}^{K}\rightarrow{\mathbb{R}}$
using an approximate linear optimizer as an oracle solver.

1Let $y^{(0)}\in\mathcal{C}$

2for  _$t=0,\dots,T$_ do

3 Let $\gamma=\frac{2}{t+2}$

4 Find $s\in\mathcal{C}$ s.t. $\langle s,\nabla
h(y^{(t)})\rangle\leq\min_{\hat{s}\in\mathcal{C}}\langle\hat{s},\nabla
h(y^{(t)})\rangle+\frac{1}{2}\rho\gamma C_{h}$

5 Update $y^{(t+1)}=(1-\gamma)y^{(t)}+\gamma s$

6

Algorithm 3 Frank-Wolfe algorithm [Jaggi, 2013]

For the results in this paper that rely on solving approximate linear
subproblems, $y^{(t)}$ in Algorithm 3 would correspond to the $K$-dimensional
loss vector $\ell(c,D)\in[0,1]^{K}$ defined for a decision
$c\in\mathcal{C}_{P}$ on dataset $D$ of size $n$.

######  Definition B.1.

The curvature constant $C_{h}$ of a convex and differentiable function
$h:{\mathbb{R}}^{K}\rightarrow{\mathbb{R}}$, with respect to a compact domain
$\mathcal{C}$ is defined as

$C_{h}=\sup_{x,s\in\mathcal{C},\gamma\in[0,1],y=x+\gamma(s-x)}\frac{2}{\gamma^{2}}\left(h(y)-h(x)-\langle
y-x,\nabla h(x)\rangle\right),$

where $\nabla h$ is the gradient of the function $h$.

######  Lemma B.2.

Let $h:\mathcal{C}\rightarrow{\mathbb{R}}$ be any convex function, then using
the Frank-Wolfe algorithm (Algorithm 3), we have that for any $t\geq 1$ and
iterates $y^{(t)},$

$h(y^{(t)})-h(y^{*})\leq\frac{2C_{h}}{t+2}(1+\rho),$

where $y^{*}\in\operatorname*{argmin}_{y\in\mathcal{C}}h(y)$, $\rho\geq 0$ is
the accuracy to which the internal linear subproblems are solved, and $C_{h}$
is the curvature constant of the function $h$.

######  Lemma B.3.

Let $h$ be a convex and differentiable Lipschitz-continuous function with
gradient $\nabla h$ w.r.t. some norm $\mathopen{\|}\cdot\mathclose{\|}$ over
domain $\mathcal{C}$. If $\nabla h$ has Lipschitz constant $\beta_{h}>0$, then

$C_{h}\leq\operatorname*{diam}_{\mathopen{\|}\cdot\mathclose{\|}}(\mathcal{C})^{2}\beta_{h},$

where $\operatorname*{diam}_{\mathopen{\|}\cdot\mathclose{\|}}(\mathcal{C})$
is the diameter of $\mathcal{C}$.

Now we describe how to solve constrained group objective optimization using
the Frank-Wolfe algorithm as opposed to the algorithm of Alabi et al. [2018].

###  B.1 Frank-Wolfe Algorithm for Constrained Group-Objective Optimization

In this section, we present a projection-free algorithm based on Frank-Wolfe
that solves the constrained group-objective optimization problem without
privacy considerations.

In each iteration $t\in[T]$, Algorithm 4 solves the following linear sub-
problem

$c_{t+1}=\operatorname*{argmin}_{c\in\mathcal{C}_{P}}\langle\,\,(\nabla
f(\ell(c_{t},D))+G\cdot\mathds{1}[g(\ell(c_{t},D))\geq 0]\cdot\nabla
g(\ell(c_{t},D))),\ell(c,D)\,\,\rangle,$

and then “moves” towards $c_{t+1}$ by a multiplicative factor of
$\frac{2}{t+2}$. We show that after
$T=O\left(\frac{K\sqrt{K}}{\alpha^{2}}\log\frac{K\sqrt{K}}{\alpha^{2}}\right)$
iterations we will get a decision $\hat{c}$ that is within $\alpha$ (in terms
of $f,g$) of the optimal decision
$c^{*}\in\operatorname*{argmin}_{c\in\mathcal{C}_{P}:g(\ell(c,D))\leq
0}f(\ell(c,D))$. The function $\text{Unif}(\\{c_{1},\ldots,c_{T}\\})$ returns
$\hat{c}$ that predicts with decision $c_{i}$ with probability $\frac{1}{T}$
for any $i\in[T]$.

1

Input:
$\operatorname*{argmin}_{\mathcal{C}_{P}}\langle\cdot,\cdot\rangle,T,\ell,\nabla
f,\nabla g,D\in(\mathcal{X}\times\mathcal{A}\times\mathcal{Y})^{n},G$

2

3

4Pick any decision $c\in\mathcal{C}_{P}$ as $c_{1}$ with $l_{1}(D)=\ell(c,D)$

5

6for  _$t=1,\ldots,T-1$_ do

7

8
$c_{t+1}=\operatorname*{argmin}_{c\in\mathcal{C}_{P}}\langle\,\,\ell(c,D),(\nabla
f(\ell(c_{t},D))+G\cdot\mathds{1}[g(\ell(c_{t},D))\geq 0]\cdot\nabla
g(\ell(c_{t},D)))\,\,\rangle$

9
$l_{t+1}(D)=\left(1-\frac{2}{t+2}\right)l_{t}(D)+\frac{2}{t+2}\ell(c_{t+1},D)$

10

11

return $\hat{c}=\text{Unif}(\\{c_{1},\ldots,c_{T}\\})$

Algorithm 4 Frank-Wolfe algorithm for Constrained Group-Objective Convex
Optimization.

######  Lemma B.4.

Suppose we are given convex, smooth functions
$f,g:[0,1]^{K}\rightarrow{\mathbb{R}}$ and loss function
$\ell:\mathcal{C}_{P}\times(\mathcal{X}\times\mathcal{A}\times\mathcal{Y})^{n}\rightarrow[0,1]^{K}$.
Then for any setting of $G>0,T\geq 3$, Algorithm 4 returns a decision
$\hat{c}\in\mathcal{C}_{P}$ with the following guarantee:

$\mathbb{E}[f(\ell(\hat{c},D))]\leq
f(\ell(c^{*},D))+\frac{2K(\beta_{f}+G\beta_{g})\log
T}{T},\quad\quad\mathbb{E}[g(\ell(\hat{c},D))]\leq\frac{2K(\beta_{f}+G\beta_{g})\log
T}{T}\cdot\frac{1}{G}+\frac{\sqrt{K}}{G},$

where $c^{*}\in\operatorname*{argmin}_{c\in\mathcal{C}_{P}:g(\ell(c,D))\leq
0}f(\ell(c,D))$ is the best decision in the feasible set $\mathcal{C}_{P}$,
$D$ is a dataset of size $n$, $\beta_{f}$ is the smoothness parameter of the
function $f$ and $\beta_{g}$ is the smoothness parameter of the function $g$.
This result holds assuming access to a linear optimizer oracle.

###### Proof.

The intuition is to optimize w.r.t. a “new” convex, smooth function
$h(\ell(c,D))=f(\ell(c,D))+G\cdot\max(0,g(\ell(c,D)))$ for any
$c\in\mathcal{C}_{P}$ and dataset $D$. We rely on the primal convergence
guarantees of the Frank-Wolfe algorithm. By Lemma B.2, we have that in
iteration $t\geq 1$, the following holds:

$h(\ell(c_{t},D))\leq h(\ell(c^{*},D))+\frac{2C_{h}}{t+2},$

where $C_{h}$ is the curvature constant of $h$. And by Lemma B.3, we have
$C_{h}\leq K(\beta_{f}+G\beta_{g})$ where $(\beta_{f}+G\beta_{g})$ is the
smoothness parameter of the function $h$. As a result we have that
$h(\ell(c_{t},D))\leq h(\ell(c^{*},D))+\frac{2K(\beta_{f}+G\beta_{g})}{t+2}$.

Then by Jensen’s inequality (Lemma A.3) and convexity of $h\circ\ell$, we have

$\displaystyle\mathbb{E}_{c\sim\\{c_{i}\\}_{i=1}^{T}}[h(\ell(c,D))]$
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}h(\ell(c_{t},D))$ (14)
$\displaystyle\leq
h(\ell(c^{*},D))+\frac{2K(\beta_{f}+G\beta_{g})}{T}\left(\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\ldots+\frac{1}{T+2}\right)$
(15) $\displaystyle\leq h(\ell(c^{*},D))+\frac{2K(\beta_{f}+G\beta_{g})\log
T}{T}$ (16)

where we used that the harmonic number $H_{T}$ is upper bounded by $\log T+1$
and that $\frac{1}{T+1}+\frac{1}{T+2}<1/2$ for $T\geq 3$.

We apply Lemma 4.1 to obtain that $\mathbb{E}[f(\ell(\hat{c},D))]\leq
f(\ell(c^{*},D))+\frac{2K(\beta_{f}+G\beta_{g})\log T}{T}$ and
$\mathbb{E}[g(\ell(\hat{c},D))]\leq\frac{2K(\beta_{f}+G\beta_{g})\log
T}{T}\cdot\frac{1}{G}+\frac{\sqrt{K}}{G}$. ∎

######  Corollary B.5.

Suppose we are given convex, smooth functions
$f,g:[0,1]^{K}\rightarrow{\mathbb{R}}$ and loss function
$\ell:\mathcal{C}_{P}\times(\mathcal{X}\times\mathcal{A}\times\mathcal{Y})^{n}\rightarrow[0,1]^{K}$.
Let $\beta_{f},\beta_{g}$ be the Lipschitz constants of the gradients of $f,g$
respectively. Then for any setting of $T\geq 3,\alpha>0$, Algorithm 4 returns
a decision $\hat{c}\in\mathcal{C}_{P}$ with the following guarantee:

$\mathbb{E}[f(\ell(\hat{c},D))]\leq f(\ell(c^{*},D))+\alpha,\text{ and
}\mathbb{E}[g(\ell(\hat{c},D))]\leq\alpha,$

provided that $G\geq\frac{\alpha+\sqrt{K}}{\alpha}$ and
$T\geq\frac{2K(\beta_{f}+G\beta_{g})}{\alpha}\log\frac{2K(\beta_{f}+G\beta_{g})}{\alpha}$
where $c^{*}\in\operatorname*{argmin}_{c\in\mathcal{C}_{P}:g(\ell(c,D))\leq
0}f(\ell(c,D))$ is the best decision in the feasible set $\mathcal{C}_{P}$,
$D$ is a dataset of size $n$, $\beta_{f}$ is the smoothness parameter of the
function $f$ and $\beta_{g}$ is the smoothness parameter of the function $g$.
This result holds assuming access to a linear optimizer oracle.

###### Proof.

The corollary follows by applying Lemmas 4.2 and B.4 where we set
$G\geq\frac{\alpha+\sqrt{K}}{\alpha}$ and

$T\geq\frac{2K(\beta_{f}+G\beta_{g})}{\alpha}\log\frac{2K(\beta_{f}+G\beta_{g})}{\alpha}$

in Algorithm 4. ∎

We adapted the Frank-Wolfe algorithm to solve the constrained group-objective
optimization problem (via calls to a linear optimizer). Given the versatility
of (stochastic) gradient descent, we could also solve the problem via the use
of gradient descent. For example, Theorem 3.7 from [Bubeck, 2015] gives
guarantees for projected gradient descent optimization of convex, smooth
functions. And Theorem 2 from Shamir and Zhang [2013] gives guarantees for
convex (but not necessarily smooth) functions.

##  Appendix C Using a Private Cost Sensitive Classification Oracle
$\operatorname*{CSC}_{\epsilon^{\prime}}$

Agarwal et al. [2018] present an exponentiated gradient algorithm for fair
classification. Jagielski et al. [2018] essentially modify this algorithm,
making it differentially private, and term the new algorithm DP-oracle-
learner. DP-oracle-learner satisfies $(\epsilon,\delta)$-differential privacy
relying on a private cost sensitive classification oracle
$\operatorname*{CSC}_{\epsilon^{\prime}}(\mathcal{H})$ in each iteration where
$\epsilon^{\prime}=\frac{\epsilon}{4\sqrt{T\log(1/\delta)}}$ and $\mathcal{H}$
is the hypothesis class to be learned.

DP-oracle-learner solves the $\gamma$-fair empirical risk minimization (ERM)
problem given by:

$\min_{Q\in\Delta(\mathcal{H})}\hat{\mathrm{err}}(Q)$
s.t. $\forall\,0\neq a\in\mathcal{A}$:
$\Delta\hat{FP}_{a}(Q)=|\hat{FP}_{a}(Q)-\hat{FP}_{0}(Q)|\leq\gamma$,
$\Delta\hat{TP}_{a}(Q)=|\hat{TP}_{a}(Q)-\hat{TP}_{0}(Q)|\leq\gamma$

where $\hat{FP}_{a}(Q),\hat{TP}_{a}(Q)$ are empirical estimates of
$FP_{a}(Q)=\mathbb{P}_{(x,y,a)}[Q(x)=1|A=a,y=0]$,
$TP_{a}(Q)=\mathbb{P}_{(x,y,a)}[Q(x)=1|A=a,y=1]$ respectively and group 0 is
used as an anchor. $\mathcal{A}$ is the set of labels for all
protected/sensitive attributes and $A$ is the random variable over
$\mathcal{A}$.

Agarwal et al. [2018] solve the following specific Lagrangian min-max problem:

$\min_{Q\in\Delta(\mathcal{H})}\max_{\bm{\lambda}\in\Lambda}L(Q,\bm{\lambda})=\hat{\mathrm{err}}(Q)+\bm{\lambda}^{T}\hat{\bm{r}}(Q),$

where $\Delta(\mathcal{H})$ is the set of all randomized classifiers that can
be obtained by hypotheses in $\mathcal{H}$, $\hat{\bm{r}}(Q)$ is a vector
representing the fairness violations of the classifier $Q$ across all groups,
$\bm{\lambda}\in\Lambda=\\{\bm{\lambda}:\mathopen{\|}\bm{\lambda}\mathclose{\|}_{1}\leq
B\\}$, and the bound $B$ is chosen to ensure convergence.

Now we state a main theorem from [Jagielski et al., 2018].

######  Theorem C.1 (Theorem 4.4 from [Jagielski et al., 2018]).

Let $(\tilde{Q},\tilde{\bm{\lambda}})$ be the output of DP-oracle-learner, an
$(\epsilon,\delta)$-differentially private algorithm, in [Jagielski et al.,
2018] and let $Q^{*}$ be a solution to the non-private $\gamma$-fair ERM
problem (see above definition). Then with probability at least $0.99,$

$\hat{\mathrm{err}}(\tilde{Q})\leq\hat{\mathrm{err}}(Q^{*})+2\nu,$

and for all $a\neq 0$,

$\Delta\hat{FP}_{a}(\tilde{Q})\leq\gamma+\frac{1+2\nu}{B},$
$\Delta\hat{TP}_{a}(\tilde{Q})\leq\gamma+\frac{1+2\nu}{B},$

where
$\nu=\tilde{O}\left(\frac{B}{\min_{a,y}\hat{q}_{ay}}\sqrt{\frac{|\mathcal{A}|\cdot\operatorname*{VC}(\mathcal{H})}{n\epsilon}}\right),$
$n$ is the number of training examples
$\\{(\text{{x}}_{i},a_{i},y_{i})\\}^{n}_{i=1}$ fed to the Algorithm,
$\operatorname*{VC}(\mathcal{H})$ is the VC dimension of $\mathcal{H}$, and
$\hat{q}_{ay}$ is an empirical estimate for $\mathbb{P}[A=a,Y=y]$.

As is done in their paper, to get rid of the algorithmic-specific dependence
on the bound $B$ (for example, in Theorem 4.6 of their paper), we set
$B=|\mathcal{A}|$.

######  Corollary C.2.

Let $(\tilde{Q},\tilde{\bm{\lambda}})$ be the output of Algorithm 3, an
$(\epsilon,\delta)$-differentially private algorithm, in [Jagielski et al.,
2018] and let $Q^{*}$ be a solution to the non-private $\alpha$-fair ERM
problem (see above definition) where
$\min_{a,y}\\{\hat{q}_{ay}\\}\leq\alpha^{(1+r)/2}$ for any $r>0$. Then with
probability at least 9/10, in order to solve the ERM problem with classifier
error $\alpha=(\hat{\mathrm{err}}(\tilde{Q})-\hat{\mathrm{err}}(Q^{*}))$ and
maximum fairness violation of
$\alpha=\max_{a\in\mathcal{A}}\max(\Delta\hat{FP}_{a}(\tilde{Q}),\Delta\hat{TP}_{a}(\tilde{Q}))$,
we could use training examples of size

$n=\tilde{O}\left(\frac{|\mathcal{A}|^{3}\cdot\operatorname*{VC}(\mathcal{H})}{\epsilon\alpha^{3+r}}\right).$

###### Proof.

Set $\min_{a,y}\\{\hat{q}_{ay}\\}\leq\alpha^{(1+r)/2}$ in Theorem C.1. ∎

Corollary C.2 is obtained directly from Theorem C.1 by solving for $n$ in
terms of the excess risk and will be used as the point of comparison to
compare our work to the work of Jagielski et al. [2018] for solving the
$\alpha$-fair ERM problem (for the Equalized Odds problem) with classifier
error of $\alpha$ with probability at least 9/10. Further note that
$K=O(|\mathcal{A}|)$ is the number of groups (in terminology used in other
parts of this paper). A result of this corollary is that to solve the
$\textrm{CGOO}(\mathcal{C}_{P},n,K,f,g,\ell,D,\alpha)$ problem when the
constraint is to satisfy $\alpha$-equalized odds, we need sample size
$n=\tilde{O}\left(\frac{|\mathcal{A}|^{3}\cdot\operatorname*{VC}(\mathcal{H})}{\epsilon\alpha^{3+r}}\right)$.
In comparison, using a generic implementation of the private oracle
$\operatorname*{LOPT}_{\epsilon,\delta}$, we need sample size
$n=\tilde{O}\left(\frac{|\mathcal{A}|^{4}\cdot\operatorname*{VC}(\mathcal{H})}{\epsilon\alpha^{3}}\right)$
which is asymptotically better (in terms of the accuracy parameter $\alpha>0$)
for all $r>0$.

Note that according to Assumption C.1 in [Jagielski et al., 2018], the
$\operatorname*{CSC}(\mathcal{H})$ oracle and its private counterpart are
often implemented via learning heuristics.