  Despite being highly over-parametrized, and having the ability to fully
interpolate the training data, deep networks are known to generalize well to
unseen data. It is now understood that part of the reason for this is that the
training algorithms used have certain implicit regularization properties that
ensure interpolating solutions with "good" properties are found. This is best
understood in linear over-parametrized models where it has been shown that the
celebrated stochastic gradient descent (SGD) algorithm finds an interpolating
solution that is closest in Euclidean distance to the initial weight vector.
Different regularizers, replacing Euclidean distance with Bregman divergence,
can be obtained if we replace SGD with stochastic mirror descent (SMD).
Empirical observations have shown that in the deep network setting, SMD
achieves a generalization performance that is different from that of SGD (and
which depends on the choice of SMD's potential function. In an attempt to begin
to understand this behavior, we obtain the generalization error of SMD for
over-parametrized linear models for a binary classification problem where the
two classes are drawn from a Gaussian mixture model. We present simulation
results that validate the theory and, in particular, introduce two data models,
one for which SMD with an $\ell_2$ regularizer (i.e., SGD) outperforms SMD with
an $\ell_1$ regularizer, and one for which the reverse happens.
