Information of varying cardinality
type: Item
instance of: scholarly article
title: Information of varying cardinality
zbMATH Open document ID: 0615.94004
DOI: 10.1016/0885-064X(86)90002-6
published in: Journal of Complexity
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3997695
zbMATH Keywords: adaptive information of varying cardinality
zbMATH Keywords: linear problems defined on a separable Banach space
zbMATH Keywords: worst case setting
zbMATH Keywords: average case setting
zbMATH Keywords: Gaussian measures
author: Grzegorz W. Wasilkowski
MaRDI profile type: Publication
cites work: On the optimality of linear methods for operator approximation in convex classes of functions
cites work: Q5829371
cites work: Q5631860
cites work: Q5532825
cites work: Optimal sequential and non-sequential procedures for evaluating a functional
cites work: On adaption with noisy information
cites work: Approximation of linear functionals on a Banach space with a Gaussian measure
cites work: On the average complexity of multivariate problems
cites work: Designs for Regression Problems With Correlated Errors: Many Parameters
cites work: Designs for Regression Problems with Correlated Errors III
cites work: Q4042533
cites work: Q3673103
cites work: Average case optimality for linear problems
cites work: Q3883494
cites work: Perspectives on information-based complexity
cites work: Q3938928
cites work: On the Regression Design Problem of Sacks and Ylvisaker
cites work: Average case optimality
cites work: Some nonlinear problems are as easy as the approximation problem
cites work: Optimal algorithms for linear problems with Gaussian measures
cites work: Can adaption help on the average?
cites work: Average case optimal algorithms in Hilbert spaces
cites work: A survey of information-based complexity
cites work: Probabilistic setting of information-based complexity
cites work: Q4089683
full work available at URL: 0885-064x(86)90002-6
OpenAlex ID: W2017309389
description: scientific article; zbMATH DE number 3997695