COLT 2018

93 papers

$\ell_1$ Regression Using Lewis Weights Preconditioning and Stochastic Gradient Descent David Durfee, Kevin A. Lai, Saurabh Sawlani

A Data Prism: Semi-Verified Learning in the Small-Alpha Regime Michela Meister, Gregory Valiant

A Direct Sum Result for the Information Complexity of Learning Ido Nachum, Jonathan Shafer, Amir Yehudayoff

A Faster Approximation Algorithm for the Gibbs Partition Function Vladimir Kolmogorov

A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation Jalaj Bhandari, Daniel Russo, Raghav Singal

A General Approach to Multi-Armed Bandits Under Risk Criteria Asaf B. Cassel, Shie Mannor, Assaf Zeevi

Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent Chi Jin, Praneeth Netrapalli, Michael I. Jordan

Accelerating Stochastic Gradient Descent for Least Squares Regression Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford

Action-Constrained Markov Decision Processes with Kullback-Leibler Cost Ana Busic, Sean P. Meyn

Active Tolerant Testing Avrim Blum, Lunjia Hu

Actively Avoiding Nonsense in Generative Models Steve Hanneke, Adam Tauman Kalai, Gautam Kamath, Christos Tzamos

Adaptivity to Smoothness in X-Armed Bandits Andrea Locatelli, Alexandra Carpentier

Algorithmic Regularization in Over-Parameterized Matrix Sensing and Neural Networks with Quadratic Activations Yuanzhi Li, Tengyu Ma, Hongyang Zhang

An Analysis of the T-SNE Algorithm for Data Visualization Sanjeev Arora, Wei Hu, Pravesh K. Kothari

An Estimate Sequence for Geodesically Convex Optimization Hongyi Zhang, Suvrit Sra

An Explicit Analysis of the Entropic Penalty in Linear Programming Jonathan Weed

An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization Tim Roughgarden, Joshua R. Wang

Approximate Nearest Neighbors in Limited Space Piotr Indyk, Tal Wagner

Approximation Beats Concentration? an Approximation View on Inference with Smooth Radial Kernels Mikhail Belkin

Averaging Stochastic Gradient Descent on Riemannian Manifolds Nilesh Tripuraneni, Nicolas Flammarion, Francis R. Bach, Michael I. Jordan

Best of Both Worlds: Stochastic & Adversarial Best-Arm Identification Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon, Alan Malek, Michal Valko

Black-Box Reductions for Parameter-Free Online Learning in Banach Spaces Ashok Cutkosky, Francesco Orabona

Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-Based Models in Polynomial Time Cheng Mao, Ashwin Pananjady, Martin J. Wainwright

Calibrating Noise to Variance in Adaptive Data Analysis Vitaly Feldman, Thomas Steinke

Certified Computation from Unreliable Datasets Themis Gouleakis, Christos Tzamos, Manolis Zampetakis

Convex Optimization with Unbounded Nonconvex Oracles Using Simulated Annealing Oren Mangoubi, Nisheeth K. Vishnoi

Counting Motifs with Graph Sampling Jason M. Klusowski, Yihong Wu

Cutting Plane Methods Can Be Extended into Nonconvex Optimization Oliver Hinder

Detecting Correlations with Little Memory and Communication Yuval Dagan, Ohad Shamir

Detection Limits in the High-Dimensional Spiked Rectangular Model Ahmed El Alaoui, Michael I. Jordan

Efficient Active Learning of Sparse Halfspaces Chicheng Zhang

Efficient Algorithms for Outlier-Robust Regression Adam R. Klivans, Pravesh K. Kothari, Raghu Meka

Efficient Contextual Bandits in Non-Stationary Worlds Haipeng Luo, Chen-Yu Wei, Alekh Agarwal, John Langford

Efficient Convex Optimization with Membership Oracles Yin Tat Lee, Aaron Sidford, Santosh S. Vempala

Empirical Bounds for Functions with Weak Interactions Andreas Maurer, Massimiliano Pontil

Exact and Robust Conformal Inference Methods for Predictive Machine Learning with Dependent Data Victor Chernozhukov, Kaspar Wüthrich, Yinchu Zhu

Exponential Convergence of Testing Error for Stochastic Gradient Methods Loucas Pillaud-Vivien, Alessandro Rudi, Francis R. Bach

Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms Ilias Diakonikolas, Jerry Li, Ludwig Schmidt

Faster Rates for Convex-Concave Games Jacob D. Abernethy, Kevin A. Lai, Kfir Y. Levy, Jun-Kun Wang

Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning Gal Dalal, Gugan Thoppe, Balázs Szörényi, Shie Mannor

Fitting a Putative Manifold to Noisy Data Charles Fefferman, Sergei Ivanov, Yaroslav Kurylev, Matti Lassas, Hariharan Narayanan

Fundamental Limits of Weak Recovery with Applications to Phase Retrieval Marco Mondelli, Andrea Montanari

Generalization Bounds of SGLD for Non-Convex Learning: Two Theoretical Viewpoints Wenlong Mou, Liwei Wang, Xiyu Zhai, Kai Zheng

Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints Yanjun Han, Ayfer Özgür, Tsachy Weissman

Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk Paul Hand, Vladislav Voroninski

Hardness of Learning Noisy Halfspaces Using Polynomial Thresholds Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket

Hidden Integrality of SDP Relaxations for Sub-Gaussian Mixture Models Yingjie Fei, Yudong Chen

Incentivizing Exploration by Heterogeneous Users Bangrui Chen, Peter I. Frazier, David Kempe

Information Directed Sampling and Bandits with Heteroscedastic Noise Johannes Kirschner, Andreas Krause

Iterate Averaging as Regularization for Stochastic Gradient Descent Gergely Neu, Lorenzo Rosasco

Langevin Monte Carlo and JKO Splitting Espen Bernton

Learning Mixtures of Linear Regressions with Nearly Optimal Complexity Yuanzhi Li, Yingyu Liang

Learning Patterns for Detection with Multiscale Scan Statistics James Sharpnack

Learning Single-Index Models in Gaussian Space Rishabh Dudeja, Daniel Hsu

Learning Without Mixing: Towards a Sharp Analysis of Linear System Identification Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, Benjamin Recht

Local Moment Matching: A Unified Methodology for Symmetric Functional Estimation and Distribution Estimation Under Wasserstein Distance Yanjun Han, Jiantao Jiao, Tsachy Weissman

Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability Belinda Tzen, Tengyuan Liang, Maxim Raginsky

Log-Concave Sampling: Metropolis-Hastings Algorithms Are Fast! Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, Bin Yu

Logistic Regression: The Importance of Being Improper Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, Karthik Sridharan

Lower Bounds for Higher-Order Convex Optimization Naman Agarwal, Elad Hazan

Marginal Singularity, and the Benefits of Labels in Covariate-Shift Samory Kpotufe, Guillaume Martinet

Minimax Bounds on Stochastic Batched Convex Optimization John C. Duchi, Feng Ruan, Chulhee Yun

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

Non-Convex Matrix Completion Against a Semi-Random Adversary Yu Cheng, Rong Ge

Nonstochastic Bandits with Composite Anonymous Feedback Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour

Online Learning over a Finite Action Set with Limited Switching Jason M. Altschuler, Kunal Talwar

Online Learning: Sufficient Statistics and the Burkholder Method Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan

Online Variance Reduction for Stochastic Optimization Zalan Borsos, Andreas Krause, Kfir Y. Levy

Open Problem: Improper Learning of Mixtures of Gaussians Elad Hazan, Roi Livni

Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon Nan Jiang, Alekh Agarwal

Optimal Approximation of Continuous Functions by Very Deep ReLU Networks Dmitry Yarotsky

Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, Lenka Zdeborová

Optimal Single Sample Tests for Structured Versus Unstructured Network Data Guy Bresler, Dheeraj Nagaraj

Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods Yan Shuo Tan, Roman Vershynin

Privacy-Preserving Prediction Cynthia Dwork, Vitaly Feldman

Private Sequential Learning John N. Tsitsiklis, Kuang Xu, Zhi Xu

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure Matthew S. Brennan, Guy Bresler, Wasim Huleihel

Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression Shiva Prasad Kasiviswanathan, Mark Rudelson

Sampling as Optimization in the Space of Measures: The Langevin Dynamics as a Composite Optimization Problem Andre Wibisono

Size-Independent Sample Complexity of Neural Networks Noah Golowich, Alexander Rakhlin, Ohad Shamir

Small-Loss Bounds for Online Learning with Partial Information Thodoris Lykouris, Karthik Sridharan, Éva Tardos

Smoothed Analysis for Low-Rank Solutions to Semidefinite Programs in Quadratic Penalty Form Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, Praneeth Netrapalli

Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent Niangjun Chen, Gautam Goel, Adam Wierman

Subpolynomial Trace Reconstruction for Random Strings \{and Arbitrary Deletion Probability Nina Holden, Robin Pemantle, Yuval Peres

Testing Symmetric Markov Chains from a Single Trajectory Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin

The Externalities of Exploration and How Data Diversity Helps Exploitation Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, Zhiwei Steven Wu

The Many Faces of Exponential Weights in Online Learning Dirk van der Hoeven, Tim van Erven, Wojciech Kotlowski

The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity Vishesh Jain, Frederic Koehler, Elchanan Mossel

The Vertex Sample Complexity of Free Energy Is Polynomial Vishesh Jain, Frederic Koehler, Elchanan Mossel

Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials Paul Beame, Shayan Oveis Gharan, Xin Yang

Underdamped Langevin MCMC: A Non-Asymptotic Analysis Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, Michael I. Jordan

Unleashing Linear Optimizers for Group-Fair Learning and Optimization Daniel Alabi, Nicole Immorlica, Adam Kalai