Learning by mirror averaging

By Anatoli B. Juditsky, Philippe Rigollet, Alexandre B. Tsybakov. 2005

177 citations recorded by the source corpus.

Given a collection of $M$ different estimators or classifiers, we study the problem of model selection type aggregation, i.e., we construct a new estimator or classifier, called aggregate, which is nearly as good as the best among them with respect to a given risk criterion. We define our aggregate by a simple recursive procedure which solves an auxiliary stochastic linear programming problem related to the original non-linear one and constitutes a special case of the mirror averaging algorithm. We show that the aggregate satisfies sharp oracle inequalities under some general assumptions. The results allow one to construct in an easy way sharp adaptive nonparametric estimators for several problems including regression, classification and density estimation.

Subfields: Management Science and Operations Research, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Convex optimization under inexact first-order information (2009, methodology): “Close techniques, based on subgradient averaging, have been proposed in Nesterov [51] and used in [24, 26] to solve certain stochastic optimization problems of the form (1.”
An optimal method for stochastic composite optimization (2011, methodology): “Close techniques, based on subgradient averaging, have been proposed in Nesterov [35] and used in [12,14] to solve certain non-smooth stochastic convex optimization problems.”
Inconsistency of Bayesian Inference for Misspecified Linear Models, and a Proposal for Repairing It (2014, background): “General Losses The original generalized posterior is a notion going back at least to Vovk (1990) and has been developed mainly within the so-called (frequentist) PAC-Bayesian framework McAllester (2003), Seeger (2002), Catoni (2007), Audibert (2004), Zhang (2006b); see also Bissiri et al.”
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration (2017, methodology): “This powerful idea has been successfully applied to a variety of contexts not only as a statistical tool for model selection [JRT08, RT11, RT12] and online learning [CBL06], but also as an optimization gadget in ﬁrst-order optimization methods such as mirror descent and proximal methods [Bub15].”
Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization (2016, methodology): “Other SA methods with provable complexities for solving convex stochastic optimization problems were also studied in [19, 26, 27, 28, 29, 30, 2, 13, 1, 51, 54].”
Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework (2012, methodology): “Similar techniques, based on subgradient averaging, have been proposed in [13, 16, 27].”
User-friendly introduction to PAC-Bayes bounds (2021, background): “In order to avoid any confusion I will stick to “PAC-Bayes bound in expectation”, but I like EAC and MAC! Early examples of PAC-Bayes bounds in expectation can be found in [1, 43, 107, 64].”
Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity (2008, methodology): “This result is further reﬁned in [4] and [20].”
Aggregation via empirical risk minimization (2009, methodology): “One can show [10,12,15,17] that, if (x, y) = (x − y)2, then for every random map A there exists a constant c depending only on the map and on δ, such that for every n, H(n,M, δ) ≥ c/√n.”
Fast Rates with Unbounded Losses (2016, methodology): “Such methods achieve fast rates under conditions such as stochastic exp-concavity (Juditsky et al., 2008), which are very similar to strong PPC, as explained by van Erven et al. (2015).”
Optimal rates and adaptation in the single-index model using aggregation (2007, methodology): “We can understand the aggregation algorithm in the following way: ﬁrst, we compute the least squares of each weak estimators.”