COLT 2012

46 papers

(weak) Calibration Is Computationally Hard Elad Hazan, Sham M. Kakade

A Characterization of Scoring Rules for Linear Properties Jacob D. Abernethy, Rafael M. Frongillo

A Conjugate Property Between Loss Functions and Uncertainty Sets in Classification Problems Takafumi Kanamori, Akiko Takeda, Taiji Suzuki

A Correlation Clustering Approach to Link Classification in Signed Networks Nicoló Cesa-Bianchi, Claudio Gentile, Fabio Vitale, Giovanni Zappella

A Method of Moments for Mixture Models and Hidden Markov Models Animashree Anandkumar, Daniel Hsu, Sham M. Kakade

Active Learning Using Smooth Relative Regret Approximations with Applications Nir Ailon, Ron Begleiter, Esther Ezra

Analysis of Thompson Sampling for the Multi-Armed Bandit Problem Shipra Agrawal, Navin Goyal

Attribute-Efficient Learning andWeight-Degree Tradeoffs for Polynomial Threshold Functions Rocco Servedio, Li-Yang Tan, Justin Thaler

Autonomous Exploration for Navigating in MDPs Shiau Hong Lim, Peter Auer

Competitive Classification and Closeness Testing Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan, Ananda Suresh

Computational Bounds on Statistical Query Learning Vitaly Feldman, Varun Kanade

Consistency of Nearest Neighbor Classification Under Selective Sampling Sanjoy Dasgupta

Differentially Private Online Learning Prateek Jain, Pravesh Kothari, Abhradeep Thakurta

Distance Preserving Embeddings for General N-Dimensional Manifolds Nakul Verma

Distributed Learning, Communication Complexity and Privacy Maria Florina Balcan, Avrim Blum, Shai Fine, Yishay Mansour

Divergences and Risks for Multiclass Experiments Dario García-García, Robert C. Williamson

Exact Recovery of Sparsely-Used Dictionaries Daniel A. Spielman, Huan Wang, John Wright

Generalization Bounds for Online Learning Algorithms with Pairwise Loss Functions Yuyang Wang, Roni Khardon, Dmitry Pechyony, Rosie Jones

Kernels Based Tests with Non-Asymptotic Bootstrap Approaches for Two-Sample Problems Magalie Fromont, Béatrice Laurent, Matthieu Lerasle, Patricia Reynaud-Bouret

L1 Covering Numbers for Uniformly Bounded Convex Functions Adityanand Guntuboyina, Bodhisattva Sen

Learning DNF Expressions from Fourier Spectrum Vitaly Feldman

Learning Functions of Halfspaces Using Prefix Covers Parikshit Gopalan, Adam R. Klivans, Raghu Meka

Learning Valuation Functions Maria Florina Balcan, Florin Constantin, Satoru Iwata, Lei Wang

Near-Optimal Algorithms for Online Matrix Prediction Elad Hazan, Satyen Kale, Shai Shalev-Shwartz

New Bounds for Learning Intervals with Implications for Semi-Supervised Learning David P. Helmbold, Philip M. Long

Online Optimization with Gradual Variations Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, Shenghuo Zhu

Open Problem: Better Bounds for Online Logistic Regression H. Brendan McMahan, Matthew Streeter

Open Problem: Does AdaBoost Always Cycle? Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies

Open Problem: Is Averaging Needed for Strongly Convex Stochastic Gradient Descent? Ohad Shamir

Open Problem: Learning Dynamic Network Models from a Static Snapshot Jan Ramon, Constantin Comendant

Open Problem: Regret Bounds for Thompson Sampling Lihong Li, Olivier Chapelle

PAC-Bayesian Bound for Gaussian Process Regression and Multiple Kernel Additive Model Taiji Suzuki

Private Convex Empirical Risk Minimization and High-Dimensional Regression Daniel Kifer, Adam Smith, Abhradeep Thakurta

Random Design Analysis of Ridge Regression Daniel Hsu, Sham M. Kakade, Tong Zhang

Rare Probability Estimation Under Regularly Varying Heavy Tails Mesrob I. Ohannessian, Munther A. Dahleh

Reconstruction from Anisotropic Random Measurements Mark Rudelson, Shuheng Zhou

Robust Interactive Learning Maria Florina Balcan, Steve Hanneke

Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model Kamalika Chaudhuri, Fan Chung, Alexander Tsiatas

The Best of Both Worlds: Stochastic and Adversarial Bandits Sébastien Bubeck, Aleksandrs Slivkins

The Optimality of Jeffreys Prior for Online Density Estimation and the Asymptotic Normality of Maximum Likelihood Estimators Fares Hedayati, Peter L. Bartlett

Tight Bounds on Proper Equivalence Query Learning of DNF Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco Servedio

Toward a Noncommutative Arithmetic-Geometric Mean Inequality: Conjectures, Case-Studies, and Consequences Benjamin Recht, Christopher Re

Toward Understanding Complex Spaces: Graph Laplacians on Manifolds with Singularities and Boundaries Mikhail Belkin, Qichao Que, Yusu Wang, Xueyuan Zhou

Towards Minimax Policies for Online Linear Optimization with Bandit Feedback Sébastien Bubeck, Nicoló Cesa-Bianchi, Sham M. Kakade

Unified Algorithms for Online Learning and Competitive Analysis Niv Buchbinder, Shahar Chen, Joshep (Seffi) Naor, Ohad Shamir

Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem Zohar Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, Omri Weinstein