COLT 2012

46 papers

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

Ohad Shamir

Open Problem: Does AdaBoost Always Cycle?

Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies

Open Problem: Learning Dynamic Network Models from a Static Snapshot

Jan Ramon, Constantin Comendant

Open Problem: Better Bounds for Online Logistic Regression

H. Brendan McMahan, Matthew Streeter

Open Problem: Regret Bounds for Thompson Sampling

Lihong Li, Olivier Chapelle

The Best of Both Worlds: Stochastic and Adversarial Bandits

Sébastien Bubeck, Aleksandrs Slivkins

Towards Minimax Policies for Online Linear Optimization with Bandit Feedback

Sébastien Bubeck, Nicolò Cesa-bianchi, Sham M. Kakade

Autonomous Exploration For Navigating In MDPs

Shiau Hong Lim, Peter Auer

Analysis of Thompson Sampling for the Multi-armed Bandit Problem

Shipra Agrawal, Navin Goyal

Near-Optimal Algorithms for Online Matrix Prediction

Elad Hazan, Satyen Kale, Shai Shalev-shwartz

Exact Recovery of Sparsely-Used Dictionaries

Daniel A. Spielman, Huan Wang, John Wright

Toward Understanding Complex Spaces: Graph Laplacians on Manifolds with Singularities and Boundaries

Mikhail Belkin, Qichao Que, Yusu Wang, Xueyuan Zhou

Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model

Kamalika Chaudhuri, Fan Chung, Alexander Tsiatas

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

Distance Preserving Embeddings for General n-Dimensional Manifolds

Nakul Verma

Tight Bounds on Proper Equivalence Query Learning of DNF

Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco Servedio

New Bounds for Learning Intervals with Implications for Semi-Supervised Learning

David P. Helmbold, Philip M. Long

A Conjugate Property between Loss Functions and Uncertainty Sets in Classification Problems

Takafumi Kanamori, Akiko Takeda, Taiji Suzuki

Divergences and Risks for Multiclass Experiments

Dario García-García, Robert C. Williamson

A Characterization of Scoring Rules for Linear Properties

Jacob D. Abernethy, Rafael M. Frongillo

Distributed Learning, Communication Complexity and Privacy

Maria Florina Balcan, Avrim Blum, Shai Fine, Yishay Mansour

Private Convex Empirical Risk Minimization and High-dimensional Regression

Daniel Kifer, Adam Smith, Abhradeep Thakurta

Differentially Private Online Learning

Prateek Jain, Pravesh Kothari, Abhradeep Thakurta

Kernels Based Tests with Non-asymptotic Bootstrap Approaches for Two-sample Problems

Magalie Fromont, BÃ©atrice Laurent, Matthieu Lerasle, Patricia Reynaud-Bouret

Competitive Classification and Closeness Testing

Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan

Rare Probability Estimation under Regularly Varying Heavy Tails

Mesrob I. Ohannessian, Munther A. Dahleh

Robust Interactive Learning

Maria Florina Balcan, Steve Hanneke

Active Learning Using Smooth Relative Regret Approximations with Applications

Nir Ailon, Ron Begleiter, Esther Ezra

Consistency of Nearest Neighbor Classification under Selective Sampling

Sanjoy Dasgupta

Learning DNF Expressions from Fourier Spectrum

Vitaly Feldman

Computational Bounds on Statistical Query Learning

Vitaly Feldman, Varun Kanade

Learning Functions of Halfspaces Using Prefix Covers

Parikshit Gopalan, Adam R. Klivans, Raghu Meka

Attribute-Efficient Learning andWeight-Degree Tradeoffs for Polynomial Threshold Functions

Rocco Servedio, Li-Yang Tan, Justin Thaler

Generalization Bounds for Online Learning Algorithms with Pairwise Loss Functions

Yuyang Wang, Roni Khardon, Dmitry Pechyony, Rosie Jones

L1 Covering Numbers for Uniformly Bounded Convex Functions

Adityanand Guntuboyina, Bodhisattva Sen

Toward a Noncommutative Arithmetic-geometric Mean Inequality: Conjectures, Case-studies, and Consequences

Benjamin Recht, Christopher Re

Reconstruction from Anisotropic Random Measurements

Mark Rudelson, Shuheng Zhou

Random Design Analysis of Ridge Regression

Daniel Hsu, Sham M. Kakade, Tong Zhang

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

Taiji Suzuki

The Optimality of Jeffreys Prior for Online Density Estimation and the Asymptotic Normality of Maximum Likelihood Estimators

Fares Hedayati, Peter L. Bartlett

Online Optimization with Gradual Variations

Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu

Unified Algorithms for Online Learning and Competitive Analysis

Niv Buchbinder, Shahar Chen, Joshep (Seffi) Naor, Ohad Shamir

Learning Valuation Functions

Maria Florina Balcan, Florin Constantin, Satoru Iwata, Lei Wang

(weak) Calibration is Computationally Hard

Elad Hazan, Sham M. Kakade

Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem

Zohar Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, OMRI WEINSTEIN