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

作     者：Attias, Idan Dziugaite, Gintare Karolina Haghifam, Mahdi Livni, Roi Roy, Daniel M. 

作者机构：Department of Computer Science Ben-Gurion University Vector Institute Google DeepMind United Kingdom Khoury College of Computer Sciences Northeastern University United States Department of Electrical Engineering Tel Aviv University Department of Statistical Sciences University of Toronto Vector Institute Canada 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Stochastic systems 

摘      要：In this work, we investigate the interplay between memorization and learning in the context of 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 [SZ20]. 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 [Liv23]. We show that, in the L2 Lipschitz–bounded setting and under strong convexity, every learner with an excess error Ε has CMI bounded below by Ω(1/Ε2) and Ω(1/Ε), respectively. We further demonstrate the essential role of memorization in learning problems in SCO by designing an adversary capable of accurately identifying a significant fraction of the training samples in specific SCO problems. Finally, we enumerate several implications of our results, such as a limitation of generalization bounds based on CMI and the incompressibility of samples in SCO problems. Copyright © 2024, The Authors. All rights reserved.