Bounds on margin distributions in learning problems

Let be a probability space and let P_n be the empirical measure based on i.i.d. sample (X₁,…,X_n) from P. Let be a class of measurable real valued functions on For define F_f(t):=P{ft} and F_n,f(t):=P_n{ft}. Given γ(0,1], define _n,γ(δ):=1/(n^1−γ/2δ^γ). We show that if the L₂(P_n)-entropy of the class grows as ^−α for some α(0,2), then, for all and all δ(0,Δ_n), Δ_n=O(n^1/2),

and

where and c(σ)↓1 as σ↓0 (the above inequalities hold for any fixed σ(0,1] with a high probability). Also, define

Then for all

uniformly in and with probability 1 (for the above ratio is bounded away from 0 and from ∞). The results are motivated by recent developments in machine learning, where they are used to bound the generalization error of learning algorithms. We also prove some more general results of similar nature, show the sharpness of the conditions and discuss the applications in learning theory.     

Entropy numbers of Sobolev embeddings of radial Besov spaces

Let be the radial subspace of the Besov space . We prove the independence of the asymptotic behavior of the entropy numbers

from the difference s₀−s₁ as long as the embedding itself is compact. In fact, we shall show that

This is in a certain contrast to earlier results on entropy numbers in the context of Besov spaces B_p,q^s(Ω) on bounded domains Ω.     

Semilinear equations with exponential nonlinearity and measure data

We study the existence and non-existence of solutions of the problem

(0.1)

where Ω is a bounded domain in , N3, and μ is a Radon measure. We prove that if , then (0.1) has a unique solution. We also show that the constant 4π in this condition cannot be improved.     

Remark on a double-inequality for the Riemann zeta function

Let ζ be the Riemann zeta function and δ(x)=1/(2^x-1). For all x>0 we have

(1-δ(x))ζ(x)+αδ(x)<ζ(x+1)<(1-δ(x))ζ(x)+βδ(x),

with the best possible constant factors

This improves a recently published result of Cerone et al., J. Inequalities Pure Appl. Math. 5(2) (43) (2004), who showed that the double-inequality holds with and .     

Orthogonal Rational Functions and Nested Disks

In Akhiezer's book [“The Classical Moment Problem and Some Related Questions in Analysis,” Oliver & Boyd, Edinburghasol;London, 1965] the uniqueness of the solution of the Hamburger moment problem, if a solution exists, is related to a theory of nested disks in the complex plane. The purpose of the present paper is to develop a similar nested disk theory for a moment problem that arises in the study of certain orthogonal rational functions. Let {α_n}^∞_n=0be a sequence in the open unit disk in the complex plane, let

Full-size image

( /|α_k|=−1 whenα_k=0), and let

Full-size image

We consider the following “moment” problem: Given a positive-definite Hermitian inner product ·, · on × , find a non-decreasing functionμon [−π, π] (or a positive Borel measureμon [−π,π)) such that

Full-size image

In particular we give necessary and sufficient conditions for the uniqueness of the solution in the case that If this series diverges the solution is always unique.     

On an integral-type operator between bloch-type spaces

Let H(B) denote the space of all holomorphic functions on the unit ball B of . Let φ be a holomorphic self-map of B and gH(B), such that g(0)=0. We study the boundedness and compactness of the following integral-type operator recently introduced by Stević

between Bloch-type spaces. Our main results are natural extensions of some results in the following paper: S. Stević, On a new integral-type operator from the Bloch space to Bloch-type spaces on the unit ball, J. Math. Anal. Appl. 354 (2009) 426–434.     

Neighborhood Conditions for Fractional ID-<Emphasis Type="Italic">k</Emphasis>-factor-critical Graphs

Let G be a graph and k ≥ 2 a positive integer. Let h: E(G) → [0, 1] be a function. If \(\sum\limits_{e \mathrel\backepsilon x} {h(e) = k} \) holds for each x ∈ V (G), then we call G[F_h] a fractional k-factor of G with indicator function h where F_h = {e ∈ E(G): h(e) > 0}. A graph G is fractional independent-set-deletable k-factor-critical (in short, fractional ID-k-factor-critical), if G ? I has a fractional k-factor for every independent set I of G. In this paper, we prove that if n ≥ 9k ? 14 and for any subset X ? V (G) we have

$${N_G}(X) = V(G)if|X| \geqslant \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ;or|{N_G}(X)| \geqslant \frac{{3k - 1}}{k}|X|if|X| < \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ,$$

then G is fractional ID-k-factor-critical.

     

Tension spline collocation methods for singularly perturbed Volterra integro-differential and Volterra integral equations

We consider the numerical discretization of singularly perturbed Volterra integro-differential equations (VIDE)

(*)

and Volterra integral equations (VIE)

(**)

by tension spline collocation methods in certain tension spline spaces, where is a small parameter satisfying 0<1, and q₁, q₂, g and K are functions sufficiently smooth on their domains to ensure that Eqs. (*) and (**) posses a unique solution.We give an analysis of the global convergence properties of a new tension spline collocation solution for 0<1 for singularly perturbed VIDE and VIE; thus, extending the existing theory for =1 to the singularly perturbed case.     

Decomposable graphs and definitions with no quantifier alternation

Let D(G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D₀(G) be the version of D(G) where we do not allow quantifier alternations in Φ. Define q₀(n) to be the minimum of D₀(G) over all graphs G of order n.We prove that for all n we have

log^*n−log^*log^*n−2≤q₀(n)≤log^*n+22,

where log^*n is equal to the minimum number of iterations of the binary logarithm needed to bring n to 1 or below. The upper bound is obtained by constructing special graphs with modular decomposition of very small depth.     

On existence of singular solutions

In the paper sufficient conditions are given under which the differential equation y⁽ⁿ⁾=f(t,y,…,y⁽ⁿ⁻²⁾)g(y⁽ⁿ⁻¹⁾) has a singular solution y :[T,τ)→R, τ<∞ fulfilling

     

Dissecting the Stanley partition function

Let p(n) denote the number of unrestricted partitions of n. For i=0, 2, let p_i(n) denote the number of partitions π of n such that . Here denotes the number of odd parts of the partition π and π^′ is the conjugate of π. Stanley [Amer. Math. Monthly 109 (2002) 760; Adv. Appl. Math., to appear] derived an infinite product representation for the generating function of p₀(n)-p₂(n). Recently, Swisher [The Andrews–Stanley partition function and p(n), preprint, submitted for publication] employed the circle method to show that

(i)

and that for sufficiently large n

(ii)

In this paper we study the even/odd dissection of the Stanley product, and show how to use it to prove (i) and (ii) with no restriction on n. Moreover, we establish the following new result:

Two proofs of this surprising inequality are given. The first one uses the Göllnitz–Gordon partition theorem. The second one is an immediate corollary of a new partition inequality, which we prove in a combinatorial manner. Our methods are elementary. We use only Jacobi's triple product identity and some naive upper bound estimates.     

Symmetry properties for the extremals of the Sobolev trace embedding

In this article we study symmetry properties of the extremals for the Sobolev trace embedding H¹(B(0,μ))L^q(∂B(0,μ)) with 1q2(N−1)/(N−2) for different values of μ. These extremals u are solutions of the problem

We find that, for 1q<2(N−1)/(N−2), there exists a unique normalized extremal u, which is positive and has to be radial, for μ small enough. For the critical case, q=2(N−1)/(N−2), as a consequence of the symmetry properties for small balls, we conclude the existence of radial extremals. Finally, for 1<q2, we show that a radial extremal exists for every ball.     

Numerical Hopf bifurcation of Runge–Kutta methods for a class of delay differential equations

In this paper, we consider the discretization of parameter-dependent delay differential equation of the form

It is shown that if the delay differential equation undergoes a Hopf bifurcation at τ=τ^*, then the discrete scheme undergoes a Hopf bifurcation at τ(h)=τ^*+O(h^p) for sufficiently small step size h, where p1 is the order of the Runge–Kutta method applied. The direction of numerical Hopf bifurcation and stability of bifurcating invariant curve are the same as that of delay differential equation.     

Quadrature formulae connected to σ-orthogonal polynomials

Let dλ(t) be a given nonnegative measure on the real line , with compact or infinite support, for which all moments exist and are finite, and μ₀>0. Quadrature formulas of Chakalov–Popoviciu type with multiple nodes

where σ=σ_n=(s₁,s₂,…,s_n) is a given sequence of nonnegative integers, are considered. A such quadrature formula has maximum degree of exactness d_max=2∑_ν=1ⁿs_ν+2n−1 if and only if

The proof of the uniqueness of the extremal nodes τ₁,τ₂,…,τ_n was given first by Ghizzetti and Ossicini (Rend. Mat. 6(8) (1975) 1–15). Here, an alternative simple proof of the existence and the uniqueness of such quadrature formulas is presented. In a study of the error term R(f), an influence function is introduced, its relevant properties are investigated, and in certain classes of functions the error estimate is given. A numerically stable iterative procedure, with quadratic convergence, for determining the nodes τ_ν, ν=1,2,…,n, which are the zeros of the corresponding σ-orthogonal polynomial, is presented. Finally, in order to show a numerical efficiency of the proposed procedure, a few numerical examples are included.     

The directed genus of the de Bruijn graph

Define the directed genus, Γ(G), of an Eulerian digraph G to be the minimum value of p for which G has a 2-cell embedding in the orientable surface of genus p so that every face of the embedding is bounded by a directed circuit in G. The directed genus of the de Bruijn graph D_n is shown to be

     

RELATIONS BETWEEN PACKING PREMEASURE AND MEASURE ON METRIC SPACE

Let X be a metric space andμa finite Borel measure on X. Let pμq,t and pμq,t be the packing premeasure and the packing measure on X, respectively, defined by the gauge (μB(x,r))q(2r)t, where q, t∈R. For any compact set E of finite packing premeasure the authors prove: (1) if q≤0 then pμq,t(E)=pμq,t(E);(2)if q>0 andμis doubling on E then pμq,t(E) and pμq,t(E) are both zero or neither.     

A note on perturbation of non-symmetric Dirichlet forms by signed smooth measures

This article discusses the perturbation of a non-symmetric Dirichlet form,(ε, D(ε)), by a signed smooth measure μ, whereμ=μ1 -μ2 with μ1 and μ2 being smooth measures. It gives a sufficient condition for the perturbed form (εμ, D(εμ)) (for some αo ≥ 0) to be a coercive closed form.     

Uniform estimates for polynomial approximation in domains with corners

Let be a domain with a Jordan boundary ∂G, consisting of l smooth curves Γ_j, such that {z_j}Γ_j-1∩Γ_j≠, j=1,…,l, where Γ₀Γ_l. Denote by α_jπ, 0<α_j2, the angles at z_j's between the curves Γ_j-1 and Γ_j, exterior with respect to G. Let Φ be a conformal mapping of the exterior of onto the exterior of the unit disk, normed by Φ^′(∞)>0. We assume that there is a neighborhood U of , such that , where

z≠z_j if α_j1. Set g_Gsup{|g(z)|:zG}. Then we prove Theorem. Let and 0βr. If a function f is analytic in G and f^(r)β_G<+∞, then for each nlr there is an algebraic polynomial P_n of degree <n, such that

     

An improved upper bound for the Laplacian spectral radius of graphs

Let G be a simple graph with n vertices, m edges. Let Δ and δ be the maximum and minimum degree of G, respectively. If each edge of G belongs to t triangles (t≥1), then we present a new upper bound for the Laplacian spectral radius of G as follows:

Moreover, we give an example to illustrate that our result is, in some cases, the best.     

Curves of positive solutions of boundary value problems on time-scales

Let TR be a time-scale, with a=infT, b=supT. We consider the nonlinear boundary value problem

(2)

(4)

u(a)=u(b)=0,