Average Stability is Invariant to Data Preconditioning. Implications to
  Exp-concave Empirical Risk Minimization
  We show that the average stability notion introduced by
\cite{kearns1999algorithmic, bousquet2002stability} is invariant to data
preconditioning, for a wide class of generalized linear models that includes
most of the known exp-concave losses. In other words, when analyzing the
stability rate of a given algorithm, we may assume the optimal preconditioning
of the data. This implies that, at least from a statistical perspective,
explicit regularization is not required in order to compensate for
ill-conditioned data, which stands in contrast to a widely common approach that
includes a regularization for analyzing the sample complexity of generalized
linear models. Several important implications of our findings include: a) We
demonstrate that the excess risk of empirical risk minimization (ERM) is
controlled by the preconditioned stability rate. This immediately yields a
relatively short and elegant proof for the fast rates attained by ERM in our
context. b) We strengthen the recent bounds of \cite{hardt2015train} on the
stability rate of the Stochastic Gradient Descent algorithm.
