Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimization

Understand

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.