Volume 23: Conference on Learning Theory, 25-27 June 2012, Edinburgh, Scotland


Editors: Shie Mannor, Nathan Srebro, Robert C. Williamson





Shie Mannor, Nathan Srebro, Robert C. Williamson ; PMLR 23:1.1-1.2

Accepted Papers

Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem

Zohar Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, Omri Weinstein ; PMLR 23:2.1-2.17

(weak) Calibration is Computationally Hard

Elad Hazan, Sham M. Kakade ; PMLR 23:3.1-3.10

Learning Valuation Functions

Maria Florina Balcan, Florin Constantin, Satoru Iwata, Lei Wang ; PMLR 23:4.1-4.24

Unified Algorithms for Online Learning and Competitive Analysis

Niv Buchbinder, Shahar Chen, Joshep (Seffi) Naor, Ohad Shamir ; PMLR 23:5.1-5.18

Online Optimization with Gradual Variations

Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, Shenghuo Zhu ; PMLR 23:6.1-6.20

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

Fares Hedayati, Peter L. Bartlett ; PMLR 23:7.1-7.13

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

Taiji Suzuki ; PMLR 23:8.1-8.20

Random Design Analysis of Ridge Regression

Daniel Hsu, Sham M. Kakade, Tong Zhang ; PMLR 23:9.1-9.24

Reconstruction from Anisotropic Random Measurements

Mark Rudelson, Shuheng Zhou ; PMLR 23:10.1-10.24

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

Benjamin Recht, Christopher Re ; PMLR 23:11.1-11.24

L1 Covering Numbers for Uniformly Bounded Convex Functions

Adityanand Guntuboyina, Bodhisattva Sen ; PMLR 23:12.1-12.13

Generalization Bounds for Online Learning Algorithms with Pairwise Loss Functions

Yuyang Wang, Roni Khardon, Dmitry Pechyony, Rosie Jones ; PMLR 23:13.1-13.22

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

Rocco Servedio, Li-Yang Tan, Justin Thaler ; PMLR 23:14.1-14.19

Learning Functions of Halfspaces Using Prefix Covers

Parikshit Gopalan, Adam R. Klivans, Raghu Meka ; PMLR 23:15.1-15.10

Computational Bounds on Statistical Query Learning

Vitaly Feldman, Varun Kanade ; PMLR 23:16.1-16.22

Learning DNF Expressions from Fourier Spectrum

Vitaly Feldman ; PMLR 23:17.1-17.19

Consistency of Nearest Neighbor Classification under Selective Sampling

Sanjoy Dasgupta ; PMLR 23:18.1-18.15

Active Learning Using Smooth Relative Regret Approximations with Applications

Nir Ailon, Ron Begleiter, Esther Ezra ; PMLR 23:19.1-19.20

Robust Interactive Learning

Maria Florina Balcan, Steve Hanneke ; PMLR 23:20.1-20.34

Rare Probability Estimation under Regularly Varying Heavy Tails

Mesrob I. Ohannessian, Munther A. Dahleh ; PMLR 23:21.1-21.24

Competitive Classification and Closeness Testing

Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan, Ananda Suresh ; PMLR 23:22.1-22.18

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

Magalie Fromont, Béatrice Laurent, Matthieu Lerasle, Patricia Reynaud-Bouret ; PMLR 23:23.1-23.23

Differentially Private Online Learning

Prateek Jain, Pravesh Kothari, Abhradeep Thakurta ; PMLR 23:24.1-24.34

Private Convex Empirical Risk Minimization and High-dimensional Regression

Daniel Kifer, Adam Smith, Abhradeep Thakurta ; PMLR 23:25.1-25.40

Distributed Learning, Communication Complexity and Privacy

Maria Florina Balcan, Avrim Blum, Shai Fine, Yishay Mansour ; PMLR 23:26.1-26.22

A Characterization of Scoring Rules for Linear Properties

Jacob D. Abernethy, Rafael M. Frongillo ; PMLR 23:27.1-27.13

Divergences and Risks for Multiclass Experiments

Dario García-García, Robert C. Williamson ; PMLR 23:28.1-28.20

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

Takafumi Kanamori, Akiko Takeda, Taiji Suzuki ; PMLR 23:29.1-29.23

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

David P. Helmbold, Philip M. Long ; PMLR 23:30.1-30.15

Tight Bounds on Proper Equivalence Query Learning of DNF

Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco Servedio ; PMLR 23:31.1-31.18

Distance Preserving Embeddings for General n-Dimensional Manifolds

Nakul Verma ; PMLR 23:32.1-32.28

A Method of Moments for Mixture Models and Hidden Markov Models

Animashree Anandkumar, Daniel Hsu, Sham M. Kakade ; PMLR 23:33.1-33.34

A Correlation Clustering Approach to Link Classification in Signed Networks

Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale, Giovanni Zappella ; PMLR 23:34.1-34.20

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

Kamalika Chaudhuri, Fan Chung, Alexander Tsiatas ; PMLR 23:35.1-35.23

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

Mikhail Belkin, Qichao Que, Yusu Wang, Xueyuan Zhou ; PMLR 23:36.1-36.26

Exact Recovery of Sparsely-Used Dictionaries

Daniel A. Spielman, Huan Wang, John Wright ; PMLR 23:37.1-37.18

Near-Optimal Algorithms for Online Matrix Prediction

Elad Hazan, Satyen Kale, Shai Shalev-Shwartz ; PMLR 23:38.1-38.13

Analysis of Thompson Sampling for the Multi-armed Bandit Problem

Shipra Agrawal, Navin Goyal ; PMLR 23:39.1-39.26

Autonomous Exploration For Navigating In MDPs

Shiau Hong Lim, Peter Auer ; PMLR 23:40.1-40.24

Towards Minimax Policies for Online Linear Optimization with Bandit Feedback

Sébastien Bubeck, Nicolo Cesa-Bianchi, Sham M. Kakade ; PMLR 23:41.1-41.14

The Best of Both Worlds: Stochastic and Adversarial Bandits

Sébastien Bubeck, Aleksandrs Slivkins ; PMLR 23:42.1-42.23

Open Problem: Regret Bounds for Thompson Sampling

Lihong Li, Olivier Chapelle ; PMLR 23:43.1-43.3

Open Problem: Better Bounds for Online Logistic Regression

H. Brendan McMahan, Matthew Streeter ; PMLR 23:44.1-44.3

Open Problem: Learning Dynamic Network Models from a Static Snapshot

Jan Ramon, Constantin Comendant ; PMLR 23:45.1-45.3

Open Problem: Does AdaBoost Always Cycle?

Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies ; PMLR 23:46.1-46.4

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

Ohad Shamir ; PMLR 23:47.1-47.3

subscribe via RSS

This site last compiled Mon, 10 Apr 2017 14:35:28 +0000
Github Account Copyright © PMLR 2017. All rights reserved.