  In contemporary deep learning practice, models are often trained to near zero
loss i.e. to nearly interpolate the training data. However, the number of
parameters in the model is usually far more than the number of data points $n$,
the theoretical minimum needed for interpolation: a phenomenon referred to as
overparameterization. In an interesting piece of work that contributes to the
considerable research that has been devoted to understand overparameterization,
Bubeck and Sellke showed that for a broad class of covariate distributions
(specifically those satisfying a natural notion of concentration of measure),
overparameterization is necessary for robust interpolation i.e. if the
interpolating function is required to be Lipschitz. However, their robustness
results were proved only in the setting of regression with square loss. In
practice, however many other kinds of losses are used, e.g. cross entropy loss
for classification. In this work, we generalize Bubeck and Selke's result to
Bregman divergence losses, which form a common generalization of square loss
and cross-entropy loss. Our generalization relies on identifying a
bias-variance type decomposition that lies at the heart of the proof and Bubeck
and Sellke.
