Seminars

Apr
19
2018

Theoretical Machine Learning Seminar

Online Improper Learning with an Approximation Oracle
Zhiyuan Li
12:15pm|White-Levy Room

We revisit the question of reducing online learning to approximate optimization of the offline problem. In this setting, we give two algorithms with near-optimal performance in the full information setting: they guarantee optimal regret and require...

Apr
17
2018

Computer Science/Discrete Mathematics Seminar II

A simple proof of a reverse Minkowski inequality
10:30am|Simonyi Hall 101

We consider the following question: how many points with bounded norm can a "non-degenerate" lattice have. Here, by a "non-degenerate" lattice, we mean an n-dimensional lattice with no surprisingly dense lower-dimensional sublattices.

Dadush and...

Apr
16
2018

Computer Science/Discrete Mathematics Seminar I

Sums of Squares Over k-Subset Hypercubes
Annie Raymond
11:00am|Simonyi Hall 101

Polynomial optimization over hypercubes has important applications in combinatorial optimization. We develop a symmetry-reduction method that finds sums of squares certificates for non-negative symmetric polynomials over k-subset hypercubes that...

Apr
12
2018

Theoretical Machine Learning Seminar

Stability and Generalization in Adaptive Data Analysis
Vitaly Feldman
12:15pm|White-Levy Room

Datasets are often used multiple times with each successive analysis depending on the outcomes of previous analyses on the same dataset. Standard techniques for ensuring generalization and statistical validity do not account for this adaptive...

Apr
10
2018

Computer Science/Discrete Mathematics Seminar II

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
10:30am|West Building Lecture Hall

In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We present an explicit binary tree code with constant distance and alphabet size polylog(n), where n is the depth...

Apr
09
2018

Computer Science/Discrete Mathematics Seminar I

Large deviations in random graphs
Eyal Lubetzky
11:00am|West Building Lecture Hall

What is the probability that the number of triangles in the Erd\H{o}s-R\'enyi random graph with edge density $p$, is at least twice its mean? What is the typical structure of the graph conditioned on this rare event? For instance, when $p=o(1)$...

Apr
05
2018

Theoretical Machine Learning Seminar

A Compressed Sensing View of Unsupervised Text Embeddings, Bag-of-n-Grams, and LSTMs
Mikhail Khodak
12:15pm|White-Levy Room

Three fundamental factors determine the quality of a statistical learning algorithm: expressiveness, optimization and generalization. The classic strategy for handling these factors is relatively well understood. In contrast, the radically different...

Mar
27
2018

Computer Science/Discrete Mathematics Seminar II

Heisenberg geometry and the Goemans—Linial SDP
10:30am|Simonyi Hall 101

Algorithmic graph partitioning tasks are naturally related to geometric issues. Over the past decades, several deeper connections of this type have emerged. In this talk, we will describe one example by showing that, up to lower order factors, the...

Mar
26
2018

Computer Science/Discrete Mathematics Seminar I

Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP
Cody Murray
11:00am|Simonyi Hall 101

We prove that if every problem in NP has n^k-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier's search space has a witness for x that can be encoded with a circuit...

Mar
20
2018

Computer Science/Discrete Mathematics Seminar II

Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing (Continued)
Yuanzhi Li
10:30am|Simonyi Hall 101

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the...