Fall 2023 Mentorship Workshop

In Fall 2023, we organized a mentorship workshop centered on communicating one’s research verbally for Undergraduate, Masters, PhD students, and Postdocs interested in Learning Theory and adjacent fields.

The event took place virtually (on gather.town) on October 26-27, 2023.

Speakers: Sanjoy Dasgupta, Maryam Fazel, Daniel Hsu, Ashwin Pananjady, Madeleine Udell, and Claire Vernade

Mentors: Adam Block, Ajil Jalal, Alankrita Bhatt, Audra McMillan, Chara Podimata, Chen-Yu Wei, Ciara Pike-Burke, Dylan Foster, Elisabetta Cornacchia, Gaurav Mahajan, Gautam Goel, Gautam Kamath, Gergely Neu, Jason Gaitonde, Karthik Sridharan, Manolis Zampetakis, Margalit Glasgow, Max Simchowitz, Meena Jagadeesan, Neha Gupta, Nikita Zhivotovsky, Omar Montasser, Princewill Okoroafor, Pritish Kamath, Raaz Dwivedi, Sarah Cen, Tijana Zrnic, Vaishnavh Nagarajan, Xinyi Chen, Yeshwanth Cherapanamjeri.

Volunteers: Vishwajeet Agrawal, Korinna Frangias, Tianyu Gao, Kimathi Kaai, Misha Khodak, Leqi Liu, Annie Marsden, Luís Espírito Santo, Shiwei Zeng

See the schedule below.

Mentorship Workshop

Event Schedule

Session 1
Session 2

October 26, 2023, 09:15 ET

Welcome Remarks. Surbhi Goel

Venue: Seminar Room (gather.town)

October 26, 2023, 09:30 ET

How-to Talk 1: Communicating your research effectively in conversations. Daniel Hsu, Claire Vernade

Venue: Seminar Room (gather.town)

This session will be geared towards senior undergrads, grad students, and postdocs, and will ideally cover questions related to effectively communicating your research (to researchers you may not personally know well) via elevator pitches, posters, and interviews.

October 26, 2023, 10:30 ET

Activity 1: Elevator Pitches and Group Chats

Leads: Bingbin Liu, Sadhika Malladi

Venue: Seminar Room (gather.town)

This session will be an interactive small-group session where the students apply what they learned in the “how-to” by giving an elevator pitch about their research and providing feedback to each other.

October 26, 2023, 11:05 ET

Break.

Venue: Lounge (gather.town)

October 26, 2023, 11:15 ET

How-to Talk 2: Communicating your research effectively through talks. Ashwin Pananjady

Venue: Seminar Room (gather.town)

This session will be geared towards senior undergrads, grad students, and postdocs, and will ideally cover the nuances of preparing an effective research talk to broad and/or specialized audiences, as well as strategies for delivering both short and long talks.

October 26, 2023, 12:15 ET

Activity 2: Practice Talks and Feedback

Leads: Moïse Blanchard, Tyler LaBonte, Sloan Nietert

Venue: Seminar Room (gather.town)

This session will be an interactive small-group session where the students get to listen to and provide feedback on a student presentation.

Speakers and Practice Talk Details

Linda Cai - Selling to Multiple No-Regret Buyers (Abstract)

We consider the problem of repeatedly auctioning a single item to multiple i.i.d, buyers who each use a no-regret learning algorithm to bid over time. In particular, we study the seller's optimal revenue, if they know that the buyers are no-regret learners (but only that their behavior satisfies some no-regret property -- they do not know the precise algorithm/heuristic used). Our main result designs an auction that extracts revenue equal to the full expected welfare whenever the buyers are "mean-based" (a property satisfied by standard no-regret learning algorithms such as Multiplicative Weights, Follow-the-Perturbed-Leader, etc.). This extends a main result of [BMSW18] which held only for a single buyer.
Rahul Ramesh - A picture of the space of tasks (Abstract)

Exploiting data from many related tasks is an idea that lies at the heart of many sub-fields like transfer, multi-task, meta- and self-supervised learning. But why do these representation learning methods work so well? In this talk, I will discuss techniques from information geometry to analyze the training trajectories of different methods when trained on different datasets. Surprisingly, we find that these trajectories lie on an effecitively low-dimensional manifold in "prediction space" --- as few as 3 dimensions capture 81% of the explained stress of training trajectories of ImageNet. We study the training trajectories of self-supervised learning, contrastive learning and episodic meta-learning to further understand structure in the space of tasks. We believe that understanding some of these phenomena may be key to solving the mysteries of generalization.
Arthur da Cunha - The Strong Lottery Ticket Hypothesis: Pruning is All You Need (Abstract)

The Strong Lottery Ticket Hypothesis (SLTH) states that randomly initialised neural networks contain subnetworks that perform well without any training. In this talk, we elucidate and discuss the SLTH, summarising the context that motivated it and briefly outlining the main ideas behind its proof.
Xinyuan Cao - Unsupervised Halfspace Learning in Polynomial Time (Abstract)

We give a polynomial-time algorithm for learning high-dimensional halfspaces with margins in $d$-dimensional space to within desired TV distance when the ambient distribution is an unknown affine transformation of the $d$-fold product of an (unknown) symmetric one-dimensional logconcave distribution, and the halfspace is introduced by deleting at least an $\epsilon$ fraction of the data in one of the component distributions. Notably, our algorithm does not need labels and establishes the unique (and efficient) identifiability of the hidden halfspace under this distributional assumption. The sample and time complexity of the algorithm are polynomial in the dimension and $1/\epsilon$. The algorithm uses only the first two moments of suitable re-weightings of the empirical distribution, which we call contrastive moments; its analysis uses classical facts about generalized Dirichlet polynomials and relies crucially on a new monotonicity property of the variance ratio of truncations of logconcave distributions.
Ramchandran Muthukumar - Sparsity-aware generalization theory for deep neural networks (Abstract)

Deep artificial neural networks achieve surprising generalization abilities that remain poorly understood. In this paper, we present a new approach to analyzing generalization for deep feed-forward ReLU networks that takes advantage of the degree of sparsity that is achieved in the hidden layer activations. By developing a framework that accounts for this reduced effective model size for each input sample, we are able to show fundamental trade-offs between sparsity and generalization. Importantly, our results make no strong assumptions about the degree of sparsity achieved by the model, and it improves over recent norm-based approaches. We illustrate our results numerically, demonstrating non-vacuous bounds when coupled with data-dependent priors even in over-parametrized settings.
Gene Li - When is Agnostic Reinforcement Learning Statistically Tractable? (Abstract)

We study the problem of agnostic PAC reinforcement learning (RL): given a policy class Π, how many rounds of interaction with an unknown MDP (with a potentially large state and action space) are required to learn a near-optimal policy with respect to Π? Towards that end, we introduce a new complexity measure, called the spanning capacity, that depends solely on the class Π and is independent of the MDP dynamics. With a generative model, we show that for any policy class Π, bounded spanning capacity characterizes PAC learnability. However, for online RL, the situation is more subtle. We show there exists a policy class Π with a bounded spanning capacity that requires a superpolynomial number of samples to learn. This reveals a surprising separation for agnostic learnability between generative access and online access models (as well as between deterministic/stochastic MDPs under online access). On the positive side, we identify an additional sunflower structure, which in conjunction with bounded spanning capacity enables statistically efficient online RL via a new algorithm called POPLER. Based on joint work with Zeyu Jia, Alexander Rakhlin, Ayush Sekhari, and Nathan Srebro. Paper link: https://arxiv.org/abs/2310.06113.
Jianyu Xu - Dynamic Pricing with Procedural and Substantive Fairness (Abstract)

We study the problem of online dynamic pricing with two types of fairness constraints: a procedural fairness which requires the proposed prices to be equal and a substantive fairness which requires the accepted prices to be equal in expectation among different groups. In this work, we show that a randomized-price policy may achieve higher revenue than the best fixed-price policy under fairness constraints. In a two-group setting, we propose an online learning algorithm that achieves $O(\sqrt{T})$ regret, zero procedural unfairness and $O(\sqrt{T})$ substantive unfairness over T rounds. We also prove its optimality with two matching lower bounds. To the best of our knowledge, this is the first dynamic pricing algorithm that learns to price while satisfying two fairness constraints at the same time. Besides, we are the first to propose an information-theoretic tradeoff between regret and unfairness.

October 26, 2023, 12:50 ET

Mentoring Tables.

Leads: Ayush Sekhari, Abhishek Shetty

Mentors: Chara Podimata, Chen-Yu Wei, Ciara Pike-Burke, Dylan Foster, Elisabetta Cornacchia, Gaurav Mahajan, Gautam Kamath, Gergely Neu, Jason Gaitonde, Manolis Zampetakis, Max Simchowitz, Neha Gupta, Pritish Kamath, Raaz Dwivedi, Tijana Zrnic, Vaishnavh Nagarajan, Xinyi Chen, Yeshwanth Cherapanamjeri.

Venue: Lounge (gather.town)

This session is intended to be free time to socialize with members of the community as well as other participants. There will be tables where a mentor would be available to seek advice and answer your questions!

October 26, 2023, 19:45 ET

Welcome Remarks. Vatsal Sharan

Venue: Seminar Room (gather.town)

October 26, 2023, 20:00 ET

How-to Talk 1: Communicating your research effectively in conversations. Maryam Fazel, Madeleine Udell

Venue: Seminar Room (gather.town)

October 26, 2023, 21:00 ET

Activity 1: Elevator Pitches and Group Chats

Leads: Bingbin Liu, Sadhika Malladi

Venue: Seminar Room (gather.town)

October 26, 2023, 21:35 ET