COLT 2016: THE 29TH ANNUAL CONFERENCE ON LEARNING THEORY

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

$
$\ell_q$-based Laplacian regularization	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
1
1-bit compressed sensing	Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise
A
Absolutely Minimal Lipschitz Extension	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
abstention	The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions
Active Learning	Best-of-K Bandits Interactive Algorithms: from Pool to Stream
Adaptive data analysis	Adaptive Learning with Robust Generalization Guarantees
aggregation	Aggregation of supports along the Lasso path
approximation	Benefits of depth in neural networks
Arithmetic Circuits	A Guide to Learning Arithmetic Circuits On the Expressive Power of Deep Learning: A Tensor Analysis
Asymptotic behavior	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
Auction Theory	Learning Simple Auctions
B
bandit	Simple Bayesian Algorithms for Best Arm Identification
Bandit problems	Online learning in repeated auctions
Bandit Theory	Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
basis learning	Basis Learning as an Algorithmic Primitive
bayesian	Simple Bayesian Algorithms for Best Arm Identification
Bayesian algorithms	Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
Belief propagation	Density Evolution in the Degree-correlated Stochastic Block Model
best arm identification	Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem Simple Bayesian Algorithms for Best Arm Identification Optimal Best Arm Identification with Fixed Confidence
best-arm identification	Maximin Action Identification: A New Bandit Framework for Games
Best-case analysis	On the Approximability of Sparse PCA
Blackwell Approachability	Online Learning and Blackwell Approachability in Quitting Games
Burer-Monteiro heuristic	On the low-rank approach for semidefinite programs arising in synchronization and community detection
C
Calibration	Online Learning and Blackwell Approachability in Quitting Games
classification	The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions
Collaborative filtering	Provably manipulation-resistant reputation systems (Best Student Paper Award)
collection of distributions	Learning and Testing Junta Distributions
communication complexity	Sign rank versus VC dimension
Community detection	Density Evolution in the Degree-correlated Stochastic Block Model Information-theoretic thresholds for community detection in sparse networks Learning Communities in the Presence of Errors Semidefinite Programs for Exact Recovery of a Hidden Community On the low-rank approach for semidefinite programs arising in synchronization and community detection
Complexity of Learning	A Guide to Learning Arithmetic Circuits
computational hardness	Online Sparse Linear Regression
computational vs. statistical tradeoffs	Noisy Tensor Completion via the Sum-of-Squares Hierarchy
concave objective	An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
condensation threshold	Information-theoretic thresholds for community detection in sparse networks
constraint	A Light Touch for Heavily Constrained SGD
contextual bandits	An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
convex bandits	Multi-scale exploration of convex functions and bandit convex optimization (Best Paper Award)
convex geometry	Multi-scale exploration of convex functions and bandit convex optimization (Best Paper Award)
Cooperative Bandits	Delay and Cooperation in Nonstochastic Bandits
correlation decay	How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
Cortical Computation	Cortical Computation via Iterative Constructions
coverage functions	Learning Combinatorial Functions from Pairwise Comparisons
Curie-Weiss	How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
D
Data Privacy	Adaptive Learning with Robust Generalization Guarantees
Deep Learning	On the Expressive Power of Deep Learning: A Tensor Analysis
degenerate saddle points	Efficient approaches for escaping higher order saddle points in non-convex optimization
Delayed Feedback	Delay and Cooperation in Nonstochastic Bandits
Density evolution	Density Evolution in the Degree-correlated Stochastic Block Model
depth hierarchy	Benefits of depth in neural networks
Depth vs. Width	The Power of Depth for Feedforward Neural Networks
design of experiments	Simple Bayesian Algorithms for Best Arm Identification
determinantal point processes sampling	Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
dimension complexity	Sign rank versus VC dimension
Distributed Learning	Delay and Cooperation in Nonstochastic Bandits
distribution learning	Properly Learning Poisson Binomial Distributions in Almost Polynomial Time Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
DNF	Complexity theoretic limitations on learning DNF's
dueling bandits	Instance-dependent Regret Bounds for Dueling Bandits
E
ensembles	Time Series Prediction and Online Learning
Error analysis	Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
Exact Learning	A Guide to Learning Arithmetic Circuits
exp-concave loss	Online Isotonic Regression
Expert Advice	Online Learning with Low Rank Experts
Exponential Weights	Online Isotonic Regression
Expressive Power	On the Expressive Power of Deep Learning: A Tensor Analysis
F
Factored linear models	Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
first-order methods	First-order Methods for Geodesically Convex Optimization
Fixed Confidence Setting	Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
fluid model	On the capacity of information processing systems
Fourier analysis	Learning and Testing Junta Distributions
Fourier transform	The Power of Depth for Feedforward Neural Networks Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
Function approximation	The Power of Depth for Feedforward Neural Networks
G
game theory	Instance-dependent Regret Bounds for Dueling Bandits
games	Maximin Action Identification: A New Bandit Framework for Games
Generalization	Adaptive Learning with Robust Generalization Guarantees
generalization bounds	Time Series Prediction and Online Learning
geodesic convexity	First-order Methods for Geodesically Convex Optimization
geometric concept classes	Preference-based Teaching
Geometric random graph model	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
Gradient descent	Gradient Descent only Converges to Minimizers
gradient iteration	Basis Learning as an Algorithmic Primitive
H
Hardnes of learning	Complexity theoretic limitations on learning DNF's
Hardness of approximation	On the Approximability of Sparse PCA
hidden convexity	Basis Learning as an Algorithmic Primitive
higher order conditions for local optimality	Efficient approaches for escaping higher order saddle points in non-convex optimization
I
image denoising	Optimal rates for total variation denoising
Improper learning	Complexity theoretic limitations on learning DNF's
information processing system	On the capacity of information processing systems
Interactive algorithms	Interactive Algorithms: from Pool to Stream
Ising models	How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
isotonic regression	Online Isotonic Regression
iteration complexity	First-order Methods for Geodesically Convex Optimization
Iterative Constructions	Cortical Computation via Iterative Constructions
J
Juntas	Learning and Testing Junta Distributions
K
kernel machines	Sign rank versus VC dimension
Knapsack constraints	An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
L
Lasserre hierarchy	How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
Lasso path	Aggregation of supports along the Lasso path
Latent Variable Model	Reinforcement Learning of POMDPs using Spectral Methods
learning	A Light Touch for Heavily Constrained SGD
learning combinatorial functions	Learning Combinatorial Functions from Pairwise Comparisons
Learning distributions	Learning and Testing Junta Distributions
learning halfspaces	Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise
learning parities	Memory, Communication, and Statistical Queries
Learning Theory	Learning Simple Auctions
learning with noise	Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise Learning Communities in the Presence of Errors
Linear regression	Aggregation of supports along the Lasso path
linear sets	Preference-based Teaching
local minimum	Gradient Descent only Converges to Minimizers
Low Rank	Online Learning with Low Rank Experts Dropping Convexity for Faster Semi-definite Optimization
Low-rank matrix completion	When Can We Rank Well from Comparisons of $O(n\log n)$ Non-Actively Chosen Pairs?
Lower Bounds	A Guide to Learning Arithmetic Circuits Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
LUCB	Maximin Action Identification: A New Bandit Framework for Games
M
manifold optimization	First-order Methods for Geodesically Convex Optimization
Manipulation-resistance	Provably manipulation-resistant reputation systems (Best Student Paper Award)
markov chains	Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
Markov Decision Process	Online Learning and Blackwell Approachability in Quitting Games
matrix concentration	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm
matroid	Pure Exploration of Multi-armed Bandit Under Matroid Constraints
maximum classes	Sign rank versus VC dimension
MDL	Optimal Best Arm Identification with Fixed Confidence
Method of Moments	Reinforcement Learning of POMDPs using Spectral Methods
metric entropy	Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
minimax	Multi-scale exploration of convex functions and bandit convex optimization (Best Paper Award)
mixing time	Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
model selection	Time Series Prediction and Online Learning
Model-based reinforcement learning	Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
modeling errors	Learning Communities in the Presence of Errors
Modular Square Root Extraction	A Guide to Learning Arithmetic Circuits
Monotone functions	Cortical Computation via Iterative Constructions
monotonic regression	Online Isotonic Regression
Monte Carlo markov chain algorithms	Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
Multi-arm Arm Bandits	Best-of-K Bandits
multi-armed bandit	Pure Exploration of Multi-armed Bandit Under Matroid Constraints
multi-armed bandit problems	Maximin Action Identification: A New Bandit Framework for Games
multi-armed bandits	An algorithm with nearly optimal pseudo-regret \\for both stochastic and adversarial bandits Optimal Best Arm Identification with Fixed Confidence An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
Multi-label learning	Learning Simple Auctions
Multiparameter Mechanism Design	Learning Simple Auctions
N
Neural networks	The Power of Depth for Feedforward Neural Networks Benefits of depth in neural networks
noisy power method	An Improved Gap-Dependency Analysis of the Noisy Power Method
non-convex	Gradient Descent only Converges to Minimizers
Non-convex optimization	Efficient approaches for escaping higher order saddle points in non-convex optimization Basis Learning as an Algorithmic Primitive Dropping Convexity for Faster Semi-definite Optimization
non-mixing	Time Series Prediction and Online Learning
non-stationary	Time Series Prediction and Online Learning
nonparametric regression	Online Isotonic Regression
nonpositively curved spaces	First-order Methods for Geodesically Convex Optimization
Nonstochastic Bandits	Delay and Cooperation in Nonstochastic Bandits
O
on-line learning	Time Series Prediction and Online Learning
online	The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions
online learning	Instance-dependent Regret Bounds for Dueling Bandits Online Sparse Linear Regression Provably manipulation-resistant reputation systems (Best Student Paper Award) Online Learning with Low Rank Experts Delay and Cooperation in Nonstochastic Bandits Highly-Smooth Zero-th Order Online Optimization Online Isotonic Regression Online Learning and Blackwell Approachability in Quitting Games Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
online sparse regression	Online Sparse Linear Regression
optimization	A Light Touch for Heavily Constrained SGD Highly-Smooth Zero-th Order Online Optimization
optimization over polynomials with real roots	Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
oracle inequalities	Aggregation of supports along the Lasso path
P
pairwise comparisons	Learning Combinatorial Functions from Pairwise Comparisons When Can We Rank Well from Comparisons of $O(n\log n)$ Non-Actively Chosen Pairs?
Partially Observable Markov Decision Process	Reinforcement Learning of POMDPs using Spectral Methods
partition function	How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
phase transition	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning Information-theoretic thresholds for community detection in sparse networks
Planted dense subgraph recovery	Semidefinite Programs for Exact Recovery of a Hidden Community
planted partitioning	Learning Communities in the Presence of Errors
planted satisfiability	Spectral thresholds in the bipartite stochastic block model
Poisson binomial distribution	Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
pool-based	Interactive Algorithms: from Pool to Stream
power methods	Basis Learning as an Algorithmic Primitive
prediction loss	Aggregation of supports along the Lasso path
preference relation	Preference-based Teaching
principal component analysis	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm An Improved Gap-Dependency Analysis of the Noisy Power Method
proper learning	Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
Property testing	Learning and Testing Junta Distributions
pure exploration	Best-of-K Bandits Pure Exploration of Multi-armed Bandit Under Matroid Constraints Simple Bayesian Algorithms for Best Arm Identification
R
racing	Maximin Action Identification: A New Bandit Framework for Games
random matrices	Spectral thresholds in the bipartite stochastic block model
rank minimization	Dropping Convexity for Faster Semi-definite Optimization
Ranking	When Can We Rank Well from Comparisons of $O(n\log n)$ Non-Actively Chosen Pairs?
recursive teaching dimension	Preference-based Teaching
refutation	Noisy Tensor Completion via the Sum-of-Squares Hierarchy
regret	Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
regret analysis	An algorithm with nearly optimal pseudo-regret \\for both stochastic and adversarial bandits
regret bounds	Online Sparse Linear Regression
Regret minimization	Time Series Prediction and Online Learning Online Learning and Blackwell Approachability in Quitting Games
reinforcement learning	Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
Repeated auctions	Online learning in repeated auctions
representation	Benefits of depth in neural networks
Reputation systems	Provably manipulation-resistant reputation systems (Best Student Paper Award)
resource-constrained learning	Memory, Communication, and Statistical Queries
robust algorithms	Learning Communities in the Presence of Errors
Robustness	Adaptive Learning with Robust Generalization Guarantees
S
saddle points	Gradient Descent only Converges to Minimizers
SDPLR	On the low-rank approach for semidefinite programs arising in synchronization and community detection
Second price auctions	Online learning in repeated auctions
semi-definite	Dropping Convexity for Faster Semi-definite Optimization
semi-definite programming	Learning Communities in the Presence of Errors
Semi-supervised learning	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
Semidefinite Programming	On the low-rank approach for semidefinite programs arising in synchronization and community detection
Semidefinite programming relaxations	Semidefinite Programs for Exact Recovery of a Hidden Community
sequential hypothesis testing	On the capacity of information processing systems
SGD	A Light Touch for Heavily Constrained SGD
sharp oracle inequalities	Optimal rates for total variation denoising
Sherali-Adams hierarchy	How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
sign rank	Sign rank versus VC dimension
Simple Regret	Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
Smoothness	Highly-Smooth Zero-th Order Online Optimization
Sparse PCA	On the Approximability of Sparse PCA
spectral algorithms	Spectral thresholds in the bipartite stochastic block model
spectral gap	Sign rank versus VC dimension An Improved Gap-Dependency Analysis of the Noisy Power Method
Spectral Methods	Reinforcement Learning of POMDPs using Spectral Methods
stability	Time Series Prediction and Online Learning
statistical query model	Memory, Communication, and Statistical Queries
stochastic and adversarial	An algorithm with nearly optimal pseudo-regret \\for both stochastic and adversarial bandits
stochastic block model	Spectral thresholds in the bipartite stochastic block model Information-theoretic thresholds for community detection in sparse networks
stochastic block models	Learning Communities in the Presence of Errors
stochastic gradient descent	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm
stochastic resource allocation	On the capacity of information processing systems
stream-based	Interactive Algorithms: from Pool to Stream
streaming algorithms	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm
strongly Rayleigh distributions	Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
Submatrix localization	Semidefinite Programs for Exact Recovery of a Hidden Community
submodularity	Learning Combinatorial Functions from Pairwise Comparisons
sum-of-squares	Noisy Tensor Completion via the Sum-of-Squares Hierarchy
sums of independent random variables	Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
Synchronization	On the low-rank approach for semidefinite programs arising in synchronization and community detection
T
teaching dimension	Preference-based Teaching
tensor completion	Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Tensor Decompositions	On the Expressive Power of Deep Learning: A Tensor Analysis
thompson sampling	Simple Bayesian Algorithms for Best Arm Identification
threshold	Information-theoretic thresholds for community detection in sparse networks
Threshold functions	Cortical Computation via Iterative Constructions
time series prediction	Time Series Prediction and Online Learning
top eigenvector	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm
total variation regularization	Optimal rates for total variation denoising
trust region methods	Efficient approaches for escaping higher order saddle points in non-convex optimization
V
validation	Time Series Prediction and Online Learning
variational inference	How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
variational methods	How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
VC dimension	Sign rank versus VC dimension
Vickrey auctions	Online learning in repeated auctions

Disclaimer | Powered by EasyChair Smart Program