COLT 2015: 28TH ANNUAL CONFERENCE ON LEARNING THEORY

A
Agarwal, Arpit	On Consistent Surrogate Risk Minimization and Property Elicitation
Agarwal, Shivani	On Consistent Surrogate Risk Minimization and Property Elicitation
Alon, Noga	Online Learning with Feedback Graphs: Beyond Bandits
Anandkumar, Animashree	Learning Overcomplete Latent Variable Models through Tensor Methods
Arora, Sanjeev	Simple, Efficient, and Neural Algorithms for Sparse Coding
Awasthi, Pranjal	Label optimal regret bounds for online local learning Efficient Learning of Linear Separators under Bounded Noise
B
Bach, Francis	From Averaging to Acceleration, There is Only a Step-size
Balcan, Maria-Florina	Efficient Representations for Lifelong Learning and Autoencoding Efficient Learning of Linear Separators under Bounded Noise
Balsubramani, Akshay	Optimally Combining Classifiers Using Unlabeled Data
Bartlett, Peter	Minimax Fixed-Design Linear Regression
Belkin, Mikhail	Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering
Belloni, Alexandre	Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
Ben-David, Shai	Hierarchical label queries with data-dependent partitions
Blum, Avrim	Efficient Representations for Lifelong Learning and Autoencoding
Bubeck, Sébastien	The entropic barrier: a simple and optimal universal self-concordant barrier Bandit Convex Optimization: sqrt{T} Regret in One Dimension
C
Cai, Yang	Optimum Statistical Estimation with Strategic Data Sources
Cesa-Bianchi, Nicolo	On the Complexity of Learning with Kernels Online Learning with Feedback Graphs: Beyond Bandits
Charikar, Moses	Label optimal regret bounds for online local learning
Chassang, Sylvain	Batched Bandit Problems
Chen, Hubie	Learnability of Solutions to Conjunctive Queries: The Full Dichotomy
Chen, Yuxin	Sequential Information Maximization: When is Greedy Near-optimal?
Cheng, Dehua	Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
Cheng, Yu	Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
Chin, Peter	Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
Clémençon, Stéphan	Learning the dependence structure of rare events: a non-asymptotic study
Cortes, Corinna	On-Line Learning Algorithms for Path Experts with Non-Additive Losses
Cummings, Rachel	Truthful Linear Regression
D
Daniely, Amit	A PTAS for Agnostically Learning Halfspaces
Dasarathy, Gautam	$S^2$: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
Daskalakis, Constantinos	Optimum Statistical Estimation with Strategic Data Sources
Dekel, Ofer	Bandit Convex Optimization: sqrt{T} Regret in One Dimension Online Learning with Feedback Graphs: Beyond Bandits
Deshpande, Yash	Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
Duchi, John	Minimax rates for memory-bounded sparse linear regression
Dudík, Miroslav	Convex Risk Minimization and Conditional Probability Estimation Contextual Dueling Bandits
E
Eldan, Ronen	The entropic barrier: a simple and optimal universal self-concordant barrier
Eldridge, Justin	Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering
F
Falahatgar, Moein	Faster Algorithms for Testing under Conditional Sampling
Feige, Uriel	Learning and inference in the presence of corrupted inputs
Flammarion, Nicolas	From Averaging to Acceleration, There is Only a Step-size
Foster, Dean	Variable Selection is Hard
Freund, Yoav	Optimally Combining Classifiers Using Unlabeled Data
Frongillo, Rafael	Vector-Valued Property Elicitation Generalized Mixability via Entropic Duality
Frostig, Roy	Competing with the Empirical Risk Minimizer in a Single Pass
G
Gaillard, Pierre	A Chaining Algorithm for Online Nonparametric Regression
Ge, Rong	Simple, Efficient, and Neural Algorithms for Sparse Coding Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition Competing with the Empirical Risk Minimizer in a Single Pass Learning Overcomplete Latent Variable Models through Tensor Methods
Gerchinovitz, Sébastien	A Chaining Algorithm for Online Nonparametric Regression
Goix, Nicolas	Learning the dependence structure of rare events: a non-asymptotic study
Gopalan, Aditya	Thompson Sampling for Learning Parameterized Markov Decision Processes
H
Haghtalab, Nika	Efficient Learning of Linear Separators under Bounded Noise
Hajek, Bruce	Computational Lower Bounds for Community Detection on Random Graphs
Harchaoui, Zaid	Adaptive recovery of signals by convex optimization
Hassani, Hamed	Sequential Information Maximization: When is Greedy Near-optimal?
Hassibi, Babak	Regularized Linear Regression: A Precise Analysis of the Estimation Error
Hatano, Kohei	Online Density Estimation of Bradley-Terry Models
Hofmann, Katja	Contextual Dueling Bandits
Honda, Junya	Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
Hopkins, Sam	Tensor principal component analysis
Huang, Furong	Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
Hutter, Marcus	Bad Universal Priors and Notions of Optimality
I
Ioannidis, Stratis	Truthful Linear Regression
J
Jafarpour, Ashkan	Faster Algorithms for Testing under Conditional Sampling
Jain, Prateek	Fast Exact Matrix Completion with Finite Samples
Janzamin, Majid	Learning Overcomplete Latent Variable Models through Tensor Methods
Jin, Chi	Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
Jin, Rong	Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization
Juditsky, Anatoli	Adaptive recovery of signals by convex optimization
K
Kakade, Sham	Competing with the Empirical Risk Minimizer in a Single Pass
Kamalaruban, Parameswaran	Exp-Concavity of Proper Composite Losses
Kamath, Sudeep	On Learning Distributions from their Samples
Kanade, Varun	MCMC Learning
Karbasi, Amin	Sequential Information Maximization: When is Greedy Near-optimal?
Karbasi, Amin	Fast Mixing for Discrete Point Processes
Karloff, Howard	Variable Selection is Hard
Karnin, Zohar	Online PCA with Spectral Bounds
Kash, Ian	Vector-Valued Property Elicitation
Kashima, Hisashi	Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
Komiyama, Junpei	Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
Koolen, Wouter M.	Second-order Quantile Methods for Experts and Combinatorial Games Minimax Fixed-Design Linear Regression
Koren, Tomer	Bandit Convex Optimization: sqrt{T} Regret in One Dimension Online Learning with Feedback Graphs: Beyond Bandits
Kpotufe, Samory	Hierarchical label queries with data-dependent partitions
Krause, Andreas	Sequential Information Maximization: When is Greedy Near-optimal?
Kuznetsov, Vitaly	On-Line Learning Algorithms for Path Experts with Non-Additive Losses
Kyng, Rasmus	Algorithms for Lipschitz Learning on Graphs
L
Lafond, Jean	Low Rank Matrix Completion with Exponential Family Noise
Lai, Kevin	Label optimal regret bounds for online local learning
Leike, Jan	Bad Universal Priors and Notions of Optimality
Liang, Tengyuan	Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions Learning with Square Loss: Localization through Offset Rademacher Complexity
Liberty, Edo	Online PCA with Spectral Bounds
Ligett, Katrina	Truthful Linear Regression
Liu, Yan	Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
Luo, Haipeng	Achieving All with No Parameters: Adaptive NormalHedge
M
Ma, Tengyu	Simple, Efficient, and Neural Algorithms for Sparse Coding
Mahdavi, Mehrdad	Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization
Makarychev, Konstantin	Correlation Clustering with Noisy Partial Information
Makarychev, Yury	Correlation Clustering with Noisy Partial Information
Malek, Alan	Minimax Fixed-Design Linear Regression
Mannor, Shie	Thompson Sampling for Learning Parameterized Markov Decision Processes
Mansour, Yishay	On the Complexity of Learning with Kernels Learning and inference in the presence of corrupted inputs
Matsumoto, Issei	Online Density Estimation of Bradley-Terry Models
Mehta, Nishant	Generalized Mixability via Entropic Duality
Mohri, Mehryar	On-Line Learning Algorithms for Path Experts with Non-Additive Losses
Moitra, Ankur	Simple, Efficient, and Neural Algorithms for Sparse Coding
Montanari, Andrea	Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
Mossel, Elchanan	MCMC Learning
N
Nakagawa, Hiroshi	Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
Narayanan, Hari	Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
Nemirovski, Arkadi	Adaptive recovery of signals by convex optimization
Netrapalli, Praneeth	Fast Exact Matrix Completion with Finite Samples
Neu, Gergely	First-order regret bounds for combinatorial semi-bandits
Neyshabur, Behnam	Norm-Based Capacity Control in Neural Networks
Nowak, Robert	$S^2$: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
O
Orlitsky, Alon	Faster Algorithms for Testing under Conditional Sampling On Learning Distributions from their Samples
Ostrovsky, Dmitry	Adaptive recovery of signals by convex optimization
Oymak, Samet	Regularized Linear Regression: A Precise Analysis of the Estimation Error
P
Papadimitriou, Christos	Cortical Learning via Prediction Optimum Statistical Estimation with Strategic Data Sources
Peng, Richard	Partitioning Well-Clustered Graphs: Spectral Clustering Works! Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
Perchet, Vianney	Batched Bandit Problems
Peres, Yuval	Bandit Convex Optimization: sqrt{T} Regret in One Dimension
Pichapati, Venkatadheeraj	Faster Algorithms for Testing under Conditional Sampling On Learning Distributions from their Samples
R
Rakhlin, Alexander	Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions Learning with Square Loss: Localization through Offset Rademacher Complexity Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints
Rao, Anup	Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery Algorithms for Lipschitz Learning on Graphs
Rebeschini, Patrick	Fast Mixing for Discrete Point Processes
Reid, Mark	Generalized Mixability via Entropic Duality
Rigollet, Philippe	Batched Bandit Problems
Risteski, Andrej	Label optimal regret bounds for online local learning
Roughgarden, Tim	Applications of Learning Theory in Algorithmic Game Theory
S
Sabourin, Anne	Learning the dependence structure of rare events: a non-asymptotic study
Sachdeva, Sushant	Algorithms for Lipschitz Learning on Graphs
Schapire, Robert	Achieving All with No Parameters: Adaptive NormalHedge Learning and inference in the presence of corrupted inputs Convex Risk Minimization and Conditional Probability Estimation Contextual Dueling Bandits
Shamir, Ohad	On the Complexity of Learning with Kernels On the Complexity of Bandit Linear Optimization
Shi, Jonathan	Tensor principal component analysis
Sidford, Aaron	Competing with the Empirical Risk Minimizer in a Single Pass
Simon, Hans	An Almost Optimal PAC Algorithm (Best Paper Award!)
Slivkins, Aleksandrs	Contextual Dueling Bandits
Snowberg, Erik	Batched Bandit Problems
Spielman, Daniel	Laplacian Matrices of Graphs: Algorithms and Applications Algorithms for Lipschitz Learning on Graphs
Srebro, Nathan	Norm-Based Capacity Control in Neural Networks
Sridharan, Karthik	Learning with Square Loss: Localization through Offset Rademacher Complexity Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints
Steinhardt, Jacob	Minimax rates for memory-bounded sparse linear regression
Steinke, Thomas	Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
Steurer, David	Tensor principal component analysis
Sun, He	Partitioning Well-Clustered Graphs: Spectral Clustering Works!
Suresh, Ananda Theertha	Faster Algorithms for Testing under Conditional Sampling On Learning Distributions from their Samples
T
Takimoto, Eiji	Online Density Estimation of Bradley-Terry Models Minimax Fixed-Design Linear Regression
Telgarsky, Matus	Convex Risk Minimization and Conditional Probability Estimation
Teng, Shang-Hua	Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
Thaler, Justin	Variable Selection is Hard
Thrampoulidis, Christos	Regularized Linear Regression: A Precise Analysis of the Estimation Error
Tomioka, Ryota	Norm-Based Capacity Control in Neural Networks
U
Ullman, Jonathan	Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
Urner, Ruth	Efficient Learning of Linear Separators under Bounded Noise Hierarchical label queries with data-dependent partitions
V
Valeriote, Matt	Learnability of Solutions to Conjunctive Queries: The Full Dichotomy
Van Erven, Tim	Second-order Quantile Methods for Experts and Combinatorial Games
Vempala, Santosh	Cortical Learning via Prediction Efficient Representations for Lifelong Learning and Autoencoding Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
Vijayaraghavan, Aravindan	Correlation Clustering with Noisy Partial Information
Villani, Cedric	Synthetic theory of Ricci curvature - when information theory, optimization, geometry and gradient flows meet
Vu, Van	Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
W
Wang, Yusu	Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering
Warmuth, Manfred	On-Line Learning Algorithms for Path Experts with Non-Additive Losses Minimax Fixed-Design Linear Regression
Williamson, Robert	Exp-Concavity of Proper Composite Losses Generalized Mixability via Entropic Duality
Wu, Yihong	Computational Lower Bounds for Community Detection on Random Graphs
X
Xiao, Ying	Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
Xu, Jiaming	Computational Lower Bounds for Community Detection on Random Graphs
Y
Yu, Huizhen	On Convergence of Emphatic Temporal-Difference Learning
Yuan, Yang	Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
Z
Zanetti, Luca	Partitioning Well-Clustered Graphs: Spectral Clustering Works!
Zhang, Lijun	Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization
Zhang, Xinhua	Exp-Concavity of Proper Composite Losses
Zhu, Xiaojin	$S^2$: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
Zoghi, Masrour	Contextual Dueling Bandits

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