Information of varying cardinality
From MaRDI portal
Publication:1821084
We study adaptive information of varying cardinality for linear problems defined on a separable Banach space. It is known that for linear problems adaptive information of fixed cardinality does not help in the worst case setting. It does not help also in the average case setting with Gaussian measures. We prove that in the worst case setting a similar result holds for information of varying cardinality. In the average case setting with Gaussian measures, information of varying cardinality can be more powerful than information of fixed cardinality. However, optimal information has a structure which is almost as simple as nonadaptive information of fixed cardinality. We also give a condition under which varying cardinality does not help. These results are useful for deriving tight bounds on complexity, which is also studied in this paper.
Recommendations
Cites work
- A survey of information-based complexity
- Approximation of linear functionals on a Banach space with a Gaussian measure
- Average case optimal algorithms in Hilbert spaces
- Average case optimality
- Average case optimality for linear problems
- Can adaption help on the average?
- Designs for Regression Problems with Correlated Errors III
- Designs for Regression Problems With Correlated Errors: Many Parameters
- scientific article; zbMATH DE number 3827201 (Why is no real title available?)
- scientific article; zbMATH DE number 3688714 (Why is no real title available?)
- scientific article; zbMATH DE number 3755545 (Why is no real title available?)
- scientific article; zbMATH DE number 3456359 (Why is no real title available?)
- scientific article; zbMATH DE number 3509627 (Why is no real title available?)
- scientific article; zbMATH DE number 3246773 (Why is no real title available?)
- scientific article; zbMATH DE number 3357742 (Why is no real title available?)
- scientific article; zbMATH DE number 3090557 (Why is no real title available?)
- On adaption with noisy information
- On the average complexity of multivariate problems
- On the optimality of linear methods for operator approximation in convex classes of functions
- On the Regression Design Problem of Sacks and Ylvisaker
- Optimal algorithms for linear problems with Gaussian measures
- Optimal sequential and non-sequential procedures for evaluating a functional
- Perspectives on information-based complexity
- Probabilistic setting of information-based complexity
- Some nonlinear problems are as easy as the approximation problem
Cited in
(45)- Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting
- Linear information for approximation of the Itô integrals
- Average case optimality
- A survey of information-based complexity
- Approximation of linear functionals on a Banach space with a Gaussian measure
- Probabilistic setting of information-based complexity
- Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
- An information-based approach to ill-posed problems
- The algorithm designer versus nature: A game-theoretic approach to information-based complexity
- Complexity of fixed points. I
- Stochastic properties of quadrature formulas
- On adaption with noisy information
- Randomization for continuous problems
- Optimal algorithms for a problem of optimal control
- Measures of uncertainty and information in computation
- Average case complexity of linear multivariate problems. I: Theory
- On the adaptive and continuous information problems
- On adaptive information with varying cardinality for linear problems with elliptically contoured measures
- A note on varying cardinality in the average case setting
- Integration and \(L_ 2\)-approximation: Average case setting with isotropic Wiener measure for smooth functions
- Information-based nonlinear approximation: an average case setting
- Optimal designs for weighted approximation and integration of stochastic processes on \([0,\infty)\)
- Testing linear operators
- Generalized adaptive versus nonadaptive recovery from noisy information
- On average case complexity of linear problems with noisy information
- On the complexity of stochastic integration
- The power of adaption for approximating functions with singularities
- Average case complexity of multivariate integration
- On the exponent of discrepancies
- Recent developments in information-based complexity
- On the Power of Adaptive Information for Functions with Singularities
- A survey of average case complexity for linear multivariate problems
- Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure
- Average-Case Optimality of a Hybrid Secant-Bisection Method
- Average case tractability of approximating -variate functions
- Average complexity for linear operators over bounded domains
- Mixed settings for linear problems
- Nonlinear Lebesgue and Itô integration problems of high complexity
- Approximate evaluations of characteristic polynomials of Boolean functions
- Randomized complexity of parametric integration and the role of adaption. I: Finite dimensional case
- On average complexity of global optimization problems
- Average case complexity of weighted approximation and integration over \(\mathbb R_{+}\)
- Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure
- Adaptive Itô-Taylor algorithm can optimally approximate the Itô integrals of singular functions
- Can adaption help on the average?
This page was built for publication: Information of varying cardinality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1821084)
