Recursive aggregation of estimators by the mirror descent algorithm with averaging

DOI10.1007/S11122-006-0005-2MaRDI QIDQ2432961zbMATH OpenOpenAlexFDO

Authors Alexandre B. Tsybakov, Nicolas Vayatis, Anatoli Juditsky, Alexander Nazin

Publication date 26 October 2006

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0505333

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Asymptotic properties of nonparametric inference (62G20) Nonparametric inference (62G99) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: We consider a recursive algorithm to construct an aggregated estimator from a finite number of base decision rules in the classification problem. The estimator approximately minimizes a convex risk functional under the l1-constraint. It is defined by a stochastic version of the mirror descent algorithm (i.e., of the method which performs gradient descent in the dual space) with an additional averaging. The main result of the paper is an upper bound for the expected accuracy of the proposed estimator. This bound is of the order $sqrt(logM)/t$ with an explicit and small constant factor, where $M$ is the dimension of the problem and $t$ stands for the sample size. A similar bound is proved for a more general setting that covers, in particular, the regression model with squared loss.

Recommendations

• Remark on ``Recursive aggregation of estimators by the mirror descent algorithm with averaging
• On stochastic subgradient mirror-descent algorithm with weighted averaging
• Unifying mirror descent and dual averaging
• Aggregation of estimators and stochastic optimization
• Generalized mirror averaging and D-convex aggregation
• Aggregating estimates by convex optimization
• Aggregated estimators and empirical complexity for least square regression
• Aggregation via empirical risk minimization
• Aggregation of affine estimators
• Ergodic mirror descent

Cites work

• A Second-Order Perceptron Algorithm
• Acceleration of Stochastic Approximation by Averaging
• Additive logistic regression: a statistical view of boosting. (With discussion and a rejoinder by the authors)
• Boosting a weak learning algorithm by majority
• Boosting the margin: a new explanation for the effectiveness of voting methods
• Convexity, Classification, and Risk Bounds
• Exponentiated gradient versus gradient descent for linear predictors
• Functional aggregation for nonparametric regression.
• scientific article; zbMATH DE number 3986406 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 3446442 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• Learning Theory and Kernel Machines
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• On the Bayes-risk consistency of regularized boosting methods.
• On the Generalization Ability of On-Line Learning Algorithms
• Online Learning with Kernels
• Optimal aggregation of classifiers in statistical learning.
• Proximal Minimization Methods with Generalized Bregman Functions
• Relative loss bounds for multidimensional regression problems
• Statistical behavior and consistency of classification methods based on convex risk minimization.
• The ordered subsets mirror descent optimization method with applications to tomography
• Variational Analysis

Cited in

(31)

• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• Algorithms of inertial mirror descent in convex problems of stochastic optimization
• On variance reduction for stochastic smooth convex optimization with multiplicative noise
• On the exponentially weighted aggregate with the Laplace prior
• General oracle inequalities for model selection
• Noisy independent factor analysis model for density estimation and classification
• A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning
• Aggregation of estimators and stochastic optimization
• On efficient randomized algorithms for finding the PageRank vector
• On the efficiency of a randomized mirror descent algorithm in online optimization problems
• Aggregation for Gaussian regression
• Simultaneous adaptation to the margin and to complexity in classification
• Some multivariate risk indicators: minimization by using a Kiefer-Wolfowitz approach to the mirror stochastic algorithm
• An optimal method for stochastic composite optimization
• Mirror averaging with sparsity priors
• Saddle point mirror descent algorithm for the robust PageRank problem
• An adaptive multiclass nearest neighbor classifier
• Prediction of time series by statistical learning: general losses and fast rates
• Randomized algorithm to determine the eigenvector of a stochastic matrix with application to the PageRank problem
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Sparse estimation by exponential weighting
• Unifying mirror descent and dual averaging
• First-order methods for convex optimization
• Non-quadratic proxy functions in mirror descent method applied to designing of robust controllers for nonlinear dynamic systems with uncertainty
• Competence-conscious associative classification
• Optimal convergence rate for mirror descent methods with special time-varying step sizes rules
• Mirror descent methods with a weighting scheme for outputs for optimization problems with functional constraints
• Iterative feature selection in least square regression estimation
• Generalized mirror averaging and D-convex aggregation
• A mirror descent algorithm for minimization of mean Poisson flow driven losses
• Learning by mirror averaging

This page was built for publication: Recursive aggregation of estimators by the mirror descent algorithm with averaging

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2432961)