COLT 2017: 30TH ANNUAL CONFERENCE ON LEARNING THEORY

This page contains an index consisting of author-provided keywords.

$
$L$-ensembles	Rates of estimation for determinantal point processes
A
Active learning	Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons Adaptivity to Noise Parameters in Nonparametric Active Learning The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
adaptive algorithms	Corralling a Band of Bandit Algorithms
Adaptive Data Analysis	Generalization for Adaptively-chosen Estimators via Stable Median
Adaptive Sampling	The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
Adaptivity	Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons Adaptivity to Noise Parameters in Nonparametric Active Learning
adversarial bandits	An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
agnostic learning	Reliably Learning the ReLU in Polynomial Time
algebraic manifolds	Effective Semisupervised Learning on Manifolds
algorithm configuration	Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
algorithmic randomness	Memoryless Sequences for Differentiable Losses
alternating minimization	Matrix Completion from O(n) Samples in Linear Time
applied probability	Ten Steps of EM Suffice for Mixtures of Two Gaussians
Approximate sampling	Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent
approximation algorithms	Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization
B
bandit	Bandits with Movement Costs and Adaptive Pricing
bandits	Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization Corralling a Band of Bandit Algorithms Online Nonparametric Learning, Chaining, and the Role of Partial Feedback
basis reduction	Correspondence retrieval
Bayesian inference	Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo
Bayesian Networks	Testing Bayesian Networks Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing
Bayesian optimization	Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
Bernstein inequality	A second-order look at stability and generalization
Best arm identification	Towards Instance Optimal Bounds for Best Arm Identification Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons
best of both worlds	An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
Boosting	Efficient PAC Learning from the Crowd
Bounded space	Mixing Implies Lower Bounds for Space Bounded Learning
Bracketing conditions	Optimal learning via local entropies and sample compression
C
center based objectives	Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
chaining	Online Nonparametric Learning, Chaining, and the Role of Partial Feedback
clustering	Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
co-training	Efficient Co-Training of Linear Separators under Weak Dependence
combinatorial bandits	Tight Bounds for Bandit Combinatorial Optimization
combinatorial optimization	Tight Bounds for Bandit Combinatorial Optimization
community detection	Fundamental limits of symmetric low-rank matrix estimation
Complexity of learning	A General Characterization of the Statistical Query Complexity
computational complexity	On Learning versus Refutation
computationally efficient and sample efficient meta-algorithms	Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
concentration	The Hidden Hubs Problem A second-order look at stability and generalization
Concentration inequalities	Two-Sample Tests for Large Random Graphs using Network Statistics
constraint satisfaction problems	On Learning versus Refutation
Continuation	Homotopy Analysis for Tensor PCA
control theory	A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
Convex Body	Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo
Convex optimization	The Sample Complexity of Optimizing a Convex Function Stochastic Composite Least-Squares Regression with convergence rate O(1/n)
covariance estimation	Computationally Efficient Robust Estimation of Sparse Functionals
Crowdsourcing	Efficient PAC Learning from the Crowd
cryptography	On Learning versus Refutation
Cumulative regret	Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
D
Deep neural networks	Surprising properties of dropout in deep networks
Depth Separation	Depth Separation for Neural Networks
Determinantal point processes	Rates of estimation for determinantal point processes
dictionary learning	Fast and robust tensor decomposition with applications to dictionary learning
Differential Privacy	The Price of Selection in Differential Privacy Generalization for Adaptively-chosen Estimators via Stable Median
Discrimination	Learning Non-Discriminatory Predictors
Disjunction of predicates	Learning Disjunctions of Predicates
distributed stochastic optimization	Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox
distribution learning	Predicting with Distributions Learning Multivariate Log-concave Distributions
distribution testing	Ten Steps of EM Suffice for Mixtures of Two Gaussians Testing Bayesian Networks
DNF formulas	On Learning versus Refutation
Dropout	Surprising properties of dropout in deep networks
dual averaging	Stochastic Composite Least-Squares Regression with convergence rate O(1/n)
E
elicitation	Multi-Observation Elicitation
Empirical risk minimization	Empirical Risk Minimization for Stochastic Convex Optimization: $O(1/n)$- and $O(1/n^2)$-type of Risk Bounds Multi-Observation Elicitation A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints Optimal learning via local entropies and sample compression
ensemble	Corralling a Band of Bandit Algorithms
Exact learning	Learning Disjunctions of Predicates
exact recovery	Exact tensor completion with sum-of-squares
Excess Risk	Empirical Risk Minimization for Stochastic Convex Optimization: $O(1/n)$- and $O(1/n^2)$-type of Risk Bounds
expectation - maximization	Ten Steps of EM Suffice for Mixtures of Two Gaussians
Exploration-Exploitation	Thompson Sampling for the MNL-Bandit
F
Fairness	Learning Non-Discriminatory Predictors
fast rates	Fast rates for online learning in Linearly Solvable Markov Decision Processes
Finito	A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
Fourier transform	On the Ability of Neural Nets to Express Distributions
function approximation	On the Ability of Neural Nets to Express Distributions
G
Gap-Entropy	Towards Instance Optimal Bounds for Best Arm Identification
Gaussian processes	Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
Gaussian smoothing	Homotopy Analysis for Tensor PCA
generalization	A second-order look at stability and generalization Generalization for Adaptively-chosen Estimators via Stable Median
Generalization bounds	Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
generalized linear models	Computationally Efficient Robust Estimation of Sparse Functionals
generative model	On the Ability of Neural Nets to Express Distributions
global optimization	Homotopy Analysis for Tensor PCA Non-Convex Learning via Stochastic Gradient Langevin Dynamics: A Nonasymptotic Analysis
GMM	Robust Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities
Gradient descent	Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent
graphical models	Testing Bayesian Networks
Grothendieck inequality	Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
group synchronization	Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
H
hardness	On Learning versus Refutation
Hardness of Approximation	Inapproximability of VC Dimension and Littlestone's Dimension
Hellinger Distance	Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing
Hidden Gaussian	The Hidden Hubs Problem
Hidden Hubs	The Hidden Hubs Problem
High-dimensional inference	High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition.
Hitting time	A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (Best Paper Award)
Homotopy	Homotopy Analysis for Tensor PCA
hypothesis testing	Testing Bayesian Networks
I
ICA	Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
Inductive bias	Surprising properties of dropout in deep networks
Instance Optimality	Towards Instance Optimal Bounds for Best Arm Identification Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
Instantaneous regret	Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
integer quadratic programming	Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
iterative projection method	Fast and robust tensor decomposition with applications to dictionary learning
J
jump systems	A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
K
k-extendible systems	Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization
k-systems	Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization
kernel methods	Reliably Learning the ReLU in Polynomial Time
L
Langevin	Non-Convex Learning via Stochastic Gradient Langevin Dynamics: A Nonasymptotic Analysis
Langevin algorithm	Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent
Le Cam's method	Sample complexity of population recovery
learning discrete mixtures	Sample complexity of population recovery
learning mixtures of product distributions	Noisy Population Recovery from Unknown Noise
Learning under classification noise	Predicting with Distributions
Learning with communication constraints	A General Characterization of the Statistical Query Complexity
Learning with Noise	Efficient PAC Learning from the Crowd
Limited adaptivity	Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons
Linear Algebra	Thresholding based Efficient Outlier Robust PCA
linear classifier	Efficient Co-Training of Linear Separators under Weak Dependence
linear programming	Sample complexity of population recovery
Linear regression	Computationally Efficient Robust Estimation of Sparse Functionals High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition.
Littlestone's Dimension	Inapproximability of VC Dimension and Littlestone's Dimension
Local entropy	Optimal learning via local entropies and sample compression
log-concave densities	Learning Multivariate Log-concave Distributions
logistic regression	Computationally Efficient Robust Estimation of Sparse Functionals
loss functions	Memoryless Sequences for Differentiable Losses Multi-Observation Elicitation
Lower bound	Mixing Implies Lower Bounds for Space Bounded Learning
Lower Bounds	The Price of Selection in Differential Privacy Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization Online Learning Without Prior Information (Best Student Paper Award) The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
M
Machine learning reduction	Predicting with Distributions
manifold learning	Effective Semisupervised Learning on Manifolds
Markov Chain Monte Carlo	Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent
Markov chain Monte Carlo methods	Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo
Markov decision processes	Fast rates for online learning in Linearly Solvable Markov Decision Processes
martingales	ZIGZAG: A new approach to adaptive online learning On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities
matrix completion	Matrix Completion from O(n) Samples in Linear Time
Matrix factorization	Fundamental limits of symmetric low-rank matrix estimation
matrix norm bounds	Exact tensor completion with sum-of-squares
matrix polynomials	Exact tensor completion with sum-of-squares
max-cut	Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
MaxCut	Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
Maximum likelihood	Rates of estimation for determinantal point processes
Membership queries	Learning Disjunctions of Predicates
memory and communication efficiency	Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox
method of moments	Correspondence retrieval
minibatch prox	Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox
Minimax testing	Two-Sample Tests for Large Random Graphs using Network Statistics
mirror descent	Stochastic Composite Least-Squares Regression with convergence rate O(1/n)
Mixing	Mixing Implies Lower Bounds for Space Bounded Learning
Mixtures of Gaussians	Robust Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities
Most biased coins	Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons
Multi-arm Bandits	The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
Multi-Armed Bandit	Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
Multi-armed bandits	Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons
multiarmed bandits	An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
Multinomial Logit Choice Model	Thompson Sampling for the MNL-Bandit
N
neural network	On the Ability of Neural Nets to Express Distributions
neural networks	Depth Separation for Neural Networks Nearly-tight VC-dimension bounds for neural networks
noise	Submodular Optimization under Noise
Noise conditions	Adaptivity to Noise Parameters in Nonparametric Active Learning
noisy recovery	Noisy Population Recovery from Unknown Noise
Non-convex	Non-Convex Learning via Stochastic Gradient Langevin Dynamics: A Nonasymptotic Analysis
Non-convex Optimization	Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (Best Paper Award) Thresholding based Efficient Outlier Robust PCA
Nonconvex optimization	Homotopy Analysis for Tensor PCA
nonparametric	Online Nonparametric Learning, Chaining, and the Role of Partial Feedback
Nonparametric classification	Adaptivity to Noise Parameters in Nonparametric Active Learning
nonparametric density estimation	Learning Multivariate Log-concave Distributions
O
online	Bandits with Movement Costs and Adaptive Pricing
online learning	ZIGZAG: A new approach to adaptive online learning Online Learning Without Prior Information (Best Student Paper Award) Fast rates for online learning in Linearly Solvable Markov Decision Processes Corralling a Band of Bandit Algorithms Online Nonparametric Learning, Chaining, and the Role of Partial Feedback Tight Bounds for Bandit Combinatorial Optimization On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities
Online optimization	Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
optimal control	Fast rates for online learning in Linearly Solvable Markov Decision Processes
optimization	Online Learning Without Prior Information (Best Student Paper Award) Submodular Optimization under Noise
orthogonal tensor	Fast and robust tensor decomposition with applications to dictionary learning
outlier	Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization
Outliers	Thresholding based Efficient Outlier Robust PCA
P
PAC learning	Predicting with Distributions On Learning versus Refutation The Sample Complexity of Optimizing a Convex Function Efficient PAC Learning from the Crowd Mixing Implies Lower Bounds for Space Bounded Learning
Partial information	Noisy Population Recovery from Unknown Noise
PCA	Fast Rates for Empirical Risk Minimization of Strict Saddle Problems Fundamental limits of symmetric low-rank matrix estimation
phase retrieval	Correspondence retrieval
Phase transitions	High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition.
population recovery	Sample complexity of population recovery
prediction markets	Memoryless Sequences for Differentiable Losses
pricing	Bandits with Movement Costs and Adaptive Pricing
Program synthesis	Learning Disjunctions of Predicates
proper learning	Robust Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities
property elicitation	Memoryless Sequences for Differentiable Losses Multi-Observation Elicitation
Property Testing	Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing
pseudorandomness	On Learning versus Refutation
Pure Exploration	Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
Q
quadratic constraints	A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
quantum golfing	Exact tensor completion with sum-of-squares
R
Random graph	Two-Sample Tests for Large Random Graphs using Network Statistics
Ranking from pairwise comparisons	Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons
Rates of convergence	Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent
Recursive teaching dimension	Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes
Recursive teaching model	Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes
reductions	On Learning versus Refutation
refutation	On Learning versus Refutation
regret	Sparse Stochastic Bandits
Regularization	Surprising properties of dropout in deep networks
reliable	Reliably Learning the ReLU in Polynomial Time
ReLU	Reliably Learning the ReLU in Polynomial Time
ReLU activation function	Nearly-tight VC-dimension bounds for neural networks
Reproducing kernel Hilbert space	Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
reweighting	Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization
Robust PCA	Thresholding based Efficient Outlier Robust PCA
robustness	Computationally Efficient Robust Estimation of Sparse Functionals Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization
Robustness in learning	Predicting with Distributions
S
SAG	A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
SAGA	A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
sample complexity	Sample complexity of population recovery Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization The Sample Complexity of Optimizing a Convex Function Generalization for Adaptively-chosen Estimators via Stable Median
Sample compression	Optimal learning via local entropies and sample compression
SDCA	A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
Second moment method	High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition.
semi supervised learning	Effective Semisupervised Learning on Manifolds
semidefinite programming	Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality Exact tensor completion with sum-of-squares A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
shortest vector problem	Correspondence retrieval
singular value thresholding	Matrix Completion from O(n) Samples in Linear Time
sparse random graphs	Matrix Completion from O(n) Samples in Linear Time
sparsity	Computationally Efficient Robust Estimation of Sparse Functionals Sparse Stochastic Bandits
spectral algorithm	Fast and robust tensor decomposition with applications to dictionary learning
Spectral Methods	The Hidden Hubs Problem
spin glasses	Fundamental limits of symmetric low-rank matrix estimation
Stability	Fast Rates for Empirical Risk Minimization of Strict Saddle Problems A second-order look at stability and generalization Generalization for Adaptively-chosen Estimators via Stable Median
Statistical estimation	Rates of estimation for determinantal point processes
statistical learning	ZIGZAG: A new approach to adaptive online learning
statistical learning theory	Effective Semisupervised Learning on Manifolds
Statistical Queries	The Hidden Hubs Problem
Statistical Query	Generalization for Adaptively-chosen Estimators via Stable Median
Statistical query learning	A General Characterization of the Statistical Query Complexity
stochastic and adversarial	An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
stochastic approximation	Stochastic Composite Least-Squares Regression with convergence rate O(1/n)
stochastic bandits	An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
Stochastic Convex Optimization	Empirical Risk Minimization for Stochastic Convex Optimization: $O(1/n)$- and $O(1/n^2)$-type of Risk Bounds
Stochastic differential equations	Non-Convex Learning via Stochastic Gradient Langevin Dynamics: A Nonasymptotic Analysis
Stochastic Gradient Langevin Dynamics	A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (Best Paper Award)
Stochastic multi-armed bandit problem	Sparse Stochastic Bandits
Strict saddle	Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
Subadditivity	Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing
submodular	Submodular Optimization under Noise
submodular maximization	Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization
Subset-Selection	The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
subspace clustering	Effective Semisupervised Learning on Manifolds
sum of squares	Fast and robust tensor decomposition with applications to dictionary learning
sum-of-squares method	Exact tensor completion with sum-of-squares
Supervised Learning	Learning Non-Discriminatory Predictors
systems of polynomial inequalities	Robust Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities
T
tail bounds	On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities
tensor completion	Exact tensor completion with sum-of-squares
tensor decomposition	Correspondence retrieval Fast and robust tensor decomposition with applications to dictionary learning
Tensor PCA	Homotopy Analysis for Tensor PCA
Thompson Sampling	Thompson Sampling for the MNL-Bandit
Time-series charts	Learning Disjunctions of Predicates
Time-space tradeoff	Mixing Implies Lower Bounds for Space Bounded Learning
Top-k ranking	Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons
Transportation inequalities	Non-Convex Learning via Stochastic Gradient Langevin Dynamics: A Nonasymptotic Analysis
Two-sample test	Two-Sample Tests for Large Random Graphs using Network Statistics
U
UCB	Sparse Stochastic Bandits
Uniform Distribution	Depth Separation for Neural Networks
unsupervised learning	Effective Semisupervised Learning on Manifolds Efficient Co-Training of Linear Separators under Weak Dependence
V
Variable selection	The Price of Selection in Differential Privacy
VC dimension	Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes Inapproximability of VC Dimension and Littlestone's Dimension Learning Multivariate Log-concave Distributions
VC-dimension	Mixing Implies Lower Bounds for Space Bounded Learning Nearly-tight VC-dimension bounds for neural networks
W
Wasserstein distance	Non-Convex Learning via Stochastic Gradient Langevin Dynamics: A Nonasymptotic Analysis

Disclaimer | Powered by EasyChair Smart Program