arXiv research

Optimizes exp-concave losses with a new risk bound.

We derive optimal statistical and computational complexity bounds for exp-concave stochastic minimization in terms of the effective dimension. For common eigendecay patterns of the population covariance matrix, this quantity is significantly smaller than the ambient dimension. Our results reveal interesting connections…

The goal of online prediction with expert advice is to find a decision strategy which will perform almost as well as the best expert in a given pool of experts, on any sequence of outcomes. This problem has been widely studied and $O(\sqrt{T})$ and $O(\log{T})$ regret bounds can be achieved for convex losses (\cite{zin…

A new algorithm reduces online exp-concave optimization runtime.

New algorithm reduces dynamic regret for exp-concave losses.

Information concentration of probability measures have important implications in learning theory. Recently, it is discovered that the information content of a log-concave distribution concentrates around their differential entropy, albeit with an unpleasant dependence on the ambient dimension. In this work, we prove th…

The overarching goal of this paper is to derive excess risk bounds for learning from exp-concave loss functions in passive and sequential learning settings. Exp-concave loss functions encompass several fundamental problems in machine learning such as squared loss in linear regression, logistic loss in classification, a…

The paper extends mixability theory to function-valued forecasts, proving various loss functions are mixable.

SA algorithms control dynamic regret in non-stationary settings with strong convexity or exp-concavity.

An online learning framework for survival analysis with real-time adaptation.

Near-logarithmic regret per switch achieved for mixable/exp-concave losses.

Improved online convex optimization with delayed feedback using curvature.

New algorithms minimize dynamic regret in non-stationary online learning.

MetaGrad adapts multiple learning rates for faster online optimization.

Reduces dynamic regret to static problem in RKHS.

Paper proposes an online learning method with multi-level adaptivity for diverse loss functions.

We introduce several new black-box reductions that significantly improve the design of adaptive and parameter-free online learning algorithms by simplifying analysis, improving regret guarantees, and sometimes even improving runtime. We reduce parameter-free online learning to online exp-concave optimization, we reduce…

New method achieves both universality and adaptivity in online convex optimization.

Improved cumulative regret for sequence prediction with limited expert advice.

In this paper, we present a simple analysis of {\bf fast rates} with {\it high probability} of {\bf empirical minimization} for {\it stochastic composite optimization} over a finite-dimensional bounded convex set with exponential concave loss functions and an arbitrary convex regularization. To the best of our knowledg…

Gaptron algorithm reduces mistakes in online multiclass classification.

New algorithms minimize dynamic regret for strongly convex losses.

Recursive least-squares algorithms often use forgetting factors as a heuristic to adapt to non-stationary data streams. The first contribution of this paper rigorously characterizes the effect of forgetting factors for a class of online Newton algorithms. For exp-concave and strongly convex objectives, the algorithms a…

A standard introduction to online learning might place Online Gradient Descent at its center and then proceed to develop generalizations and extensions like Online Mirror Descent and second-order methods. Here we explore the alternative approach of putting Exponential Weights (EW) first. We show that many standard meth…

Unified derivation of PAC-Bayes and MI bounds for general VC classes with fast rates.

The speed with which a learning algorithm converges as it is presented with more data is a central problem in machine learning --- a fast rate of convergence means less data is needed for the same level of performance. The pursuit of fast rates in online and statistical learning has led to the discovery of many conditi…

Improved regret bounds for online convex optimization under stochastic and adversarial settings.