# A Comparison between Fixed-Basis and Variable-Basis Schemes for

Authors: Giorgio Gnecco
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Fixed-basis and variable-basis approximation schemes are compared for the problems of function
approximation and functional optimization (also known as infinite programming). Classes
of problems are investigated for which variable-basis schemes with sigmoidal computational
units perform better than fixed-basis ones, in terms of the minimum number of computational
units needed to achieve a desired error in function approximation or approximate optimization.
Previously known bounds on the accuracy are extended, with better rates, to families ofd-variable functions whose actual dependence is on a subset of d′≪d variables, where the indices
of these d′ variables are not known a priori.


---

## Body

## 1. Introduction

In functional optimization problems, also known as infinite programming problems, functionals have to be minimized with respect to functions belonging to subsets of function spaces. Function-approximation problems, the classical problems of the calculus of variations [1] and, more generally, all optimization tasks in which one has to find a function that is optimal in a sense specified by a cost functional belong to this family of problems. Such functions may express, for example, the routing strategies in communication networks, the decision functions in optimal control problems and economic ones, and the input/output mappings of devices that learn from examples.Experience has shown that optimization of functionals over admissible sets of functions made up of linear combinations of relatively few basis functions with a simple structure and depending nonlinearly on a set of “inner” parameters (e.g., feedforward neural networks with one hidden layer and linear output activation units) often provides surprisingly good suboptimal solutions. In such approximation schemes, each function depends on both external parameters (the coefficients of the linear combination) and inner parameters (the ones inside the basis functions). These are examples ofvariable-basis approximators since the basis functions are not fixed but their choice depends on the one of the inner parameters. In contrast, classical approximation schemes (such as the Ritz method in the calculus of variations [1]) do not use inner parameters but employ fixed basis functions, and the corresponding approximators exhibit only a linear dependence on the external parameters. Then, they are called fixed-basis or linear approximators. In [2], certain variable-basis approximators were applied to obtain approximate solutions to functional optimization problems. This technique was later formalized as the extended Ritz method(ERIM) [3] and was motivated by the innovative and successful application of feedforward neural networks in the late 80 s. For experimental results and theoretical investigations about the ERIM, see [2–7] and the references therein.The basic motivation to search for suboptimal solutions of these forms is quite intuitive: when the number of basis functions becomes sufficiently large, the convergence of the sequence of suboptimal solutions to an optimal one may be ensured by suitable properties of the set of basis functions, the admissible set of functions, and the functional to be optimized [1, 5, 8]. Computational feasibility requirements (i.e., memory occupancy and time needed to find sufficiently good values for the parameters) make it crucial to estimate the minimum number of computational units needed by an approximator to guarantee that suboptimal solutions are “sufficiently close” to an optimal one. Such a number plays the role of “model complexity” of the approximator and can be studied with tools from linear and nonlinear approximation theory [9, 10].As compared to fixed-basis approximators, in variable-basis ones the nonlinearity of the parametrization of the variable basis functions may cause the loss of useful properties of best approximation operators [11], such as uniqueness, homogeneity, and continuity, but may allow improved rates of approximation or approximate optimization [9, 12–14]. Then, to justify the use of variable-basis schemes instead of fixed-basis ones, it is crucial to investigate families of function-approximation and functional optimization problems for which, for a given desired accuracy, variable-basis schemes require a smaller number of computational units than fixed-basis ones. This is the aim of this work.In the paper, the approximate solution of certain function-approximation and functional optimization problems via fixed- and variable-basis schemes is investigated. In particular, families of problems are presented, for which variable-basis schemes of a certain kind perform better than any fixed-basis one, in terms of the minimum number of computational units needed to achieve a desired worst-case error. Propositions2.4, 2.7, 2.8, and 3.2 are the main contributions, which are presented after the exposition of results available in the literature.The paper is organized as follows. Section2 compares variable- and fixed-basis approximation schemes for function-approximation problems, which are particular instances of functional optimization. Section 3 extends the estimates to some more general families of functional optimization problems through the concepts of modulus of continuity and modulus of convexity of a functional. Section 4 is a short discussion.


## 2. Comparison of Bounds for Fixed- and Variable-Basis Approximation

Here and in the following, the “bigO,” “big Ω,” and “big Θ” notations [18] are used. For two functions f,g:(0,+∞)→ℝ, one writes f=O(g) if and only if there exist M>0 and x0>0 such that |f(x)|≤M|g(x)| for all x>x0, f=Ω(g) if and only if g=O(f), and f=Θ(g) if and only if both f=O(g) and f=Ω(g) hold. In order to be able to use such notations also for multivariable functions, in the following it is assumed that all their arguments are fixed with the exception of one of them (more precisely, the argument ɛ).Two approaches have been adopted in the literature to compare the approximation capabilities of fixed- and variable-basis approximation schemes (see also [15] for a discussion on this topic). In the first one, one fixes the family of functions to be approximated (e.g., the unit ball in a Sobolev space [16]), then one finds bounds on the worst-case approximation error for functions belonging to such a family, for various approximation schemes (fixed- and variable-basis ones). The second approach, initiated by Barron [12, 17], fixes a variable-basis approximation scheme (e.g., the set of one-hidden-layer perceptrons with a given upper bound on the number of sigmoidal computational units) and searches for families of functions that are well approximated by such an approximation scheme. Then, for these families of functions, the approximation capability of the variable-basis approximation scheme is compared with the ones of fixed-basis approximation schemes. In this context, one is interested in finding cases for which, the number of computational units being the same, one has upper bounds on the worst-case approximation error for certain variable-basis approximation schemes that are smaller than corresponding lower bounds for any fixed-basis one, implying that such variable-basis schemes have better approximation capabilities than every fixed-basis one.One problem of the first approach is that, for certain families of smooth functions to be approximated, the bounds on the worst-case approximation error obtained for fixed- and variable-basis approximation schemes are very similar. In particular, typically one obtains the so-calledJackson rate of approximation [4] n=Θ(ɛ-d/m), where n is the number of computational units, ɛ>0 is the worst-case approximation error, m is a measure of smoothness, and d is the number of variables on which such functions depend. Following the second approach, it was shown in [12, 17] that, for certain function-approximation problems, variable-basis schemes exhibit some advantages over fixed-basis ones (see Sections 2.1 and 2.2, where extensions of some results from [12, 17] are also derived).In Section2.1, some bounds in the ℒ2-norm are considered, whereas Section 2.2 investigates bounds in the supnorm. Estimates in the ℒ2-norm can be applied, for example, to investigate the approximation of the optimal policies in static team optimization problems [19]. Estimates in the supnorm are required, for example, to investigate the approximation of the optimal policies in dynamic optimization problems with a finite number of stages [20]. Indeed, for such problems, the supnorm can be used to analyze the error propagation from one stage to the next one, while this is not the case for the ℒ2-norm [20]. Moreover, it provides guarantees on the approximation errors in the design of the optimal decision laws.


### 2.1. Bounds in theℒ2-Norm

The following Theorem2.1 from [12] describes a quite general set of functions of d real variables (described in terms of their Fourier distributions) whose approximation from variable-basis approximation schemes with sigmoidal computational units requires O(ɛ-2) computational units, where ɛ>0 is the desired worst-case approximation error measured in the ℒ2-norm. Recall that a sigmoidal function is defined in general as a bounded measurable function σ:ℝ→ℝ such that σ(y)→1 as y→+∞ and σ(y)→0 as y→-∞ [21]. For C>0, d a positive integer, and B a bounded subset of ℝd containing 0, by ΓB,C we denote the set of functions f:ℝd→ℝ having a Fourier representation of the form(2.1)f(x)=∫Rdeiω⋅xF̂(dω)
for some complex-valued measure F̂(dω)=eiθ(ω)F(dω) (where F(dω) and θ(ω) are the magnitude distribution and the phase at the pulsation ω, resp.) such that(2.2)∫Rdsup⁡x∈B|〈ω,x〉|F(dω)≤C,
where 〈·,·〉 is the standard inner product on ℝd. Functions in ΓB,C are continuously differentiable on B [12]. When B is the hypercube [-1,1]d, the inequality (2.2) reduces to(2.3)∫Rd‖ω‖1F(dω)≤C,
where ∥·∥1 denotes the l1-norm.For a probability measureμ on B, we denote by ℒ2(B,μ) the Hilbert space of functions g:B→ℝ with inner product 〈g1,g2〉ℒ2(B,μ):=∫Bg1(x)g2(x)μ(dx) and induced norm ∥g∥ℒ2(B,μ):=〈g,g〉ℒ2(B,μ). When there is no risk of confusion, the simpler notation ∥g∥ℒ2 is used instead of ∥g∥ℒ2(B,μ).Theorem 2.1 (see [12, Theorem  1]).
For everyf∈ΓB,C, every sigmoidal function σ:ℝ→ℝ, every probability measure μ on B, and every n≥1, there exist ak∈ℝd, bk,ck∈ℝ, and fn:B→ℝ of the form
(2.4)fn(x)=∑k=1nckσ(〈ak,x〉+bk)+c0,
such that
(2.5)‖f-fn‖L2:=∫B(f(x)-fn(x))2μ(dx)≤2Cn.Variable-basis approximators of the form (2.4) are called one-hidden-layer perceptrons with n computational units. Formula (2.5) shows that at most(2.6)n1*=⌈(2C)2ɛ-2⌉
computational units are required to guarantee a desired worst-case approximation error ɛ in the ℒ2-norm, when variable-basis approximation schemes of the form (2.4) are used to approximate functions belonging to the set ΓB,C.In contrast to this, Theorem2.2 from [12] shows that, when B is the unit hypercube [0,1]d and μ=μu is the uniform probability measure on [0,1]d, for the same set of functions ΓB,C the best linear approximation scheme requires Ω(ɛ-d) computational units in order to achieve the same worst-case approximation error ɛ. The set of all linear combinations of n fixed basis functions h1,h2,…,hn in a linear space is denoted by span(h1,h2,…,hn).Theorem 2.2 (see [12, Theorem  6]).
For everyn≥1 and every choice of fixed basis functions h1,h2,…,hn∈ℒ2([0,1]d,μu), one has
(2.7)sup⁡f∈Γ[0,1]d,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≥C16πeπ-1d(12n)1/d.Remark 2.3.
Inspection of the proof of [12, Theorem  6] shows that the factors 1/8 and 1/n, which appear in the original statement of the theorem, have to be replaced by 1/16 and 1/2n in (2.7), respectively.
Inspection of the proof of Theorem2.2 in [12] shows also that the lower bound (2.7) still holds if the set Γ[0,1]d,C is replaced by either
(2.8)S1:={f:[0,1]d⟶R:f(x)=C2π‖l‖1cos⁡(ω⋅x):ω=2πlforl∈{0,1,…}d,l≠(0,…,0)}∪{f:[0,1]d⟶R:f(x)=C2π}
or
(2.9)S2:={f:[0,1]d⟶R:f(x)=βcos⁡(ω⋅x):|β|≤C2π‖l‖1,ω=2πlforl∈{0,1,…}d,l≠(0,…,0){C2π‖l‖1}}∪{f:[0,1]d⟶R:f(x)=β,|β|≤C2π},
where l denotes any multi-index and ∥l∥1 its norm (i.e., the sum of the components of l, which are nonnegative). Obviously, when B is the unit hypercube [0,1]d, the upper bound (2.5) still holds under one of these two replacements, since 𝒮1⊂𝒮2⊂Γ[0,1]d,C.The inequality (2.7) implies that for a uniform probability measure on [0,1]d, at least(2.10)n2*=⌊12(C16πeπ-1d)dɛ-d⌋
computational units are required to guarantee a desired worst-case approximation error ɛ in the ℒ2-norm, when fixed-basis approximation schemes of the form span(h1,h2,…,hn) are used to approximate functions in Γ[0,1]d,C. Then, at least for a sufficiently small value of ɛ, Theorems 2.1 and 2.2 show that for d>2, variable-basis approximators of the form (2.4) provide a smaller approximation error than any fixed-basis one for functions in Γ[0,1]d,C, the number of computational units being the same.It should be noted that, for fixedC and ɛ, the estimate (2.6) is constant with respect to d, whereas the one (2.10) goes to 0 as d goes to +∞. So, a too small value of (1/2)(C/16πeπ-1d)d in the bound (2.10) for fixed-basis approximation may make the theoretical advantage of variable-basis approximation of impractical use, since for large d it would be guaranteed only for sufficiently small ɛ (depending on C, too). In the following, families of d-variable functions are considered, for which this drawback is mitigated. These are families of d-variable functions whose actual dependence is on a subset of d′≪d variables, where the indices of these d′ variables are not known a priori. These families are of interest, for example, in machine learning applications, for problems with redundant or correlated features. In this context, each of the d real variables represents a feature (e.g., a measure of some physical property of an object), and one is interested in learning a function of these features on the basis of a set of supervised examples. As it often happens in applications, only a small subset of the features is useful for the specific task (typically, classification or regression), due to the presence of redundant or correlated features. Then, one may assume that the function to be learned depends only on subset of d′≪d features but one may not know a priori which particular subset is. The problem of finding such a subset (or finding a subset of features of sufficiently small cardinality d′ on which the function mostly depends, when the function depends on all the d features) is called the feature-selection problem [22].Ford′ a positive integer and d its multiple, Γ[0,1]d,d′,C denotes the subset of functions in Γ[0,1]d,C that depend only on d′ of their possible d arguments.Proposition 2.4.
For everyn≥1 and every choice of fixed basis functions h1,h2,…,hn∈ℒ2([0,1]d,μu),   for n≤(d+1)/2 one has
(2.11)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≥C8π
and for n>(d+1)/2(2.12)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≥(dd′)1/d′C16πeπ-1d′(12n)1/d′.Proof.
The proof is similar to the one of [12, Theorem  6]. The following is a list of the changes to that proof, needed to derive (2.11) and (2.12). We denote by ∥l∥0 the number of nonzero components of the multi-index l. Proceeding likewise in the proof of [12, Theorem  6], we get
(2.13)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≥C8πm*,
where m* is the smallest positive integer m such that the number Nm,d,d′ of multi-indices l∈{0,1,…}d with norm ∥l∥1≤m and that satisfy the constraint ∥l∥0≤d′ is larger than or equal to 2n. More precisely, (2.13) is obtained by observing that for such an integer m the set 𝒮2∩Γ[0,1]d,d′,C contains at least 2n orthogonal cosinusoidal functions with ℒ2([0,1]d,μu)-norm equal to C/4πm and applying [12, Lemma  6], which states that for any orthonormal basis of a 2n-dimensional space, there does not exist a linear subspace of dimension n having distance smaller than 1/2 from every basis function in such an orthonormal basis. The constraint ∥l∥0≤d′ is not present in the proof of [12, Theorem  6] and is due to the specific form of the set Γ[0,1]d,d′,C. Because of such a constraint, the functions in 𝒮2 with ∥l∥0>d′ do not belong to Γ[0,1]d,d′,C.
Then we get(2.14)Nm,d,d′=(m+dd)ford=d′or1≤m≤d′,(2.15)(m+dd)≥Nm,d,d′≥dd′(m+d′d′)fordd′a positiveinteger>1andm>1.
Indeed, for d=d′ the equality (2.14) follows recalling that the number of different ways of placing No identical objects in Nb distinct boxes is (No+Nb-1Nb-1) [23, Theorem  5.1], and for this case it is the same estimate as the one obtained in the proof of [12, Theorem  6]. Similarly, for 1≤m≤d′ the constraint ∥l∥0≤d′ is redundant and we get again (2.14). Finally, for d/d′ a positive integer larger than 1 and m>1, the upper bound in (2.15) is obtained ignoring the constraint ∥l∥0≤d′, whereas the lower bound is obtained as follows. First, we partition the set of d variables into d/d′ subsets of cardinality d′, and then we apply to each subset the estimate Nm,d′,d′=(m+d′d′) obtained by replacing d by d′ in (2.14). In this way, the multi-index l=0 is counted d/d′ times (one for each subset), but the final estimate Nm,d,d′≥d/d′(m+d′d′) so obtained holds since for m>1 there are at least other d/d′-1 multi-indices that have been not counted in this process.
In the following, we apply (2.14) and (2.15) for m=1 and m>1, respectively. For m=1, the condition Nm,d,d′≥2n becomes(2.16)(1+dd)=d+1≥2n,
so m*=1 for n≤(d+1)/2. This, combined with (2.13), proves (2.11).
Now, likewise in the proof of [12, Theorem  6], for m>1 we exploit a bound from Stirling’s formula, according to which (m+d′d′)≥(m/eπ-1d′)d′, so the condition Nm,d,d′≥2n holds if we impose(2.17)dd′(meπ-1d′)d′≥2n,
which is equivalent to
(2.18)m≥⌈eπ-1d′(2n)1/d′(d′d)1/d′⌉
(note that, for n>(d+1)/2, the value of m provided by (2.18) is indeed larger than 1, as required for the application of (2.15)). Since
(2.19)2eπ-1d′(2n)1/d′(d′d)1/d′≥⌈eπ-1d′(2n)1/d′(d′d)1/d′⌉
we conclude that m*≤2eπ-1d′(2n)1/d′(d′/d)1/d′ for n>(d+1)/2. This, together with (2.13), proves the statement (2.12).For the case considered by Proposition2.4, an uniform probability measure on [0,1]d, and 0<ɛ<C/8π, formulas (2.11) and (2.12) show that at least(2.20)n3*=max⁡{⌈d+12⌉,⌊12dd′(C16πeπ-1d′)d′ɛ-d′⌋}
computational units are required to guarantee a desired worst-case approximation error ɛ in the ℒ2-norm, when fixed-basis approximation schemes of the form span(h1,h2,…,hn) are used to approximate functions in Γ[0,1]d,d′,C.Remark 2.5.
The quantityd′ in Proposition 2.4 has to be interpreted as an effective number of variables for the family of functions Γ[0,1]d,d′,C to be approximated. Roughly speaking, the flexibility of the neural network architecture (2.4) allows one to identify, for each f∈Γ[0,1]d,d′,C, the d′ variables on which it actually depends, whereas fixed-basis approximation schemes have not this flexibility. Indeed, differently from the lower bound (2.10), for fixed C, ɛ, and d′ the lower bound (2.20) goes to +∞ as d goes to +∞. Finally, similar remarks as in Remark 2.3 apply to Proposition 2.4.


### 2.2. Bounds in the Supnorm

The next result is from [17] and is analogous to Theorem 2.1, but it measures the worst-case approximation error in the supnorm.Theorem 2.6 (see [17, Theorem  2]).
For everyf∈ΓB,C and every n≥1, there exists fn:B→ℝ of the form (2.4) such that
(2.21)sup⁡x∈B|f(x)-fn(x)|≤120Cnd.Upper bounds in the supnorm similar to the one from Theorem2.6 are given, for example, in [24, 25]. Moreover, for f∈Γ[0,1]d,d′,C, the following estimate holds.Proposition 2.7.
For everyf∈Γ[0,1]d,d′,C and every n≥1, there exists fn:[0,1]d→ℝ of the form (2.4) such that
(2.22)sup⁡x∈[0,1]d|f(x)-fn(x)|≤120Cnd′.Proof.
Each functionf∈Γ[0,1]d,d′,C depends on d′ arguments; let i1,…,id′ be their indices. Let f̃:[0,1]d′→ℝ be defined by f̃(y):=f(x), where xi1=y1,…,xid′=yd′, and all the other components of x are arbitrary in [0,1]d-d′. Then f̃∈Γ[0,1]d′,C, so by Theorem 2.6 there exists an approximation f̃n:[0,1]d′→ℝ made up of n sigmoidal computational units and a constant term such that supx∈[0,1]d′|f̃(x)-f̃n(x)|≤(120C/n)d′. Finally, we observe that f̃n can be extended to a function fn:[0,1]d→ℝ of the form (2.4) such that supx∈[0,1]d|f(x)-fn(x)|=supx∈[0,1]d′|f̃(x)-f̃n(x)|, then one obtains (2.22).The estimates (2.21) and (2.22) show that at most(2.23)n4*=⌈(120C)2d2ɛ-2⌉,n5*=⌈(120C)2d′2ɛ-2⌉
computational units, respectively, are required to guarantee a desired worst-case approximation error ɛ in the supnorm,  when variable-basis approximation schemes of the form (2.4) are used to approximate functions belonging to the sets ΓB,C and Γ[0,1]d,d′,C, respectively.The next proposition, combined with Theorem2.6 and Proposition 2.7, allows one to compare the approximation capabilities of fixed- and variable-basis schemes in the supnorm, showing cases for which the upper bounds (2.21) and (2.22) are smaller than one of the corresponding lower bounds (2.24)–(2.26), at least for n sufficiently large.Proposition 2.8.
For everyn≥1 and every choice of fixed bounded and μu-measurable basis functions h1,h2,…,hn:[0,1]d→ℝ, the following hold.(i)
For the approximation of functions inΓ[0,1]d,C, one has
(2.24)sup⁡f∈Γ[0,1]d,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|≥C16πeπ-1d(12n)1/d.(ii)
For the approximation of functions inΓ[0,1]d,d′,C, for n≤(d+1)/2, one has
(2.25)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|≥C8π
whereas for n>(d+1)/2(2.26)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|≥(dd′)1/d′C16πeπ-1d′(12n)1/d′.Proof.
For each bounded andμu-measurable function g:[0,1]d→ℝ, we get
(2.27)∫[0,1]dg2(x)μu(dx)≤sup⁡x∈[0,1]d|g(x)|∫[0,1]dμu(dx)=sup⁡x∈[0,1]d|g(x)|,
so
(2.28)sup⁡f∈Γ[0,1]d,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≤sup⁡f∈Γ[0,1]d,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|,sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≤sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|.
Then we get the lower bounds (2.24)–(2.26) by (2.7), (2.11), and (2.12), respectively.For the case considered by Proposition2.8, the estimate (2.24) implies that at leastn2* computational units are required to guarantee a desired worst-case approximation error ɛ in the supnorm, when fixed-basis approximation schemes of the form span(h1,h2,…,hn) are used to approximate functions in Γ[0,1]d,C. Similarly, for 0<ɛ<C/8π, the bounds (2.25) and (2.26) imply that at leastn3* computational units are required when Γ[0,1]d,C is replaced by Γ[0,1]d,d′,C. One can observe that, for each d, d′ and C, each of the lower bounds (2.25) and (2.26) is larger than (2.24). Moreover, all the other parameters being fixed, the lower bound (2.24) goes to 0 as d tends to +∞, whereas for d≥2n-1, the lower bound (2.25) holds, and it does not depend on the specific value of d. Finally, for d>2, the upper bound (2.21) is smaller than the lower bound (2.24) for n sufficiently large, and similarly, for d′>2, the upper bound (2.22) is smaller than the lower bounds (2.25) and (2.26) for n sufficiently large. For instance, in the latter case and for d′ sufficiently small with respect to d, this happens for ⌈225d′2/π2⌉≤n≤(d+1)/2 and for(2.29)n≥min⁡{⌈d+12⌉,⌈K1dK2⌉},
where K1=(1920·21/d′πeπ-1)2d′/(d′-2)d′2(2d+1)/(d′-2) and K2=2/(d′-2).Similar remarks as in Remark2.3 can be made about the bounds in the supnorm derived in this section.


## 2.1. Bounds in theℒ2-Norm

The following Theorem2.1 from [12] describes a quite general set of functions of d real variables (described in terms of their Fourier distributions) whose approximation from variable-basis approximation schemes with sigmoidal computational units requires O(ɛ-2) computational units, where ɛ>0 is the desired worst-case approximation error measured in the ℒ2-norm. Recall that a sigmoidal function is defined in general as a bounded measurable function σ:ℝ→ℝ such that σ(y)→1 as y→+∞ and σ(y)→0 as y→-∞ [21]. For C>0, d a positive integer, and B a bounded subset of ℝd containing 0, by ΓB,C we denote the set of functions f:ℝd→ℝ having a Fourier representation of the form(2.1)f(x)=∫Rdeiω⋅xF̂(dω)
for some complex-valued measure F̂(dω)=eiθ(ω)F(dω) (where F(dω) and θ(ω) are the magnitude distribution and the phase at the pulsation ω, resp.) such that(2.2)∫Rdsup⁡x∈B|〈ω,x〉|F(dω)≤C,
where 〈·,·〉 is the standard inner product on ℝd. Functions in ΓB,C are continuously differentiable on B [12]. When B is the hypercube [-1,1]d, the inequality (2.2) reduces to(2.3)∫Rd‖ω‖1F(dω)≤C,
where ∥·∥1 denotes the l1-norm.For a probability measureμ on B, we denote by ℒ2(B,μ) the Hilbert space of functions g:B→ℝ with inner product 〈g1,g2〉ℒ2(B,μ):=∫Bg1(x)g2(x)μ(dx) and induced norm ∥g∥ℒ2(B,μ):=〈g,g〉ℒ2(B,μ). When there is no risk of confusion, the simpler notation ∥g∥ℒ2 is used instead of ∥g∥ℒ2(B,μ).Theorem 2.1 (see [12, Theorem  1]).
For everyf∈ΓB,C, every sigmoidal function σ:ℝ→ℝ, every probability measure μ on B, and every n≥1, there exist ak∈ℝd, bk,ck∈ℝ, and fn:B→ℝ of the form
(2.4)fn(x)=∑k=1nckσ(〈ak,x〉+bk)+c0,
such that
(2.5)‖f-fn‖L2:=∫B(f(x)-fn(x))2μ(dx)≤2Cn.Variable-basis approximators of the form (2.4) are called one-hidden-layer perceptrons with n computational units. Formula (2.5) shows that at most(2.6)n1*=⌈(2C)2ɛ-2⌉
computational units are required to guarantee a desired worst-case approximation error ɛ in the ℒ2-norm, when variable-basis approximation schemes of the form (2.4) are used to approximate functions belonging to the set ΓB,C.In contrast to this, Theorem2.2 from [12] shows that, when B is the unit hypercube [0,1]d and μ=μu is the uniform probability measure on [0,1]d, for the same set of functions ΓB,C the best linear approximation scheme requires Ω(ɛ-d) computational units in order to achieve the same worst-case approximation error ɛ. The set of all linear combinations of n fixed basis functions h1,h2,…,hn in a linear space is denoted by span(h1,h2,…,hn).Theorem 2.2 (see [12, Theorem  6]).
For everyn≥1 and every choice of fixed basis functions h1,h2,…,hn∈ℒ2([0,1]d,μu), one has
(2.7)sup⁡f∈Γ[0,1]d,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≥C16πeπ-1d(12n)1/d.Remark 2.3.
Inspection of the proof of [12, Theorem  6] shows that the factors 1/8 and 1/n, which appear in the original statement of the theorem, have to be replaced by 1/16 and 1/2n in (2.7), respectively.
Inspection of the proof of Theorem2.2 in [12] shows also that the lower bound (2.7) still holds if the set Γ[0,1]d,C is replaced by either
(2.8)S1:={f:[0,1]d⟶R:f(x)=C2π‖l‖1cos⁡(ω⋅x):ω=2πlforl∈{0,1,…}d,l≠(0,…,0)}∪{f:[0,1]d⟶R:f(x)=C2π}
or
(2.9)S2:={f:[0,1]d⟶R:f(x)=βcos⁡(ω⋅x):|β|≤C2π‖l‖1,ω=2πlforl∈{0,1,…}d,l≠(0,…,0){C2π‖l‖1}}∪{f:[0,1]d⟶R:f(x)=β,|β|≤C2π},
where l denotes any multi-index and ∥l∥1 its norm (i.e., the sum of the components of l, which are nonnegative). Obviously, when B is the unit hypercube [0,1]d, the upper bound (2.5) still holds under one of these two replacements, since 𝒮1⊂𝒮2⊂Γ[0,1]d,C.The inequality (2.7) implies that for a uniform probability measure on [0,1]d, at least(2.10)n2*=⌊12(C16πeπ-1d)dɛ-d⌋
computational units are required to guarantee a desired worst-case approximation error ɛ in the ℒ2-norm, when fixed-basis approximation schemes of the form span(h1,h2,…,hn) are used to approximate functions in Γ[0,1]d,C. Then, at least for a sufficiently small value of ɛ, Theorems 2.1 and 2.2 show that for d>2, variable-basis approximators of the form (2.4) provide a smaller approximation error than any fixed-basis one for functions in Γ[0,1]d,C, the number of computational units being the same.It should be noted that, for fixedC and ɛ, the estimate (2.6) is constant with respect to d, whereas the one (2.10) goes to 0 as d goes to +∞. So, a too small value of (1/2)(C/16πeπ-1d)d in the bound (2.10) for fixed-basis approximation may make the theoretical advantage of variable-basis approximation of impractical use, since for large d it would be guaranteed only for sufficiently small ɛ (depending on C, too). In the following, families of d-variable functions are considered, for which this drawback is mitigated. These are families of d-variable functions whose actual dependence is on a subset of d′≪d variables, where the indices of these d′ variables are not known a priori. These families are of interest, for example, in machine learning applications, for problems with redundant or correlated features. In this context, each of the d real variables represents a feature (e.g., a measure of some physical property of an object), and one is interested in learning a function of these features on the basis of a set of supervised examples. As it often happens in applications, only a small subset of the features is useful for the specific task (typically, classification or regression), due to the presence of redundant or correlated features. Then, one may assume that the function to be learned depends only on subset of d′≪d features but one may not know a priori which particular subset is. The problem of finding such a subset (or finding a subset of features of sufficiently small cardinality d′ on which the function mostly depends, when the function depends on all the d features) is called the feature-selection problem [22].Ford′ a positive integer and d its multiple, Γ[0,1]d,d′,C denotes the subset of functions in Γ[0,1]d,C that depend only on d′ of their possible d arguments.Proposition 2.4.
For everyn≥1 and every choice of fixed basis functions h1,h2,…,hn∈ℒ2([0,1]d,μu),   for n≤(d+1)/2 one has
(2.11)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≥C8π
and for n>(d+1)/2(2.12)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≥(dd′)1/d′C16πeπ-1d′(12n)1/d′.Proof.
The proof is similar to the one of [12, Theorem  6]. The following is a list of the changes to that proof, needed to derive (2.11) and (2.12). We denote by ∥l∥0 the number of nonzero components of the multi-index l. Proceeding likewise in the proof of [12, Theorem  6], we get
(2.13)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≥C8πm*,
where m* is the smallest positive integer m such that the number Nm,d,d′ of multi-indices l∈{0,1,…}d with norm ∥l∥1≤m and that satisfy the constraint ∥l∥0≤d′ is larger than or equal to 2n. More precisely, (2.13) is obtained by observing that for such an integer m the set 𝒮2∩Γ[0,1]d,d′,C contains at least 2n orthogonal cosinusoidal functions with ℒ2([0,1]d,μu)-norm equal to C/4πm and applying [12, Lemma  6], which states that for any orthonormal basis of a 2n-dimensional space, there does not exist a linear subspace of dimension n having distance smaller than 1/2 from every basis function in such an orthonormal basis. The constraint ∥l∥0≤d′ is not present in the proof of [12, Theorem  6] and is due to the specific form of the set Γ[0,1]d,d′,C. Because of such a constraint, the functions in 𝒮2 with ∥l∥0>d′ do not belong to Γ[0,1]d,d′,C.
Then we get(2.14)Nm,d,d′=(m+dd)ford=d′or1≤m≤d′,(2.15)(m+dd)≥Nm,d,d′≥dd′(m+d′d′)fordd′a positiveinteger>1andm>1.
Indeed, for d=d′ the equality (2.14) follows recalling that the number of different ways of placing No identical objects in Nb distinct boxes is (No+Nb-1Nb-1) [23, Theorem  5.1], and for this case it is the same estimate as the one obtained in the proof of [12, Theorem  6]. Similarly, for 1≤m≤d′ the constraint ∥l∥0≤d′ is redundant and we get again (2.14). Finally, for d/d′ a positive integer larger than 1 and m>1, the upper bound in (2.15) is obtained ignoring the constraint ∥l∥0≤d′, whereas the lower bound is obtained as follows. First, we partition the set of d variables into d/d′ subsets of cardinality d′, and then we apply to each subset the estimate Nm,d′,d′=(m+d′d′) obtained by replacing d by d′ in (2.14). In this way, the multi-index l=0 is counted d/d′ times (one for each subset), but the final estimate Nm,d,d′≥d/d′(m+d′d′) so obtained holds since for m>1 there are at least other d/d′-1 multi-indices that have been not counted in this process.
In the following, we apply (2.14) and (2.15) for m=1 and m>1, respectively. For m=1, the condition Nm,d,d′≥2n becomes(2.16)(1+dd)=d+1≥2n,
so m*=1 for n≤(d+1)/2. This, combined with (2.13), proves (2.11).
Now, likewise in the proof of [12, Theorem  6], for m>1 we exploit a bound from Stirling’s formula, according to which (m+d′d′)≥(m/eπ-1d′)d′, so the condition Nm,d,d′≥2n holds if we impose(2.17)dd′(meπ-1d′)d′≥2n,
which is equivalent to
(2.18)m≥⌈eπ-1d′(2n)1/d′(d′d)1/d′⌉
(note that, for n>(d+1)/2, the value of m provided by (2.18) is indeed larger than 1, as required for the application of (2.15)). Since
(2.19)2eπ-1d′(2n)1/d′(d′d)1/d′≥⌈eπ-1d′(2n)1/d′(d′d)1/d′⌉
we conclude that m*≤2eπ-1d′(2n)1/d′(d′/d)1/d′ for n>(d+1)/2. This, together with (2.13), proves the statement (2.12).For the case considered by Proposition2.4, an uniform probability measure on [0,1]d, and 0<ɛ<C/8π, formulas (2.11) and (2.12) show that at least(2.20)n3*=max⁡{⌈d+12⌉,⌊12dd′(C16πeπ-1d′)d′ɛ-d′⌋}
computational units are required to guarantee a desired worst-case approximation error ɛ in the ℒ2-norm, when fixed-basis approximation schemes of the form span(h1,h2,…,hn) are used to approximate functions in Γ[0,1]d,d′,C.Remark 2.5.
The quantityd′ in Proposition 2.4 has to be interpreted as an effective number of variables for the family of functions Γ[0,1]d,d′,C to be approximated. Roughly speaking, the flexibility of the neural network architecture (2.4) allows one to identify, for each f∈Γ[0,1]d,d′,C, the d′ variables on which it actually depends, whereas fixed-basis approximation schemes have not this flexibility. Indeed, differently from the lower bound (2.10), for fixed C, ɛ, and d′ the lower bound (2.20) goes to +∞ as d goes to +∞. Finally, similar remarks as in Remark 2.3 apply to Proposition 2.4.


## 2.2. Bounds in the Supnorm

The next result is from [17] and is analogous to Theorem 2.1, but it measures the worst-case approximation error in the supnorm.Theorem 2.6 (see [17, Theorem  2]).
For everyf∈ΓB,C and every n≥1, there exists fn:B→ℝ of the form (2.4) such that
(2.21)sup⁡x∈B|f(x)-fn(x)|≤120Cnd.Upper bounds in the supnorm similar to the one from Theorem2.6 are given, for example, in [24, 25]. Moreover, for f∈Γ[0,1]d,d′,C, the following estimate holds.Proposition 2.7.
For everyf∈Γ[0,1]d,d′,C and every n≥1, there exists fn:[0,1]d→ℝ of the form (2.4) such that
(2.22)sup⁡x∈[0,1]d|f(x)-fn(x)|≤120Cnd′.Proof.
Each functionf∈Γ[0,1]d,d′,C depends on d′ arguments; let i1,…,id′ be their indices. Let f̃:[0,1]d′→ℝ be defined by f̃(y):=f(x), where xi1=y1,…,xid′=yd′, and all the other components of x are arbitrary in [0,1]d-d′. Then f̃∈Γ[0,1]d′,C, so by Theorem 2.6 there exists an approximation f̃n:[0,1]d′→ℝ made up of n sigmoidal computational units and a constant term such that supx∈[0,1]d′|f̃(x)-f̃n(x)|≤(120C/n)d′. Finally, we observe that f̃n can be extended to a function fn:[0,1]d→ℝ of the form (2.4) such that supx∈[0,1]d|f(x)-fn(x)|=supx∈[0,1]d′|f̃(x)-f̃n(x)|, then one obtains (2.22).The estimates (2.21) and (2.22) show that at most(2.23)n4*=⌈(120C)2d2ɛ-2⌉,n5*=⌈(120C)2d′2ɛ-2⌉
computational units, respectively, are required to guarantee a desired worst-case approximation error ɛ in the supnorm,  when variable-basis approximation schemes of the form (2.4) are used to approximate functions belonging to the sets ΓB,C and Γ[0,1]d,d′,C, respectively.The next proposition, combined with Theorem2.6 and Proposition 2.7, allows one to compare the approximation capabilities of fixed- and variable-basis schemes in the supnorm, showing cases for which the upper bounds (2.21) and (2.22) are smaller than one of the corresponding lower bounds (2.24)–(2.26), at least for n sufficiently large.Proposition 2.8.
For everyn≥1 and every choice of fixed bounded and μu-measurable basis functions h1,h2,…,hn:[0,1]d→ℝ, the following hold.(i)
For the approximation of functions inΓ[0,1]d,C, one has
(2.24)sup⁡f∈Γ[0,1]d,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|≥C16πeπ-1d(12n)1/d.(ii)
For the approximation of functions inΓ[0,1]d,d′,C, for n≤(d+1)/2, one has
(2.25)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|≥C8π
whereas for n>(d+1)/2(2.26)sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|≥(dd′)1/d′C16πeπ-1d′(12n)1/d′.Proof.
For each bounded andμu-measurable function g:[0,1]d→ℝ, we get
(2.27)∫[0,1]dg2(x)μu(dx)≤sup⁡x∈[0,1]d|g(x)|∫[0,1]dμu(dx)=sup⁡x∈[0,1]d|g(x)|,
so
(2.28)sup⁡f∈Γ[0,1]d,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≤sup⁡f∈Γ[0,1]d,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|,sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)∫[0,1]d(f(x)-fn(x))2μu(dx)≤sup⁡f∈Γ[0,1]d,d′,Cinf⁡fn∈span⁡(h1,h2,…,hn)sup⁡x∈[0,1]d|f(x)-fn(x)|.
Then we get the lower bounds (2.24)–(2.26) by (2.7), (2.11), and (2.12), respectively.For the case considered by Proposition2.8, the estimate (2.24) implies that at leastn2* computational units are required to guarantee a desired worst-case approximation error ɛ in the supnorm, when fixed-basis approximation schemes of the form span(h1,h2,…,hn) are used to approximate functions in Γ[0,1]d,C. Similarly, for 0<ɛ<C/8π, the bounds (2.25) and (2.26) imply that at leastn3* computational units are required when Γ[0,1]d,C is replaced by Γ[0,1]d,d′,C. One can observe that, for each d, d′ and C, each of the lower bounds (2.25) and (2.26) is larger than (2.24). Moreover, all the other parameters being fixed, the lower bound (2.24) goes to 0 as d tends to +∞, whereas for d≥2n-1, the lower bound (2.25) holds, and it does not depend on the specific value of d. Finally, for d>2, the upper bound (2.21) is smaller than the lower bound (2.24) for n sufficiently large, and similarly, for d′>2, the upper bound (2.22) is smaller than the lower bounds (2.25) and (2.26) for n sufficiently large. For instance, in the latter case and for d′ sufficiently small with respect to d, this happens for ⌈225d′2/π2⌉≤n≤(d+1)/2 and for(2.29)n≥min⁡{⌈d+12⌉,⌈K1dK2⌉},
where K1=(1920·21/d′πeπ-1)2d′/(d′-2)d′2(2d+1)/(d′-2) and K2=2/(d′-2).Similar remarks as in Remark2.3 can be made about the bounds in the supnorm derived in this section.


## 3. Application to Functional Optimization Problems

The results of Section2 can be extended, with the same rates of approximation or similar ones, to the approximate solution of certain functional optimization problems. This can be done by exploiting the concepts of modulus of continuity and modulus of convexity of a functional, provided that continuity and uniform convexity assumptions are satisfied. The basic ideas are the following (see also [5] for a similar analysis).


### 3.1. Rates of Approximate Optimization in Terms of the Modulus of Continuity

Let𝒳 be a normed linear space, X⊆𝒳, and Φ:X→ℝ a functional. Suppose that the functional optimization problem(3.1)min⁡f∈XΦ(f)
has a solution f∘, and let X1⊆X2⊆⋯⊆Xn⊆⋯⊆X be a nested sequence of subsets of X such that(3.2)inf⁡fn∈Xn‖f∘-fn‖X≤ɛn
for some ɛn>0, where ɛn→0 as n→+∞. Then, if the functional Φ is continuous, too, one has(3.3)inf⁡fn∈Xn|Φ(f∘)-Φ(fn)|≤αf∘(ɛn)⟶0asn⟶+∞,
where αf∘:[0,+∞)→[0,+∞) defined by αf∘(t)=sup{|Φ(f∘)-Φ(g)|:g∈X,∥f-g∥𝒳≤t} is the modulus of continuity of Φ at f∘. For instance, if Φ is Lipschitz continuous with Lipschitz constant KΦ, one has αf∘(t)≤KΦt, and by(3.2)(3.4)inf⁡fn∈Xn|Φ(f∘)-Φ(fn)|≤KΦɛn.
Then, if an upper bound on ɛn in terms of n is known (e.g., ɛn=O(n-1/2) under the assumptions of Theorem 2.1, where X=ΓB,C⊂ℒ2(B,μ)=𝒳 and Xn is the set of functions of the form (2.4)), then the same upper bound (up to a multiplicative constant) holds on inffn∈Xn|Φ(f∘)-Φ(fn)|. So, investigating the approximating capabilities of the sets Xn is useful for functional optimization purposes, too.


### 3.2. Rates of Approximate Optimization in Terms of the Modulus of Convexity

When dealing with suboptimal solutions from a setXn⊆X, the following question arises: suppose that f̃n∈Xn is such that(3.5)|Φ(f∘)-Φ(f̃n)|≤γn
for some γn>0, where γn→0 as n→+∞. This can be guaranteed, for example, if the functional is continuous, the sets Xn satisfy the property (3.2), and one chooses f̃n∈argminfn∈Xn∥f∘-fn∥𝒳 assuming, almost without loss of generality, that such a set is nonempty. If this is not the case, then one can proceed as follows. For ϵ>0, let argminϵ,fn∈Xn∥f-fn∥𝒳:={fn∈Xn:∥f∘-fn∥𝒳≤inffn∈Xn∥f∘-fn∥𝒳+ϵ}. Then one obtains estimates similar to the ones of this section (obtained assuming that argminfn∈Xn∥f∘-fn∥𝒳 is nonempty) by choosing f̃n∈argminηɛn,fn∈Xn∥f∘-fn∥𝒳, where η>1 is a constant. Does the estimate (3.5) imply an upper bound on the approximation error ∥f∘-f̃n∥𝒳? A positive answer can be given when the functional Φ is uniformly convex. Recall that a functional Φ:X→ℝ is called convex on a convex set X⊆𝒳 if and only if for all h,g∈X and all λ∈[0,1], one has Φ(λh+(1-λ)g)≤λΦ(h)+(1-λ)Φ(g) and it is called uniformly convex if and only if there exists a nonnegative function δ:[0,+∞)→[0,+∞) such that δ(0)=0, δ(t)>0 for all t>0, and for all h,g∈X and all λ∈[0,1], one has(3.6)Φ(λh+(1-λ)g)≤λΦ(h)+(1-λ)Φ(g)-λ(1-λ)δ(‖h-g‖X).
Any such function δ is called a modulus of convexity of Φ [26]. The terminology is not unified: some authors use the term “strictly uniformly convex” instead of “uniformly convex” and reserve the term “uniformly convex” for the case where δ:[0,+∞)→[0,+∞) merely satisfies δ(0)=0 and δ(t0)>0 for some t0>0 (see, e.g., [27, 28]). Note that when 𝒳 is a Hilbert space and δ(t) has the quadratic expression(3.7)δ(t)=12ct2
for some constant c>0, the condition (3.6) is equivalent to the convexity of the functional Φ(·)-δ(∥·∥𝒳)=Φ(·)-(1/2)c∥·∥𝒳2. Indeed, the latter property means that, for all h,g∈X and all λ∈[0,1], one has(3.8)Φ(λh+(1-λ)g)-12c‖λh+(1-λ)g‖X2≤λΦ(h)-λ2c‖h‖X2+(1-λ)Φ(g)-1-λ2c‖g‖X2,
and this is equivalent to(3.9)Φ(λh+(1-λ)g)≤λΦ(h)+(1-λ)Φ(g)-λ(1-λ)2c‖h-g‖X2,
since one can show through straightforward computations that, for 𝒳 a Hilbert space, one has(3.10)12c‖λh+(1-λ)g‖X2-λ2c‖h‖X2-1-λ2c‖g‖X2=-λ(1-λ)2c‖h-g‖X2.One of the most useful properties of uniform convexity is thatf∘∈argminf∈XΦ(f) implies the lower bound(3.11)|Φ(f∘)-Φ(f)|≥δ(‖f∘-f‖X)
for any f∈X (see, e.g., [5, Proposition  2.1(iii)]). When the modulus of convexity has the form (3.7), this implies (together with (3.5))(3.12)‖f∘-f̃n‖X≤2γnc⟶0asn⟶+∞.
When (3.2) holds, too, and Φ has modulus of continuity αf∘ at f∘, one can take(3.13)γn=αf∘(ɛn)
in (3.12), thus obtaining(3.14)‖f∘-f̃n‖X≤2αf∘(ɛn)c⟶0asn⟶+∞.
Again, this allows one to extend rates of function approximation to functional optimization, supposing, as in Section 3.1, that Φ is also Lipschitz continuous with Lipschitz constant KΦ and that ɛn=O(n-1/2). Then, one obtains (from the choice (3.13) for γn and formula (3.14))(3.15)|Φ(f∘)-Φ(f̃n)|=O(n-1/2),(3.16)‖f∘-f̃n‖X=O(n-1/4).Remark 3.1.
In [29], a greedy algorithm is proposed to construct a sequence of sets Xn corresponding to variable-basis schemes and functions f̃n∈Xn that achieve the rate (3.15) for certain uniformly convex functional optimization problems. Such an algorithm can be interpreted as an extension to functional optimization of the greedy algorithm proposed in [12] for function approximation by sigmoidal neural networks.
Finally, it should be noted that the rate (3.15) is achieved in general by imposing some structure on the sets X and Xn. For instance, the set X in [29] is the convex hull of some set of functions G⊂𝒳, that is,(3.17)X=co⁡G:={∑j=1kαjgj:αj≥0,∑j=1kαj=1,gj∈G,k∈Z+},
whereas, for each n∈ℤ+, the set Xn in [29] is
(3.18)Xn=co⁡nG:={∑j=1nαjgj:αj≥0,∑j=1nαj=1,gj∈G}.
Functional optimization problems have in general a natural domain X larger than coG (or its closure co¯G in the norm of the ambient space 𝒳). Therefore, the choice of a set X of the form (3.17) as the domain of the functional Φ might seem unmotivated. This is not the case, because there are several examples of functional optimization problems for which, for suitable sets G and a natural domain X larger than coG (resp., co¯G), the set
(3.19)argminf∈XΦ(f)
has a nonempty intersection with coG (resp., co¯G), or it is contained in it. This issue is studied in [20] for dynamic optimization problems and in [19] for static team optimization ones, where structural properties (e.g., smoothness) of the minimizers are studied.


### 3.3. Comparison between Fixed- and Variable-Basis Schemes for Functional Optimization

The proposition follows by combining the results derived in Sections2.1, 3.1, and 3.2.Proposition 3.2.
Let the functionalΦ be Lipschitz continuous with Lipschitz constant KΦ and uniformly convex with modulus of convexity of the form (3.7), X=ΓB,C, μ any probability measure on B, 𝒳=ℒ2(B,μ), and suppose that there exists a minimizer f∘∈argminf∈ΓB,CΦ(f). Then the following hold.(i)
For everyn≥1 there exists fn of the form (2.4) such that
(3.20)‖f∘-fn‖L2≤2Cn.
For each such fn one has
(3.21)|Φ(f∘)-Φ(fn)|≤KΦ2Cn
and if f̃n of the form (2.4) is such that
(3.22)|Φ(f∘)-Φ(f̃n)|≤KΦ2Cn,
then
(3.23)‖f∘-f̃n‖L2≤2KΦCc1n4.(ii)
ForB=[0,1]d, μu equal to the uniform probability measure on [0,1]d, every n≥1, and every choice of fixed-basis functions h1,…,hn∈ℒ2([0,1]d,μu), there exists a uniformly convex functional Φ¯ (such a functional Φ¯ can be also chosen to be Lipschitz continuous with Lipschitz constant KΦ¯, but this is not needed in the inequalities (3.24)–(3.29), since they do not contain KΦ¯) with modulus of convexity of the form (3.7) and minimizer f¯∘∈argminf∈Γ[0,1]d,CΦ¯(f) such that for every 0<χ<1 one has
(3.24)inf⁡fn∈span⁡{h1,h2,…,hn}‖f¯∘-fn‖L2≥χC16πeπ-1d(12n)1/d,(3.25)inf⁡fn∈span⁡{h1,h2,…,hn}|Φ¯(f¯∘)-Φ¯(fn)|≥12c(χC16πeπ-1d)2(12n)2/d.(iii)
The statements (i) and (ii) still hold by replacing the setΓB,C by Γ[0,1]d,d′,C, for d a multiple of d′. The only difference is that the estimates (3.24) and (3.25) are replaced, respectively, by
(3.26)inf⁡fn∈span⁡{h1,h2,…,hn}‖f¯∘-fn‖L2≥χC8π,(3.27)inf⁡fn∈span⁡{h1,h2,…,hn}|Φ¯(f¯∘)-Φ¯(fn)|≥12c(χC8π)2
for n≤(d+1)/2 and by
(3.28)inf⁡fn∈span⁡{h1,h2,…,hn}‖f¯∘-fn‖L2≥χ(dd′)1/d′C16πeπ-1d′(12n)1/d′,(3.29)inf⁡fn∈span⁡{h1,h2,…,hn}|Φ¯(f¯∘)-Φ¯(fn)|≥12c(dd′)2/d′(χC16πeπ-1d′)2(12n)2/d′
for n>(d+1)/2.Proof.
(i) The estimate (3.20) follows by Theorem 2.1. The bound (3.21) follows by (3.20), the definition of modulus of continuity, and the assumption of Lipschitz continuity of Φ. Finally, (3.23) is obtained by property (3.11) of the modulus of convexity and its expression (3.7).
(ii) (3.24) comes from Theorem 2.2: the constant χ is introduced in order to remove the supremum with respect to f∈Γ[0,1]d,C in formula (2.7) and replace it with the choice f=f¯∘, where f¯∘ is any function that achieves the bound (2.7) up to the constant factor χ; (3.25) follows from (3.24), (3.11), and (3.7), choosing as Φ¯ any functional that is uniformly convex with modulus of convexity of the form (3.7), and such that f¯∘∈argminf∈Γ[0,1]d,CΦ¯(f).
(iii) The estimates (3.20), (3.21), (3.23) still hold when the set ΓB,C is replaced by Γ[0,1]d,d′,C since Γ[0,1]d,d′,C⊂ΓB,C for B=[0,1]d, whereas formulas (3.26)–(3.29) are obtained likewise formulas (3.24) and (3.25), by applying Proposition 2.4 instead of Theorem 2.2.


## 3.1. Rates of Approximate Optimization in Terms of the Modulus of Continuity

Let𝒳 be a normed linear space, X⊆𝒳, and Φ:X→ℝ a functional. Suppose that the functional optimization problem(3.1)min⁡f∈XΦ(f)
has a solution f∘, and let X1⊆X2⊆⋯⊆Xn⊆⋯⊆X be a nested sequence of subsets of X such that(3.2)inf⁡fn∈Xn‖f∘-fn‖X≤ɛn
for some ɛn>0, where ɛn→0 as n→+∞. Then, if the functional Φ is continuous, too, one has(3.3)inf⁡fn∈Xn|Φ(f∘)-Φ(fn)|≤αf∘(ɛn)⟶0asn⟶+∞,
where αf∘:[0,+∞)→[0,+∞) defined by αf∘(t)=sup{|Φ(f∘)-Φ(g)|:g∈X,∥f-g∥𝒳≤t} is the modulus of continuity of Φ at f∘. For instance, if Φ is Lipschitz continuous with Lipschitz constant KΦ, one has αf∘(t)≤KΦt, and by(3.2)(3.4)inf⁡fn∈Xn|Φ(f∘)-Φ(fn)|≤KΦɛn.
Then, if an upper bound on ɛn in terms of n is known (e.g., ɛn=O(n-1/2) under the assumptions of Theorem 2.1, where X=ΓB,C⊂ℒ2(B,μ)=𝒳 and Xn is the set of functions of the form (2.4)), then the same upper bound (up to a multiplicative constant) holds on inffn∈Xn|Φ(f∘)-Φ(fn)|. So, investigating the approximating capabilities of the sets Xn is useful for functional optimization purposes, too.


## 3.2. Rates of Approximate Optimization in Terms of the Modulus of Convexity

When dealing with suboptimal solutions from a setXn⊆X, the following question arises: suppose that f̃n∈Xn is such that(3.5)|Φ(f∘)-Φ(f̃n)|≤γn
for some γn>0, where γn→0 as n→+∞. This can be guaranteed, for example, if the functional is continuous, the sets Xn satisfy the property (3.2), and one chooses f̃n∈argminfn∈Xn∥f∘-fn∥𝒳 assuming, almost without loss of generality, that such a set is nonempty. If this is not the case, then one can proceed as follows. For ϵ>0, let argminϵ,fn∈Xn∥f-fn∥𝒳:={fn∈Xn:∥f∘-fn∥𝒳≤inffn∈Xn∥f∘-fn∥𝒳+ϵ}. Then one obtains estimates similar to the ones of this section (obtained assuming that argminfn∈Xn∥f∘-fn∥𝒳 is nonempty) by choosing f̃n∈argminηɛn,fn∈Xn∥f∘-fn∥𝒳, where η>1 is a constant. Does the estimate (3.5) imply an upper bound on the approximation error ∥f∘-f̃n∥𝒳? A positive answer can be given when the functional Φ is uniformly convex. Recall that a functional Φ:X→ℝ is called convex on a convex set X⊆𝒳 if and only if for all h,g∈X and all λ∈[0,1], one has Φ(λh+(1-λ)g)≤λΦ(h)+(1-λ)Φ(g) and it is called uniformly convex if and only if there exists a nonnegative function δ:[0,+∞)→[0,+∞) such that δ(0)=0, δ(t)>0 for all t>0, and for all h,g∈X and all λ∈[0,1], one has(3.6)Φ(λh+(1-λ)g)≤λΦ(h)+(1-λ)Φ(g)-λ(1-λ)δ(‖h-g‖X).
Any such function δ is called a modulus of convexity of Φ [26]. The terminology is not unified: some authors use the term “strictly uniformly convex” instead of “uniformly convex” and reserve the term “uniformly convex” for the case where δ:[0,+∞)→[0,+∞) merely satisfies δ(0)=0 and δ(t0)>0 for some t0>0 (see, e.g., [27, 28]). Note that when 𝒳 is a Hilbert space and δ(t) has the quadratic expression(3.7)δ(t)=12ct2
for some constant c>0, the condition (3.6) is equivalent to the convexity of the functional Φ(·)-δ(∥·∥𝒳)=Φ(·)-(1/2)c∥·∥𝒳2. Indeed, the latter property means that, for all h,g∈X and all λ∈[0,1], one has(3.8)Φ(λh+(1-λ)g)-12c‖λh+(1-λ)g‖X2≤λΦ(h)-λ2c‖h‖X2+(1-λ)Φ(g)-1-λ2c‖g‖X2,
and this is equivalent to(3.9)Φ(λh+(1-λ)g)≤λΦ(h)+(1-λ)Φ(g)-λ(1-λ)2c‖h-g‖X2,
since one can show through straightforward computations that, for 𝒳 a Hilbert space, one has(3.10)12c‖λh+(1-λ)g‖X2-λ2c‖h‖X2-1-λ2c‖g‖X2=-λ(1-λ)2c‖h-g‖X2.One of the most useful properties of uniform convexity is thatf∘∈argminf∈XΦ(f) implies the lower bound(3.11)|Φ(f∘)-Φ(f)|≥δ(‖f∘-f‖X)
for any f∈X (see, e.g., [5, Proposition  2.1(iii)]). When the modulus of convexity has the form (3.7), this implies (together with (3.5))(3.12)‖f∘-f̃n‖X≤2γnc⟶0asn⟶+∞.
When (3.2) holds, too, and Φ has modulus of continuity αf∘ at f∘, one can take(3.13)γn=αf∘(ɛn)
in (3.12), thus obtaining(3.14)‖f∘-f̃n‖X≤2αf∘(ɛn)c⟶0asn⟶+∞.
Again, this allows one to extend rates of function approximation to functional optimization, supposing, as in Section 3.1, that Φ is also Lipschitz continuous with Lipschitz constant KΦ and that ɛn=O(n-1/2). Then, one obtains (from the choice (3.13) for γn and formula (3.14))(3.15)|Φ(f∘)-Φ(f̃n)|=O(n-1/2),(3.16)‖f∘-f̃n‖X=O(n-1/4).Remark 3.1.
In [29], a greedy algorithm is proposed to construct a sequence of sets Xn corresponding to variable-basis schemes and functions f̃n∈Xn that achieve the rate (3.15) for certain uniformly convex functional optimization problems. Such an algorithm can be interpreted as an extension to functional optimization of the greedy algorithm proposed in [12] for function approximation by sigmoidal neural networks.
Finally, it should be noted that the rate (3.15) is achieved in general by imposing some structure on the sets X and Xn. For instance, the set X in [29] is the convex hull of some set of functions G⊂𝒳, that is,(3.17)X=co⁡G:={∑j=1kαjgj:αj≥0,∑j=1kαj=1,gj∈G,k∈Z+},
whereas, for each n∈ℤ+, the set Xn in [29] is
(3.18)Xn=co⁡nG:={∑j=1nαjgj:αj≥0,∑j=1nαj=1,gj∈G}.
Functional optimization problems have in general a natural domain X larger than coG (or its closure co¯G in the norm of the ambient space 𝒳). Therefore, the choice of a set X of the form (3.17) as the domain of the functional Φ might seem unmotivated. This is not the case, because there are several examples of functional optimization problems for which, for suitable sets G and a natural domain X larger than coG (resp., co¯G), the set
(3.19)argminf∈XΦ(f)
has a nonempty intersection with coG (resp., co¯G), or it is contained in it. This issue is studied in [20] for dynamic optimization problems and in [19] for static team optimization ones, where structural properties (e.g., smoothness) of the minimizers are studied.


## 3.3. Comparison between Fixed- and Variable-Basis Schemes for Functional Optimization

The proposition follows by combining the results derived in Sections2.1, 3.1, and 3.2.Proposition 3.2.
Let the functionalΦ be Lipschitz continuous with Lipschitz constant KΦ and uniformly convex with modulus of convexity of the form (3.7), X=ΓB,C, μ any probability measure on B, 𝒳=ℒ2(B,μ), and suppose that there exists a minimizer f∘∈argminf∈ΓB,CΦ(f). Then the following hold.(i)
For everyn≥1 there exists fn of the form (2.4) such that
(3.20)‖f∘-fn‖L2≤2Cn.
For each such fn one has
(3.21)|Φ(f∘)-Φ(fn)|≤KΦ2Cn
and if f̃n of the form (2.4) is such that
(3.22)|Φ(f∘)-Φ(f̃n)|≤KΦ2Cn,
then
(3.23)‖f∘-f̃n‖L2≤2KΦCc1n4.(ii)
ForB=[0,1]d, μu equal to the uniform probability measure on [0,1]d, every n≥1, and every choice of fixed-basis functions h1,…,hn∈ℒ2([0,1]d,μu), there exists a uniformly convex functional Φ¯ (such a functional Φ¯ can be also chosen to be Lipschitz continuous with Lipschitz constant KΦ¯, but this is not needed in the inequalities (3.24)–(3.29), since they do not contain KΦ¯) with modulus of convexity of the form (3.7) and minimizer f¯∘∈argminf∈Γ[0,1]d,CΦ¯(f) such that for every 0<χ<1 one has
(3.24)inf⁡fn∈span⁡{h1,h2,…,hn}‖f¯∘-fn‖L2≥χC16πeπ-1d(12n)1/d,(3.25)inf⁡fn∈span⁡{h1,h2,…,hn}|Φ¯(f¯∘)-Φ¯(fn)|≥12c(χC16πeπ-1d)2(12n)2/d.(iii)
The statements (i) and (ii) still hold by replacing the setΓB,C by Γ[0,1]d,d′,C, for d a multiple of d′. The only difference is that the estimates (3.24) and (3.25) are replaced, respectively, by
(3.26)inf⁡fn∈span⁡{h1,h2,…,hn}‖f¯∘-fn‖L2≥χC8π,(3.27)inf⁡fn∈span⁡{h1,h2,…,hn}|Φ¯(f¯∘)-Φ¯(fn)|≥12c(χC8π)2
for n≤(d+1)/2 and by
(3.28)inf⁡fn∈span⁡{h1,h2,…,hn}‖f¯∘-fn‖L2≥χ(dd′)1/d′C16πeπ-1d′(12n)1/d′,(3.29)inf⁡fn∈span⁡{h1,h2,…,hn}|Φ¯(f¯∘)-Φ¯(fn)|≥12c(dd′)2/d′(χC16πeπ-1d′)2(12n)2/d′
for n>(d+1)/2.Proof.
(i) The estimate (3.20) follows by Theorem 2.1. The bound (3.21) follows by (3.20), the definition of modulus of continuity, and the assumption of Lipschitz continuity of Φ. Finally, (3.23) is obtained by property (3.11) of the modulus of convexity and its expression (3.7).
(ii) (3.24) comes from Theorem 2.2: the constant χ is introduced in order to remove the supremum with respect to f∈Γ[0,1]d,C in formula (2.7) and replace it with the choice f=f¯∘, where f¯∘ is any function that achieves the bound (2.7) up to the constant factor χ; (3.25) follows from (3.24), (3.11), and (3.7), choosing as Φ¯ any functional that is uniformly convex with modulus of convexity of the form (3.7), and such that f¯∘∈argminf∈Γ[0,1]d,CΦ¯(f).
(iii) The estimates (3.20), (3.21), (3.23) still hold when the set ΓB,C is replaced by Γ[0,1]d,d′,C since Γ[0,1]d,d′,C⊂ΓB,C for B=[0,1]d, whereas formulas (3.26)–(3.29) are obtained likewise formulas (3.24) and (3.25), by applying Proposition 2.4 instead of Theorem 2.2.


## 4. Discussion

Classes of function-approximation and functional optimization problems have been investigated for which, for a given desired error, certain variable-basis approximation schemes with sigmoidal computational units require less parameters than fixed-basis ones. Previously known bounds on the accuracy have been extended, with better rates, to families of functions whose effective number of variablesd′ is much smaller than the number of their arguments d.Proposition3.2 shows that there is a strict connection between certain problems of function approximation and functional optimization. For such two classes of problems, indeed, the approximation error rates for the first class can be converted into rates of approximate optimization for the second one and vice versa. In particular, for d>2, X=Γ[0,1]d,C, and any linear approximation scheme span{h1,h2,…,hn}, the estimates (3.21) and (3.25) show families of functional optimization problems for which the error in approximate optimization with variable-basis schemes of sigmoidal type is smaller than the one associated with the linear scheme. For d′>2 and X=Γ[0,1]d,d′,C, a similar remark can be made for the estimates (3.21) and (3.27) and for the bounds (3.21) and (3.29). Finally, the bound (3.23) shows that for large n any approximate minimizer f̃n of the form (2.4) differs slightly from the true minimizer f∘, even though the error in approximate optimization (3.22) and the associated approximation error (3.23) have different rates. In contrast, the estimates (3.24), (3.26), and (3.28) show that, for any linear approximation scheme span{h1,h2,…,hn}, there exists a functional optimization problem whose minimizer f¯∘ cannot be approximated with the same accuracy by the linear scheme.The results presented in the paper provide some theoretical justification for the use of variable-basis approximation schemes (instead of fixed-basis ones) in function approximation and functional optimization.



---

*Source: 806945-2012-01-12.xml*