The curse of dimensionality for the class of monotone functions and for the class of convex functions

DOI10.1016/J.JAT.2011.02.009zbMATH Open1230.65035arXiv1011.3680OpenAlexW1541034379MaRDI QIDQ2275488FDOQ2275488

Authors: Aicke Hinrichs, Erich Novak, H. Woźniakowski 

Publication date: 9 August 2011

Published in: Journal of Approximation Theory (Search for Journal in Brave)

Abstract: We study the integration and approximation problems for monotone and convex bounded functions that depend on $d$ variables, where $d$ can be arbitrarily large. We consider the worst case error for algorithms that use finitely many function values. We prove that these problems suffer from the curse of dimensionality. That is, one needs exponentially many (in $d$) function values to achieve an error $epsilon$.

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

Recommendations

• ``Curse of dimensionality for complexity of approximation for classes of functions satisfying Lipschitz condition
• scientific article; zbMATH DE number 6731408
• Monotone class theorems for multi-dimensional functions
• The relevance of convex analysis for the study of monotonicity
• Generalized convexity and generalized monotonocity
• G-monotonicity and G-convexity
• Functions of many variables, monotone on pseudoconvex sets
• The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\)
• Generalized monotonicity and generalized convexity
• Convexification of nonsmooth monotone functions

zbMATH Keywords

curse of dimensionalitymonotone functionsconvex functionsintegration problemminimal cost computing

Mathematics Subject Classification ID

Numerical quadrature and cubature formulas (65D32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximate quadratures (41A55)

Cites Work

• Deterministic and stochastic error bounds in numerical analysis
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• A geometric inequality and the complexity of computing volume
• Integration of monotone functions of several variables
• Widths and shape-preserving widths of Sobolev-type classes of \(s\)-monotone functions
• Quadrature formulas for multivariate convex functions
• Title not available (Why is that?)

Cited In (9)

• Title not available (Why is that?)
• The difficulty of Monte Carlo approximation of multivariate monotone functions
• The curse of dimensionality for numerical integration of smooth functions. II
• The curse of dimensionality for numerical integration of smooth functions
• Approximation of curve-based sleeve functions in high dimensions
• Integration of monotone functions of several variables
• Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
• Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration
• ``Curse of dimensionality for complexity of approximation for classes of functions satisfying Lipschitz condition

This page was built for publication: The curse of dimensionality for the class of monotone functions and for the class of convex functions

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