Conference on Learning Theory
TechTalks from event: Conference on Learning Theory

The Best of Both Worlds: Stochastic and Adversarial BanditsWe present a new bandit algorithm, SAO (Stochastic and Adversarial Optimal) whose regret is (essentially) optimal both for adversarial rewards and for stochastic rewards. Specifically, SAO combines the O(?n) worstcase regret of Exp3 (Auer et al., 2002b) and the (poly)logarithmic regret of UCB1 (Auer et al., 2002a) for stochastic rewards. Adversarial rewards and stochastic rewards are the two main settings in the literature on multiarmed bandits (MAB). Prior work on MAB treats them separately, and does not attempt to jointly optimize for both. This result falls into the general agenda to design algorithms that combine the optimal worstcase performance with improved guarantees for "nice" problem instances.

Open Problem: Better Bounds for Online Logistic RegressionKnown algorithms applied to online logistic regression on a feasible set of L2 diameter D achieve regret bounds like O(eD log T) in one dimension, but we show a bound of O(?D + log T) is possible in a binary 1dimensional problem. Thus, we pose the following question: Is it possible to achieve a regret bound for online logistic regression that is O(poly(D) log(T))? Even if this is not possible in general, it would be interesting to have a bound that reduces to our bound in the onedimensional case.

Open Problem: Learning Dynamic Network Models from a Static SnapshotIn this paper we consider the problem of learning a graph generating process given the evolving graph at a single point in time. Given a graph of sufficient size, can we learn the (repeatable) process that generated it? We formalize the generic problem and then consider two simple instances which are variations on the wellknow graph generation models by ErdsRnyi and AlbertBarabasi.

Open Problem: Does AdaBoost Always Cycle?We pose the question of whether the distributions computed by AdaBoost always converge to a cycle.

Open Problem: Is Averaging Needed for Strongly Convex Stochastic Gradient Descent?Stochastic gradient descent (SGD) is a simple and very popular iterative method to solve stochastic optimization problems which arise in machine learning. A common practice is to return the average of the SGD iterates. While the utility of this is wellunderstood for general convex problems, the situation is much less clear for strongly convex problems (such as solving SVM). Although the standard analysis in the strongly convex case requires averaging, it was recently shown that this actually degrades the convergence rate, and a better rate is obtainable by averaging just a suffix of the iterates. The question we pose is whether averaging is needed at all to get optimal rates.
 All Talks
 Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem
 (weak) Calibration is Computationally Hard
 Learning Valuation Functions
 Unified Algorithms for Online Learning and Competitive Analysis
 Online Optimization with Gradual Variations
 The Optimality of Jeffreys Prior for Online Density Estimation and the Asymptotic Normality of Maximum Likelihood Estimators
 PACBayesian Bound for Gaussian Process Regression and Multiple Kernel Additive Model
 Random Design Analysis of Ridge Regression
 Reconstruction from Anisotropic Random Measurements
 Toward a Noncommutative Arithmeticgeometric Mean Inequality: Conjectures, Casestudies, and Consequences
 L1 Covering Numbers for Uniformly Bounded Convex Functions
 Generalization Bounds for Online Learning Algorithms with Pairwise Loss Functions
 AttributeEfficient Learning andWeightDegree Tradeoffs for Polynomial Threshold Functions
 Learning Functions of Halfspaces Using Prefix Covers
 Computational Bounds on Statistical Query Learning
 Learning DNF Expressions from Fourier Spectrum
 Consistency of Nearest Neighbor Classification under Selective Sampling
 Active Learning Using Smooth Relative Regret Approximations with Applications
 Robust Interactive Learning
 Rare Probability Estimation under Regularly Varying Heavy Tails
 Competitive Classification and Closeness Testing
 Kernels Based Tests with Nonasymptotic Bootstrap Approaches for Twosample Problems
 Differentially Private Online Learning
 Private Convex Empirical Risk Minimization and Highdimensional Regression
 Distributed Learning, Communication Complexity and Privacy
 A Characterization of Scoring Rules for Linear Properties
 Divergences and Risks for Multiclass Experiments
 A Conjugate Property between Loss Functions and Uncertainty Sets in Classification Problems
 New Bounds for Learning Intervals with Implications for SemiSupervised Learning
 Tight Bounds on Proper Equivalence Query Learning of DNF
 Distance Preserving Embeddings for General nDimensional Manifolds
 A Method of Moments for Mixture Models and Hidden Markov Models
 A Correlation Clustering Approach to Link Classification in Signed Networks
 Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model
 Toward Understanding Complex Spaces: Graph Laplacians on Manifolds with Singularities and Boundaries
 Exact Recovery of SparselyUsed Dictionaries
 NearOptimal Algorithms for Online Matrix Prediction
 Analysis of Thompson Sampling for the Multiarmed Bandit Problem
 Autonomous Exploration For Navigating In MDPs
 Towards Minimax Policies for Online Linear Optimization with Bandit Feedback
 The Best of Both Worlds: Stochastic and Adversarial Bandits
 Open Problem: Regret Bounds for Thompson Sampling
 Open Problem: Better Bounds for Online Logistic Regression
 Open Problem: Learning Dynamic Network Models from a Static Snapshot
 Open Problem: Does AdaBoost Always Cycle?
 Open Problem: Is Averaging Needed for Strongly Convex Stochastic Gradient Descent?