Conference on Learning Theory June 25–June 27, 2012 — Edinburgh, Scotland

Overview

  • Sunday - June 24,2012
    • 18:30 - Welcoming Reception - Appleton Tower (registration desk will be open)
  • Monday - June 25, 2012
    • 8:30 - Opening remarks
    • 8:35 - Computational Learning Theory I
    • 9:50 - Break
    • 10:10 - Online Learning I
    • 11:25 - Break
    • 11:45 - Statistical Learning Theory I
    • 13:00 - Lunch (on your own)
    • 14:45 - Invited Talk - Andrew Ng
    • 15:45 - Break
    • 15:50 - Statistical Learning Theory II
    • 17:15 - Break
    • 17:45 - Computational Learning Theory II
    • 20:00 - COLT Banquet - Ghillie Dhu, 2 Rutland Place
  • Tuesday - June 26, 2012
    • 8:30 - Active Learning
    • 9:45 - Break
    • 10:05 - Hypothesis Testing and Estimation
    • 11:30 - Box Lunch (provided)
    • 12:30 - Invited Tutorial - Arkadi Nemirovski
    • 13:30 - Privacy
    • 14:45 - Break
    • 15:05 - Risk Functions
    • 16:20 - Break
    • 16:40 - Tight Bounds
    • 17:30 - Impromptu Session
    • 18:30 - Reception
  • Wednesday - June 27, 2012
    • 8:30 - ICML Welcome
    • 8:40 - ICML Invited Talk - Sethu Muthukrishnan
    • 9:40 - ICML Best Paper
    • 10:00 - Break
    • 10:30 - Manifolds and Clustering
    • 12:10 - Lunch / Business Meeting
    • 14:00 - Invited Talk - Dimitris Achlioptas
    • 15:00 - COLT Best Paper
    • 15:30 - Break
    • 16:00 - Online Learning II
    • 17:40 - Posters
    • 17:50 - Open Problems

In general, all COLT sessions are in AT LT 3 (Appleton Tower == AT), exceptions noted below

Monday - June 25, 2012

  • 8:30
    • Opening remarks
  • 8:35 - 9:50 - Computational Learning Theory I (Session chair: Shai Shalev-Shwartz)
    • Unsupervised SVMs: On the complexity of the Furthest Hyperplane Problem
      - Omri Weinstein, Edo Liberty, Shachar Lovett, Roy Schwartz and Zohar Karnin
    • (weak) Calibration is Computationally Hard
      - Elad Hazan and Sham Kakade
    • Learning Valuation Functions
      - Maria-Florina Balcan, Florin Constantin, Satoru Iwata and Lei Wang
  • 10:10 - 11:25 - Online Learning I (Session chair: Elad Hazan)
    • Unified Algorithms for Online Learning and Competitive Analysis
      - Niv Buchbinder, Shahar Chen, Joseph Naor and Ohad Shamir
    • Online Optimization with Gradual Variations
      - Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin and Shenghuo Zhu
    • The Optimality of Jeffreys Prior for Online Density Estimation and the Asymptotic Normality of Maximum Likelihood Estimators
      - Fares Hedayati and Peter Bartlett
  • 11:45 - 13:00 - Statistical Learning Theory I (Session chair: Kamalika Chaudhuri)
    • PAC-Bayesian Bound for Gaussian Process Regression and Multiple Kernel Additive Model
      - Taiji Suzuki
    • Random Design Analysis of Ridge Regression
      - Daniel Hsu, Sham Kakade and Tong Zhang
    • Generalization Bounds for Online Learning Algorithms with Pairwise Loss Functions
      - Yuyang Wang, Roni Khardon, Dmitry Pechyony and Rosie Jones
  • 14:45 - 15:45 - Invited Talk (Session chair: Nati Srebro)
    • Machine learning and AI via large scale brain simulations
      - Andrew Ng
  • 15:50 - 17:15 - Statistical Learning Theory II (Session chair: Shai Ben David)
    • Toward a noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
      - Benjamin Recht and Christopher Re
    • Announcement: The Generalization Ability of Online Algorithms for Dependent Data
      - Alekh Agarwal, John C. Duchi
    • Impromptu Session
  • 17:45 - 19:25 - Computational Learning Theory II (Session chair: Nina Balcan)
    • Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions
      - Rocco Servedio, Li-Yang Tan and Justin Thaler
    • Learning Functions of Halfspaces using Prefix Covers
      - Parikshit Gopalan, Adam Klivans and Raghu Meka
    • Computational Bounds on Statistical Query Learning
      - Vitaly Feldman and Varun Kanade
    • Learning of DNF Expressions from Fourier Spectrum
      - Vitaly Feldman
  • 20:00
    • COLT Banquet

Tuesday - June 26, 2012

  • 8:30 - 9:45 - Active Learning (Session chair: Jacob Abernathy)
    • Consistency of nearest neighbor classification under selective sampling
      - Sanjoy Dasgupta
    • Active Learning Using Smooth Relative Regret Approximations with Applications
      - Nir Ailon, Ron Begleiter and Esther Ezra
    • Robust Interactive Learning
      - Maria-Florina Balcan and Steve Hanneke
  • 10:05 - 11:30 - Hypothesis Testing and Estimation (Session chair: Phil Long)
    • Rare Probability Estimation under Regularly Varying Heavy Tails
      - Mesrob Ohannessian and Munther Dahleh
    • Competitive Classification and Closeness Testing
      - Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan and Ananda Theertha Suresh
    • Kernels based tests with non-asymptotic bootstrap approaches for two-sample problems
      - Magalie Fromont, Béatrice Laurent, Matthieu Lerasle and Patricia Reynaud-Bouret
    • Announcement: Bounds on the Bayes Error Given Moments
      - Bela Frigyik and Maya R. Gupta
  • 12:30 - 13:30 (AT LT4) - Invited Tutorial (Session chair: Shie Mannor)
    • Mirror Descent Algorithms for Large-Scale Convex Optimization
      - Arkadi Nemirovski
  • 13:30 - 14:45 (AT LT4) - Privacy (Session chair: Satyen Kale)
    • Differentially Private Convex Optimization for Empirical Risk Minimization with Applications to High-dimensional Regression
      - Daniel Kifer, Adam Smith and Abhradeep Thakurta
    • Differentially Private Online Learning
      - Prateek Jain, Pravesh Kothari and Abhradeep Thakurta
    • Distributed Learning, Communication Complexity and Privacy - Runner Up Best Paper -
      - Maria-Florina Balcan, Avrim Blum, Shai Fine and Yishay Mansour
  • 15:05 - 16:20 - Risk Functions (Session chair: Ohad Shamir)
    • A Characterization of Scoring Rules for Linear Properties
      - Rafael Frongillo and Jacob Abernethy
    • Divergences and Risks for Multiclass Experiments
      - Dario Garcia Garcia and Robert C. Williamson
    • A Conjugate Property between Loss Functions and Uncertainty Sets in Classification Problems
      - Takafumi Kanamori, Akiko Takeda and Taiji Suzuki
  • 16:40 - 17:30 - Tight Bounds (Karthik Sridharan)
    • New Bounds for Learning Intervals with Implications for Semi-Supervised Learning
      - David Helmbold and Philip Long
    • Tight Bounds on Proper Equivalence Query Learning of DNF
      - Lisa Hellerstein, Devorah Kletenik, Linda Sellie and Rocco Servedio
  • 17:30 - 18:15
    • Impromptu Session
    • Reconstruction from anisotropic random measurements
      - Mark Rudelson and Shuheng Zhou
  • 18:30
    • Reception

Wednesday - June 27, 2012

  • 8:30 (split between AT LT4, LT5, and LT2)
    • ICML Welcome
  • 8:40 (split between AT LT4, LT5, and LT2) - ICML Invited Talk
    • Modern Algorithmic Tools for Analyzing Data Streams
      - Sethu Muthukrishnan
  • 9:40 (split between AT LT4, LT5, and LT2) - ICML best paper
    • Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring - Best Paper -
      - Sungjin Ahn, Anoop Korattikara, Max Welling
  • 10:30 - 12:10 - Manifolds and Clustering (Session chair: Peter Auer)
    • Distance Preserving Embeddings for General n-Dimensional Manifolds
      - Nakul Verma
    • A Method of Moments for Hidden Markov Models and Multi-view Mixture Models
      - Animashree Anandkumar, Daniel Hsu and Sham Kakade
    • A Correlation Clustering Approach to Link Classification in Signed Networks
      - Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale and Giovanni Zappella
    • Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model
      - Kamalika Chaudhuri, Fan Chung and Alexander Tsiatas
    • Toward understanding complex spaces: graph Laplacians on manifolds with singularities and boundaries
      - Mikhail Belkin, Qichao Que, Yusu Wang and Xueyuan Zhou
  • 14:00 (split between AT LT4, LT5, and LT2) - Invited Talk (Session chair: Jyrki Kivinen)
    • Phase Transitions, Algorithmic Barriers, and Data Clustering
      - Dimitris Achlioptas
  • 15:00 - 15:30 (split between AT LT4, LT5, and LT2) - COLT best paper
    • Exact Recovery of Sparsely-Used Dictionaries - Best Paper -
      - Daniel Spielman, Huan Wang and John Wright
  • 16:00 - 17:40 - Online Learning II (Session chair: Alexander Rakhlin)
    • Near-Optimal Algorithms for Online Matrix Prediction
      - Elad Hazan, Satyen Kale and Shai Shalev-Shwartz
    • Analysis of Thompson Sampling for the multi-armed bandit problem
      - Shipra Agrawal and Navin Goyal
    • Autonomous Exploration For Navigating In MDPs
      - Shiau Hong Lim and Peter Auer
    • Towards Minimax Policies for Online Linear Optimization with Bandit Feedback
      - Sébastien Bubeck, Nicolo Cesa-Bianchi and Sham M. Kakade
    • The best of both worlds: stochastic and adversarial bandits
      - Sébastien Bubeck and Aleksandrs Slivkins
  • 17:40 - 20:00
    • Posters
  • 17:50 - 18:25 - Open problems
    • Regret Bounds for Thompson Sampling
      - Lihong Li and Olivier Chapelle
    • Better Bounds for Online Logistic Regression
      - H. Brendan McMahan and Matthew Streeter
    • Does AdaBoost Always Cycle?
      - Cynthia Rudin, Robert E. Schapire, and Ingrid Daubechies
    • Learning dynamic network models from a static snapshot
      - Jan Ramon and Constantin Comendant
    • Is Averaging Needed for Strongly Convex Stochastic Gradient Descent?
      - Ohad Shamir