[edit]

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

[edit]

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

[bib][citeproc]

Contents:

Preface

Preface

Shie Mannor, Nathan Srebro, Robert C. Williamson; Proceedings of the 25th Annual Conference on Learning Theory, 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; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:2.1-2.17

(weak) Calibration is Computationally Hard

Elad Hazan, Sham M. Kakade; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:3.1-3.10

Learning Valuation Functions

Maria Florina Balcan, Florin Constantin, Satoru Iwata, Lei Wang; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:4.1-4.24

Unified Algorithms for Online Learning and Competitive Analysis

Niv Buchbinder, Shahar Chen, Joshep (Seffi) Naor, Ohad Shamir; Proceedings of the 25th Annual Conference on Learning Theory, 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; Proceedings of the 25th Annual Conference on Learning Theory, 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; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:7.1-7.13

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

Taiji Suzuki; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:8.1-8.20

Random Design Analysis of Ridge Regression

Daniel Hsu, Sham M. Kakade, Tong Zhang; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:9.1-9.24

Reconstruction from Anisotropic Random Measurements

Mark Rudelson, Shuheng Zhou; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:10.1-10.24

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

Benjamin Recht, Christopher Re; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:11.1-11.24

L1 Covering Numbers for Uniformly Bounded Convex Functions

Adityanand Guntuboyina, Bodhisattva Sen; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:12.1-12.13

Generalization Bounds for Online Learning Algorithms with Pairwise Loss Functions

Yuyang Wang, Roni Khardon, Dmitry Pechyony, Rosie Jones; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:13.1-13.22

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

Rocco Servedio, Li-Yang Tan, Justin Thaler; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:14.1-14.19

Learning Functions of Halfspaces Using Prefix Covers

Parikshit Gopalan, Adam R. Klivans, Raghu Meka; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:15.1-15.10

Computational Bounds on Statistical Query Learning

Vitaly Feldman, Varun Kanade; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:16.1-16.22

Learning DNF Expressions from Fourier Spectrum

Vitaly Feldman; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:17.1-17.19

Consistency of Nearest Neighbor Classification under Selective Sampling

Sanjoy Dasgupta; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:18.1-18.15

Active Learning Using Smooth Relative Regret Approximations with Applications

Nir Ailon, Ron Begleiter, Esther Ezra; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:19.1-19.20

Robust Interactive Learning

Maria Florina Balcan, Steve Hanneke; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:20.1-20.34

Rare Probability Estimation under Regularly Varying Heavy Tails

Mesrob I. Ohannessian, Munther A. Dahleh; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:21.1-21.24

Competitive Classification and Closeness Testing

Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan, Ananda Suresh; Proceedings of the 25th Annual Conference on Learning Theory, 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; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:23.1-23.23

Differentially Private Online Learning

Prateek Jain, Pravesh Kothari, Abhradeep Thakurta; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:24.1-24.34

Private Convex Empirical Risk Minimization and High-dimensional Regression

Daniel Kifer, Adam Smith, Abhradeep Thakurta; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:25.1-25.40

Distributed Learning, Communication Complexity and Privacy

Maria Florina Balcan, Avrim Blum, Shai Fine, Yishay Mansour; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:26.1-26.22

A Characterization of Scoring Rules for Linear Properties

Jacob D. Abernethy, Rafael M. Frongillo; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:27.1-27.13

Divergences and Risks for Multiclass Experiments

Dario García-García, Robert C. Williamson; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:28.1-28.20

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

Takafumi Kanamori, Akiko Takeda, Taiji Suzuki; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:29.1-29.23

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

David P. Helmbold, Philip M. Long; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:30.1-30.15

Tight Bounds on Proper Equivalence Query Learning of DNF

Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco Servedio; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:31.1-31.18

Distance Preserving Embeddings for General n-Dimensional Manifolds

Nakul Verma; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:32.1-32.28

A Method of Moments for Mixture Models and Hidden Markov Models

Animashree Anandkumar, Daniel Hsu, Sham M. Kakade; Proceedings of the 25th Annual Conference on Learning Theory, 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; Proceedings of the 25th Annual Conference on Learning Theory, 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; Proceedings of the 25th Annual Conference on Learning Theory, 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; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:36.1-36.26

Exact Recovery of Sparsely-Used Dictionaries

Daniel A. Spielman, Huan Wang, John Wright; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:37.1-37.18

Near-Optimal Algorithms for Online Matrix Prediction

Elad Hazan, Satyen Kale, Shai Shalev-Shwartz; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:38.1-38.13

Analysis of Thompson Sampling for the Multi-armed Bandit Problem

Shipra Agrawal, Navin Goyal; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:39.1-39.26

Autonomous Exploration For Navigating In MDPs

Shiau Hong Lim, Peter Auer; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:40.1-40.24

Towards Minimax Policies for Online Linear Optimization with Bandit Feedback

Sébastien Bubeck, Nicoló Cesa-Bianchi, Sham M. Kakade; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:41.1-41.14

The Best of Both Worlds: Stochastic and Adversarial Bandits

Sébastien Bubeck, Aleksandrs Slivkins; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:42.1-42.23

Open Problem: Regret Bounds for Thompson Sampling

Lihong Li, Olivier Chapelle; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:43.1-43.3

Open Problem: Better Bounds for Online Logistic Regression

H. Brendan McMahan, Matthew Streeter; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:44.1-44.3

Open Problem: Learning Dynamic Network Models from a Static Snapshot

Jan Ramon, Constantin Comendant; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:45.1-45.3

Open Problem: Does AdaBoost Always Cycle?

Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:46.1-46.4

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

Ohad Shamir; Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:47.1-47.3

subscribe via RSS