APPLICATIONS OF BERNSTEIN-DURRMEYER OPERATORS IN ESTIMATING THE COVERING NUMBER

The paper deals with estimates of the covering number for some Mercer kernel Hilbert space with Bernstein-Durrmeyer operators. We first give estimates of l2- norm of Mercer kernel matrices reproducing by the kernelsK（α,β）（x,y）：=∑∞k=0 Ck（α,β）（x）Qk（α,β）（y）,where Qk（α,β） （x） are the Jacobi polynomials of order k on （0, 1 ）, Ck（α,β） 〉 0 are real numbers, and from which give the lower and upper bounds of the covering number for some particular reproducing kernel Hilbert space reproduced by Kα,β （x, y）.

ON THE MINIMUM COVERING NUMBER FORMULA OF GRAPHS

Throughout this paper,D=（d1,d2,...,dn）denote a sequence of nonnegative inte-gers.We let（?）（D）denote the class of all graphs with degree sequence D,or equally,theclass of all symmetric（0,1）--matrices with trace 0 and row sum vector D.The structure matrix S=S（D） of D is a matrix of order n+1,whose entries

On the Covering Number c_λ(3,W_4^((3)),v)

Abstract A t-hyperwhesl （t 〉 3） of length l （or Wz（t） for brevity） is a t-uniform hypergraph （V, E）, where t E= {e1,e2,...,el} and vl,v2,...,vt are distinct vertices of V = Ui=1 ei such that for i= 1,...,1, vi,vi＋1 ∈ei and ei ∩ ej = P, j ∈ {i - 1, i,i ＋ 1}, where the operation on the subscripts is modulo 1 and P is a vertex of V which is different from vi, 1 〈 i 〈 l. In this paper, the minimum covering problem of MCλ（3, W（3）,v） is investigated. Direct and recursive constructions on MCλ（3, W（3）,v） are presented. The covering number cλ（3, W4（3）, v） is finally determined for any positive integers v 〉 5 and A.

Reasoning and predicting POMDP planning complexity via covering numbers

Partially observable Markov decision processes （POMDPs） provide a rich mathematical framework for planning tasks in partially observable stochastic environments. The notion of the covering number, a metric of capturing the search space size of a POMDP planning problem, has been proposed as a complexity measure of approximate POMDP planning. Existing theoretical results are based on POMDPs with finite and discrete state spaces and measured in the l1- metric space. When considering heuristics, they are assumed to be always admissible. This paper extends the theoretical results on the covering numbers of different search spaces, including the newly defined space reachable under inadmissible heuristics, to the ln-metric spaces. We provide a simple but scalable algorithm for estimating covering numbers. Experimentally, we provide estimated covering numbers of the search spaces reachable by following different policies on several benchmark problems, and analyze their abilities to predict the runtime of POMDP planning algorithms.

On Covering Number of Groups with Trivial Fitting Subgroup

Let G be a finite group and S be a subset of Irr(G).If for every prime divisor p of|G|there is a characterχin S such that p dividesχ(1),S is called a covering set of G.The covering number of G,denoted by cn(G),is defined as the minimal number of Card(S),where S is a covering set of G and Card(S)is the cardinality of set S.In this paper,we prove that if G is a finite group with F(G)=1,then the covering number cn(G)≤3.Especially,if PSL2(q)or J1 is not involved in G,then cn(G)≤2.

Error Analysis of ERM Algorithm with Unbounded and Non-Identical Sampling

A standard assumption in the literature of learning theory is the samples which are drawn independently from an identical distribution with a uniform bounded output. This excludes the common case with Gaussian distribution. In this paper we extend these assumptions to a general case. To be precise, samples are drawn from a sequence of unbounded and non-identical probability distributions. By drift error analysis and Bennett inequality for the unbounded random variables, we derive a satisfactory learning rate for the ERM algorithm.

QUASIMEROMORPHIC MAPPINGS OF SEVERAL COMPLEX VARIABLES

The definitions of quasimeromorphic mappings from Cn to P1n, where P1 C U {∞}, P1n= P1×P1× ×P1(n-times) are introduced. From an inequality of the value distribution of quasimeromorphic functions of single variable, it follows that a normal criterion for the family of quasimeromorphic functions of several complex variables. Futhermore, a normal criterion for the family of quasimeromorphic mappings from Cn to P1n has been obtained.

RELATIONS AMONG SOME PARAMETERS OF HYPERGRAPHS

The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.

Minimum Coverings of Complete Directed Graphs with Odd Size Circuits

Let DKv denote the symmetric complete directed graph with v vertices, the covering number C(v,m) is a minimum number of covering DKv by m-circuits. In this paper, C(v,m) is determined for any fixed odd positive integer m and positive integer v, m ≤ v ≤ m + 6.

EDGE COVERING COLORING AND FRACTIONAL EDGE COVERING COLORING

Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.

On the Relations of Graph Parameters and Its Total Parameters

In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and βT（G） are the covering number, edge-covering number, independent number, edge-independent number （or matching number）, total covering number and total independent number, respectively.

Learning rates of least-square regularized regression with polynomial kernels

This paper presents learning rates for the least-square regularized regression algorithms with polynomial kernels. The target is the error analysis for the regression problem in learning theory. A regularization scheme is given, which yields sharp learning rates. The rates depend on the dimension of polynomial space and polynomial reproducing kernel Hilbert space measured by covering numbers. Meanwhile, we also establish the direct approximation theorem by Bernstein-Durrmeyer operators in $ L_{\rho _X }^2 $ with Borel probability measure.

Generalization errors of Laplacian regularized least squares regression

Semi-supervised learning is an emerging computational paradigm for machine learning,that aims to make better use of large amounts of inexpensive unlabeled data to improve the learning performance.While various methods have been proposed based on different intuitions,the crucial issue of generalization performance is still poorly understood.In this paper,we investigate the convergence property of the Laplacian regularized least squares regression,a semi-supervised learning algorithm based on manifold regularization.Moreover,the improvement of error bounds in terms of the number of labeled and unlabeled data is presented for the first time as far as we know.The convergence rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers.Some new techniques are exploited for the analysis since an extra regularizer is introduced.

On the Distribution of Laplacian Eigenvalues of a Graph

This paper presents some bounds on the number of Laplacian eigenvalues contained in various subintervals of [0, n] by using the matching number and edge covering number for G, and asserts that for a connected graph the Laplacian eigenvalue 1 appears with certain multiplicity. Furthermore, as an application of our result （Theorem 13）, Grone and Merris＇ conjecture [The Laplacian spectrum of graph II. SIAM J. Discrete Math., 7, 221-229 （1994）] is partially proved.

Sharp learning rates of coefficient-based l^q-regularized regression with indefinite kernels

Learning with coefficient-based regularization has attracted a considerable amount of attention in recent years, on both theoretical analysis and applications. In this paper, we study coefficient-based learning scheme （CBLS） for regression problem with /q-regularizer （1 〈 q ≤ 2）. Our analysis is conducted under more general conditions, and particularly the kernel function is not necessarily positive definite. This paper applies concentration inequality with/2-empirical covering numbers to present an elaborate capacity dependence analysis for CBLS, which yields sharper estimates than existing bounds. Moreover, we estimate the regularization error to support our assumptions in error analysis, also provide an illustrative example to further verify the theoretical results.

ERM Learning with Unbounded Sampling

The learning approach of empirical risk minimization （ERM） is taken for the regression problem in the least square framework. A standard assumption for the error analysis in the literature is the uniform boundedness of the output sampling process. In this paper we abandon this boundedness assumption and conduct error analysis for the ERM learning algorithm with unbounded sampling processes satisfying an increment condition for the moments of the output. The key novelty of our analysis is a covering number argument for estimating the sample error.