COLT 2018: 31ST ANNUAL CONFERENCE ON LEARNING THEORY

A
Abbasi-Yadkori, Yasin	Best of both worlds: Stochastic & adversarial best-arm identification
Abernethy, Jacob	Faster Rates for Convex-Concave Games
Agarwal, Alekh	Efficient Contextual Bandits in Non-stationary Worlds
Agarwal, Alekh	The Dependence of Sample Complexity Lower Bounds on Planning Horizon
Agarwal, Naman	Lower Bounds for Higher-Order Convex Optimization
Alabi, Daniel	Unleashing Linear Optimizers for Group-Fair Learning and Optimization
Altschuler, Jason	Online learning over a finite action set with limited switching
Arora, Sanjeev	An Analysis of the t-SNE Algorithm for Data Visualization
B
Bach, Francis	Averaged Stochastic Gradient Descent on Riemannian Manifolds Exponential convergence of testing error for stochastic gradient methods
Barbier, Jean	Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
Bartlett, Peter	Underdamped Langevin MCMC: A non-asymptotic analysis Best of both worlds: Stochastic & adversarial best-arm identification
Beame, Paul	Time-Space Tradeoffs for Learning Finite Functions from Random Tests, with Applications to Polynomials
Belkin, Mikhail	Approximation beats concentration? An approximation view on inference with smooth radial kernels
Bernton, Espen	Langevin Monte Carlo and JKO splitting
Bhandari, Jalaj	A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation
Bhattacharyya, Arnab	Hardness of Learning Noisy Halfspaces using Polynomial Thresholds
Bhojanapalli, Srinadh	Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
Blum, Avrim	Active Tolerant Testing
Borsos, Zalán	Online Variance Reduction for Stochastic Optimization
Boumal, Nicolas	Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
Brennan, Matthew	Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
Bresler, Guy	Optimal Single Sample Tests for Structured versus Unstructured Network Data Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
Busic, Ana	Action-Constrained Markov Decision Processes With Kullback-Leibler Cost
C
Carpenter, Timothy	Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
Carpentier, Alexandra	Adaptivity to Smoothness in X-armed bandits
Cassel, Asaf	A General Approach to Multi-Armed Bandits Under Risk Criteria
Cesa-Bianchi, Nicolo'	Nonstochastic Bandits with Composite Anonymous Feedback
Chatterji, Niladri S.	Underdamped Langevin MCMC: A non-asymptotic analysis
Chen, Bangrui	Incentivizing Exploration by Heterogeneous Users
Chen, Niangjun	Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent
Chen, Yuansi	Log-concave sampling: Metropolis-Hastings algorithms are fast!
Chen, Yudong	Hidden Integrality of SDP Relaxations for Sub-Gaussian Mixture Models
Cheng, Xiang	Underdamped Langevin MCMC: A non-asymptotic analysis
Cheng, Yu	Non-Convex Matrix Completion Against a Semi-Random Adversary
Chernozhukov, Victor	Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data
Cutkosky, Ashok	Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
D
Dagan, Yuval	Detecting Correlations with Little Memory and Communication
Dalal, Gal	Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
Daskalakis, Constantinos	Testing Symmetric Markov Chains From a Single Trajectory
Diakonikolas, Ilias	Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
Dikkala, Nishanth	Testing Symmetric Markov Chains From a Single Trajectory
Duchi, John	Minimax Bounds on Stochastic Batched Convex Optimization
Dudeja, Rishabh	Learning Single Index Models in Gaussian Space
Durfee, David	L1 Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent
Dwivedi, Raaz	Log-concave sampling: Metropolis-Hastings algorithms are fast!
Dwork, Cynthia	Privacy-preserving Prediction
E
El Alaoui, Ahmed	Detection limits in the high-dimensional spiked rectangular model
F
Fefferman, Charles	Fitting a putative manifold to noisy data
Fei, Yingjie	Hidden Integrality of SDP Relaxations for Sub-Gaussian Mixture Models
Feldman, Vitaly	Privacy-preserving Prediction Calibrating Noise to Variance in Adaptive Data Analysis
Flammarion, Nicolas	Averaged Stochastic Gradient Descent on Riemannian Manifolds
Foster, Dylan	Online Learning: Sufficient Statistics and the Burkholder Method Logistic Regression: The Importance of Being Improper
Frazier, Peter	Incentivizing Exploration by Heterogeneous Users
G
Gabillon, Victor	Best of both worlds: Stochastic & adversarial best-arm identification
Ge, Rong	Non-Convex Matrix Completion Against a Semi-Random Adversary
Gentile, Claudio	Nonstochastic Bandits with Composite Anonymous Feedback
Ghoshal, Suprovat	Hardness of Learning Noisy Halfspaces using Polynomial Thresholds
Goel, Gautam	Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent
Golowich, Noah	Size-Independent Sample Complexity of Neural Networks
Gouleakis, Themis	Learning from Unreliable Datasets
Gravin, Nick	Testing Symmetric Markov Chains From a Single Trajectory
H
Han, Yanjun	Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance
Hand, Paul	Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk
Hanneke, Steve	Actively Avoiding Nonsense in Generative Models
Hastad, Johan	Some problems that I like connected to small-depth circuits and hardness of approximation
Hazan, Elad	Improper Learning of Mixtures of Gaussians
Hazan, Elad	Lower Bounds for Higher-Order Convex Optimization
Hinder, Oliver	Cutting plane methods can be extended into nonconvex optimization
Holden, Nina	Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
Hsu, Daniel	Learning Single Index Models in Gaussian Space
Hu, Lunjia	Active Tolerant Testing
Hu, Wei	An Analysis of the t-SNE Algorithm for Data Visualization
Huleihel, Wasim	Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
I
Immorlica, Nicole	Unleashing Linear Optimizers for Group-Fair Learning and Optimization
Indyk, Piotr	Approximate Nearest Neighbors in Limited Space
Ivanov, Sergei	Fitting a putative manifold to noisy data
J
Jain, Prateek	Accelerating Stochastic Gradient Descent for Least Squares Regression Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
Jain, Vishesh	The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity The Vertex Sample Complexity of Free Energy is Polynomial
Jiang, Nan	The Dependence of Sample Complexity Lower Bounds on Planning Horizon
Jiao, Jiantao	Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance
Jin, Chi	Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
Jordan, Michael	Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification Underdamped Langevin MCMC: A non-asymptotic analysis Averaged Stochastic Gradient Descent on Riemannian Manifolds Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
Jordan, Michael	Detection limits in the high-dimensional spiked rectangular model
K
Kakade, Sham	Accelerating Stochastic Gradient Descent for Least Squares Regression
Kale, Satyen	Logistic Regression: The Importance of Being Improper
Kamath, Gautam	Actively Avoiding Nonsense in Generative Models
Kasiviswanathan, Shiva	Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression
Kempe, David	Incentivizing Exploration by Heterogeneous Users
Kidambi, Rahul	Accelerating Stochastic Gradient Descent for Least Squares Regression
Kirschner, Johannes	Information Directed Sampling and Bandits with Heteroscedastic Noise
Klivans, Adam	Efficient Algorithms for Outlier-Robust Regression
Klusowski, Jason	Counting Motifs with Graph Sampling
Koehler, Frederic	The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity The Vertex Sample Complexity of Free Energy is Polynomial
Kolmogorov, Vladimir	A Faster Approximation Algorithm for the Gibbs Partition Function
Kothari, Pravesh K	Efficient Algorithms for Outlier-Robust Regression An Analysis of the t-SNE Algorithm for Data Visualization
Kotłowski, Wojciech	The Many Faces of Exponential Weights in Online Learning
Kpotufe, Samory	Marginal Singularity, and the Benefits of Labels in Covariate-Shift
Krause, Andreas	Information Directed Sampling and Bandits with Heteroscedastic Noise Online Variance Reduction for Stochastic Optimization
Krzakala, Florent	Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
Kurylev, Yaroslav	Fitting a putative manifold to noisy data
L
Lai, Kevin A.	L1 Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent Faster Rates for Convex-Concave Games
Langford, John	Efficient Contextual Bandits in Non-stationary Worlds
Lassas, Matti	Fitting a putative manifold to noisy data
Lee, Yin Tat	Efficient Convex Optimization with Membership Oracles
Levy, Kfir Y.	Faster Rates for Convex-Concave Games Online Variance Reduction for Stochastic Optimization
Li, Jerry	Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms
Li, Yuanzhi	Learning Mixtures of Linear Regressions with Nearly Optimal Complexity Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
Liang, Tengyuan	Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability
Liang, Yingyu	Learning Mixtures of Linear Regressions with Nearly Optimal Complexity
Livni, Roi	Improper Learning of Mixtures of Gaussians
Locatelli, Andrea	Adaptivity to Smoothness in X-armed bandits
Luo, Haipeng	More Adaptive Algorithms for Adversarial Bandits Efficient Contextual Bandits in Non-stationary Worlds Logistic Regression: The Importance of Being Improper
Lykouris, Thodoris	Small-loss bounds for online learning with partial information
M
Ma, Tengyu	Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
Macris, Nicolas	Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
Malek, Alan	Best of both worlds: Stochastic & adversarial best-arm identification
Mallat, Stephane	Unsupervised Learning from Max Entropy to Deep Generative Networks
Mangoubi, Oren	Convex Optimization with Unbounded Nonconvex Oracles Using Simulated Annealing
Mania, Horia	Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
Mannor, Shie	Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning A General Approach to Multi-Armed Bandits Under Risk Criteria
Mansour, Yishay	Nonstochastic Bandits with Composite Anonymous Feedback
Mao, Cheng	Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
Martinet, Guillaume	Marginal Singularity, and the Benefits of Labels in Covariate-Shift
Maurer, Andreas	Empirical bounds for functions with weak interactions
Meister, Michela	A Data Prism: Semi-verified learning in the small-alpha regime
Meka, Raghu	Efficient Algorithms for Outlier-Robust Regression
Meyn, Sean	Action-Constrained Markov Decision Processes With Kullback-Leibler Cost
Miolane, Leo	Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
Mohri, Mehryar	Logistic Regression: The Importance of Being Improper
Mondelli, Marco	Fundamental Limits of Weak Recovery with Applications to Phase Retrieval
Montanari, Andrea	Fundamental Limits of Weak Recovery with Applications to Phase Retrieval
Mossel, Elchanan	The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity The Vertex Sample Complexity of Free Energy is Polynomial
Mou, Wenlong	Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
Murphy, Susan	Mobile Health: Adventures in Sequential Experimentation and Reinforcement Learning!
N
Nachum, Ido	A Direct Sum for Information Learners
Nagaraj, Dheeraj	Optimal Single Sample Tests for Structured versus Unstructured Network Data
Narayanan, Hariharan	Fitting a putative manifold to noisy data
Netrapalli, Praneeth	Accelerating Stochastic Gradient Descent for Least Squares Regression Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
Neu, Gergely	Iterate Averaging as Regularization for Stochastic Gradient Descent
O
Orabona, Francesco	Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
Oveis Gharan, Shayan	Time-Space Tradeoffs for Learning Finite Functions from Random Tests, with Applications to Polynomials
Ozgur, Ayfer	Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints
P
Pananjady, Ashwin	Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
Pemantle, Robin	Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
Peres, Yuval	Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
Pillaud-Vivien, Loucas	Exponential convergence of testing error for stochastic gradient methods
Pontil, Massimiliano	Empirical bounds for functions with weak interactions
R
Raghavan, Manish	The Externalities of Exploration and How Data Diversity Helps Exploitation
Raginsky, Maxim	Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability
Rakhlin, Alexander	Online Learning: Sufficient Statistics and the Burkholder Method Size-Independent Sample Complexity of Neural Networks
Recht, Benjamin	Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
Rosasco, Lorenzo	Iterate Averaging as Regularization for Stochastic Gradient Descent
Roughgarden, Tim	An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization
Ruan, Feng	Minimax Bounds on Stochastic Batched Convex Optimization
Rudelson, Mark	Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression
Rudi, Alessandro	Exponential convergence of testing error for stochastic gradient methods
Russo, Daniel	A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation
S
Saket, Rishi	Hardness of Learning Noisy Halfspaces using Polynomial Thresholds
Sawlani, Saurabh	L1 Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent
Schmidt, Ludwig	Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms
Shafer, Jonathan	A Direct Sum for Information Learners
Shamir, Ohad	Size-Independent Sample Complexity of Neural Networks Detecting Correlations with Little Memory and Communication
Sharpnack, James	Learning Patterns for Detection with Multiscale Scan Statistics
Sidford, Aaron	Efficient Convex Optimization with Membership Oracles Accelerating Stochastic Gradient Descent for Least Squares Regression
Sidiropoulos, Anastasios	Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
Simchowitz, Max	Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
Singal, Raghav	A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation
Slivkins, Aleksandrs	The Externalities of Exploration and How Data Diversity Helps Exploitation
Sra, Suvrit	An Estimate Sequence for Geodesically Convex Optimization
Sridharan, Karthik	Online Learning: Sufficient Statistics and the Burkholder Method Logistic Regression: The Importance of Being Improper Small-loss bounds for online learning with partial information
Steinke, Thomas	Calibrating Noise to Variance in Adaptive Data Analysis
Stewart, Alistair	Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
Szorenyi, Balazs	Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
T
Talwar, Kunal	Online learning over a finite action set with limited switching
Tan, Yan Shuo	Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods
Tardos, Eva	Small-loss bounds for online learning with partial information
Tauman Kalai, Adam	Unleashing Linear Optimizers for Group-Fair Learning and Optimization Actively Avoiding Nonsense in Generative Models
Thoppe, Gugan	Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
Tripuraneni, Nilesh	Averaged Stochastic Gradient Descent on Riemannian Manifolds
Tsitsiklis, John	Private Sequential Learning
Tu, Stephen	Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
Tzamos, Christos	Learning from Unreliable Datasets Actively Avoiding Nonsense in Generative Models
Tzen, Belinda	Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability
V
Valiant, Gregory	A Data Prism: Semi-verified learning in the small-alpha regime
Valko, Michal	Best of both worlds: Stochastic & adversarial best-arm identification
van der Hoeven, Dirk	The Many Faces of Exponential Weights in Online Learning
van Erven, Tim	The Many Faces of Exponential Weights in Online Learning
Vaughan, Jennifer Wortman	The Externalities of Exploration and How Data Diversity Helps Exploitation
Vempala, Santosh	Efficient Convex Optimization with Membership Oracles
Vershynin, Roman	Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods
Vishnoi, Nisheeth	Convex Optimization with Unbounded Nonconvex Oracles Using Simulated Annealing
Voroninski, Vladislav	Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk
W
Wagner, Tal	Approximate Nearest Neighbors in Limited Space
Wainwright, Martin	Log-concave sampling: Metropolis-Hastings algorithms are fast! Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
Wang, Joshua	An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization
Wang, Jun-Kun	Faster Rates for Convex-Concave Games
Wang, Liwei	Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
Weed, Jonathan	An explicit analysis of the entropic penalty in linear programming
Wei, Chen-Yu	More Adaptive Algorithms for Adversarial Bandits Efficient Contextual Bandits in Non-stationary Worlds
Weissman, Tsachy	Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance
Wibisono, Andre	Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
Wierman, Adam	Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent
Wu, Yihong	Counting Motifs with Graph Sampling
Wu, Zhiwei Steven	The Externalities of Exploration and How Data Diversity Helps Exploitation
Wuthrich, Kaspar	Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data
X
Xu, Kuang	Private Sequential Learning
Xu, Zhi	Private Sequential Learning
Y
Yang, Xin	Time-Space Tradeoffs for Learning Finite Functions from Random Tests, with Applications to Polynomials
Yarotsky, Dmitry	Optimal approximation of continuous functions by very deep ReLU networks
Yehudayoff, Amir	A Direct Sum for Information Learners
Yu, Bin	Log-concave sampling: Metropolis-Hastings algorithms are fast!
Yun, Chulhee	Minimax Bounds on Stochastic Batched Convex Optimization
Z
Zampetakis, Manolis	Learning from Unreliable Datasets
Zdeborova, Lenka	Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
Zeevi, Assaf	A General Approach to Multi-Armed Bandits Under Risk Criteria
Zhai, Xiyu	Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
Zhang, Chicheng	Efficient Active Learning of Sparse Halfspaces
Zhang, Hongyang	Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
Zhang, Hongyi	An Estimate Sequence for Geodesically Convex Optimization
Zheng, Kai	Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
Zhu, Yinchu	Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data

Disclaimer | Powered by EasyChair Smart Program