2016 - T1 - WS4 - Inference problems theme

Collection 2016 - T1 - WS4 - Inference problems theme

Organizer(s) Chakrabarti, Amit ; McGregor, Andrew ; Pfister, Henry ; Shah, Devavrat ; Woodruff, David

Date(s) 07/03/2016 - 18/03/2016

linked URL https://web.archive.org/web/20221228152148/http://iss.bu.edu/bobak/csnexus//inference.html

00:00:00 / 00:00:00

37 41

Density estimation via piecewise polynomial approximation in sample near-linear time

By Ilias Diakonikolas

In this talk, I will focus on the problem of density estimation, i. e. , how to estimate (learn) a probability distribution based on random samples. I will describe a sample-optimal and computationally efficient algorithm to learn univariate distributions that are well-approximated by piecewise polynomial density functions. As a consequence of this algorithm, we obtain the first (near-)sample optimal andear-linear time density estimators for a wide range of well-studied structured distribution families. If time permits, I will mention applications of the underlying algorithmic ideas to other inference tasks (e. g. , regression). (Joint work with J. Acharya, J. Li, and L. Schmidt. )

Information about the video

Date of recording 14/03/2016
Date of publication 08/04/2016
Institution IHP
Licence CC BY-NC-ND
Format MP4

Domain(s)

Computer Science

MSC codes

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

All the collection videos

47:29

published on March 28, 2016

Sketching and Embeddings 1/2

By Alex Andoni

01:02:28

published on March 28, 2016

Sketching and Embeddings 2/2

By Alex Andoni

40:14

published on March 28, 2016

Dynamics of Randomized Row-Action Methods for High-Dimensional Estimation

By Yue Lu

56:03

published on March 28, 2016

Sampling from log-concave non-smooth densities or when Moreau meets Langevin

By Eric Moulines

43:00

published on March 28, 2016

Testing properties of distributions over big domains : An introduction

By Ronitt Rubinfeld

48:15

published on March 28, 2016

Testing properties of distributions over big domains : information theoretic quantities

By Ronitt Rubinfeld

47:05

published on March 28, 2016

Convex Programming in Small Space

By Sudipto Guha

50:07

published on March 28, 2016

New Algorithms for Heavy Hitters in Data Streams 1/2

By David Woodruff

49:51

published on March 28, 2016

New Algorithms for Heavy Hitters in Data Streams 2/2

By David Woodruff

33:38

published on March 28, 2016

Challenges in Streaming XML

By Christian Konrad

50:53

published on March 28, 2016

Approximating matchings in sublinear space

By Michael Kapralov

42:31

published on March 28, 2016

Communication Complexity of Learning Discrete Distributions

By Krzysztof Onak

40:56

published on March 28, 2016

Data Reduction for Clustering on Streams

By Harry Lang

49:14

published on March 28, 2016

Stream, sketching and Big Data – 1/2

By Graham Cormode

46:40

published on March 28, 2016

Streram, sketching and Big Data – 2/2

By Graham Cormode

42:02

published on March 28, 2016

Testing Cluster Structure of Graphs

By Christian Sohler

45:26

published on March 28, 2016

Nonasymptotic guarantees for sampling from a log-concave density

By Arnak Dalalyan

43:15

published on March 28, 2016

Communication Complexity with a more-than usal emphasis on Upper Bounds. Part 1 : Setting the stage

By Amit Chakrabarti

56:17

published on March 28, 2016

Communication Complexity with a more-than usal emphasis on Upper Bounds. Part 2 : The Information Complexity Paradigm

By Amit Chakrabarti

46:15

published on March 28, 2016

Streaming sums and symmetric norms

By Stephen Chestnut

01:20:39

published on April 8, 2016

Analysis of double covers of factor graphs

By Pascal Vontobel

56:46

published on April 8, 2016

Spatial coupling as a proof technique

By Nicolas Macris

38:53

published on April 8, 2016

Testing temporal causality and estimating directed information

By Ioannis Kontoyiannis

52:44

published on April 8, 2016

An Optimal Affine Invariant Smooth Minimization Algorithm

By Alexandre d'Aspremont

49:26

published on April 8, 2016

The Area Theorem and Capacity-Achieving Codes – 1/2

By Ruediger Urbanke

38:36

published on April 8, 2016

The Area Theorem and Capacity-Achieving Codes – 2/2

By Ruediger Urbanke

58:04

published on April 8, 2016

Near-optimal message-passing algorithms for crowdsourcing

By Sewoong Oh

41:57

published on April 8, 2016

Efficient Monte Carlo Methods for the Potts Model at Low Temperature

By Mehdi Molkaraie

50:24

published on April 8, 2016

(Arguably) Hard on Average Optimization Problems and the Overlap Gap Property

By David Gamarnik

54:23

published on April 8, 2016

Factor Graphs, Belief Propagation, and Density Evolution – 1/2

By Henry Pfister

53:21

published on April 8, 2016

Factor Graphs, Belief Propagation, and Density Evolution – 2/2

By Henry Pfister

46:52

published on April 8, 2016

Group-testing: Together we are one

By Sidharth Jaggi

51:24

published on April 8, 2016

Iteratively-Decoded Erasure-Correcting Coding for Distributed Storage

By Iryna Andriyanova

48:24

published on April 8, 2016

Understanding the MMSE of compressed sensing one measurement at a time

By Galen Reeves

01:02:39

published on April 8, 2016

New Algorithmic Techniques for Massive graphs – 1/2

By Andrew McGregor

39:25

published on April 8, 2016

New Algorithmic Techniques for Massive graphs – 2/2

By Andrew McGregor

47:33

published on April 8, 2016

Density estimation via piecewise polynomial approximation in sample near-linear time

By Ilias Diakonikolas

56:01

published on April 8, 2016

When your big data seems too small: accurate inferences beyond the empirical distribution 1/2

By Gregory Valiant

56:17

published on April 8, 2016

When your big data seems too small: accurate inferences beyond the empirical distribution 2/2

By Gregory Valiant

46:18

published on April 8, 2016

How to estimate the mean of a random variable? - Part 1

By Gábor Lugosi

39:48

published on April 8, 2016

How to estimate the mean of a random variable? - Part 2

By Gábor Lugosi

Copyright Carmin.tv 2025

Give feedback