Rates of Minimization of Error Functionals over Boolean Variable-Basis Functions

Authors: Kainen, P.¹; Krkov, V.²; Sanguineti, M.³

Source: Journal of Mathematical Modelling and Algorithms, Volume 4, Number 4, December 2005 , pp. 355-368(14)

Publisher: Springer

Key:

- Free Content

- New Content

- Subscribed Content

- Free Trial Content

Abstract:

Approximate solution of optimization tasks that can be formalized as minimization of error functionals over admissible sets computable by variable-basis functions (i.e., linear combinations of n-tuples of functions from a given basis) is investigated. Estimates of rates of decrease of infima of such functionals over sets formed by linear combinations of increasing number n of elements of the bases are derived, for the case in which such admissible sets consist of Boolean functions. The results are applied to target sets of various types (e.g., sets containing functions representable either by linear combinations of a ???small??? number of generalized parities or by ???small??? decision trees and sets satisfying smoothness conditions defined in terms of Sobolev norms).

Keywords: high-dimensional optimization; minimizing sequences; Boolean decision functions; decision trees

Document Type: Research article

DOI: 10.1007/s10852-005-1625-z

Affiliations: 1: Email: kainen@georgetown.edu 2: Email: vera@cs.cas.cz 3: Email: marcello@dist.unige.it