TCS+ talk: Wednesday, March 11 — Thomas Steinke, IBM Research Almaden
The next TCS+ talk will take place this coming Wednesday, March 11th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Thomas Steinke from IBM Research Almaden will speak about “Reasoning About Generalization via Conditional Mutual Information” (abstract below).
Please make sure you reserve a spot for your group to join us live by signing up on the online form. In view of the recent travel restrictions and coronavirus precautions, in particular, do not hesitate to reserve a seat even for a group of size one: there should be enough room for everyone, so don’t be shy!
As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
Abstract: We provide an information-theoretic framework for studying the generalization properties of machine learning algorithms. Our framework ties together existing approaches, including uniform convergence bounds and recent methods for adaptive data analysis. Specifically, we use Conditional Mutual Information (CMI) to quantify how well the input (i.e., the training data) can be recognized given the output (i.e., the trained model) of the learning algorithm. We show that bounds on CMI can be obtained from VC dimension, compression schemes, differential privacy, and other methods. We then show that bounded CMI implies various forms of generalization.
Based on joint work with Lydia Zakynthinou.
-cut” (abstract below).
. The best lower bounds come from conjectures about the solvability of the 
. Our recent results have given special-purpose algorithms that solve the problem in time 
, and ones that have better performance for special classes of graphs (e.g., for small integer weights).
and 
, we give a deterministic 
-time algorithm that outputs a 
vertices that is 
(excluding the single trivial eigenvalue of 
-dimensional hypercube graph, one can easily choose half of the vertices such that they induce an empty graph. However, having even just one more vertex would cause the induced subgraph to contain a vertex of degree at least 
. This result is best possible, and improves a logarithmic lower bound shown by Chung, Furedi, Graham and Seymour in 1988. In this talk we will discuss a very short algebraic proof of it.
petals is a collection of 
, with at least about 
sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to 
for some constant 
. Despite much research, the best bounds until recently were all of the order of 
for some constant c. In this work, we improve the bounds to about 
.
of convex sets in 
until last year but has recently been solved twice. The first solution gives a 
competitive algorithm while the second gives a nearly optimal 
competitive algorithm for 
requests. The latter result is based on the Steiner point, which is the exact optimal solution to a related geometric problem called Lipschitz selection and dates from 1840. In the talk, I will briefly outline the first solution and fully explain the second.
TCS+ 