Back to Events

Seminar Series

December 05

Bagging is an Optimal PAC Learner

Kasper Green Larsen, Asst. Professor, Dept. of Computer Science, Aarhus University
Aarhus University

Part Of

4:00P
- 5:15P

Location

G449 KIVA
G449 KIVA
Add to Calendar 2023-12-05 16:00:00 2023-12-05 17:15:00 America/New_York Bagging is an Optimal PAC Learner Abstract:Determining the optimal sample complexity of PAC learning in the realizable setting was a central open problem in learning theory for decades. Finally, the seminal work by Hanneke (2016) gave an algorithm with a provably optimal sample complexity. His algorithm is based on a careful and structured sub-sampling of the training data and then returning a majority vote among hypotheses trained on each of the sub-samples. While being a very exciting theoretical result, it has not had much impact in practice, in part due to inefficiency, since it constructs a polynomial number of sub-samples of the training data, each of linear size. In this talk, we prove the surprising result that the practical and classic heuristic Bagging (a.k.a. bootstrap aggregation), due to Breiman (1996), is in fact also an optimal PAC learner. Bagging pre-dates Hanneke's algorithm by twenty years and is taught in most undergraduate machine learning courses. Moreover, we show that it only requires a logarithmic number of sub-samples to reach optimality. This work was published at COLT’23 and received the Best Paper Award. G449 KIVA

November 21

A one-query lower bound for unitary synthesis and breaking quantum cryptography

Fermi Ma
Berkeley

Part Of

4:00P
- 5:15P

Location

KIVA G449
KIVA G449
Add to Calendar 2023-11-21 16:00:00 2023-11-21 17:15:00 America/New_York A one-query lower bound for unitary synthesis and breaking quantum cryptography Abstract: The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function?In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm A^f can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle O) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries A^f. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, this result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks.No background in quantum computing will be assumed. This is a joint work with Alex Lombardi and John Wright. arXiv: https://arxiv.org/pdf/2310.08870.pdfMilk & Cookies at 4pm, talk to begin at 4:15pm. KIVA G449

November 14

Additive Randomized Encodings

Yuval Ishai
Technion

Part Of

4:15P
- 5:30P

Location

G-449 KIVA
G-449 KIVA
Add to Calendar 2023-11-14 16:15:00 2023-11-14 17:30:00 America/New_York Additive Randomized Encodings A secure computation protocol for f(x_1,...,x_n) enables n parties toevaluate f on their local inputs x_i while hiding everything except theoutput. A useful special case, which is often easier to solve, is when fcomputes addition in a finite Abelian group G. Can we reduce the generalcase to this special case by first locally mapping each x_i to x'_i in G,and then securely computing the sum of all x'_i?Such a reduction is captured by the abstract notion of *additive randomizedencoding* (ARE). An ARE of f(x_1,...,x_n) is an n-tuple of randomized localmappings g_i(x_i) whose sum reveals the output of f but hides (essentially)everything else about the inputs. I will present positive results, negativeresults, and open questions about the existence of ARE with eitherinformation-theoretic or computational security.As an application of our positive results, we obtain (under a standardcryptographic assumption) the first non-interactive secure computationprotocol for general functions f in the shuffle model, where parties canpost messages on an anonymous bulletin board. This implies a generalutility-preserving compiler from differential privacy in the central modelto (computational) differential privacy in the shuffle model.Joint work with Shai Halevi, Eyal Kushilevitz, and Tal RabinMilk and Cookies at 4pm, Seminar to start at 4:15pm. G-449 KIVA

October 24

Stability and Learning in Strategic Games

Eva Tardos
Cornell

Part Of

4:00P
- 5:30P

Location

G-449
G-449
Add to Calendar 2023-10-24 16:00:00 2023-10-24 17:30:00 America/New_York Stability and Learning in Strategic Games Over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated games assuming players use a form of no-regret learning to adapt to the environment. We will review how this area evolved since its early days, and also discuss some of the new frontiers, including when repeated interactions have carry-over effects between rounds: when outcomes in one round effect the game in the future, as is the case in many applications. In this talk, we study this phenomenon in the context of a game modeling repeated auction with budgets and queuing systems: routers compete for servers, where packets that do not get served need to be resent, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. In joint work with Giannis Fikioris and Jason Gaitonde respectively, we analyze the resulting highly dependent random processes, and show bounds on the resulting budgeted welfare for auctions and the excess server capacity needed to guarantee that all packets get served in the queuing system despite the selfish (myopic) behavior of the participants.Milk & Cookies served at 4pm, Seminar to start at 4:15pm. G-449

October 17

Two Source Extractors for Asymptotically Optimal Entropy, and Improved Ramsey Graphs

Xin Li
Johns Hopkins University

Part Of

4:15P
- 5:15P

Location

32-G449 KIVA
32-G449 KIVA
Add to Calendar 2023-10-17 16:15:00 2023-10-17 17:15:00 America/New_York Two Source Extractors for Asymptotically Optimal Entropy, and Improved Ramsey Graphs Randomness extractors are functions that extract almost uniform random bits from weak random sources with severe biases. One of the most important and well studied types of extractors is the so-called two source extractor, where the input consists of two independent weak sources. Assuming each source has n bits, one can show the existence of two source extractors for entropy k =log n+O(1). Such an extractor also gives a (bipartite) Ramsey graph with N=2^n vertices (on each side), such that there is no (bipartite) clique or independent set of size K=O(log N). Explicit constructions of two source extractors and Ramsey graphs are long standing open problems, dating back to the year of 1947 when Erd˝os invented the probabilistic method.However, despite considerable effort and several recent breakthroughs, previously the best explicit two source extractor only works for entropy k=o(log n log log n). Correspondingly, the best explicit construction of Ramsey graphs only guarantees the non-existence of a clique or independent set of size K=(log N)^{o(log log log N)}.In this talk I will describe a new construction of explicit two source extractors for asymptotically optimal entropy of k=O(log n), which gives explicit Ramsey graphs on N vertices with on clique or independent set of size K=log^c N for some absolute constant c>1. I will also briefly talk about some other applications.Milk & Cookies served at 4pm, talk to begin at 4:15pm. 32-G449 KIVA