Approximation and learning by greedy algorithms
From MaRDI portal
Publication:2477053
Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Multidimensional problems (41A63) Applications of functional analysis in probability theory and statistics (46N30) Nonparametric regression and quantile regression (62G08) Learning and adaptive systems in artificial intelligence (68T05)
Abstract: We consider the problem of approximating a given element from a Hilbert space by means of greedy algorithms and the application of such procedures to the regression problem in statistical learning theory. We improve on the existing theory of convergence rates for both the orthogonal greedy algorithm and the relaxed greedy algorithm, as well as for the forward stepwise projection algorithm. For all these algorithms, we prove convergence results for a variety of function classes and not simply those that are related to the convex hull of the dictionary. We then show how these bounds for convergence rates lead to a new theory for the performance of greedy algorithms in learning. In particular, we build upon the results in [IEEE Trans. Inform. Theory 42 (1996) 2118--2132] to construct learning algorithms based on greedy approximations which are universally consistent and provide provable convergence rates for large classes of functions. The use of greedy algorithms in the context of learning is very appealing since it greatly reduces the computational burden when compared with standard model selection using general dictionaries.
Recommendations
- Greedy approximations
- Greedy algorithms for adaptive approximation
- Adaptive approximations by greedy algorithms
- Approximation in learning theory
- Greedy approximation
- Greedy approximation
- Adaptive greedy approximations
- Greedy in Approximation Algorithms
- Approximation algorithms for budgeted learning problems
- Simultaneous approximation by greedy algorithms
Cites work
- A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
- Adaptive greedy approximations
- Approximation by Ridge Functions and Neural Networks
- Bounds on rates of variable-basis and neural-network approximation
- Comparison of worst case errors in linear and neural network approximation
- Efficient agnostic learning of neural networks with bounded fan-in
- Greedy algorithms with restricted depth search
- scientific article; zbMATH DE number 17222 (Why is no real title available?)
- scientific article; zbMATH DE number 192914 (Why is no real title available?)
- scientific article; zbMATH DE number 3536702 (Why is no real title available?)
- scientific article; zbMATH DE number 1215245 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Least angle regression. (With discussion)
- Nonlinear methods of approximation
- Rate of convergence of pure greedy algorithm.
- Some remarks on greedy algorithms
- The elements of statistical learning. Data mining, inference, and prediction
- Two lower estimates in greedy approximation
- Universal approximation bounds for superpositions of a sigmoidal function
Cited in
(99)- Elastic-net regularization in learning theory
- A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
- Greedy function approximation: A gradient boosting machine.
- Stochastic subspace correction in Hilbert space
- LOL selection in high dimension
- Asymptotics for high-dimensional covariance matrices and quadratic forms with applications to the trace functional and shrinkage
- Provable approximation properties for deep neural networks
- Regularized greedy algorithms for network training with data noise
- On the sparseness of 1-norm support vector machines
- Learning rates of multi-kernel regression by orthogonal greedy algorithm
- On the convergence rate of kernel-based sequential greedy regression
- Lasso, iterative feature selection and the correlation selector: oracle inequalities and numerical performances
- The Lasso as an \(\ell _{1}\)-ball model selection procedure
- Restricted strong convexity implies weak submodularity
- Sampling based approximation of linear functionals in reproducing kernel Hilbert spaces
- Duality gap estimates for a class of greedy optimization algorithms in Banach spaces
- Uniform approximation rates and metric entropy of shallow neural networks
- Aggregation of estimators and stochastic optimization
- A multiscale virtual element method for elliptic problems in heterogeneous porous media
- Almost optimal estimates for approximation and learning by radial basis function networks
- Semi-nonparametric approximation and index options
- A unified way of analyzing some greedy algorithms
- Duality gap estimates for weak Chebyshev greedy algorithms in Banach spaces
- On universal estimators in learning theory
- Approximation methods for supervised learning
- Greedy algorithms for prediction
- Growing axons: greedy learning of neural networks with application to function approximation
- Greedy training algorithms for neural networks and applications to PDEs
- Prediction-based termination rule for greedy learning with massive data
- How to best sample a solution manifold?
- Penalized empirical relaxed greedy algorithm for fixed design Gaussian regression
- Linear and nonlinear approximation of spherical radial basis function networks
- Rescaled pure greedy algorithm for Hilbert and Banach spaces
- A nonparametric estimator for the covariance function of functional data
- Proper generalized decompositions and separated representations for the numerical solution of high dimensional stochastic problems
- Greedy approximation
- Nearly optimal minimax estimator for high-dimensional sparse linear regression
- Micro-macro models for viscoelastic fluids: modelling, mathematics and numerics
- Greedy and randomized versions of the multiplicative Schwarz method
- Convergence rate of the semi-supervised greedy algorithm
- Greedy algorithms and approximation properties for frames in Hilbert spaces
- Sure independence screening for ultrahigh dimensional feature space. With discussion and authors' reply
- On the Convergence of a Greedy Algorithm for the Solution of the Problem for the Construction of Monotone Regression
- Estimation for the prediction of point processes with many covariates
- Greedy Algorithms for Optimal Measurements Selection in State Estimation Using Reduced Models
- 10.1162/153244304773936108
- Covariate selection for accelerated failure time data
- Wavelets centered on a knot sequence: theory, construction, and applications
- Efficiency of the weak Rescaled Pure Greedy Algorithm
- On some similarities and differences between deep neural networks and kernel learning machines
- Two-Layer Neural Networks with Values in a Banach Space
- Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications
- Wavelet neural networks functional approximation and application
- Unified error estimate for weak biorthogonal greedy algorithms
- A Sequential Significance Test for Treatment by Covariate Interactions
- Learning Rates of lq Coefficient Regularization Learning with Gaussian Kernel
- Density estimation with quadratic loss: a confidence intervals method
- Semiparametric estimation of plane similarities: application to fast computation of aeronautic loads
- Schwarz iterative methods: infinite space splittings
- The greedy ridge algorithm in Gaussian weighted \(L^2\)
- A New Function Space from Barron Class and Application to Neural Network Approximation
- Optimality of the rescaled pure greedy learning algorithms
- Turnpike in optimal control of PDEs, ResNets, and beyond
- Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits
- Fully corrective gradient boosting with squared hinge: fast learning rates and early stopping
- On the selection of predictors by using greedy algorithms and information theoretic criteria
- Characterization of the variation spaces corresponding to shallow neural networks
- Adaptive piecewise Poly-Sinc methods for function approximation
- ReLU neural network Galerkin BEM
- Quadratic Neural Networks for Solving Inverse Problems
- Structured, sparse regression with application to HIV drug resistance
- Sharp Bounds on the Approximation Rates, Metric Entropy, and n-Widths of Shallow Neural Networks
- Entropy-based convergence rates of greedy algorithms
- Greedy approximation and regression analysis for the discrete TM system
- A reduced conjugate gradient basis method for fractional diffusion
- Inverse problems: a deterministic approach using physics-based reduced models
- Weighted variation spaces and approximation by shallow ReLU networks
- Brief introduction in greedy approximation
- Optimal approximation of zonoids and uniform approximation by shallow neural networks
- Randomized greedy algorithms for neural network optimization in solving partial differential equations
- A new rational approximation algorithm via the empirical interpolation method
- -Rescaled Pure Super Greedy Algorithm with respect to Riesz dictionary
- Spectral Barron space for deep neural network approximation
- High-dimensional L₂-Boosting: rate of convergence
- Error bounds of approximate weak rescaled pure greedy algorithms
- Deep learning for PDE-based inverse problems. Abstracts from the workshop held October 27 -- November 1, 2024
- On greedy approximation in complex Banach spaces
- A new analysis of empirical interpolation methods and Chebyshev greedy algorithms
- Introduction: Wolfgang Dahmen's mathematical work (as of 2009)
- Compositional sparsity, approximation classes, and parametric transport equations
- Ensemble projection pursuit for general nonparametric regression
- Approximation properties of some vector weak biorthogonal greedy algorithms
- Provable wavelet-based neural approximation
- Kernel-based L₂-boosting with structure constraints
- Iterative feature selection in least square regression estimation
- Expansive natural neural gradient flows for energy minimization
- High-dimensional variable selection
- Results and questions on a nonlinear approximation approach for solving high-dimensional partial differential equations
- On \(n\)-term approximation with positive coefficients
This page was built for publication: Approximation and learning by greedy algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2477053)
