Parking Information: There are visitor parking spots in front of Building 1950, but please consider carpooling.
0930-1000: Breakfast
1000-1015: Welcome
1015-1100: Li-Yang Tan (Stanford): New algorithms and lower bounds for decision tree learning
1100-1145: Gagan Aggarwal (Google): Autobidding and Auctions
1145-1245: Short Talks I
Daniel Paul Pena (UC Santa Cruz): Homomorphism Orbit Counting in Bounded Degeneracy Graphs
June Vuong (Stanford): Parallel Discrete Sampling via Continuous Walks
Xin Lyu (UC Berkeley): Optimal Private Learning of Threshold Functions
Guy Blanc (Stanford): Subsampling suffices for adaptive data analysis
Yatong Chen (UC Santa Cruz): Metric-Fair Classifier Derandomization
Geoff Ramseyer (Stanford): A Convex Program for Arrow-Debreu Exchange Markets with Constant Function Market Makers
1245-1400: Lunch (provided) and campus tour
1400-1445: Sandy Irani (Simons/UC Berkeley/UC Irvine): Computational Complexity of Quantum Systems
1445-1530: Kunal Talwar (Apple): Shifted Divergences for Privacy and Mixing
1530-1600: Coffee Break
1600-1730: Short Talks II
Sabyasachi Basu (UC Santa Cruz): Spectral Triadic Decompositions of Real World Networks
Yujia Jin (Stanford): A Near-Optimal Method for Minimizing the Maximum of N Convex Loss Functions
Serena Wang (UC Berkeley/Google): Lost in Translation: Reimagining the Machine Learning Life Cycle to Improve Educational Outcomes of Students
Prasanna Ramakrishnan (Stanford): Metric distortion bounds for randomized social choice
Steven Kordonowy (UC Santa Cruz): Classical and quantum algorithms for local maxcut
Lunjia Hu (Stanford): A Unifying Theory of Distance from Calibration
Reilly Raab (UC Santa Cruz): Conjugate Natural Selection
Frederic Koehler (Stanford): Statistical Efficiency of Score Matching: The View from Isoperimetry
Title: New algorithms and lower bounds for decision tree learning
Abstract: Constructing decision tree representations of data is a basic problem of computer science, sitting right at the boundary of our understanding of efficient computation. I will discuss two recent results about this problem, a new algorithm and a new lower bound:
1. An almost-polynomial time membership query algorithm for the uniform-distribution setting. The previous fastest algorithm ran in quasipolynomial time, a consequence of a classic algorithm of Ehrenfeucht and Haussler from 1989. (https://dl.acm.org/doi/abs/10.1145/3561047)
2. A superpolynomial lower bound for the distribution-free setting, assuming the Exponential Time Hypothesis. This builds on and improves upon prior work by Alekhnovich, Braverman, Feldman, Klivans, and Pitassi from 2004. (https://arxiv.org/abs/2210.06375)
Joint works with Guy Blanc, Caleb Koch, Jane Lange, Mingda Qiao, and Carmen Strassle.
Title: Autobidding and Auctions
Abstract: Over the past few years, more and more Internet advertisers have started using automated bidding for optimizing their advertising campaigns. Advertisers using automated bidding have an optimization goal (e.g. to maximize conversions), and some constraints (e.g. a budget or an upper bound on average cost per conversion), and the automated bidding system optimizes their auction bids on their behalf. In this talk, we discuss several fundamental questions around autobidding and auctions. How should an autobidder bid to optimize their goals? Do optimal bidding algorithms depend on the underlying auction? What happens when all advertisers adopt optimal autobidding? Does an equilibrium exist, and is it efficient? How do we define efficiency in the presence of autobidding? What happens to the equilibrium when the auctioneer uses reserve prices to optimize its revenue? We will attempt to answer some of these questions in this talk. In particular, we will present a practical algorithm for autobidding that is optimal if and only if the underlying auction is truthful. We will also take a look at equilibrium behavior and show that the price of anarchy for any equilibrium is no more than 2. Furthermore, we will show that the use of reserve prices can increase the price of anarchy, and bound the resulting increase.
This is based on joint work with Ashwinkumar Badanidiyuru, Aranyak Mehta, Andres Perlroth and Junyao Zhao.
Title: Computational Complexity of Quantum Systems
Abstract: One of the goals of quantum information theory is to understand quantum systems from the standpoint of computational complexity. How difficult is it to compute fundamental properties of a quantum system or simulate a particular system over time? Physicists have been using computers for decades to understand various aspects of quantum systems, but these methods are typically heuristic and achieve success on only limited classes of systems. This talk will give an overview of recent developments in the effort to understand these problems from a formal complexity-theoretic point of view. In particular, one of the most basic properties of a system is its lowest energy state or ground state. I will survey results on the complexity of ground states of finite and infinite systems and the computational resources required to compute them. I will also discuss heuristics to find ground states on more near-term quantum computers.
Title: Shifted Divergences for Privacy and Mixing
Abstract: This talk will discuss a line of work on Shifted Divergences, a notion of distance between distributions over real vectors that is regularized by optimal transport. I will show two applications of this concept, one to differential privacy, and one to rapid mixing.
The first result shows a tight privacy analysis of noisy stochastic gradient descent and its variants for smooth, convex loss functions. We show that the privacy cost of the algorithm, that grows initially with the number of iterations, plateaus after a certain number of steps. The second result studies the convergence of the Langevin Monte Carlo algorithm, a classical algorithm for sampling from a log concave distribution. We give a tight bound on the mixing time of the (discretized) Langevin algorithm to its stationary distribution, in various measures of distance.
No differential privacy background will be assumed. Based on joint works with Jason Altschuler, Vitaly Feldman, Ilya Mironov and Abhradeep Thakurta.