Approximation in Learning Theory

This paper addresses 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_ρ (or its projection) of an unknown Borel probability measure ρ defined on Z = X × Y. We assume that (x_i,y_i), i = 1,...,m, are independent and distributed according to ρ. We discuss the following two problems: I. the projection learning problem (improper function learning problem); II. universal (adaptive) estimators in the proper function learning problem. In the first problem we do not impose any restrictions on a Borel measure ρ except our standard assumption that |y|≤ M a.e. with respect to ρ. In this case we use the data z to estimate (approximate) the L₂(ρ_X) projection (f_ρ)_W of f_ρ onto a function class W of our choice. Here, ρ_X is the marginal probability measure. In [KT1,2] this problem has been studied for W satisfying the decay condition ε_n(W,B) ≤ Dn^-r of the entropy numbers ε_n(W,B) of W in a Banach space B in the case B = C(X) or B = L₂(\rho_X). In this paper we obtain the upper estimates in the case ε_n(W,L₁(ρ_X)) ≤ Dn^-r with an extra assumption that W is convex. In the second problem we assume that an unknown measure ρ satisfies some conditions. Following the standard way from nonparametric statistics we formulate these conditions of the form f_ρ ∈ Θ. Next, we assume that the only a priori information available is that f_ρ belongs to a class Θ (unknown) from a known collection {Θ} of classes. We want to build an estimator that provides approximation of f_ρ close to the optimal for the class Θ. Along with standard penalized least squares estimators we consider a new method of construction of universal estimators. This method is based on a combination of two powerful ideas in building universal estimators. The first one is the use of penalized least squares estimators. This idea works well in the case of general setting with rather abstract methods of approximation. The second one is the idea of thresholding that works very well when we use wavelets expansions as an approximation tool. A new estimator that we call the big jump estimator uses the least squares estimators and chooses a right model by a thresholding criteria instead of the penalization. In this paper we illustrate how ideas and methods of approximation theory can be used in learning theory both in formulating a problem and in solving it.     

On saturation effects in the Neumann boundary control of elliptic optimal control problems

A Neumann boundary control problem for a linear-quadratic elliptic optimal control problem in a polygonal domain is investigated. The main goal is to show an optimal approximation order for discretized problems after a postprocessing process. It turns out that two saturation processes occur: The regularity of the boundary data of the adjoint is limited if the largest angle of the polygon is at least 2π/3. Moreover, piecewise linear finite elements cannot guarantee the optimal order, if the largest angle of the polygon is greater than π/2. We will derive error estimates of order h ^α with α∈[1,2] depending on the largest angle and properties of the finite elements. Finally, numerical test illustrates the theoretical results.     

On the bestm-term trigonometric and orthogonal trigonometric approximations of functions from the classesL Ψ β,ρ

We obtain estimates exact in order for the best trigonometric and orthogonal trigonometric approximations of the classesL _Ψ^β,ρ of functions of one variable in the spaceL _q in the case 2<p <q < ∞.     

Convex polynomial and spline approximation inL p,O<p<∞

We prove that a convex functionf ∈ L _p[−1, 1], 0<p<∞, can be approximated by convex polynomials with an error not exceeding Cω ₃ ^ϕ (f,1/n)_p where ω ₃ ^ϕ (f,·) is the Ditzian-Totik modulus of smoothness of order three off. We are thus filling the gap between previously known estimates involving ω ₃ ^ϕ (f,1/n)_p, and the impossibility of having such estimates involving ω₄. We also give similar estimates for the approximation off by convexC ⁰ andC ¹ piecewise quadratics as well as convexC ² piecewise cubic polynomials. Communicated by Dietrich Braess     

Approximation Methods for Supervised Learning

Let ρ be an unknown Borel measure defined on the space Z := X × Y with X ⊂ ℝ^d and Y = [-M,M]. Given a set z of m samples z_i =(x_i,y_i) drawn according to ρ, the problem of estimating a regression function f_ρ using these samples is considered. The main focus is to understand what is the rate of approximation, measured either in expectation or probability, that can be obtained under a given prior f_ρ ∈ Θ, i.e., under the assumption that f_ρ is in the set Θ, and what are possible algorithms for obtaining optimal or semioptimal (up to logarithms) results. The optimal rate of decay in terms of m is established for many priors given either in terms of smoothness of f_ρ or its rate of approximation measured in one of several ways. This optimal rate is determined by two types of results. Upper bounds are established using various tools in approximation such as entropy, widths, and linear and nonlinear approximation. Lower bounds are proved using Kullback-Leibler information together with Fano inequalities and a certain type of entropy. A distinction is drawn between algorithms which employ knowledge of the prior in the construction of the estimator and those that do not. Algorithms of the second type which are universally optimal for a certain range of priors are given.     

On the embedding problem with non-Abelian kernel of orderp 4. IV

In the present paper, the embedding problem is considered for number fields with p-groups whose kernel is either of two groups with two generators α and β and with the following relations: (1) α^ρ=1, α^ρ=1, [α,β,β]=1, [α,β,α,α]=1, or (2) α^ρ=[α, β α], β^ρ=1, [α,β,β]=1. It is shown that for the solvability of the original embedding problem it is necessary and sufficient to have the solvability of the associated Abelian and local problems for all completions of the base fields. Bibliography: 7 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 211, 1994, pp. 120–126. Translated by V. V. Ishkhanov.     

Error estimates for the numerical approximation of Neumann control problems

We continue the discussion of error estimates for the numerical analysis of Neumann boundary control problems we started in Casas et al. (Comput. Optim. Appl. 31:193–219, 2005). In that paper piecewise constant functions were used to approximate the control and a convergence of order O(h) was obtained. Here, we use continuous piecewise linear functions to discretize the control and obtain the rates of convergence in L ²(Γ). Error estimates in the uniform norm are also obtained. We also discuss the approach suggested by Hinze (Comput. Optim. Appl. 30:45–61, 2005) as well as the improvement of the error estimates by making an extra assumption over the set of points corresponding to the active control constraints. Finally, numerical evidence of our estimates is provided. The authors were supported by Ministerio de Ciencia y Tecnología (Spain).     

Triangular finite elements of HCT type and classC ρ

Let τ be some triangulation of a planar polygonal domain Ω. Given a smooth functionu, we construct piecewise polynomial functionsv∈C ^ρ(Ω) of degreen=3 ρ for ρ odd, andn=3ρ+1 for ρ even on a subtriangulation τ₃ of τ. The latter is obtained by subdividing eachT∈ρ into three triangles, andv/T is a composite triangular finite element, generalizing the classicalC ¹ cubic Hsieh-Clough-Tocher (HCT) triangular scheme. The functionv interpolates the derivatives ofu up to order ρ at the vertices of τ. Polynomial degrees obtained in this way are minimal in the family of interpolation schemes based on finite elements of this type.     

High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension

Let A be a d by n matrix, d < n. Let C be the regular cross polytope (octahedron) in Rⁿ. It has recently been shown that properties of the centrosymmetric polytope P = AC are of interest for finding sparse solutions to the underdetermined system of equations y = Ax [9]. In particular, it is valuable to know that P is centrally k-neighborly. We study the face numbers of randomly projected cross polytopes in the proportional-dimensional case where d ∼ δn, where the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of Rⁿ. We derive ρ_N(δ) > 0 with the property that, for any ρ < ρ_N(δ), with overwhelming probability for large d, the number of k-dimensional faces of P = AC is the same as for C, for 0 ≤ k ≤ ρd. This implies that P is centrally ⌊ ρ d ⌋-neighborly, and its skeleton Skel_{⌊ ρ d ⌋}(P) is combinatorially equivalent to Skel_{⌊ ρ d⌋}(C). We display graphs of ρ_N. Two weaker notions of neighborliness are also important for understanding sparse solutions of linear equations: weak neighborliness and sectional neighborliness [9]; we study both. Weak (k,ε)-neighborliness asks if the k-faces are all simplicial and if the number of k-dimensional faces f_k(P) ≥ f_k(C)(1 – ε). We characterize and compute the critical proportion ρ_W(δ) > 0 such that weak (k,ε) neighborliness holds at k significantly smaller than ρ_W · d and fails for k significantly larger than ρ_W · d. Sectional (k,ε)-neighborliness asks whether all, except for a small fraction ε, of the k-dimensional intrinsic sections of P are k-dimensional cross polytopes. (Intrinsic sections intersect P with k-dimensional subspaces spanned by vertices of P.) We characterize and compute a proportion ρ_S(δ) > 0 guaranteeing this property for k/d ∼ ρ < ρ_S(δ). We display graphs of ρ_S and ρ_W.     

Distribution functions of binary solutions (exact analytic solution)

We show that the general solution of the Ornstein-Zernike system of equations for multicomponent solutions has the form h_αβ=∑A _αβ ^j exp(-λ_jr)/r, where λ_j are the roots of the transcendental equation 1-ρΔ(λ_j)=0 and the amplitudes A_αβ ^j can be calculated if the direct correlation functions are given. We investigate the properties of this solution including the behavior of the roots A _αβ ^j and amplitudes A_αβ ^j in both the low-density limit and the vicinity of the critical point. Several relations on A_αβ ^j and C_αβ are found. In the vicinity of the critical point, we find the state equation for a liquid, which confirms the Van der Waals similarity hypothesis. The expansion under consideration is asymptotic because we expand functions in series in eigenfunctions of the asymptotic Ornstein-Zernike equation valid at r→∞. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 123, No. 3, pp. 500–515, June, 2000.     

Error estimates and superconvergence of semidiscrete mixed methods for optimal control problems governed by hyperbolic equations

In this paper, we investigate the L ^??(L ₂)-error estimates and superconvergence of the semidiscrete mixed finite elementmethods for quadratic optimal control problems governed by linear hyperbolic equations. The state and the co-state are discretized by the order k Raviart-Thomas mixed finite element spaces and the control is approximated by piecewise polynomials of order k(k ?? 0). We derive error estimates for approximation of both state and control. Moreover, we present the superconvergence analysis for mixed finite element approximation of the optimal control problems.     

On approximation properties of Balázs-Szabados operators their Kantorovich extension

In this paper we deal with a sequence of positive linear operatorsR _n^[β] approximating functions on the unbounded interval [0, t8) which were firstly used by K. Balázs and J. Szabados. We give pointwise estimates in the framework of polynomial weighted function spaces. Also we establish a Voronovskaja type theorem in the same weighted spaces for K_n^[β] operators, representing the integral generalization in Kantorovich sense of the R_n^[β].     

Error estimates of mixed finite element methods for quadratic optimal control problems

In this paper, we investigate the error estimates for the solutions of optimal control problems by mixed finite element methods. The state and costate are approximated by Raviart-Thomas mixed finite element spaces of order k and the control is approximated by piecewise polynomials of order k. Under the special constraint set, we will show that the control variable can be smooth in the whole domain. We derive error estimates of optimal order both for the state variables and the control variable.     

The relative trace formula for groups with involution

A theorem of Bourgain states that the harmonic measure for a domain in ℝ ^d is supported on a set of Hausdorff dimension strictly less thand [2]. We apply Bourgain’s method to the discrete case, i.e., to the distribution of the first entrance point of a random walk into a subset of ℤ ^d ,d≥2. By refining the argument, we prove that for allβ>0 there existsρ(d,β)<d andN(d,β), such that for anyn>N(d,β), anyx ∈ ℤ ^d , and anyA ⊂ {1,…,n} ^d •{y∈ℤ whereν _A,x (y) denotes the probability thaty is the first entrance point of the simple random walk starting atx intoA. Furthermore,ρ must converge tod asβ → ∞. Supported by Swiss NF grant 20-55648.98.     

A finite volume method based on the Crouzeix–Raviart element for elliptic PDE's in two dimensions

We introduce and analyse a finite volume method for the discretization of elliptic boundary value problems in . The method is based on nonuniform triangulations with piecewise linear nonconforming spaces. We prove optimal order error estimates in the –norm and a mesh dependent –norm. Received September 10, 1997 / Revised version received March 18, 1998     

Superconvergence and a posteriori error estimates of RT1 mixed methods for elliptic control problems with an integral constraint

In this paper, we investigate the superconvergence property and a posteriori error estimates of mixed finite element methods for a linear elliptic control problem with an integral constraint. The state and co-state are approximated by the order k = 1 Raviart-Thomas mixed finite element spaces and the control variable is approximated by piecewise constant functions. Approximations of the optimal control of the continuous optimal control problem will be constructed by a projection of the discrete adjoint state. It is proved that these approximations have convergence order h ². Moreover, we derive a posteriori error estimates both for the control variable and the state variables. Finally, a numerical example is given to demonstrate the theoretical results.     

Small sample properties of the power function ofF tests in two-way error component regression

In this paper we investigate properties of the power function of the generalized least squaresF test for linear hypotheses under regression models with two-way error component model. The covariance structure of the model depends on the correlation coefficients ρ1 and ρ2 corresponding to the random effects. This model has been frequently applied to the analysis of panel data. In general, we show that the power is a monotonically increasing function of ρ1(ρ2) in a region which is close to the ρ1(ρ2) axis, and a monotonically decreasing function of ρ1(ρ2) in a region close to the ρ2(ρ1) axis. This research is supported by the National Natural Science Foundation of China, the Natural Science Foundation of Beijing, a project of Science and Technology of Beijing Education Committee, the Academy of Finland, and the University of Tampere.     

A nodal basis of Cμ-rational spline functions on triangulations

Let ρ be a triangulation of a polygonal domain D⊂R² with vertices V={v_i:l≤i≤N_v} and RS^k(D, ρ)={u∈C^k(D): ≠ T∈ρ, u/_T is a rational function}. The purpose of this paper is to study the existence and construction of C^μ-rational spline functions on any triangulation ρ for CAGD. The Hermite problem H^μ(V,U)={find u∈U: D^αu(v_i)=D^αf(v_i),|α|≤μ} is solved by the generalized wedge function method in rational spline function family, i.e. U=RS^μ. this solution needs only the knowledge of partial derivatives of order≤μ at v_i. The explicit repesentations of all C^μ-GWF(generalized wedge functions)and the interpolating operator with degree of precision at least 2μ+1 for any triangulation are given.     

Efficient algorithms for heavy-tail analysis under interval uncertainty

Most applications of statistics to science and engineering are based on the assumption that the corresponding random variables are normally distributed, i.e., distributed according to Gaussian law in which the probability density function ρ(x) exponentially decreases with x: ρ(x)∼exp (−k⋅x ²). Normal distributions indeed frequently occur in practice. However, there are also many practical situations, including situations from mathematical finance, in which we encounter heavy-tailed distributions, i.e., distributions in which ρ(x) decreases as ρ(x)∼x ^−α . To properly take this uncertainty into account when making decisions, it is necessary to estimate the parameters of such distributions based on the sample data x ₁,…,x _n —and thus, to predict the size and the probabilities of large deviations. The most well-known statistical estimates for such distributions are the Hill estimator H for α and the Weismann estimator W for the corresponding quantiles.     

A fully discrete numerical scheme for weighted mean curvature flow

Summary. We analyze a fully discrete numerical scheme approximating the evolution of n–dimensional graphs under anisotropic mean curvature. The highly nonlinear problem is discretized by piecewise linear finite elements in space and semi–implicitly in time. The scheme is unconditionally stable und we obtain optimal error estimates in natural norms. We also present numerical examples which confirm our theoretical results. Received October 2, 2000 / Published online July 25, 2001