Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization

Understand

In this work, we investigate the interplay between memorization and learning in the context of \emph{stochastic convex optimization} (SCO).

• We define memorization via the information a learning algorithm reveals about its training data points.
• We then quantify this information using the framework of conditional mutual information (CMI) proposed by Steinke and Zakynthinou (2020).
• Our main result is a precise characterization of the tradeoff between the accuracy of a learning algorithm and its CMI, answering an open question posed by Livni (2023).