Wyniki wyszukiwania

1

Optimal estimators in learning theory

100%

Temlyakov V.

Banach Center Publications

|

2006

|

tom 72

|

nr 1

341-366

EN

This paper is a survey of recent results on some problems of supervised learning in the setting formulated by Cucker and Smale. Supervised learning, or learning-from-examples, refers to a process that builds on the base of available data of inputs $x_i$ and outputs $y_i$, i = 1,...,m, a function that best represents the relation between the inputs x ∈ X and the corresponding outputs y ∈ Y. The goal is to find an estimator $f_{z}$ on the base of given data $z: = ((x₁,y₁),...,(x_m,y_m))$ that approximates well the regression function $f_ρ$ of an unknown Borel probability measure ρ defined on Z = X × Y. We assume that $(x_i,y_i)$, i = 1,...,m, are indepent and distributed according to ρ. We discuss a problem of finding optimal (in the sense of order) estimators for different classes Θ (we assume $f_ρ ∈ Θ$). It is known from the previous works that the behavior of the entropy numbers ϵₙ(Θ,B) of Θ in a Banach space B plays an important role in the above problem. The standard way of measuring the error between a target function $f_ρ$ and an estimator $f_{z}$ is to use the $L₂(ρ_X)$ norm ($ρ_X$ is the marginal probability measure on X generated by ρ). The usual way in regression theory to evaluate the performance of the estimator $f_{z}$ is by studying its convergence in expectation, i.e. the rate of decay of the quantity $E(||f_{ρ} - f_{z}||²_{L₂(ρ_X)})$ as the sample size m increases. Here the expectation is taken with respect to the product measure $ρ^m$ defined on $Z^m$. A more accurate and more delicate way of evaluating the performance of $f_{z}$ has been pushed forward in [CS]. In [CS] the authors study the probability distribution function $ρ^m{z: ||f_{ρ} - f_{z}||_{L₂(ρ_X)} ≥ η}$ instead of the expectation $E(||f_{ρ} - f_{z}||²_{L₂(ρ_X)})$. In this survey we mainly discuss the optimization problem formulated in terms of the probability distribution function.

2

Convergence of greedy approximation II. The trigonometric system

64%

Konyagin S., Temlyakov V.

Studia Mathematica

|

2003

|

tom 159

|

nr 2

161-184

EN

We study the following nonlinear method of approximation by trigonometric polynomials. For a periodic function f we take as an approximant a trigonometric polynomial of the form $Gₘ(f) : = ∑_{k∈Λ} f̂(k)e^{i(k,x)}$, where $Λ ⊂ ℤ^{d}$ is a set of cardinality m containing the indices of the m largest (in absolute value) Fourier coefficients f̂(k) of the function f. Note that Gₘ(f) gives the best m-term approximant in the L₂-norm, and therefore, for each f ∈ L₂, ||f-Gₘ(f)||₂ → 0 as m → ∞. It is known from previous results that in the case of p ≠ 2 the condition $f ∈ L_{p}$ does not guarantee the convergence $||f - Gₘ(f)||_{p} → 0$ as m → ∞. We study the following question. What conditions (in addition to $f ∈ L_{p}$) provide the convergence $||f - Gₘ(f)||_{p} → 0$ as m → ∞? In the case 2 < p ≤ ∞ we find necessary and sufficient conditions on a decreasing sequence ${Aₙ}_{n=1}^{∞}$ to guarantee the $L_{p}$-convergence of {Gₘ(f)} for all $f ∈ L_{p}$ satisfying aₙ(f) ≤ Aₙ, where {aₙ(f)} is the decreasing rearrangement of the absolute values of the Fourier coefficients of f.

3

Greedy approximation and the multivariate Haar system

64%

Kamont A., Temlyakov V.

Studia Mathematica

|

2004

|

tom 161

|

nr 3

199-223

EN

We study nonlinear m-term approximation in a Banach space with regard to a basis. It is known that in the case of a greedy basis (like the Haar basis 𝓗 in $L_{p}([0,1])$, 1 < p < ∞) a greedy type algorithm realizes nearly best m-term approximation for any individual function. In this paper we generalize this result in two directions. First, instead of a greedy algorithm we consider a weak greedy algorithm. Second, we study in detail unconditional nongreedy bases (like the multivariate Haar basis $𝓗^{d} = 𝓗 × ... × 𝓗$ in $L_{p}([0,1]^{d})$, 1 < p < ∞, p ≠ 2). We prove some convergence results and also some results on convergence rate of weak type greedy algorithms. Our results are expressed in terms of properties of the basis with respect to a given weakness sequence.

4

Convergence of greedy approximation I. General systems

64%

Konyagin S., Temlyakov V.

Studia Mathematica

|

2003

|

tom 159

|

nr 1

143-160

EN

We consider convergence of thresholding type approximations with regard to general complete minimal systems {eₙ} in a quasi-Banach space X. Thresholding approximations are defined as follows. Let {eₙ*} ⊂ X* be the conjugate (dual) system to {eₙ}; then define for ε > 0 and x ∈ X the thresholding approximations as $T_{ε}(x) : = ∑_{j∈D_{ε}(x)} e*_{j}(x)e_{j}$, where $D_{ε}(x): = {j: |e*_{j}(x)| ≥ ε}$. We study a generalized version of $T_{ε}$ that we call the weak thresholding approximation. We modify the $T_{ε}(x)$ in the following way. For ε > 0, t ∈ (0,1) we set $D_{t,ε}(x) : = {j: tε ≤ |e*_{j}(x)| < ε}$ and consider the weak thresholding approximations $T_{ε,D}(x) : = T_{ε}(x) + ∑_{j∈D} e*_{j}(x)e_{j}$, $D ⊆ D_{t,ε}(x)$. We say that the weak thresholding approximations converge to x if $T_{ε,D(ε)}(x) → x$ as ε → 0 for any choice of $D(ε) ⊆ D_{t,ε}(x)$. We prove that the convergence set WT{eₙ} does not depend on the parameter t ∈ (0,1) and that it is a linear set. We present some applications of general results on convergence of thresholding approximations to A-convergence of both number series and trigonometric series.

5

Quasi-greedy bases and Lebesgue-type inequalities

51%

Dilworth S., Soto-Bajo M., Temlyakov V.

Studia Mathematica

|

2012

|

tom 211

|

nr 1

41-69

EN

We study Lebesgue-type inequalities for greedy approximation with respect to quasi-greedy bases. We mostly concentrate on the $L_{p}$ spaces. The novelty of the paper is in obtaining better Lebesgue-type inequalities under extra assumptions on a quasi-greedy basis than known Lebesgue-type inequalities for quasi-greedy bases. We consider uniformly bounded quasi-greedy bases of $L_{p}$, 1 < p < ∞, and prove that for such bases an extra multiplier in the Lebesgue-type inequality can be taken as C(p)ln(m+1). The known magnitude of the corresponding multiplier for general (no assumption of uniform boundedness) quasi-greedy bases is of order $m^{|1/2-1/p|}$, p ≠ 2. For uniformly bounded orthonormal quasi-greedy bases we get further improvements replacing ln(m+1) by $(ln(m+1))^{1/2}$.

Ograniczanie wyników

4 Studia Mathematica

1 Banach Center Publications

5 Temlyakov V.

2 Konyagin S.

1 Dilworth S.

1 Kamont A.

1 Soto-Bajo M.

1 2012

1 2006

1 2004

2 2003

Optimal estimators in learning theory

Convergence of greedy approximation II. The trigonometric system

Greedy approximation and the multivariate Haar system

Convergence of greedy approximation I. General systems

Quasi-greedy bases and Lebesgue-type inequalities