Timezone: »
Poster
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
Brian Axelrod · Ilias Diakonikolas · Alistair Stewart · Anastasios Sidiropoulos · Gregory Valiant
Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #217
We consider the problem of computing the maximum likelihood multivariate log-concave distribution for a set of points. Specifically, we present an algorithm which, given $n$ points in $\mathbb{R}^d$ and an accuracy parameter $\eps>0$, runs in time $\poly(n,d,1/\eps),$ and returns a log-concave distribution which, with high probability, has the property that the likelihood of the $n$ points under the returned distribution is at most an additive $\eps$ less than the maximum likelihood that could be achieved via any log-concave distribution. This is the first computationally efficient (polynomial time) algorithm for this fundamental and practically important task. Our algorithm rests on a novel connection with exponential families: the maximum likelihood log-concave distribution belongs to a class of structured distributions which, while not an exponential family, ``locally'' possesses key properties of exponential families. This connection then allows the problem of computing the log-concave maximum likelihood distribution to be formulated as a convex optimization problem, and solved via an approximate first-order method. Efficiently approximating the (sub) gradients of the objective function of this optimization problem is quite delicate, and is the main technical challenge in this work.
Author Information
Brian Axelrod (Stanford)
Ilias Diakonikolas (UW Madison)
Alistair Stewart (University of Southern California)
Anastasios Sidiropoulos (University of Illinois at Chicago)
Gregory Valiant (Stanford University)
More from the Same Authors
-
2021 Spotlight: List-Decodable Mean Estimation in Nearly-PCA Time »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard · Jerry Li · Kevin Tian -
2021 Spotlight: Forster Decomposition and Learning Halfspaces with Noise »
Ilias Diakonikolas · Daniel Kane · Christos Tzamos -
2021 Spotlight: Statistical Query Lower Bounds for List-Decodable Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart -
2021 Poster: ReLU Regression with Massart Noise »
Ilias Diakonikolas · Jong Ho Park · Christos Tzamos -
2021 Poster: Statistical Query Lower Bounds for List-Decodable Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart -
2021 Poster: Forster Decomposition and Learning Halfspaces with Noise »
Ilias Diakonikolas · Daniel Kane · Christos Tzamos -
2021 Poster: NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs »
Evan McCarty · Qi Zhao · Anastasios Sidiropoulos · Yusu Wang -
2021 Poster: List-Decodable Mean Estimation in Nearly-PCA Time »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard · Jerry Li · Kevin Tian -
2020 Poster: List-Decodable Mean Estimation via Iterative Multi-Filtering »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard -
2020 Poster: Worst-Case Analysis for Randomly Collected Data »
Justin Chen · Gregory Valiant · Paul Valiant -
2020 Oral: Worst-Case Analysis for Randomly Collected Data »
Justin Chen · Gregory Valiant · Paul Valiant -
2020 Poster: Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals »
Ilias Diakonikolas · Daniel Kane · Nikos Zarifis -
2020 Poster: Non-Convex SGD Learns Halfspaces with Adversarial Label Noise »
Ilias Diakonikolas · Vasilis Kontonis · Christos Tzamos · Nikos Zarifis -
2020 Poster: The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise »
Ilias Diakonikolas · Daniel M. Kane · Pasin Manurangsi -
2020 Poster: Outlier Robust Mean Estimation with Subgaussian Rates via Stability »
Ilias Diakonikolas · Daniel M. Kane · Ankit Pensia -
2019 Poster: Private Testing of Distributions via Sample Permutations »
Maryam Aliakbarpour · Ilias Diakonikolas · Daniel Kane · Ronitt Rubinfeld -
2019 Poster: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Poster: Distribution-Independent PAC Learning of Halfspaces with Massart Noise »
Ilias Diakonikolas · Themis Gouleakis · Christos Tzamos -
2019 Poster: Equipping Experts/Bandits with Long-term Memory »
Kai Zheng · Haipeng Luo · Ilias Diakonikolas · Liwei Wang -
2019 Spotlight: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Oral: Distribution-Independent PAC Learning of Halfspaces with Massart Noise »
Ilias Diakonikolas · Themis Gouleakis · Christos Tzamos -
2019 Poster: Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering »
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Eric Price · Alistair Stewart -
2018 Poster: Estimating Learnability in the Sublinear Data Regime »
Weihao Kong · Gregory Valiant -
2018 Poster: Robust Learning of Fixed-Structure Bayesian Networks »
Yu Cheng · Ilias Diakonikolas · Daniel Kane · Alistair Stewart -
2018 Poster: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart -
2018 Poster: Testing for Families of Distributions via the Fourier Transform »
Alistair Stewart · Ilias Diakonikolas · ClĂ©ment L Canonne -
2018 Spotlight: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart