"Information Complexity of Stochastic Convex Optimization" - Idan Attias, Talks at TTIC

Originally presented on: Friday, September 20th, 2024 at 10:30am CT, TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 530
Title: "Information Complexity of Stochastic Convex Optimization: Applications to Generalization, Memorization and Privacy"
Speaker: Idan Attias, IDEAL Institute
Abstract:
Despite intense study, the relationship between generalization and memorization in machine learning has yet to be fully characterized. Classically, ideal learning algorithms would primarily extract relevant information from their training data, avoiding memorization of irrelevant information. This intuition is supported by theoretical work demonstrating the benefits of limited memorization for strong generalization. This intuition, however, is challenged by the success of modern overparameterized deep neural networks. These models often achieve high test accuracy despite memorizing a significant number of training data. Recent studies suggest that memorization plays a more complex role in generalization than previously thought: memorization might even be necessary for good generalization.
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 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.
#artificialintelligence #machinelearning #algorithm #computervision #robotics #research