Friday, July 03, 2015

Proceedings of The 28th Conference on Learning Theory - COLT 2015

So the COLT conference started this morning in sweltering Paris. Many of the presentations have been featured in a fashion or another on Nuit Blanche. Here are the full proceedings


Regular Papers

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

Open Problems

  • Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs, Arindam Banerjee, Sheng Chen, Vidyashankar Sivakumar, [abs] [pdf]
  • Open Problem: The landscape of the loss surfaces of multilayer networks, Anna, Choromanska, Yann, LeCun, Gérard Ben Arous [abs] [pdf]
  • Open Problem: The Oracle Complexity of Smooth Convex Optimization in Nonstandard Settings, Cristóbal Guzmán [abs] [pdf]
  • Open Problem: Online Sabotaged Shortest Path, Wouter M. Koolen, Manfred K. Warmuth, Dmitri Adamskiy, [abs] [pdf]
  • Open Problem: Learning Quantum Circuits with Queries, Jeremy Kun, Lev Reyzin, [abs] [pdf]
  • Open Problem: Recursive Teaching Dimension Versus VC Dimension, Hans U. Simon, Sandra Zilles, [abs] [pdf]
Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments: