9th TOCA-SV Day

Abstracts

Li-Yang Tan (Stanford)

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.

Gagan Aggarwal (Google)

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.

Sandy Irani (Simons/UC Berkeley/UC Irvine)

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.

Kunal Talwar (Apple)

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.