COLT 2015: 28TH ANNUAL CONFERENCE ON LEARNING THEORY

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

A
absolutely minimal Lipschitz extension	Algorithms for Lipschitz Learning on Graphs
Acceleration	From Averaging to Acceleration, There is Only a Step-size
Active Learning	Sequential Information Maximization: When is Greedy Near-optimal? Hierarchical label queries with data-dependent partitions Efficient Learning of Linear Separators under Bounded Noise
active learning on graphs	$S^2$: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
adaptive estimation	Adaptive recovery of signals by convex optimization
adaptive regret	Achieving All with No Parameters: Adaptive NormalHedge
adaptivity	Achieving All with No Parameters: Adaptive NormalHedge
adversarial noise	Learning and inference in the presence of corrupted inputs
aggregating algorithm	Exp-Concavity of Proper Composite Losses
Agnostic learning	A PTAS for Agnostically Learning Halfspaces
AIXI	Bad Universal Priors and Notions of Optimality
approximate policy evaluation	On Convergence of Emphatic Temporal-Difference Learning
Approximation algorithms	A PTAS for Agnostically Learning Halfspaces
asymptotic optimality	Bad Universal Priors and Notions of Optimality
autoencoding	Efficient Representations for Lifelong Learning and Autoencoding
Averaging	From Averaging to Acceleration, There is Only a Step-size
B
balanced Pareto optimality	Bad Universal Priors and Notions of Optimality
bandit algorithms	Contextual Dueling Bandits
Bandit convex optimization	Bandit Convex Optimization: sqrt{T} Regret in One Dimension
bandit linear optimization	On the Complexity of Bandit Linear Optimization
batches	Batched Bandit Problems
Bounded (a.k.a Massart) Noise	Efficient Learning of Linear Separators under Bounded Noise
Bradley-Terry model	Online Density Estimation of Bradley-Terry Models
C
Censor Block Model	Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
chaining	A Chaining Algorithm for Online Nonparametric Regression
classification	Convex Risk Minimization and Conditional Probability Estimation
Closeness testing	Faster Algorithms for Testing under Conditional Sampling
cluster assumption	Hierarchical label queries with data-dependent partitions
Combinatorial prediction	Second-order Quantile Methods for Experts and Combinatorial Games
Community Detection	Computational Lower Bounds for Community Detection on Random Graphs
computational complexity	Variable Selection is Hard Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
computational learning theory	MCMC Learning
Computational lower bounds	Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
Computationally Efficient Algorithms	Efficient Learning of Linear Separators under Bounded Noise
computationally efficient kernel learning	On the Complexity of Learning with Kernels
concentration	Learning with Square Loss: Localization through Offset Rademacher Complexity
concentration inequalities	Learning the dependence structure of rare events: a non-asymptotic study
concentration of measure	Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization
conditional probability estimation	Convex Risk Minimization and Conditional Probability Estimation
Conditional sampling	Faster Algorithms for Testing under Conditional Sampling
conjunctive query	Learnability of Solutions to Conjunctive Queries: The Full Dichotomy
consistency	Convex Risk Minimization and Conditional Probability Estimation
contextual dueling bandits	Contextual Dueling Bandits
convergence	On Convergence of Emphatic Temporal-Difference Learning
convex analysis	Generalized Mixability via Entropic Duality
Convex calibrated surrogates	On Consistent Surrogate Risk Minimization and Property Elicitation
convex duality	Convex Risk Minimization and Conditional Probability Estimation
Convex optimization	Adaptive recovery of signals by convex optimization From Averaging to Acceleration, There is Only a Step-size
convexity	Regularized Linear Regression: A Precise Analysis of the Estimation Error
correlation clustering	Correlation Clustering with Noisy Partial Information
corrupted inputs	Learning and inference in the presence of corrupted inputs
Cortical algorithms	Cortical Learning via Prediction
Crowd Sourcing	Optimum Statistical Estimation with Strategic Data Sources
D
data privacy	Truthful Linear Regression
decay of correlation	Fast Mixing for Discrete Point Processes
deep learning	Norm-Based Capacity Control in Neural Networks
dictionary learning	Simple, Efficient, and Neural Algorithms for Sparse Coding
Differential Privacy	Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery Truthful Linear Regression
Dimension Reduction	Online PCA with Spectral Bounds
Discrete point process	Fast Mixing for Discrete Point Processes
dueling bandit problem	Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
E
Eigenvalue spacing	Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
elicitation	Vector-Valued Property Elicitation
empirical processes	Learning with Square Loss: Localization through Offset Rademacher Complexity
empirical risk minimization	Competing with the Empirical Risk Minimizer in a Single Pass
Ensemble aggregation	Optimally Combining Classifiers Using Unlabeled Data
estimation error	An Almost Optimal PAC Algorithm (Best Paper Award!)
excess risk	Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization
exp-concavity	Exp-Concavity of Proper Composite Losses
expert algorithm	Achieving All with No Parameters: Adaptive NormalHedge
exponential family model	Low Rank Matrix Completion with Exponential Family Noise
exponentially concave losses	Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization
extreme data classification	Learning the dependence structure of rare events: a non-asymptotic study
F
f-divergence	On Learning Distributions from their Samples
fast mixing	Fast Mixing for Discrete Point Processes
Feed-forward neural networks	Norm-Based Capacity Control in Neural Networks
Feedback graphs	Online Learning with Feedback Graphs: Beyond Bandits
first order bounds	Achieving All with No Parameters: Adaptive NormalHedge
first-order bounds	First-order regret bounds for combinatorial semi-bandits
follow the perturbed leader	First-order regret bounds for combinatorial semi-bandits
Fourier PCA	Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
G
game theory	Contextual Dueling Bandits
Gaussian min-max Theorem	Regularized Linear Regression: A Precise Analysis of the Estimation Error
Gaussian Sampling	Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
general reinforcement learning	Bad Universal Priors and Notions of Optimality
graph partitioning	Partitioning Well-Clustered Graphs: Spectral Clustering Works!
graph prediction	Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints
grouped clinical trials	Batched Bandit Problems
H
Halfspaces	A PTAS for Agnostically Learning Halfspaces
Hartigan consistency	Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering
heat kernel	Partitioning Well-Clustered Graphs: Spectral Clustering Works!
Hidden clique	Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
hierarchical clustering	Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering
I
identification function	Vector-Valued Property Elicitation
Identity testing	Faster Algorithms for Testing under Conditional Sampling
importance sampling	On Convergence of Emphatic Temporal-Difference Learning
improvement for small losses	First-order regret bounds for combinatorial semi-bandits
Independent Component Analysis	Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
individual sequences	A Chaining Algorithm for Online Nonparametric Regression
inference	Learning and inference in the presence of corrupted inputs
information theory	Sequential Information Maximization: When is Greedy Near-optimal? Minimax rates for memory-bounded sparse linear regression
Interactive Data Analysis	Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
interior point methods	The entropic barrier: a simple and optimal universal self-concordant barrier
K
k-means	Partitioning Well-Clustered Graphs: Spectral Clustering Works!
kernel methods	On the Complexity of Learning with Kernels
L
labeling	Hierarchical label queries with data-dependent partitions
LAD	Regularized Linear Regression: A Precise Analysis of the Estimation Error
Lasserre hierarchy	Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints
LASSO	Regularized Linear Regression: A Precise Analysis of the Estimation Error
latent variable models	Learning Overcomplete Latent Variable Models through Tensor Methods
learning	Learning and inference in the presence of corrupted inputs
learning on graphs	Algorithms for Lipschitz Learning on Graphs
least squares	Variable Selection is Hard
Legg-Hutter intelligence	Bad Universal Priors and Notions of Optimality
Lifelong learning	Efficient Representations for Lifelong Learning and Autoencoding
linear bandits	The entropic barrier: a simple and optimal universal self-concordant barrier
linear regression	Truthful Linear Regression Minimax Fixed-Design Linear Regression Regularized Linear Regression: A Precise Analysis of the Estimation Error
Linear Separators	Efficient Learning of Linear Separators under Bounded Noise
Lipschitz extension	Algorithms for Lipschitz Learning on Graphs
local algorithms	Learning and inference in the presence of corrupted inputs
localization	Learning with Square Loss: Localization through Offset Rademacher Complexity A PTAS for Agnostically Learning Halfspaces
log-concave measures	The entropic barrier: a simple and optimal universal self-concordant barrier
low rank matrix estimation	Low Rank Matrix Completion with Exponential Family Noise
lower bound	Label optimal regret bounds for online local learning
lower bounds	On the Complexity of Bandit Linear Optimization On the Complexity of Learning with Kernels
Luckiness bounds	Second-order Quantile Methods for Experts and Combinatorial Games
M
majority vote	An Almost Optimal PAC Algorithm (Best Paper Award!)
Markov Decision Process	Thompson Sampling for Learning Parameterized Markov Decision Processes
Markov decision processes	On Convergence of Emphatic Temporal-Difference Learning
markov random fields	MCMC Learning
matrix completion	Fast Exact Matrix Completion with Finite Samples Low Rank Matrix Completion with Exponential Family Noise
Matrix perturbation theory	Fast Exact Matrix Completion with Finite Samples
Matrix Polynomials	Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
maximum entropy	Convex Risk Minimization and Conditional Probability Estimation
mcmc	MCMC Learning Fast Mixing for Discrete Point Processes
mean-square-error	Regularized Linear Regression: A Precise Analysis of the Estimation Error
Mechanism Design	Optimum Statistical Estimation with Strategic Data Sources Truthful Linear Regression
metric distortion	Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering
minimax	Optimally Combining Classifiers Using Unlabeled Data
minimax regret	Minimax Fixed-Design Linear Regression
Minimax risk	On Learning Distributions from their Samples
mixability	Exp-Concavity of Proper Composite Losses Generalized Mixability via Entropic Duality
Multi-armed bandit	Online Learning with Feedback Graphs: Beyond Bandits
multi-armed bandit problem	Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
Multi-armed bandit problems	Batched Bandit Problems
multi-stage allocation	Batched Bandit Problems
Multiclass classification	On Consistent Surrogate Risk Minimization and Property Elicitation
Multiple Communities	Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
multitask learning	Efficient Representations for Lifelong Learning and Autoencoding
multivariate extremes	Learning the dependence structure of rare events: a non-asymptotic study
N
neuroidal computation	Cortical Learning via Prediction
noise sensitivity	MCMC Learning
non-additive losses	On-Line Learning Algorithms for Path Experts with Non-Additive Losses
non-convex functions	Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
non-convex optimization	Simple, Efficient, and Neural Algorithms for Sparse Coding Fast Exact Matrix Completion with Finite Samples Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
nonparametric classification	$S^2$: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
nonparametric regression	A Chaining Algorithm for Online Nonparametric Regression
nonparametric statistics	Adaptive recovery of signals by convex optimization
NormalHedge	Achieving All with No Parameters: Adaptive NormalHedge
nuclear norm	Low Rank Matrix Completion with Exponential Family Noise
O
offset Rademacher complexity	Learning with Square Loss: Localization through Offset Rademacher Complexity
on-line learning	On-Line Learning Algorithms for Path Experts with Non-Additive Losses
Online	Online PCA with Spectral Bounds
online combinatorial optimization	First-order regret bounds for combinatorial semi-bandits
online density estimation	Online Density Estimation of Bradley-Terry Models
online learning	Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem A Chaining Algorithm for Online Nonparametric Regression On the Complexity of Bandit Linear Optimization Second-order Quantile Methods for Experts and Combinatorial Games Minimax Fixed-Design Linear Regression Bandit Convex Optimization: sqrt{T} Regret in One Dimension Generalized Mixability via Entropic Duality Contextual Dueling Bandits Online Learning with Feedback Graphs: Beyond Bandits
online local learning	Label optimal regret bounds for online local learning
Optimal Mechanism	Optimum Statistical Estimation with Strategic Data Sources
optimal PAC algorithm	An Almost Optimal PAC Algorithm (Best Paper Award!)
Optimization	Sequential Information Maximization: When is Greedy Near-optimal? Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
orlicz spaces	Convex Risk Minimization and Conditional Probability Estimation
overcomplete representations	Learning Overcomplete Latent Variable Models through Tensor Methods
P
PAC-learning	An Almost Optimal PAC Algorithm (Best Paper Award!)
parameter estimation	Tensor principal component analysis
Pareto optimality	Bad Universal Priors and Notions of Optimality
Partitioning trees	Hierarchical label queries with data-dependent partitions
PCA	Online PCA with Spectral Bounds
planted clique	Computational Lower Bounds for Community Detection on Random Graphs Label optimal regret bounds for online local learning
planted dense subgraph	Label optimal regret bounds for online local learning
Polynomial approximation	A PTAS for Agnostically Learning Halfspaces
Polynomial regression	A PTAS for Agnostically Learning Halfspaces
polynomial-time approximation scheme	Correlation Clustering with Noisy Partial Information
Polynomial-time Reduction	Computational Lower Bounds for Community Detection on Random Graphs
prediction	Cortical Learning via Prediction
Prediction with expert advice	Second-order Quantile Methods for Experts and Combinatorial Games Generalized Mixability via Entropic Duality
prediction with membership queries	Learnability of Solutions to Conjunctive Queries: The Full Dichotomy
predictive join (PJOIN)	Cortical Learning via Prediction
Principal Component Analysis	Tensor principal component analysis Online PCA with Spectral Bounds
privacy	Truthful Linear Regression
Probability estimation	On Learning Distributions from their Samples
proper composite losses	Exp-Concavity of Proper Composite Losses
proper loss	Vector-Valued Property Elicitation
Proper losses	On Consistent Surrogate Risk Minimization and Property Elicitation
Proper scoring rules	On Consistent Surrogate Risk Minimization and Property Elicitation
property	Vector-Valued Property Elicitation
Property elicitation	On Consistent Surrogate Risk Minimization and Property Elicitation
Property testing	Faster Algorithms for Testing under Conditional Sampling
Q
Quantiles	Second-order Quantile Methods for Experts and Combinatorial Games
query complexity of finding a cut	$S^2$: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
R
Rademacher complexity	Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints
random walk	Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
Random Walks	Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
ranking	Online Density Estimation of Bradley-Terry Models
Regression	Optimum Statistical Estimation with Strategic Data Sources
regret	Label optimal regret bounds for online local learning
regret bounds	Batched Bandit Problems
Regret Minimization	Thompson Sampling for Learning Parameterized Markov Decision Processes
reinforcement learning	On Convergence of Emphatic Temporal-Difference Learning
resource-constrained learning	Minimax rates for memory-bounded sparse linear regression
S
saddle points	Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
Sample Complexity	Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
sample size	An Almost Optimal PAC Algorithm (Best Paper Award!)
sample size determination	Batched Bandit Problems
scale-sensitive capacity control	Norm-Based Capacity Control in Neural Networks
scoring rule	Vector-Valued Property Elicitation
Second-order	Second-order Quantile Methods for Experts and Combinatorial Games
self-concordant barriers	The entropic barrier: a simple and optimal universal self-concordant barrier
semi-bandit feedback	First-order regret bounds for combinatorial semi-bandits
semi-random model	Correlation Clustering with Noisy Partial Information
semi-supervised learning	Algorithms for Lipschitz Learning on Graphs
semidefinite programming	Tensor principal component analysis
shared representations	Efficient Representations for Lifelong Learning and Autoencoding
shifted power iteration	Tensor principal component analysis
shifting regret	Achieving All with No Parameters: Adaptive NormalHedge
simulated annealing	Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
Singular Value Decomposition	Online PCA with Spectral Bounds
sleeping expert	Achieving All with No Parameters: Adaptive NormalHedge
sparse coding	Simple, Efficient, and Neural Algorithms for Sparse Coding
sparse regression	Variable Selection is Hard Minimax rates for memory-bounded sparse linear regression
sparsity	Regularized Linear Regression: A Precise Analysis of the Estimation Error
Spectral Algorithm	Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
spectral algorithms	Tensor principal component analysis
spectral clustering	Partitioning Well-Clustered Graphs: Spectral Clustering Works!
Spectral Sparsification	Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
stable tail dependence function	Learning the dependence structure of rare events: a non-asymptotic study
Statistical Estimation	Optimum Statistical Estimation with Strategic Data Sources
Statistical Query Model	Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
stochastic approximation	Competing with the Empirical Risk Minimizer in a Single Pass On Convergence of Emphatic Temporal-Difference Learning
Stochastic Block Model	Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
stochastic gradient	From Averaging to Acceleration, There is Only a Step-size Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
stochastic optimization	Competing with the Empirical Risk Minimizer in a Single Pass Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization
streaming algorithms	Competing with the Empirical Risk Minimizer in a Single Pass
structured prediction	On-Line Learning Algorithms for Path Experts with Non-Additive Losses
structured signals	Regularized Linear Regression: A Precise Analysis of the Estimation Error
submodular functions	Fast Mixing for Discrete Point Processes
substitution functions	Exp-Concavity of Proper Composite Losses
Sum of squares	Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
sum-of-squares method	Tensor principal component analysis
Surrogate risk minimization	On Consistent Surrogate Risk Minimization and Property Elicitation
SVD	Online PCA with Spectral Bounds
switching cost	Batched Bandit Problems
T
temporal difference methods	On Convergence of Emphatic Temporal-Difference Learning
tensor decomposition	Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity Learning Overcomplete Latent Variable Models through Tensor Methods Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
Tensors	Tensor principal component analysis
Thompson sampling	Bandit Convex Optimization: sqrt{T} Regret in One Dimension Thompson Sampling for Learning Parameterized Markov Decision Processes
time-varying competitors	Achieving All with No Parameters: Adaptive NormalHedge
transductive	Optimally Combining Classifiers Using Unlabeled Data
U
unbounded functions	Learning with Square Loss: Localization through Offset Rademacher Complexity
unified framework	Regularized Linear Regression: A Precise Analysis of the Estimation Error
Uniform distribution	A PTAS for Agnostically Learning Halfspaces
Unique Dominant Strategy Equilibrium	Optimum Statistical Estimation with Strategic Data Sources
universal algebra	Learnability of Solutions to Conjunctive Queries: The Full Dichotomy
universal Turing machine	Bad Universal Priors and Notions of Optimality
unknown competitors	Achieving All with No Parameters: Adaptive NormalHedge
unsupervised and semi-supervised learning	Learning Overcomplete Latent Variable Models through Tensor Methods
unsupervised learning	Cortical Learning via Prediction Simple, Efficient, and Neural Algorithms for Sparse Coding
V
variable selection	Variable Selection is Hard
variance reduction	Competing with the Empirical Risk Minimizer in a Single Pass
VC theory	Learning the dependence structure of rare events: a non-asymptotic study
W
weighted average algorithm	Exp-Concavity of Proper Composite Losses

Disclaimer | Powered by EasyChair Smart ProgramDisclaimer | Powered by EasyChair Smart Program