TOC Group links
TOC Home
TOC Calendar
Seminars
TOC Colloquium
A&C Seminar
CIS Seminar
Theory Lunch
Harvard/MIT/MSR
Reading Group

Algorithms & Complexity Seminar, MIT : Fall 2023

Organizers: Noah Golowich (nzg AT mit DOT edu), Rahul Ilango (rilango AT mit DOT edu)

The Algorithms & Complexity Seminar will usually (unless otherwise stated) meet on Wednesdays 4pm-5pm at MIT. The style and format of these meetings are variable. Please feel free to contact the organizers to find out more details. To receive announcements of upcoming talks, subscribe to the mailing list by either visiting the mailman page or send an empty email to compalgsem-subscribe@lists.csail.mit.edu.

Talks

  • Wednesday, September 6, 2023: Nika Haghtalab (UC Berkeley). [Time: 4-5pm: 32-G575] (Joint w/ ToC Colloquium)
    Topic. A unified framework for robustness, fairness, and collaboration in machine learning
    Abstract. Pervasive needs for robustness, multi-agent collaboration, and fairness have motivated the design of new methods in research and development. However, these methods remain largely stylized, lacking a foundational perspective and provable performance. In this talk, I will introduce and highlight the importance of multi-objective learning as a unifying paradigm for addressing these needs. This paradigm aims to optimize complex and unstructured objectives from only a small amount of sampled data. I will also discuss how the multi-objective learning paradigm relates to the classical and modern considerations in machine learning broadly, introduce technical tools with versatile provable guarantees, and empirical evidence for its performance on a range of important benchmarks.
  • Monday, September 25, 2023: Pasin Manurangsi (Google Research). [Time: 4-5pm: 32-G449] (Special day and location)
    Topic. User-Level Differential Privacy With Few Examples Per User
    Abstract. Previous work on user-level differential privacy (DP) [Ghazi et al., NeurIPS 2021; Bun et al., STOC 2023] obtained generic algorithms that work for various learning tasks. However, their focus was on the example-rich regime, where the users have so many examples that each user could themselves solve the problem. In this work we consider the example-scarce regime, where each user has only a few examples, and obtain the following results: For approximate-DP, we give a generic transformation of any item-level DP algorithm to a user-level DP algorithm. Roughly speaking, the latter gives a (multiplicative) savings of O_{ε,δ}(√m) in terms of the number of users required for achieving the same utility, where m is the number of examples per user. This algorithm, while recovering most known bounds for specific problems, also gives new bounds, e.g., for PAC learning. For pure-DP, we present a simple technique for adapting the exponential mechanism [McSherry & Talwar, FOCS 2007] to the user-level setting. This gives new bounds for a variety of tasks, such as private PAC learning, hypothesis selection, and distribution learning. For some of these problems, we show that our bounds are near-optimal.
  • Wednesday, October 4, 2023: Shivam Gupta (UT Austin). [Time: 4-5pm: 32-D507] (special location)
    Topic. Finite-Sample Symmetric Mean Estimation with Fisher Information Rate
    Abstract. We consider the problem of estimating the mean of a $1$-dimensional distribution $f$ given $n$ i.i.d. samples. When $f$ is known up to shift, the classical maximum-likelihood estimate (MLE) is known to be optimal in the limit as $n \to \infty$: it is asymptotically normal with variance matching the Cramer-Rao lower bound of $\frac{1}{n \mathcal I}$ where $\mathcal I$ is the Fisher information of $f$. Furthermore, [Stone; 1975] showed that the same convergence can be achieved even when $f$ is \emph{unknown} but \emph{symmetric}. However, these results do not hold for finite $n$, or when $f$ varies with $n$ and failure probability $\delta$. In this talk, I will present two recent works that together develop a finite sample theory for symmetric mean estimation in terms of Fisher Information. We show that for arbitrary (symmetric) $f$ and $n$, one can recover finite-sample guarantees based on the \emph{smoothed} Fisher information of $f$, where the smoothing radius decays with $n$. Based on joint works with Jasper C.H. Lee, Eric Price, and Paul Valiant.
  • Wednesday, October 11, 2023: Sidhanth Mohanty (MIT). [Time: 4-5pm: 32-G575]
    Topic. High-dimensional expansion in random geometric graphs
    Abstract. High-dimensional expansion is a generalization of expansion to hypergraphs where the expansion of certain random walks are witnessed by local neighborhoods. This talk is on the topic of constructing natural probability distributions over sparse high-dimensional expanders (HDXes). On one hand, (standard/1-dimensional) sparse expanders are plentiful, since a constant degree random graph is an expander with high probability. On the other hand, most natural random models over hypergraphs fail to exhibit 2-dimensional expansion unless the average degree exceeds sqrt(number of vertices). However, sparse HDXes are known to exist due to algebraic and number theory based construction. We describe some progress towards constructing sparse HDXes based on random geometric graphs on the unit sphere. Based on joint work with Siqi Liu, Tselil Schramm, and Elizabeth Yang. https://arxiv.org/abs/2210.00158
  • Wednesday, October 18, 2023: Nikhil Vyas (Harvard). [Time: 4-5pm: 32-G575]
    Topic. On Provable Copyright Protection for Generative Models
    Abstract. There is a growing concern that learned conditional generative models may output samples that are substantially similar to some copyrighted data C that was in their training set. We give a formal definition of near access-freeness (NAF) and prove bounds on the probability that a model satisfying this definition outputs a sample similar to C, even if C is included in its training set. Roughly speaking, a generative model p is k-NAF if for every potentially copyrighted data C, the output of p diverges by at most k-bits from the output of a model q that did not access C at all. We also give generative model learning algorithms, which efficiently modify the original generative model learning algorithm in a black box manner, that output generative models with strong bounds on the probability of sampling protected content. Furthermore, we provide promising experiments showing minimal degradation in output quality while ensuring strong protections against sampling protected content. Joint work with Sham Kakade and Boaz Barak (https://arxiv.org/abs/2302.10870)
  • Wednesday, October 25, 2023: Binghui Peng (Columbia). [Time: 4-5pm: 32-G575]
    Topic. Fast (distributional) swap regret and applications to approximate correlated equilibria
    Abstract. We give a simple and computationally efficient algorithm that, for any constant ε>0, obtains εT distributional swap regret within only T = polylog(n) rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of [Blum-Mansour JMLR'07]. Our algorithm has an exponential dependence on ε, but we prove a new, matching lower bound. Our algorithm for swap regret implies faster convergence to ε Correlated Equilibrium (ε-CE) in several regimes: For normal form two-player games with n actions, it implies the first uncoupled dynamics that converges to the set of ε-CE in polylogarithmic rounds; a polylog(n)-bit communication protocol for ε-CE in two-player games (resolving an open problem mentioned by [Babichenko-Rubinstein STOC'2017, Ganor-CS APPROX'18, Goos-Rubinstein FOCS'2018}; and an $\tilde{O}(n)$-query algorithm for ε-CE (resolving an open problem of [Babichenko 2020] and obtaining the first separation between ε-CE and ε-Nash equilibrium in the query complexity model). For extensive-form games, our algorithm implies a PTAS for normal form correlated equilibria, a solution concept widely conjectured to be computationally intractable (e.g. [Stengel-Forges MOR'08, Fujii'23]). Joint work with Aviad Rubinstein
  • Wednesday, November 1, 2023: Chris Harshaw (MIT). [Time: 4-5pm: 32-G575]
    Topic. Clip-OGD: An Experimental Design for Adaptive Neyman Allocation in Sequential Experiments
    Abstract. From clinical trials and public health to development economics and political science, randomized experiments stand out as one of the most reliable methodological tools, as they require the fewest assumptions to estimate causal effects. Adaptive experiment designs – where experimental subjects arrive sequentially and the probability of treatment assignment can depend on previously observed outcomes – are becoming an increasingly popular method for causal inference, as they offer the possibility of improved precision over their non-adaptive counterparts. However, in simple settings (e.g. two treatments) the extent to which adaptive designs can improve precision is not sufficiently well understood. In this talk, I present my recent work on the problem of Adaptive Neyman Allocation, where the experimenter seeks to construct an adaptive design which is nearly as efficient as the optimal (but infeasible) non-adaptive Neyman design which has access to all potential outcomes. I will show that the experimental design problem is equivalent to an adversarial online convex optimization problem, suggesting that any solution must exhibit some amount of algorithmic sophistication. Next, I present Clip-OGD, an experimental design that combines the online gradient descent principle with a new time-varying probability-clipping technique. I will show that the Neyman variance is attained in large samples by showing that the expected regret of the online optimization problem is bounded by O(\sqrt{T}), up to sub-polynomial factors. Even though the design is adaptive, we construct a consistent (conservative) estimator for the variance, which facilitates the development of valid confidence intervals. Finally, we demonstrate the method on data collected from a micro-economic experiment.
  • Wednesday, November 15, 2023: Mitali Bafna (MIT). [Time: 4-5pm: 32-G575]
    Topic. Direct Product Testing on High Dimensional Expanders
    Abstract. The problem of testing direct product functions lies at the intersection of many areas within theoretical computer science, such as error correcting codes, probabilistically checkable proofs (PCPs), hardness amplification and property testing. We want to efficiently encode a function from [n] to {0,1} using local views in a way that admits local testability and the direct product encoding gives us the restriction of f on various subsets of [n]. A set system is said to support a direct product test when the following property holds: whenever a natural 2-query test passes with noticeable probability, the encoding is correlated to a direct-product encoding. We study the question of what hypergraph expansion properties are required of the set systems that support a direct product test in the list-decoding regime. In contrast to the unique-decoding regime, we show that spectral expansion is insufficient and the set-system must additionally possess a form of topological expansion called coboundary expansion. This also turns out to be sufficient, thus giving us a characterization of such set systems. Building set systems with these expansion properties would thus lead to the ultimate form of efficient direct product testers and perhaps also allow for efficient hardness amplification. Based on joint work with Dor Minzer (https://eccc.weizmann.ac.il/report/2023/120/)
  • Monday, November 27, 2023: Yeshwanth Cherapanamjeri (MIT). [Time: 4-5pm: 32-D507] (Special day and location)
    Topic. Optimal PAC Bounds without Uniform Convergence
    Abstract. In statistical learning theory, the problem of determining the optimal sample complexity of binary classification was a longstanding challenge only recently resolved by Hanneke. Unfortunately, these arguments rely on the so-called uniform convergence principle which limits its applicability to more general learning settings. In this talk, we will discuss a new technique that overcomes this limitation and allows us to derive optimal sample complexity bounds for settings where uniform convergence is provably suboptimal and in some cases, does not yield any quantitative finite sample guarantees, e.g. multiclass classification, partial concept classification, and bounded regression. Our bounds resolve a few open questions in the literature, and our learning algorithm is based on a novel analysis of the online-to-batch framework of Littlestone and the celebrated one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth. Based on joint work with Ishaq Aden-Ali, Abhishek Shetty, and Nikita Zhivotovskiy.
  • December 6, 2024: Ali Vakilian (TTIC). [Time: 4-5pm: 32-G575]
    Topic. Algorithms for Generalized Clustering: Min-Max Objective to Cascaded Norms
    Abstract. In this talk, I will consider the k-clustering problem with min-max objective: Given an input set of points P partitioned into L predefined groups, the aim is to find a k-clustering that minimizes the maximum average clustering cost (e.g., k-means cost) across these groups, reflecting fairness in applications like polling station or vaccination sites placement. I present a O(log L/ log log L)-approximation for the clustering problem with min-max objective, which exponentially improves over the previously known O(L)-approximation and is optimal up to a constant factor. Moreover, I will discuss the generalization of the problem to (p,q)-cascaded norms and arbitrary weight functions over the points. As an application, this allows a “relaxed” way of enforcing the fairness requirement, as its objective interpolates between the objective of classic k-clustering and that of socially fair clustering. Moreover, the problem is closely related to other well-known problems in combinatorial optimization such as densest k-subgraph and min-k union.
  • December 7, 2023: Lijie Chen (UC Berkeley). [Time: 4-5pm: 32-G575]
    Topic. New Circuit Lower Bounds via Solving Range Avoidance
    Abstract. Almost all n-bit Boolean functions have near-maximum (2^n/n) circuit complexity, and a central challenge of complexity theory is to pinpoint one such hard function. Formally, the goal is to identify the smallest complexity class containing a language with exponential circuit complexity. Despite being extremely important, there had been essentially no progress on this question since the four-decade-old work of Kannan. In particular, it remained open whether Sigma_2 E, an important frontier class in complexity theory, contains a language with exponential circuit complexity. In a recent paper with Hanlin Ren and Shuichi Hirahara ([CHR'23]), we finally resolved this long-standing open question by showing that Sigma_2 E requires near-maximum (2^n/n) circuit complexity. The lower bound also extends to S_2E/1 (symmetric exponential time with one bit of advice). Our lower bound was further simplified and improved by an exciting recent work by Zeyong Li [Li'23], who showed that S_2E (and therefore Sigma_2 E) requires a maximum circuit complexity on all input lengths. In this talk, I will explain the new lower bounds for Sigma_2 E, which are corollaries of new algorithms for range avoidance. In particular, I will first describe an algorithm for range avoidance (from [CHR'23]) that works on infinitely many input lengths (which follows the iterative win-win paradigm). I will then explain how [Li'23] significantly simplifies and improves the CHR'23 algorithm to work on all input lengths. This improvement also allows [Li'23] to answer a recent open question posed by Vyas and Williams, giving a quasi-polynomial-size depth-3 AC^0 circuits for the Missing String problem.

Theory Calendar

Add this calendar to yours to receive details about upcoming events in the Theory group
(includes A&C Seminars, TOC Colloquium, CIS Seminars, Theory Lunch, TOC tea and more!) :


Click on the events above to get more description about the same (title/abstract for talks, etc.)

Earlier Editions of A&C Seminar