Search for tag: "arc colloquium"

Samuel Hopkins - Robust Mean Estimation in Nearly-Linear Time

Robust mean estimation is the following basic estimation question: given i.i.d. copies of a random vector X in d-dimensional Euclidean space of which a small constant fraction are corrupted, how well…

From  Kathryn Gentilello on December 6th, 2019 3 plays 0  

Jelani Nelson - Some new approaches to the heavy hitters problem

In the 'frequent items' problem one sees a sequence of items in a stream (e.g. a stream of words coming into a search query engine likeGoogle) and wants to report a small list of items…

From  Kathryn Gentilello on December 3rd, 2019 6 plays 0  

Yuhao Yi - Fast Approximation Algorithms and Complexity Analysis for Design of Networked Systems

This talk focuses on network design algorithms for optimizing average consensus dynamics, dynamics that are widely used for information diffusion and distributed coordination in networked control…

From  Kathryn Gentilello on December 3rd, 2019 6 plays 0  

Nima Anari - Rapidly Mixing Random Walks via Log-Concave Polynomials (Part 2)

(This is Part 2, continuation of Tuesday's lecture.)A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve…

From  Kathryn Gentilello on November 13th, 2019 5 plays 0  

Nima Anari - Rapidly Mixing Random Walks via Log-Concave Polynomials (Part 1)

A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve computational problems. The main parameter defining the…

From  Kathryn Gentilello on November 13th, 2019 9 plays 0  

Ravi Kumar - Algorithmic Discrete Choice

In this talk we consider random utility models for discrete choice. In discrete choice, the task is to select exactly one element from a discrete set of alternatives. We focus on algorithmic…

From  Kathryn Gentilello on November 13th, 2019 7 plays 0  

Rong Ge - What 2-layer neural nets can we optimize?

Optimizing neural networks is a highly nonconvex problem, and even optimizing a 2-layer neural network can be challenging. In the recent years many different approaches were proposed to learn 2-layer…

From  Kathryn Gentilello on November 12th, 2019 15 plays 0  

Umang Bhaskar - Partial Function Extension with Applications to Learning and Property Testing

In partial function extension, we are given a partial function consisting of points from a domain and a function value at each point.Our objective is to determine if this partial function can be…

From  Kathryn Gentilello on October 30th, 2019 1 plays 0  

Thomas Rothvoss - Linear Size Sparsifier and the Geometry of the Operator Norm Ball

The Matrix Spencer Conjecture asks whether given n symmetric matrices in ℝn×n with eigenvalues in [−1,1] one can always find signs so that their signed sum has singular values bounded by…

From  Kathryn Gentilello on October 17th, 2019 2 plays 0  

Nikhil Devanur - Lagrangian Duality in Mechanism Design

This talk surveys the usage of Lagrangian Duality in the design and analysis of auctions. Designing optimal (revenue maximizing) auctions in multi-parameter settings has been among the most active…

From  Kathryn Gentilello on October 14th, 2019 2 plays 0  

Shipra Agrawal - Thompson Sampling for learning in online decision making

Modern online marketplaces feed themselves. They rely on historical data to optimize content and user-interactions, but further, the data generated from these interactions is fed back into the system…

From  Kathryn Gentilello on October 7th, 2019 19 plays 0  

Moses Charikar - Approximating Profile Maximum Likelihood Efficiently

Symmetric properties of distributions arise in multiple settings. For each of these, separate estimators and analysis techniques have been developed. Recently, Orlitsky et al showed that a single…

From  Kathryn Gentilello on September 30th, 2019 11 plays 0  

Aleksandar Nikolov - The Power of Factorization Mechanisms in Differential Privacy

A central goal in private data analysis is to estimate statistics about an unknown distribution from a dataset possibly containing sensitive information, so that the privacy of any individual…

From  Kathryn Gentilello on August 28th, 2019 8 plays 0  

Yin Tat Lee - Solving Linear Programs in the Current Matrix Multiplication Time

We show how to solve linear programs with accuracy epsilon in time n^{omega+o(1)} log(1/epsilon) where omega~2.3728639 is the current matrix multiplication constant. This hits a natural barrier of…

From  Kathryn Gentilello on May 23rd, 2019 25 plays 0  

Will Perkins - Abstract polymer models, the cluster expansion, and applications

I will give two lectures introducing abstract polymer models and the cluster expansion from statistical physics. I will describe some of the original applications of these tools in statistical…

From  Kathryn Gentilello on May 22nd, 2019 3 plays 0  

Ola Svensson - Lecture 2: Different approaches for asymmetric TSP

The traveling salesman problem is one of the most fundamental optimization problems. Given n cities and pairwise distances, it is the problem of finding a tour of minimum distance that visits each…

From  Kathryn Gentilello on May 3rd, 2019 9 plays 0