Скачать с ютуб Idan Attias - Information Complexity of Stochastic Convex Optimization: в хорошем качестве

Idan Attias - Information Complexity of Stochastic Convex Optimization:

Presented on Thursday, May 16th, 2024, 10:30 AM, room B220 Speaker Idan Attias (BGU) Title Information Complexity of Stochastic Convex Optimization: Applications to Generalization, Memorization and Privacy Abstract: We investigate the interplay between memorization and learning in the context of stochasticconvex optimization (SCO). We define memorization via the information a learning algorithm revealsabout its training data points. We then quantify this information using the framework of conditionalmutual information (CMI) proposed by Steinke and Zakynthinou [SZ20]. Our main result is a precisecharacterization of the tradeoff between the accuracy of a learning algorithm and its CMI, answering anopen question posed by Livni [Liv23]. We show that, in the L2 Lipschitz–bounded setting and understrong 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 bydesigning an adversary capable of accurately identifying a significant fraction of the training samples inspecific SCO problems. Finally, we enumerate several implications of our results, such as a limitation ofgeneralization bounds based on CMI and the incompressibility of samples in SCO problems. Bio: Idan is a PhD student advised by Aryeh Kontorovich and Yishay Mansour. He will start a postdoctoral position this fall at IDEAL (NSF program), hosted by Lev Reyzin and Avrim Blum. His primary research interests lie in the foundations of machine learning theory and data-driven sequential decision-making, and its intersection with game theory, optimization, statistics, private data analysis, causal inference, and information theory. Relevant links: You can watch previous talks in Panopto and on our YouTube channel. Future lectures are published on our website and google calendar. If you want to get email updates about the next talks, please subscribe to our mailing list.