Lunch In Theory This Thursday (12:00 PM, 04/02, GCS 302c)

[Devansh Gupta]

Hi all,

Please join us for Lunch in Theory this Thursday, 04/02 at 12:00 PM in GCS 302c. This week we have Yue Wu giving a talk this week.

Reminder: Please bring your own lunch, as lunch will not be provided.

Best,

Devansh

[Devansh Gupta]

Please find the talk title and abstract attached.

See you all there!

Best,

Devansh

Title: Living on the Edge (of Stability): Why "Too Large" Step Sizes are Actually Good

Abstract: 

In the old-school optimization theory analysis of Gradient Descent (GD), as long as the step size is small enough, GD enjoys smooth, monotonic descent to the minimum. The math is clean, and theoreticians are happy.

Unfortunately, modern deep learning does not care about our feelings. The step sizes are often too large for the sharpness of the loss function. In this week's Theory Lunch, we are going to review a series of work about what happens when step sizes are "too large." 

We will look at how non-monotonic, realistic GD trains modern neural networks at the "Edge of Stability." We will see how large-step-size GD causes oscillations that self-stabilize and converge towards a flatter minimum.

We will also extend the classical, convex setting to show that intentionally violating the descent lemma is mathematically optimal. We'll look at how GD's sample complexity can be improved just by occasionally using massive step sizes, and how this can be analyzed as a 2-player game.

[Devansh Gupta]

Please find the zoom link attached: https://usc.zoom.us/j/6555952212.

[Devansh Gupta]

[Devansh Gupta]

Hi all,

Please join us for Lunch in Theory this Thursday, 04/09 at 12:00 PM in GCS 302c. This week we have Spandan Senapati giving a talk this week on Multicalibration for Elicitable Properties.

Reminder: Please bring your own lunch, as lunch will not be provided.

Best,

Devansh

Title: Efficient Swap Multicalibration of Elicitable Properties

Abstract: Multicalibration [HJKRR18] is an algorithmic fairness perspective that demands that the predictions of a predictor are correct conditional on themselves and membership in a collection of potentially overlapping subgroups of a population. The work of [NR23] established a surprising connection between multicalibration for an arbitrary property Γ (e.g., mean or median) and property elicitation: a property Γ can be multicalibrated if and only if it is elicitable, where elicitability is the notion that the true property value of a distribution can be obtained by solving a regression problem over the distribution. In the online setting, [NR23] proposed an inefficient algorithm that achieves T‾‾√ ℓ2-multicalibration error for a hypothesis class of group membership functions and an elicitable property Γ, after T rounds of interaction between a forecaster and adversary.

In this paper, we generalize multicalibration for an elicitable property Γ from group membership functions to arbitrary bounded hypothesis classes and introduce a stronger notion -- swap multicalibration, following [GKR23]. Subsequently, we propose an oracle-efficient algorithm which, when given access to an online agnostic learner, achieves T1/(r+1) ℓr-swap multicalibration error with high probability (for r≥2) for a hypothesis class with bounded sequential Rademacher complexity and an elicitable property Γ. For the special case of r=2, this implies an oracle-efficient algorithm that achieves T1/3 ℓ2-swap multicalibration error, which significantly improves on the previously established bounds for the problem [NR23, GMS25, LSS25a], and completely resolves an open question raised in [GJRR24] on the possibility of an oracle-efficient algorithm that achieves T‾‾√ ℓ2-mean multicalibration error by answering it in a strongly affirmative sense.

[Devansh Gupta]

Hi all,

Please find the zoom link attached for today's meeting: https://usc.zoom.us/j/6555952212.

Best,

Devansh