Games in Machine Learning

Dear all, 

In the second half of next week's lecture (starting at 15h), we will have Manolis Zampetakis who will talk about the complexity of min-max optimization; see details below. Manolis is a great researcher always working on interesting and challenging questions, and we did not cover in the course the work he'll present, so I highly recommend you join. 
Please note we will start at our usual time in person, and the guest lecture will be streamed in the lecture room (for those of you joining remotely use 'zoom link (tatjana)' in the materials tab).

Title: The Complexity of Constrained Min-Max Optimization

Abstract:

Despite its important applications in Machine Learning, min-max optimization of objective functions that are nonconvex-nonconcave remains elusive. We show that an approximate local min-max point of large enough approximation is guaranteed to exist, but finding one such point is PPAD-complete. The same is true of computing an approximate fixed point of the (Projected) Gradient Descent/Ascent update dynamics.

An important byproduct of our proof is to establish an unconditional hardness result in the Nemirovsky-Yudin oracle optimization model. In particular, we show that, given oracle access to some function and its gradient, every algorithm that finds an approximate local min-max point needs to make a number of queries that is exponential in the dimension or the accuracy. This comes in sharp contrast to minimization problems, where finding approximate local minima in the same setting can be done with Projected Gradient Descent polynomially many queries. Our result is the first to show an exponential separation between these two fundamental optimization problems in the oracle model.

Joint work with Constantinos Daskalakis and Stratis Skoulakis.

Short-Bio:

Manolis Zampetakis is currently an Assistant Professor at the Computer Science Department of Yale University. Before that, he was a post-doctoral researcher at the EECS Department of UC Berkeley working with Michael Jordan. He received his PhD from the EECS Department at MIT where he was advised by Constantinos Daskalakis. He has been awarded the Google PhD Fellowship and the ACM SIGEcom Doctoral Dissertation Award. He works on the foundations of machine learning (ML), statistics, and data science, with a focus on statistical analysis from biased data, optimization methods in multi-agent environments, and convergence properties of popular heuristic methods.

Paper: https://arxiv.org/abs/2009.09623

Dear all,

Project 2: This is a kind reminder to submit a draft of Project 2 by end of today.

Please note that the draft will not be graded. However, at the very least, please submit a PDF that includes the title and your names. The more polished the draft is, the better. This will help us to schedule the final presentations.

Project 1: We would like to apologize for the delay in grading Project 1. We can confirm that all of the properly submitted projects have achieved a passing grade, but we will need a few more days to finalize the grades.

Dear students,  

Regrettably, due to logistical constraints (due to the snowfall and earlier appointments), we cannot give the GML lecture in person tomorrow.

Having in mind the advantages of in-person lectures and discussions, we are rescheduling tomorrow's lecture to Thursday at 4 PM, in the same lecture hall.
 

Looking forward to seeing you on Thursday,
Tatjana Chavdarova

Dear students,

Several of you have reached out that you couldn't attend the lectures due to scheduling conflicts with other courses. In response, we will offer either additional sessions, recordings, or lecture summaries between the end of the courses and the exam. Feel free to email us with specific requests regarding which lectures or material you would like us to review.

It's important to note, however, that the deadline for completing the first project remains unchanged. We have extended the first project application deadline to 23:59 on December 23rd, 2023, and the submission deadline is 23:59 on December 28th, 2023.
 

Best regards,
Tatjana

Dear all,

Tomorrow we will have an exercise session from 13h30 -15h over Zoom. You can use this opportunity to also consult about the topic for your second project.

You will find the Zoom link under the materials tab.

If you cannot make it at that time and/or you prefer consulting in person, please send me an email, and we will schedule a meeting time for Friday at the C0 building.

best,
tatjana

 

Dear all,

If you've already applied for the first project:

• You should have received the assignment for the first project. Please edit directly the Colab without creating a copy.
• Please be aware that a Gmail account is required for editing the designated Colab. If you don't have one, kindly create a temporary account and share the details with us, following the instructions provided when we shared your designated Colab.

If you haven't applied yet but plan to do so:

• It is advisable to apply sooner, as it might take us several days to send you the designated Colab. The registration link for the project can be found in the materials tab.
   

Wishing you a pleasant rest of the week,
Tatjana

Dear students,

We are offering the first online exercise session/office hour this week on Thursday, 13.30h (the link will be added under 'materials').

You are cordially invited to ask any questions you may have, especially about the first part (optimization), but of course also about the more recent content.

(Note that the structure or content will not be different from the 'live' session offered on Tuesdays. It is just an opportunity for people who cannot attend on Tuesdays to ask questions).

The zoom link for tomorrow's lecture is again "Zoom link (tatjana)."

Dear students,

Thank you for registering for the GML (Games in Machine Learning) course.
We will have our first lecture tomorrow, Tuesday (24.10.2023), at 14:15.

Place: in CISPA lecture hall. E9.1 (CISPA building), room 0.05 (main lecture room)
Zoom link: visible for registered students