COLT 2018

94 papers

Open problem: Improper learning of mixtures of Gaussians

Elad Hazan, Livni Roi

Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon

Nan Jiang, Alekh Agarwal

Certified Computation from Unreliable Datasets

Themis Gouleakis, Christos Tzamos, Manolis Zampetakis

Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form

Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, Praneeth Netrapalli

Iterate Averaging as Regularization for Stochastic Gradient Descent

Gergely Neu, Lorenzo Rosasco

Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance

Yanjun Han, Jiantao Jiao, Tsachy Weissman

Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints

Yanjun Han, Ayfer Ozgur, Tsachy Weissman

Minimax Bounds on Stochastic Batched Convex Optimization

John Duchi, Feng Ruan, Chulhee Yun

Online Learning: Sufficient Statistics and the Burkholder Method

Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan

Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem

Andre Wibisono

The Many Faces of Exponential Weights in Online Learning

Dirk Hoeven, Tim Erven, Wojciech Kotłowski

Unleashing Linear Optimizers for Group-Fair Learning and Optimization

Daniel Alabi, Nicole Immorlica, Adam Kalai

Breaking the 1/√n Barrier: Faster Rates for Permutation-based Models in Polynomial Time

Cheng Mao, Ashwin Pananjady, Martin J. Wainwright

Approximate Nearest Neighbors in Limited Space

Piotr Indyk, Tal Wagner

Counting Motifs with Graph Sampling

Jason M. Klusowski, Yihong Wu

Hidden Integrality of SDP Relaxations for Sub-Gaussian Mixture Models

Yingjie Fei, Yudong Chen

Learning Single-Index Models in Gaussian Space

Rishabh Dudeja, Daniel Hsu

Marginal Singularity, and the Benefits of Labels in Covariate-Shift

Samory Kpotufe, Guillaume Martinet

Efficient active learning of sparse halfspaces

Chicheng Zhang

An explicit analysis of the entropic penalty in linear programming

Jonathan Weed

Subpolynomial trace reconstruction for random strings \{and arbitrary deletion probability

Nina Holden, Robin Pemantle, Yuval Peres

Langevin Monte Carlo and JKO splitting

Espen Bernton

Efficient Contextual Bandits in Non-stationary Worlds

Haipeng Luo, Chen-Yu Wei, Alekh Agarwal, John Langford

The Externalities of Exploration and How Data Diversity Helps Exploitation

Manish Raghavan, Aleksandrs Slivkins, Jennifer Vaughan Wortman, Zhiwei Steven Wu

An Estimate Sequence for Geodesically Convex Optimization

Hongyi Zhang, Suvrit Sra

Privacy-preserving Prediction

Cynthia Dwork, Vitaly Feldman

A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation

Jalaj Bhandari, Daniel Russo, Raghav Singal

Optimal Single Sample Tests for Structured versus Unstructured Network Data

Guy Bresler, Dheeraj Nagaraj

ℓ_1 Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent

David Durfee, Kevin A. Lai, Saurabh Sawlani

Faster Rates for Convex-Concave Games

Jacob Abernethy, Kevin A. Lai, Kfir Y. Levy, Jun-Kun Wang

Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent

Niangjun Chen, Gautam Goel, Adam Wierman

Online learning over a finite action set with limited switching

Jason Altschuler, Kunal Talwar

A Direct Sum Result for the Information Complexity of Learning

Ido Nachum, Jonathan Shafer, Amir Yehudayoff

A Data Prism: Semi-verified learning in the small-alpha regime

Michela Meister, Gregory Valiant

Black-Box Reductions for Parameter-free Online Learning in Banach Spaces

Ashok Cutkosky, Francesco Orabona

Adaptivity to Smoothness in X-armed bandits

Andrea Locatelli, Alexandra Carpentier

An Analysis of the t-SNE Algorithm for Data Visualization

Sanjeev Arora, Wei Hu, Pravesh K. Kothari

Cutting plane methods can be extended into nonconvex optimization

Oliver Hinder

Fundamental Limits of Weak Recovery with Applications to Phase Retrieval

Marco Mondelli, Andrea Montanari

Action-Constrained Markov Decision Processes With Kullback-Leibler Cost

Ana Busic, Sean Meyn

Efficient Algorithms for Outlier-Robust Regression

Adam Klivans, Pravesh K. Kothari, Raghu Meka

The Vertex Sample Complexity of Free Energy is Polynomial

Vishesh Jain, Frederic Koehler, Elchanan Mossel

Non-Convex Matrix Completion Against a Semi-Random Adversary

Yu Cheng, Rong Ge

Approximation beats concentration? An approximation view on inference with smooth radial kernels

Mikhail Belkin

The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity

Vishesh Jain, Frederic Koehler, Elchanan Mossel

An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization

Tim Roughgarden, Joshua R. Wang

A General Approach to Multi-Armed Bandits Under Risk Criteria

Asaf Cassel, Shie Mannor, Assaf Zeevi

Efficient Convex Optimization with Membership Oracles

Yin Tat Lee, Aaron Sidford, Santosh S. Vempala

More Adaptive Algorithms for Adversarial Bandits

Chen-Yu Wei, Haipeng Luo

Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities

Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos, Alistair Stewart

Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning

Gal Dalal, Gugan Thoppe, Balázs Szörényi, Shie Mannor

Detecting Correlations with Little Memory and Communication

Yuval Dagan, Ohad Shamir

Learning Mixtures of Linear Regressions with Nearly Optimal Complexity

Yuanzhi Li, Yingyu Liang

Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing

Oren Mangoubi, Nisheeth K. Vishnoi

Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

Chi Jin, Praneeth Netrapalli, Michael I. Jordan

Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression

Shiva Prasad Kasiviswanathan, Mark Rudelson

Empirical bounds for functions with weak interactions

Andreas Maurer, Massimiliano Pontil

Small-loss bounds for online learning with partial information

Thodoris Lykouris, Karthik Sridharan, Eva Tardos

Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk

Paul Hand, Vladislav Voroninski

Learning Patterns for Detection with Multiscale Scan Statistics

James Sharpnack

Best of both worlds: Stochastic & adversarial best-arm identification

Yasin Abbasi-Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, Michal Valko

Hardness of Learning Noisy Halfspaces using Polynomial Thresholds

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket

Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability

Belinda Tzen, Tengyuan Liang, Maxim Raginsky

Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials

Paul Beame, Shayan Oveis Gharan, Xin Yang

Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms

Ilias Diakonikolas, Jerry Li, Ludwig Schmidt

Incentivizing Exploration by Heterogeneous Users

Bangrui Chen, Peter Frazier, David Kempe

Log-concave sampling: Metropolis-Hastings algorithms are fast!

Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, Bin Yu

Lower Bounds for Higher-Order Convex Optimization

Naman Agarwal, Elad Hazan

Nonstochastic Bandits with Composite Anonymous Feedback

Nicolò Cesa-bianchi, Claudio Gentile, Yishay Mansour

Exact and Robust Conformal Inference Methods for Predictive Machine Learning with Dependent Data

Victor Chernozhukov, Kaspar Wüthrich, Zhu Yinchu

Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models

jean barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, Lenka Zdeborová

Private Sequential Learning

John Tsitsiklis, Kuang Xu, Zhi Xu

Fitting a Putative Manifold to Noisy Data

Charles Fefferman, Sergei Ivanov, Yaroslav Kurylev, Matti Lassas, Hariharan Narayanan

Averaging Stochastic Gradient Descent on Riemannian Manifolds

Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, Michael I. Jordan

Optimal approximation of continuous functions by very deep ReLU networks

Dmitry Yarotsky

Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints

Wenlong Mou, Liwei Wang, Xiyu Zhai, Kai Zheng

Accelerating Stochastic Gradient Descent for Least Squares Regression

Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford

Calibrating Noise to Variance in Adaptive Data Analysis

Vitaly Feldman, Thomas Steinke

Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods

Yan Shuo Tan, Roman Vershynin

Active Tolerant Testing

Avrim Blum, Lunjia Hu

Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification

Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, Benjamin Recht

Detection limits in the high-dimensional spiked rectangular model

Ahmed El Alaoui, Michael I. Jordan

Testing Symmetric Markov Chains From a Single Trajectory

Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin

Information Directed Sampling and Bandits with Heteroscedastic Noise

Johannes Kirschner, Andreas Krause

Online Variance Reduction for Stochastic Optimization

Zalán Borsos, Andreas Krause, Kfir Y. Levy

Underdamped Langevin MCMC: A non-asymptotic analysis

Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, Michael I. Jordan

Size-Independent Sample Complexity of Neural Networks

Noah Golowich, Alexander Rakhlin, Ohad Shamir

Exponential Convergence of Testing Error for Stochastic Gradient Methods

Loucas Pillaud-Vivien, Alessandro Rudi, Francis Bach

A Faster Approximation Algorithm for the Gibbs Partition Function

Vladimir Kolmogorov

Actively Avoiding Nonsense in Generative Models

Steve Hanneke, Adam Tauman Kalai, Gautam Kamath, Christos Tzamos

Logistic Regression: The Importance of Being Improper

Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, Karthik Sridharan

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

Matthew Brennan, Guy Bresler, Wasim Huleihel

Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations

Yuanzhi Li, Tengyu Ma, Hongyang Zhang

Conference on Learning Theory 2018: Preface

Sébastien Bubeck, Philippe Rigollet