text:
## Abstract

Estimating the Rademacher chaos complexity of order two is important for understanding the performance of multikernel learning (MKL) machines. In this letter, we develop a novel entropy integral for Rademacher chaos complexities. As compared to the previous bounds, our result is much improved in that it introduces an adjustable parameter ε to prohibit the divergence of the involved integral. With the use of the iteration technique in Steinwart and Scovel (2007), we also apply our Rademacher chaos complexity bound to the MKL problems and improve existing learning rates.

## 1.  Introduction

During the last few years, kernel-based methods such as support vector machines have found great success in solving supervised learning problems like classification and regression (Schölkopf & Smola, 2002; Shawe-Taylor & Cristianini, 2004). For these tasks, the performance of the learning algorithms largely depends on the data representation via the choice of kernel functions—ones that are typically handcrafted and fixed in advance (Varma & Babu, 2009; Ying & Campbell, 2010). While this provides opportunities for us to incorporate the prior knowledge into the learning process, it can also be difficult in practice to find prior justifications for the use of one kernel instead of another (Lanckriet, Cristianini, Bartlett, Ghaoui, & Jordan, 2004). In this context, multikernel learning (MKL) has been introduced into the learning community to tackle this issue (Rakotomamonjy, Bach, Canu, & Grandvalet, 2007; Micchelli & Pontil, 2005; Lanckriet et al., 2004). Given a set of candidate (base) kernels, MKL tries to search for the most appropriate kernel from the training data. This strategy can significantly enhance the interpretability of the decision function, and it also reflects the fact that typical learning problems often involve multiple, heterogeneous data sources (Rakotomamonjy et al., 2007; Sonnenburg, Rätsch, & Schäfer, 2006).

Although learning the kernel from data allows greater flexibility in matching the target function (Srebro & Ben-David, 2006), this is not sufficient to guarantee the quality of the obtained model since one also needs to take into account the capacity of the hypothesis space. In this letter, we seek to characterize the capacity of by the so-called Rademacher chaos complexity of order two.

However, the Rademacher chaos complexity bounds in Ying and Campbell (2010), which are based on the standard entropy integral, may not be useful when the involved integral diverges, which occurs naturally if the logarithm of the covering number or the associated fat-shattering dimension grows at a polynomial rate with an exponent not less than 1 (Mendelson, 2003). This letter tackles this issue by presenting some refined entropy integrals for Rademacher chaos complexities. We use the standard Cauchy-Schwartz inequality to relate the Rademacher chaos complexities of to that of an -cover , which can be tackled by a chaining argument to yield a bound of the desirable form. As compared to the previous results, our bound admits some possible superiority since it allows the parameter to traverse an interval to attain a balance between the accuracy of the approximation by a cover and the complexity of that cover. With the aid of the iteration trick proposed by Steinwart and Scovel (2007), we also consider the application of our results to the MKL problems and improve the existing learning rates.

This letter is organized as follows. Section 2 introduces the statement of the problem. In section 3, we establish the refined entropy integral for Rademacher chaos complexities and consider its application to some specific function classes. Section 4 illustrates the effectiveness of our result by investigating MKL machines’ learning rates. Our conclusions are presented in section 5.

## 2.  Statement of the Problem

Before formulating our problem, we introduce some notations that we use throughout this letter. For a function , the sign function sgn(f) is defined as sgn(f)(x)=1 if and sgn(f)(x)=−1 if f(x)<0. We use c to denote positive constants, and their values may change from line to line or even within the same line.

Definition 1
(Rademacher chaos complexities). Let P be a probability measure defined on from which the examples are independently drawn. Let be a class of functions on , and let be n independent Rademacher random variables, that is, . The homogeneous Rademacher chaos process of order two, with respect to the Rademacher variable , is a random variable system of the form }. The empirical Rademacher chaos complexity of order two for is defined as the expectation of its suprema:

For simplicity, we always mean empirical Rademacher chaos complexities of order two when referring to Rademacher chaos complexities.

Definition 2
(Rademacher complexities). Let P be a probability measure on from which the examples are independently drawn. Let be n independent Rademacher random variables. For a class of functions , the (ordinary) empirical Rademacher complexity is defined as

It is worth mentioning that the Rademacher process , indexed by , can also be regarded as the homogeneous Rademacher chaos process of order one. Other than the Rademacher chaos complexities of order one or two, De la Peña and Giné (1999) also provided a definition for Rademacher chaos complexities of order .

Definition 3
(covering numbers). Let be a metric space and set . For any , a set is called an -cover of if for every we can find an element satisfying . The covering number is the cardinality of the minimal -cover of :
For brevity, whenis a normed space with norm, we also denote bythe covering number ofwith respect to the metric.
The quantitative relationship between Rademacher complexities and covering numbers can be formulated by the following far-reaching inequality (Srebro, Sridharan, & Tewari, 2010; Srebro & Sridharan, 2010),
2.1
where the norm is defined as . Inequality 2.1 can be considered a refinement of Dudley's original entropy integral of the following form (Dudley, 1999):
2.2

As compared to equation 2.2, the refined version, equation 2.1, is more effective and can be applied to the case where the integral in equation 2.2 diverges. The first main purpose of this letter is to derive a novel characterization analogous to equation 2.1 for Rademacher chaos complexities. In this respect, our work can be considered a generalization of the refined entropy integral equation 2.1, from Rademacher complexities to Rademacher chaos complexities.

### 2.2.  The Kernel Learning Problem.

In the context of classification, we are usually given an input space and an output space . The product space is always assumed to be equipped with a probability measure to govern the relationship between the input variable X and the output variable Y. Given a sequence of examples drawn independently from , the goal of learning is to construct a discriminant function so that the associated classifier sgn(f) is able to do the prediction as accurately as possible when new data arrive (Anthony & Bartlett, 1999). The error incurred by using f to classify a point (x, y) can be quantified by the term , where is a nonnegative function called the loss function. Consequently, the quality of a classifier can be assessed by the expected loss when used to do the prediction:
2.3
which is always called the generalization error or risk of f (with respect to ). However, since the generalization error involving an unknown probability measure is not computable, its discretion is used. The term is called the empirical error, and it is always used to guide the process of choosing a prediction rule from a candidate function class called the hypothesis space. This letter considers only the hinge loss , which is a standard choice due to its computation and statistical merit (Zhang, 2004).
We say that is a Mercer kernel (Cucker & Smale, 2002; Zhou, 2002) if it is continuous, symmetric, and positive semidefinite; that is, for any finite set of distinct points and any , the quadratic form is always nonnegative. The reproducing kernel Hilbert space (RKHS) associated with a Mercer kernel K is defined to be the closure of the linear span of functions , equipped with the inner product given by . An important property making the RKHS an appropriate choice as the candidate hypothesis space is the so-called reproducing property (Cucker & Zhou, 2007), which says that
In the context of multikernel learning, we are given a class of kernels, and our purpose is to learn a function from one of the RKHSs that is most suitable to model the data. We consider here the regularized learning scheme to avoid the possibility of overfitting. Formally, the general MKL scheme can be cast as a two-layer minimization problem,
2.4
where is the regularization parameter. The parameter should be chosen according to the sample size n to balance the goodness of the fit, as assessed by , and the simplicity of the model, as assessed by .

Our second goal is to use the refined bounds on Rademacher chaos complexities to study the generalization ability of the classifier , the theme of section 4.

## 3.  Refined Bounds on Rademacher Chaos Complexities

This section is devoted to establishing a refined bound on Rademacher chaos complexities when the information of covering numbers is available. Let be a set of functions on and . Then one can define a pseudometric on as follows:
3.1
With the assumption and , Ying and Campbell (2010) offered a characterization of the form1
3.2
The inequality, equation 3.2, known as a generalization of Dudley's entropy integral, equation 2.2, is novel since it builds the connection between Rademacher chaos complexities and covering numbers. Ying and Campbell (2010) also used such bounds to estimate learning rates for the kernel learning problem and obtained some interesting results. However, such bound may not be useful when the involved integral diverges, which can happen in some interesting situations (Mendelson, 2003).

Noticing that the divergence of the entropy integral is due to the rapid expansion of when r is approaching zero, we naturally ask whether a bound exists for which the lower limit of the integration is kept a distance from 0. As we will see, this can be achieved by introducing a threshold to prevent the divergence that will result from too fine an approximation.

For this purpose, we first consider the Rademacher chaos complexity for an -cover of the original class . In view of as an empirical process indexed by , the Rademacher chaos complexity is indeed the L1-norm of the maxima for a finite class of random variables, and it can be addressed by the powerful maximal inequalities in empirical process theory.

### 3.1.  Refined Rademacher Chaos Complexity Bounds.

The following theorem provides an example of maximal inequalities sufficient for our purpose, which can be considered a modification of equation 3.2 in that we provide a maximal inequality for the -cover rather than the whole class. Its proof is based on the chaining argument (Dudley, 1999; Anthony & Bartlett, 1999), whose basic idea is to split each function of interest in the class into a sum of functions chosen from a sequence of classes of progressively increasing complexity. Then the desired maximal inequality for is obtained by combining maximal inequalities for all of these classes. The underlying reason that we can allow the lower limit of the integration to stay away from 0 is that elements of can be exactly represented without resorting to -covers with .

Theorem 1.
Let be a class of functions defined on with and , where the metric dx is defined as equation 3.1. For any , let be a minimal -cover of with respect to the metric dx. Then we have the following inequality controlling the Rademacher chaos complexity of :
3.3
Proof.
Let be the minimal integer not less than . For each , let be a minimal -cover of with respect to the metric dx, where . Without loss of generality, we can assume that and . For any and , we denote by fj the closest point to f in . From the definition of -cover, we know that . Now for any , one can rewrite in a telescope form,
from which and the fact f0=0, one can derive that
3.4
The definition of -cover shows that , coupled with the triangle inequality, implies that for any we have
3.5
Ying and Campbell (2010) established the following maximal inequality for any t>1 and any finite class of functions on :2
3.6
Combining inequalities 3.5 and 3.6 together and noticing that the cardinality of the set is at most , we obtain that
3.7
When we plug inequality 3.7 back into 3.4, the monotonicity of implies that
In the last step of the deduction, we have used the fact that and , which is obvious from the construction of . Since the above inequality holds for any t>1, the desired result, equation 3.3, is immediate.

With theorem 1 as a stepping-stone, we are now ready to present the first main result of this letter. We first temporarily fix an and construct an -cover for the initial function class, thus transferring the original problem to the discussion of and . The complexity can be directly controlled by theorem 1 to yield a bound involving an integral of the desired form, while the term can be addressed by the standard Cauchy-Schwartz inequality. The following theorem is motivated by the recent work of Srebro and Sridharan (2010), who established an improvement, equation 2.1, of the standard entropy integral for the ordinary Rademacher complexity.

Theorem 2.
Let be a class of functions defined on with and , where the metric dx is defined as equation 3.1. Then for any , there holds that
3.8
Proof.
For any , let be a minimal -cover of with respect to the metric dx. For any , denote by the closest element to f in . To tackle the quantity , we first decompose it into two parts:
3.9
The first term can be addressed through the famous Cauchy-Schwartz inequality:
3.10
As for the term , one can take t=2 in equation 3.3 to derive that
3.11
When we put inequalities 3.10 and 3.11 back into 3.9, the promised inequality, 3.8, is direct.
Remark 1.

As can be seen clearly from inequality 3.8, our bound can be at least as sharp as inequality 3.2 since the in inequality 3.8 can be made arbitrarily close to 0. Also, the parameter is permitted to traverse the interval (0, D) to achieve a trade-off between the accuracy of the approximation by the cover and the complexity of that cover, which efficiently prohibits the divergence of the integration over the interval (0, D). Theorem 2 can be readily extended to the setting of Rademacher chaos complexities with order larger than two.

### 3.2.  Rademacher Chaos Complexities for Some Specific Classes.

As a specific example to show the possible superiority of our result over the previous one, we consider the Rademacher chaos complexities of function classes for which the logarithm of the covering number grows as a polynomial of 1/r.

Corollary 1.
Let be a class of functions defined on with and . Suppose that there exist constants and p>0 such that for any x. Then the homogeneous Rademacher chaos complexities of order two can be bounded as follows:
3.12
Proof.

We proceed with our discussion by distinguishing three cases:

• Case p<1. In this case, one can invoke theorem 2 here to show that
where the infimum is achieved with the assignment and the last inequality follows from condition p<1.
• Case p=1. Now it follows from theorem 2 that
where the infimum is attained by taking the choice .
• Case p>1. For such p, analyzing analogous to the case p<1, one obtains that
where the last inequality is obvious since p>1.

Notice that the bound of the form 3.2 cannot tackle the case since the involved integral diverges for such p. Here are some explicit function classes that satisfy the entropy conditions in corollary 1.

Example 1.
Micchelli and Pontil (2005) considered the problem of finding an optimal kernel from the convex hull of a basic kernel class :
If the base class admits a finite pseudodimension d, then the covering numbers of can be controlled by an exponential of 1/r (Van der Vaart & Wellner, 1996, corollary 2.6.12):
3.13
where K is a constant independent of r. If d>2, the exponent of 1/r in equation 3.13 is larger than 1, and thus the direct application of the traditional entropy integral, equation 3.2 is not possible in this situation. Although corollary 1 can be applied here, a better strategy is to employ the structural property (Ying & Campbell, 2010), which reduces the discussion of to that of . Interested readers are referred to Srebro and Ben-David (2006) for some interesting basic classes with finite pseudodimensions (e.g., gaussian kernels with covariance matrices).
Example 2.
We consider here an example that can be considered an RKHS on the space of kernels . Specifically, let be the compounded index set, and let be a Mercer kernel. Denote by the RKHS associated with the kernel , and define as a ball with radius R in the Hilbert space , that is,
3.14
Rejchel (2012) considered the function spaces of the form 3.14 in the context of ranking, and the estimation of is important to understand the behavior of the associated estimators. Ong, Smola, and Williamson (2005) also provided a novel approach to learning the kernel in such by minimizing the regularized quality functional, and is called a hyperkernel in their setting.3
If is a closed subset of with piecewise smooth boundary and the Mercer kernel belongs to the generalized Lipschitz space , then for any 0<r<R, the covering numbers satisfy the growing rate (Cucker & Zhou, 2007, theorem 5.8):
3.15
Consequently, the exponent 4d/s in equation 3.15 would exceed 1 if the smoothness parameter s is smaller than 4d.
Example 3.
Let be a sequence of Mercer kernels with and a sequence of positive numbers with . Consider the classes of kernels that can be expressed as an (infinite) nonnegative combination of Ki under the “l2-constraint”:
3.16
Reformulating the class 3.16 as
and applying corollary 3 in Zhang (2002) to tackle its covering numbers, we obtain4

## 4.  Applications to the Multikernel Learning Problem

In this section, we demonstrate the effectiveness of the previous results on Rademacher chaos complexities by showing how they can be applied to the kernel learning problem. The foundation on which our discussion is based is a novel connection (theorem 4) between the uniform deviation and the Rademacher chaos complexities, attributed to Ying and Campbell (2010).

Our main aim is to show the Bayes consistency of the multikernel regularized classifiers defined in equation 2.4 by providing some satisfactory estimates for the excess misclassification error , where is the risk of the prediction rule sgn(f) as assessed by the 0-1 loss and is the Bayes rule. The following theorem (Zhang, 2004; Bartlett, Jordan, & McAuliffe, 2006), called the comparison inequality, implies that the “excess misclassification error” can be controlled by the “excess -risk” , where is a measurable function minimizing the -risk. Consequently, the discussion of is sufficient for our purpose.

Theorem 3
(Zhang, 2004). For the hinge loss , we have the following inequality for any measurable function f:
4.1
For any , we take
A standard approach to addressing is to relate it to two associated errors by the following error decomposition (Wu et al., 2007),
4.2
where the regularization error,
expresses the approximation power of the involved space, and the sample error
reflects the difficulty of selecting the optimal classifier in a given hypothesis space. Here is the regularization function. For simplicity, we assume the existence of the regularization function and the empirical classifier (Wu et al., 2007). We always suppose that the regularization error decays polynomially in this section, that is, for some universal constants c and . This is a standard assumption, and there are many sufficient conditions guaranteeing the polynomial decay of the regularization error (Wu et al., 2007; Chen, Wu, Ying, & Zhou, 2004; Chen, Pan, Li, & Tang, 2013). We also assume that the quantity is finite.
Let
4.3
be the union of the R-balls in the candidate RKHSs. For any R>0, denote by
the set of samples for which the corresponding empirical classifier lies in .
Theorem 4
(Ying & Campbell, 2010). Assume that the loss function is the hinge loss. Then for any , the following inequality holds with probability at least :
4.4

With theorem 4 as a stepping-stone, we can now present the second result of this letter. Theorem 6 provides a general result on MKL algorithms’ learning rate under the hinge loss and shows that the excess generalization error can be controlled by the regularization error for some restricted parameter . Its proof is based on the iteration trick due to Steinwart and Scovel (2007). For this purpose, we first give a lemma illustrating how the norm decreases as a function of the radius R.

Lemma 5.
Let be the hinge loss, and let c0, c1 be two positive constants. Assume that the regularization parameter satisfies
4.5
and suppose that . Then for any there is a set with such that
where a and b are two constants independent of R:
4.6
Proof.
From the definition of , it follows that
from which we know that . Consequently, for any , the reproducing property implies that . Now, one can apply Hoeffding inequality (see, Boucheron, Lugosi, & Bousquet, 2004) here to show that with probability at least , there holds
4.7
Utilizing inequalities 4.2 and 4.7 and applying theorem 4 to the set , we know that there is a set with such that for any , there holds
4.8
where in the second step of the above deduction, we have used the assumption and equation 4.5.
Consequently, for any and some constant c depending on c0, c1, and , we have
That is, there exists a set VR with such that .
Theorem 6.
Under the condition of lemma 5 and for any , the generalization performance of can be characterized by the following inequality with probability at least :
4.9
Proof.
For any examples , there holds (Ying & Campbell, 2010) that , and thus we have . Define a sequence by and
4.10
where the numbers a and b are given by equation 4.6. From lemma 5, we know that there exists a subset sequence with and . Consequently, for any , there holds
4.11
Utilizing the recurrent relationship 4.10 and the basic inequality , it is not hard to check
4.12
According to equation 4.11, with confidence at least that , we have with R(J) controlled by equation 4.12. Utilizing this fact and applying inequality 4.8 with R replaced by R(J), the following inequality holds with probability at least :
Taking the choice , we have and thus with probability at least , there holds
The above inequality can be rewritten as equation 4.9. The proof is complete.
Remark 2.
Noticing that the functions and are always contained in , Ying and Campbell (2010) simply applied theorem 4 with to obtain
4.13
As compared to this result, inequality 4.9 is better and can yield some faster learning rates. The underlying reason for this improved result lies in the fact that by using the iteration technique, we essentially show , and thus the application of theorem 4 with is sufficient.
Corollary 2.
Let be the hinge loss and suppose the regularization error admits a polynomial decay . Let be a prescribed set of candidate kernels with and for any , where and p are any two positive constants. Then by choosing if p<1, if p=1 and if p>1, for any , the excess misclassification error of the classifier in equation 2.4 can be controlled with probability at least as follows:
Proof.

By the reproducing property, it is not hard to check that . We can proceed with this proof by distinguishing three cases according to the magnitude of p:

• Case p<1. In this case, corollary 1 yields that . Consequently, the choice satisfies condition 4.5, and thus inequality 4.9 reduces to
4.14
• Case p=1. For such p, one can derive from corollary 1 that , and thus is a suitable choice meeting condition 4.5. Now, from equation 4.9, it follows directly that
• Case p>1. In this case, corollary 1 implies that . It can be directly checked that the choice satisfies condition 4.5, and thus inequality 4.9 reduces to

When we put the three cases together and use inequality 4.1 to connect the excess misclassification error with the excess generalization error , the stated inequality is immediate.

Remark 3.

The analysis based on theorem 6 and the previous entropy integral, 3.2, can tackle only the case p<1, while our discussion yields satisfactory learning rates for all p>0. One can refer to the examples in section 3.2 for some specific function classes satisfying the entropy conditions in corollary 2. The condition also holds (Mendelson, 2003) if the fat-shattering dimension grows as a polynomial of 1/r with exponent p.

Remark 4.
When the Rademacher chaos complexity is bounded by a constant independent of n (which happens if the exponent p is less than 1), Ying and Campbell (2010, example 1) derived the following inequality with probability at least ,
by applying equation 4.13 with the assignment . Comparing this generalization bound with equation 4.14, one can see that corollary 2 is much improved when . Furthermore, as approaches 0, our learning rate can roughly attain the speed (we ignore the logarithm for simplicity), a great improvement. For the case with , a direct calculation shows that learning rates given by corollary 2 are also sharper than the bounds that can be induced from equation 4.13 and the refined entropy integral. Notice that the improvement is due to the iteration technique since we are using the same entropy integral to control Rademacher chaos complexities here.

## 5.  Conclusion

In this letter, we provide a refined entropy integral for the Rademacher chaos complexity that can be extremely useful when the standard integral diverges. We apply our bounds to some function classes and obtain some satisfactory results. We also combine our Rademacher chaos complexity bounds and the iteration technique in Steinwart and Scovel (2007) to improve the learning rates of MKL machines.

We consider the use of the Rademacher chaos complexity only in the MKL context. However, our discussion can also have direct applications in other learning problems for which the goal is to construct a function f defined on . Some well-known examples include ranking (Rejchel, 2012), where the function f is used to predict the ordering between objects. Specifically, Rejchel (2012) considered the generalization bounds for the ranking rules, and the discussion there is based on the assumption that the logarithm of the covering number grows as a polynomial with exponent less than 1 (Rejchel, 2012, assumption B), which is due to the fact that Rejchel used equation 3.2 to control Rademacher chaos complexities (Rejchel, 2012, equation 18). If one uses the refined entropy integral instead, however, this assumption can be safely removed.

## Acknowledgments

This work is supported in part by the National Natural Science Foundation of China (grant 60975050, 61165004). We also appreciate the anonymous referees for their insightful and constructive comments, which greatly improved the quality of the letter.

## References

Anthony
,
M.
, &
Bartlett
,
P.
(
1999
).
Neural network learning: Theoretical foundations
.
New York
:
Cambridge University Press
.
Bartlett
,
P.
,
Jordan
,
M.
, &
McAuliffe
,
J.
(
2006
).
Convexity, classification, and risk bounds
.
J. Am. Stat. Assoc.
,
101
(
473
),
138
156
.
Bartlett
,
P.
, &
Mendelson
,
S.
(
2002
).
Rademacher and gaussian complexities: Risk bounds and structural results
.
J. Mach. Learn. Res.
,
3
,
463
482
.
Boucheron
,
S.
,
Lugosi
,
G.
, &
Bousquet
,
O.
(
2004
).
Concentration inequalities
. In
O. Bousquet, U. Von Luxburg, & G. Rätsch
(Eds.),
(pp.
208
240
).
New York
:
Springer-Verlag
.
Bousquet
,
O.
(
2003
).
New approaches to statistical learning theory
.
Ann. Inst. Stat. Math.
,
55
(
2
),
371
389
.
Bousquet
,
O.
, &
Herrmann
,
D.
(
2002
).
On the complexity of learning the kernel matrix
. In
S. Becker, S. Thrün, & K. Obermayer (Eds.)
,
Advances in neural information processing systems, 15
(pp.
399
406
).
Cambridge, MA
:
MIT Press
.
Chen
,
D.
,
Wu
,
Q.
,
Ying
,
Y.
, &
Zhou
,
D.
(
2004
).
Support vector machine soft margin classifiers: Error analysis
.
J. Mach. Learn. Res.
,
5
,
1143
1175
.
Chen
,
H.
, &
Li
,
L.
(
2010
).
Learning rates of multi-kernel regularized regression
.
J. Stat. Plan. Infer.
,
140
(
9
),
2562
2568
.
Chen
,
H.
,
Pan
,
Z.
,
Li
,
L.
, &
Tang
,
Y.
(
2013
).
Error analysis of coefficient-based regularized algorithm for density-level detection
.
Neural. Comput.
,
25
(
4
),
1107
1121
.
Cucker
,
F.
, &
Smale
,
S.
(
2002
).
On the mathematical foundations of learning
.
Bull. Am. Math. Soc.
,
39
(
1
),
1
50
.
Cucker
,
F.
, &
Zhou
,
D.
(
2007
).
Learning theory: An approximation theory viewpoint
.
Cambridge
:
Cambridge University Press
.
De la Peña
,
V.
, &
Giné
,
E.
(
1999
).
Decoupling: From dependence to independence
.
New York
:
Springer-Verlag
.
Dudley
,
R.
(
1999
).
Uniform central limit theorems
.
Cambridge
:
Cambridge University Press
.
Lanckriet
,
G.
,
Cristianini
,
N.
,
Bartlett
,
P.
,
Ghaoui
,
L.
, &
Jordan
,
M.
(
2004
).
Learning the kernel matrix with semidefinite programming
.
J. Mach. Learn. Res.
,
5
,
27
72
.
Mendelson
,
S.
(
2003
).
A few notes on statistical learning theory
. In
S. Mendelson & A. Smola (Eds.)
,
(pp.
1
40
).
Berlin
:
Springer-Verlag
.
Micchelli
,
C.
, &
Pontil
,
M.
(
2005
).
Learning the kernel function via regularization
.
J. Mach. Learn. Res.
,
6
,
1099
1125
.
Ong
,
C. S.
,
Smola
,
A. J.
, &
Williamson
,
R. C.
(
2005
).
Learning the kernel with hyperkernels
.
J. Mach. Learn. Res.
,
6
,
1043
1071
.
Rakotomamonjy
,
A.
,
Bach
,
F.
,
Canu
,
S.
, &
Grandvalet
,
Y.
(
2007
).
More efficiency in multiple kernel learning
. In
Z. Ghahramani
(Ed.),
Proceedings of the 24th International Conference on Machine Learning
(pp. 775–782). New York
:
ACM Press
.
Rejchel
,
W.
(
2012
).
On ranking and generalization bounds
.
J. Mach. Learn. Res.
,
13
,
1373
1392
.
Schölkopf
,
B.
, &
Smola
,
A.
(
2002
).
Learning with kernels: Support vector machines, regularization, optimization, and beyond
.
Cambridge, MA
:
MIT Press
.
Shawe-Taylor
,
J.
, &
Cristianini
,
N.
(
2004
).
Kernel methods for pattern analysis
.
New York
:
Cambridge University Press
.
Sonnenburg
,
S.
,
Rätsch
,
G.
, &
Schäfer
,
C.
(
2006
).
A general and efficient multiple kernel learning algorithm
. In
Y. Weiss, B. Schölkopf, & J. Platt
(Eds.),
Advances in neural information processing systems, 18
(pp.
1273
1280
).
Cambridge, MA
:
MIT Press
.
Srebro
,
N.
, &
Ben-David
,
S.
(
2006
).
Learning bounds for support vector machines with learned kernels
. In
G. Lugosi & H. Simon (Eds.)
,
Learning theory
(pp.
169
183
).
Berlin
:
Springer-Verlag
.
Srebro
,
N.
, &
Sridharan
,
K.
(
2010
).
Note on refined Dudley integral covering number bound.
Unpublished results
. http://ttic.uchicago.edu/karthik/dudley.pdf.
Srebro
,
N.
,
Sridharan
,
K.
, &
Tewari
,
A.
(
2010
).
Smoothness, low-noise and fast rates
. In
J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, & A. Culotta (Eds.)
,
Advances in neural information processing systems
,
23
(pp.
2199
2207
).
Red Hook, NY
:
Curran
.
Steinwart
,
I.
, &
Scovel
,
C.
(
2007
).
Fast rates for support vector machines using gaussian kernels
.
Ann. Statist.
,
35
(
2
),
575
607
.
Van der Vaart
,
A.
, &
Wellner
,
J.
(
1996
).
Weak convergence and empirical processes: With applications to statistics
.
New York
:
Springer-Verlag
.
Varma
,
M.
, &
Babu
,
B.
(
2009
).
More generality in efficient multiple kernel learning
. In
A. Danyluk, L. Bottou, & M. Littman
(Eds.),
Proceedings of the 26th Annual International Conference on Machine Learning
(pp.
1065
1072
).
New York
:
ACM
.
Wu
,
Q.
,
Ying
,
Y.
, &
Zhou
,
D.
(
2007
).
Multi-kernel regularized classifiers
.
J. Complex.
,
23
(
1
),
108
134
.
Ying
,
Y.
, &
Campbell
,
C.
(
2009
).
Generalization bounds for learning the kernel
. In
S. Dasgupta & A. Klivans (Eds.)
,
Proceedings of the 22nd Annual Conference on Learning Theory
.
New York
:
Springer-Verlag
.
Ying
,
Y.
, &
Campbell
,
C.
(
2010
).
Rademacher chaos complexities for learning the kernel problem
.
Neural. Comput.
,
22
(
11
),
2858
2886
.
Ying
,
Y.
, &
Zhou
,
D.
(
2007
).
Learnability of gaussians with flexible variances
.
J. Mach. Learn. Res.
,
8
,
249
276
.
Zhang
,
T.
(
2002
).
Covering number bounds of certain regularized linear function classes
.
J. Mach. Learn. Res.
,
2
,
527
550
.
Zhang
,
T.
(
2004
).
Statistical behavior and consistency of classification methods based on convex risk minimization
.
Ann. Stat.
,
32
(
1
),
56
85
.
Zhou
,
D.
(
2002
).
The covering number in learning theory
.
J. Complex.
,
18
(
3
),
739
767
.

## Notes

1
Indeed, Ying and Campbell (2010) obtained the inequality
However, it can be shown that the additional term D can be removed under the assumption .
2
Ying and Campbell (2010) obtained the inequality
However, it is not hard to derive the slightly stronger inequality 3.6 through their deduction.
3
The hyperkernel should satisfy the symmetric condition . One can always achieve this by introducing a new kernel,
when it is necessary. The kernel K learned in is not necessarily positive semidefinite, and one needs to impose an additional constraint to guarantee that the kernel matrix [K(xi, xj)]ni,j=1 is positive semidefinite (Ong et al., 2005).
4

The metric dx can be considered (up to some factors) as the empirical L2-covering numbers with respect to the data .


text:
# Evaluate the integral $\int \frac{dx}{x(x+1)(x+2) \cdot \cdot \cdot (x+n)}$

I found the integral in this pdf. $$\int \frac{dx}{x(x+1)(x+2) \cdot \cdot \cdot (x+n)}$$

My first thought was to use partial fraction decomposition. Namely, \begin{align*}\prod_{k=0}^n \frac{1}{(x+k)} &= \sum_{k=0}^n \frac{A_k}{(x+k)} \\ 1&=\prod_{k=0}^n(x+k) \sum_{k=0}^n \frac{A_k}{(x+k)} \end{align*} Where $A_k$ is a constant. However, I'm not even sure if my progress is correct, or if there is a simpler way to approach this. Any help would be appreciated.

• your approach is correct and standard – SiXUlm Dec 30 '15 at 22:24
• @SiXUlm so I see the pattern $1 = A_1 \left[(x+1)(x+2)(x+3)\cdot\cdot\cdot (x+n)\right] + A_2 \left[x(x+2)(x+3)\cdot\cdot\cdot (x+n) \right] + A_3 \left[x(x+1)(x+2)\cdot\cdot\cdot (x+n)\right]$ but I'm not sure how to continue. – rgarci0959 Dec 30 '15 at 22:31
• Now, substitute $x=0$, you will have is $A_1 n! = 1$ . So $A_1 = 1/n!$. Next, substitute $x = -1$, you have $-A_2 (n-1)! = 1$, and so on for $x = -2, ..., -n$ – SiXUlm Dec 30 '15 at 22:38

In general, if $P(x)$ is a polynomial whose roots $\lambda_1, \ldots, \lambda_n$ are all simple and $Q(x)$ is another polynomial with degree lower than that of $P(x)$, we have $$\frac{Q(x)}{P(x)} = \sum_{k=1}^n \frac{Q(\lambda_k)}{(x-\lambda_k)P'(\lambda_k)}$$ In particular, if $\displaystyle\;P(x) = \prod_{k=1}^n (x-\lambda_k)\;$, then $\displaystyle\;P'(\lambda_k) = \prod_{j=1,\ne k}^n (\lambda_k - \lambda_j)\;$.
For your case, this becomes $$\prod_{k=0}^n\frac{1}{x+k} = \sum_{k=0}^n\frac{1}{x+k}\prod_{j=0,\ne k}^n\frac{1}{j-k} = \sum_{k=0}^n\frac{(-1)^k}{(x+k)(n-k)!k!}$$ The partial fraction decomposition for the integrand isn't that complicated at all.
$$\prod_{k=0}^n \frac{1}{x+k} = \sum_{k=0}^n \frac{A_k}{x+k},$$ $$\prod_{m=0,\,m\not= k}^n \frac{1}{x+m} = A_k + \sum_{m=0,\,m\not= k}^n \frac{x+k}{x+m}A_m,$$ $$x\to -k: \quad\prod_{m=0,\,m\not= k}^n \frac{1}{m-k} = A_k.$$

format: plain


text:
UCTE-DEF Importer

The UCTE-DEF (UCTE Data Format Exchange) format is the format used by UCTE TSOs to exchange grid models for load-flow and three-phase short-circuit studies. The data is contained in an unformatted standard US ASCII file, organized in several sections:

• N : nodes
• L : lines
• T : two windings transformers
• R : two windings transformers regulation
• TT : 2 windings transformers special description (optional)
• E : exchange powers (optional)

The UCTE importer support files with the following extensions: .uct and .UCT

# Example

##C 2007.05.01
This is an example of UCTE-DEF file
##N
##ZXX
XXNODE11              1 0      0       0       0       0       0       0       0       0       0     0       0       0
XXNODE21              1 0      0       0       0       0       0       0       0       0       0     0       0       0
##ZFR
FRNODE11              0 0      0     100       0       0       0       0       0       0       0     0       0       0
##ZES
ESNODE11              0 0    400       0       0    -100       0       0    -200     200    -200     0       0       0
##L
FRNODE11 XXNODE11 1 0      2     10       65    200 INTERCO FR
ESNODE11 XXNODE21 1 0      2     10       65    200 DANGLING XNODE
ESNODE11 XXNODE11 1 0      2     10       65    200 INTERCO ES

# Maven configuration

To support UCTE-DEF files, add the following dependencies to the pom.xml file:

<dependency>
<groupId>com.powsybl</groupId>
<artifactId>powsybl-ucte-converter</artifactId>
<version>${powsybl.version}</version> </dependency> <dependency> <groupId>com.powsybl</groupId> <artifactId>powsybl-ucte-network</artifactId> <version>${powsybl.version}</version>
</dependency>

NB: In order to work, the UCTE importer also need an IIDM implementation in the pom.xml. Powsybl provides one so you can simply add it:

<dependency>
<groupId>com.powsybl</groupId>
<artifactId>powsybl-iidm-impl</artifactId>
<version>\${powsybl.version}</version>
</dependency>


text:
NIPS Proceedingsβ

Implicit Bias of Gradient Descent on Linear Convolutional Networks

[PDF] [BibTeX] [Supplemental] [Reviews]

Abstract

We show that gradient descent on full-width linear convolutional networks of depth $L$ converges to a linear predictor related to the $\ell_{2/L}$ bridge penalty in the frequency domain. This is in contrast to linearly fully connected networks, where gradient descent converges to the hard margin linear SVM solution, regardless of depth.


text:
# How would we differentiate graphite, bromine, hydrogen fluoride, lithium fluoride, and hydrogen bromide?

Nov 5, 2016

Well, $\text{carbon (graphite)}$, and $\text{lithium fluoride}$ are non-molecular materials.
On the other hand, $B {r}_{2}$, $H B r$, and $H F$ are all molecular species, containing discrete molecules held together by intermolecular forces. For elemental bromine, the elemental forces are relatively weak dispersion forces, nevertheless, the physical size of the electron cloud around the bromine molecule results in a normal boiling point of $59$ ""^@C.
Hydrogen fluoride features hydrogen bound to a highly electronegative fluorine, and results in an elevated boiling point of $19.5$ ""^@C; as with water, the phenomenon of hydrogen bonding is a potent intermolecular force. For $H B r$ the strength of intermolecular bonding would not be so pronounced given the reduced electronegativity of $B r$, and a boiling point of $- 66.8$ ""^@C is reported.


text:
#### Change ddev password for a single project

I try to change a ddev database password for a single project.

I need to check sign-escaping for a project, because I want to know how and if that works.

How can I change a database password in a single ddev-project?

I use

• Docker 3.5.1 (66090)
• ddev 1.17.2
• macOS Catalina 10.15.7

I got answers in slack, thanks for that, but I run into those errors, if I do so:

ddev mysql

MariaDB [db]> GRANT ALL PRIVILEGES ON *.* TO 'db'@'%';


text:
×

# Real analysis

Let $$\dot{\mathcal P }$$ be a tagged partition of $$[0,3]$$.

(a) Show that the union $$U_1$$ of all subintervals in $$\dot{\mathcal P}$$ with tags in $$[0,1]$$ satisfies $$[ 0, 1- ||\dot{\mathcal P} || \subseteq U1 \subseteq [ 0, 1 + || \dot{\mathcal P} || ]$$.

(b) Show that the union $$U_2$$ of all subintervals in $$\dot{\mathcal P}$$ with tags in $$[1,2]$$ satisfies $$[ 1 + ||\dot{\mathcal P} || , 2- ||\dot{\mathcal P} || \subseteq U2 \subseteq [ 1 - ||\dot{\mathcal P} ||, 2 + || \dot{\mathcal P} || ]$$.

Note by Syed Subhan Siraj
1 year, 7 months ago


text:
# Reeve tetrahedron

Reeve tetrahedron

In geometry, the Reeve tetrahedron is a polyhedron, in three-dimensional space with vertices at (0, 0, 0), (1, 0, 0), (0, 1, 0) and (1, 1, r) where r is a positive integer. It is named after John Reeve, who used it to show that higher-dimensional generalizations of Pick's theorem do not exist.

## Counterexample to generalizations of Pick's theorem

Each vertex of the Reeve tetrahedron lies on a fundamental lattice point (a point in 3). No other fundamental lattice points lie on the surface or in the interior of the tetrahedron. The volume of the Reeve tetrahedron is r/6. In 1957 Reeve used this tetrahedron to show that there exist tetrahedra with four lattice points as vertices, and containing no other lattice points, but with arbitrarily large volume.[1]

In two dimensions, the area of every polyhedron with lattice vertices is determined as a formula of the number of lattice points at its vertices, on its boundary, and in its interior, according to Pick's theorem. The Reeve tetrahedra imply that there can be no corresponding formula for the volume in three or more dimensions. Any such formula would be unable to distinguish the Reeve tetrahedra with different choices of r from each other, but their volumes are different from each other.[1]

Despite this negative result, it is possible (as Reeve showed) to devise a more complicated formula for lattice polyhedron volume that combines the number of lattice points in the polyhedron, the number of points of a finer lattice in the polyhedron, and the Euler characteristic of the polyhedron.[1][2]

## Ehrhart polynomial

The Ehrhart polynomial of any lattice polyhedron counts the number of lattice points that it contains when scaled up by an integer factor. The Ehrhart polynomial of the Reeve tetrahedron Tr of height r is[3]

${\displaystyle L({\mathcal {T}}_{r},t)={\frac {r}{6}}t^{3}+t^{2}+\left(2-{\frac {r}{6}}\right)t+1.}$

Thus, for r ≥ 13, the coefficient of t in the Ehrhart polynomial of Tr is negative. This example shows that Ehrhart polynomials can sometimes have negative coefficients.[3]

## References

1. ^ a b c Reeve, J. E. (1957). "On the volume of lattice polyhedra". Proceedings of the London Mathematical Society. Third Series. 7: 378–395. doi:10.1112/plms/s3-7.1.378. MR 0095452.
2. ^ Kołodziejczyk, Krzysztof (1996). "An "odd" formula for the volume of three-dimensional lattice polyhedra". Geometriae Dedicata. 61 (3): 271–278. doi:10.1007/BF00150027. MR 1397808.
3. ^ a b Beck, Matthias; Robins, Sinai (2015). Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics (Second ed.). New York: Springer. pp. 78–79, 82. doi:10.1007/978-1-4939-2969-6. ISBN 978-1-4939-2968-9. MR 3410115.


text:
Copied to
clipboard

## G = (C2×Q8).Q8order 128 = 27

### 2nd non-split extension by C2×Q8 of Q8 acting via Q8/C2=C22

p-group, metabelian, nilpotent (class 4), monomial

Series: Derived Chief Lower central Upper central Jennings

 Derived series C1 — C2×C4 — (C2×Q8).Q8
 Chief series C1 — C2 — C22 — C23 — C22×C4 — C22×Q8 — C23.67C23 — (C2×Q8).Q8
 Lower central C1 — C2 — C22 — C2×C4 — (C2×Q8).Q8
 Upper central C1 — C22 — C23 — C22×Q8 — (C2×Q8).Q8
 Jennings C1 — C2 — C22 — C22×Q8 — (C2×Q8).Q8

Generators and relations for (C2×Q8).Q8
G = < a,b,c,d,e | a2=b4=d4=1, c2=b2, e2=ab-1d2, dbd-1=ab=ba, ece-1=ac=ca, ad=da, eae-1=ab2, cbc-1=b-1, be=eb, cd=dc, ede-1=cd-1 >

Subgroups: 192 in 86 conjugacy classes, 32 normal (18 characteristic)
C1, C2, C2, C4, C22, C22, C8, C2×C4, C2×C4, C2×C4, Q8, C23, C42, C4⋊C4, C2×C8, M4(2), C22×C4, C22×C4, C22×C4, C2×Q8, C2×Q8, C2×Q8, C2.C42, C4.10D4, C4.10D4, C2×C42, C2×C4⋊C4, C2×M4(2), C22×Q8, C23.67C23, C2×C4.10D4, (C2×Q8).Q8
Quotients: C1, C2, C4, C22, C2×C4, D4, Q8, C42, C22⋊C4, C4⋊C4, C2.C42, C23⋊C4, C23.9D4, C42.C4, C42.3C4, (C2×Q8).Q8

Character table of (C2×Q8).Q8

 class 1 2A 2B 2C 2D 2E 4A 4B 4C 4D 4E 4F 4G 4H 4I 4J 4K 4L 8A 8B 8C 8D 8E 8F 8G 8H size 1 1 1 1 2 2 4 4 4 4 4 4 4 4 4 4 8 8 8 8 8 8 8 8 8 8 ρ1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 trivial ρ2 1 1 1 1 1 1 -1 1 1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 linear of order 2 ρ3 1 1 1 1 1 1 -1 1 1 1 1 -1 1 -1 -1 1 -1 -1 1 1 -1 -1 -1 -1 1 1 linear of order 2 ρ4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 linear of order 2 ρ5 1 -1 1 -1 -1 1 i 1 -1 -1 1 i -1 -i -i 1 i -i 1 1 -i -i i i -1 -1 linear of order 4 ρ6 1 1 1 1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 1 -i i i -i i -i -i i linear of order 4 ρ7 1 1 1 1 1 1 1 1 1 -1 -1 1 -1 1 1 -1 -1 -1 i -i i -i i -i i -i linear of order 4 ρ8 1 -1 1 -1 -1 1 -i 1 -1 1 -1 -i 1 i i -1 i -i -i i 1 -1 -1 1 i -i linear of order 4 ρ9 1 -1 1 -1 -1 1 i 1 -1 -1 1 i -1 -i -i 1 i -i -1 -1 i i -i -i 1 1 linear of order 4 ρ10 1 1 1 1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 1 i -i -i i -i i i -i linear of order 4 ρ11 1 1 1 1 1 1 1 1 1 -1 -1 1 -1 1 1 -1 -1 -1 -i i -i i -i i -i i linear of order 4 ρ12 1 -1 1 -1 -1 1 -i 1 -1 1 -1 -i 1 i i -1 i -i i -i -1 1 1 -1 -i i linear of order 4 ρ13 1 -1 1 -1 -1 1 -i 1 -1 -1 1 -i -1 i i 1 -i i -1 -1 -i -i i i 1 1 linear of order 4 ρ14 1 -1 1 -1 -1 1 i 1 -1 1 -1 i 1 -i -i -1 -i i i -i 1 -1 -1 1 -i i linear of order 4 ρ15 1 -1 1 -1 -1 1 -i 1 -1 -1 1 -i -1 i i 1 -i i 1 1 i i -i -i -1 -1 linear of order 4 ρ16 1 -1 1 -1 -1 1 i 1 -1 1 -1 i 1 -i -i -1 -i i -i i -1 1 1 -1 i -i linear of order 4 ρ17 2 2 2 2 2 2 0 -2 -2 2 2 0 -2 0 0 -2 0 0 0 0 0 0 0 0 0 0 orthogonal lifted from D4 ρ18 2 2 2 2 2 2 0 -2 -2 -2 -2 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 orthogonal lifted from D4 ρ19 2 -2 2 -2 -2 2 0 -2 2 -2 2 0 2 0 0 -2 0 0 0 0 0 0 0 0 0 0 orthogonal lifted from D4 ρ20 2 -2 2 -2 -2 2 0 -2 2 2 -2 0 -2 0 0 2 0 0 0 0 0 0 0 0 0 0 symplectic lifted from Q8, Schur index 2 ρ21 4 -4 4 -4 4 -4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 orthogonal lifted from C23⋊C4 ρ22 4 4 4 4 -4 -4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 orthogonal lifted from C23⋊C4 ρ23 4 4 -4 -4 0 0 -2 0 0 0 0 2 0 2 -2 0 0 0 0 0 0 0 0 0 0 0 symplectic lifted from C42.3C4, Schur index 2 ρ24 4 4 -4 -4 0 0 2 0 0 0 0 -2 0 -2 2 0 0 0 0 0 0 0 0 0 0 0 symplectic lifted from C42.3C4, Schur index 2 ρ25 4 -4 -4 4 0 0 2i 0 0 0 0 -2i 0 2i -2i 0 0 0 0 0 0 0 0 0 0 0 complex lifted from C42.C4 ρ26 4 -4 -4 4 0 0 -2i 0 0 0 0 2i 0 -2i 2i 0 0 0 0 0 0 0 0 0 0 0 complex lifted from C42.C4

Smallest permutation representation of (C2×Q8).Q8
On 32 points
Generators in S32
(1 27)(2 32)(3 29)(4 26)(5 31)(6 28)(7 25)(8 30)(9 18)(10 23)(11 20)(12 17)(13 22)(14 19)(15 24)(16 21)
(1 25 5 29)(2 26 6 30)(3 27 7 31)(4 28 8 32)(9 20 13 24)(10 21 14 17)(11 22 15 18)(12 23 16 19)
(1 21 5 17)(2 9 6 13)(3 19 7 23)(4 15 8 11)(10 29 14 25)(12 27 16 31)(18 28 22 32)(20 26 24 30)
(2 22 6 18)(3 29)(4 15 8 11)(7 25)(9 32 13 28)(10 23)(14 19)(20 26 24 30)
(1 2 3 4 5 6 7 8)(9 10 11 12 13 14 15 16)(17 18 19 20 21 22 23 24)(25 26 27 28 29 30 31 32)

G:=sub<Sym(32)| (1,27)(2,32)(3,29)(4,26)(5,31)(6,28)(7,25)(8,30)(9,18)(10,23)(11,20)(12,17)(13,22)(14,19)(15,24)(16,21), (1,25,5,29)(2,26,6,30)(3,27,7,31)(4,28,8,32)(9,20,13,24)(10,21,14,17)(11,22,15,18)(12,23,16,19), (1,21,5,17)(2,9,6,13)(3,19,7,23)(4,15,8,11)(10,29,14,25)(12,27,16,31)(18,28,22,32)(20,26,24,30), (2,22,6,18)(3,29)(4,15,8,11)(7,25)(9,32,13,28)(10,23)(14,19)(20,26,24,30), (1,2,3,4,5,6,7,8)(9,10,11,12,13,14,15,16)(17,18,19,20,21,22,23,24)(25,26,27,28,29,30,31,32)>;

G:=Group( (1,27)(2,32)(3,29)(4,26)(5,31)(6,28)(7,25)(8,30)(9,18)(10,23)(11,20)(12,17)(13,22)(14,19)(15,24)(16,21), (1,25,5,29)(2,26,6,30)(3,27,7,31)(4,28,8,32)(9,20,13,24)(10,21,14,17)(11,22,15,18)(12,23,16,19), (1,21,5,17)(2,9,6,13)(3,19,7,23)(4,15,8,11)(10,29,14,25)(12,27,16,31)(18,28,22,32)(20,26,24,30), (2,22,6,18)(3,29)(4,15,8,11)(7,25)(9,32,13,28)(10,23)(14,19)(20,26,24,30), (1,2,3,4,5,6,7,8)(9,10,11,12,13,14,15,16)(17,18,19,20,21,22,23,24)(25,26,27,28,29,30,31,32) );

G=PermutationGroup([[(1,27),(2,32),(3,29),(4,26),(5,31),(6,28),(7,25),(8,30),(9,18),(10,23),(11,20),(12,17),(13,22),(14,19),(15,24),(16,21)], [(1,25,5,29),(2,26,6,30),(3,27,7,31),(4,28,8,32),(9,20,13,24),(10,21,14,17),(11,22,15,18),(12,23,16,19)], [(1,21,5,17),(2,9,6,13),(3,19,7,23),(4,15,8,11),(10,29,14,25),(12,27,16,31),(18,28,22,32),(20,26,24,30)], [(2,22,6,18),(3,29),(4,15,8,11),(7,25),(9,32,13,28),(10,23),(14,19),(20,26,24,30)], [(1,2,3,4,5,6,7,8),(9,10,11,12,13,14,15,16),(17,18,19,20,21,22,23,24),(25,26,27,28,29,30,31,32)]])

Matrix representation of (C2×Q8).Q8 in GL6(𝔽17)

 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 16 0 0 0 0 0 0 16
,
 16 0 0 0 0 0 0 16 0 0 0 0 0 0 4 0 0 0 0 0 0 13 0 0 0 0 0 0 4 0 0 0 0 0 0 13
,
 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 16 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 16 0
,
 4 0 0 0 0 0 0 13 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 16 0
,
 0 16 0 0 0 0 16 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 13 0 0 0 0 0 0 4 0 0

G:=sub<GL(6,GF(17))| [1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,16,0,0,0,0,0,0,16],[16,0,0,0,0,0,0,16,0,0,0,0,0,0,4,0,0,0,0,0,0,13,0,0,0,0,0,0,4,0,0,0,0,0,0,13],[1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,16,0,0,0,0,0,0,0,0,16,0,0,0,0,1,0],[4,0,0,0,0,0,0,13,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,16,0,0,0,0,1,0],[0,16,0,0,0,0,16,0,0,0,0,0,0,0,0,0,13,0,0,0,0,0,0,4,0,0,1,0,0,0,0,0,0,1,0,0] >;

(C2×Q8).Q8 in GAP, Magma, Sage, TeX

(C_2\times Q_8).Q_8
% in TeX

G:=Group("(C2xQ8).Q8");
// GroupNames label

G:=SmallGroup(128,126);
// by ID

G=gap.SmallGroup(128,126);
# by ID

G:=PCGroup([7,-2,2,-2,2,2,-2,-2,56,85,120,758,352,1466,521,248,2804,4037]);
// Polycyclic

G:=Group<a,b,c,d,e|a^2=b^4=d^4=1,c^2=b^2,e^2=a*b^-1*d^2,d*b*d^-1=a*b=b*a,e*c*e^-1=a*c=c*a,a*d=d*a,e*a*e^-1=a*b^2,c*b*c^-1=b^-1,b*e=e*b,c*d=d*c,e*d*e^-1=c*d^-1>;
// generators/relations

Export

׿
×
𝔽


text:
×

Hey adding a favourite button for questions we have already done...so that we can remember them in future and revise them might be a good idea

Note by Srinath Reddy
4 years, 4 months ago

Sort by:

Hi Srinath,

This is an interesting idea, and one that we have talked about sometimes here at Brilliant Headquarters. We already have some functionality that lets you reproduce the desired outcomes, but letting students create a virtual "notebook" of their favorite problems might happen in the future.

Right now, you can use the Solutions tab on the home page to see your answer and solutions to problems you have tried previously. Alternatively, if you create a Shared Problem, it will be permanently stored to your Shared Problems tab, and you can revisit it there. This also allows you to challenge your friends with problems you have enjoyed, and introduce them to Brilliant! · 4 years, 4 months ago

I agree, I like this idea! · 4 years, 4 months ago

yeah!! · 4 years, 4 months ago

Yeah ! A favorite buttom is a great idea...... · 4 years, 4 months ago

Excellent thinking!!!!!! · 4 years, 4 months ago

×


text:
# What is lim_(n→∞) ∫_(-∞)^∞〖〖 x〗^n e^(-n|x|) dm 〗?

#### Jack

##### New member
What is lim_(n→∞) ∫_(-∞)^∞〖〖 x〗^n e^(-n|x|) dm 〗?

What is lim_(n→∞) ∫_(-∞)^∞〖〖 x〗^n e^(-n|x|) dm 〗?

Last edited:

#### Sudharaka

##### Well-known member
MHB Math Helper
Re: What is lim_(n→∞) ∫_(-∞)^∞〖〖 x〗^n e^(-n|x|) dm 〗?

What is lim_(n→∞) ∫_(-∞)^∞〖〖 x〗^n e^(-n|x|) dm 〗?
Hi Jack,

I suggest you should learn some LaTeX before posting questions since the characters that you use makes it difficult to understand what your question is. We have a nice collection of threads that you can use to learn LaTeX.

$\lim_{n\rightarrow\infty}\int_{-\infty}^{\infty}\left|x\right|^{n} e^{-n|x|}\,dx$

Kind Regards,
Sudharaka.

#### Jack

##### New member
Re: What is lim_(n→∞) ∫_(-∞)^∞〖〖 x〗^n e^(-n|x|) dm 〗?

Hi Jack,

I suggest you should learn some LaTeX before posting questions since the characters that you use makes it difficult to understand what your question is. We have a nice collection of threads that you can use to learn LaTeX.

$\lim_{n\rightarrow\infty}\int_{-\infty}^{\infty}\left|x\right|^{n} e^{-n|x|}\,dx$

Kind Regards,
Sudharaka.
YEs。

#### Sudharaka

##### Well-known member
MHB Math Helper
Re: What is lim_(n→∞) ∫_(-∞)^∞〖〖 x〗^n e^(-n|x|) dm 〗?

$\int_{-\infty}^{\infty}\left|x\right|^{n} e^{-n|x|}\,dx=2\int_{0}^{\infty}x^{n} e^{-nx}\,dx$

Substitute $$y=nx$$ and we get,

\begin{eqnarray}

\int_{-\infty}^{\infty}\left|x\right|^{n} e^{-n|x|}\,dx&=&\frac{2}{n^{n+1}}\int_{0}^{\infty}y^{n} e^{-y}\,dy\\

&=&\frac{2}{n^{n+1}}\Gamma(n+1)

\end{eqnarray}

I am assuming that $$n$$ is a positive integer. Then,

$\int_{-\infty}^{\infty}\left|x\right|^{n} e^{-n|x|}\,dx=\frac{2\Gamma(n+1)}{n^{n+1}}=\frac{2n!}{n^{n+1}}$

It could be shown that, $$\displaystyle\lim_{n\rightarrow \infty}\frac{2n!}{n^{n+1}}=0$$.

$\therefore \lim_{n\rightarrow \infty}\int_{-\infty}^{\infty}\left|x\right|^{n} e^{-n|x|}\,dx=\lim_{n\rightarrow \infty}\frac{2n!}{n^{n+1}}=0$


text:
# Which has optimum performance? raw core or multithreaded

Let's say there's a single process performed in the machine which utilizes all available processors (whether physical or logical processors). The process use 100% processor utilization most of the time on all processors.

Which machine will perform better?

• Machine with 2 cores, 1 thread per core (2 physical processors); or the
• Machine with 2 cores, 2 threads per core (4 logical processors)

This is assuming everything (memory, clock speed, etc) is the same and the only thing that differ is the number of threads.

My initial thoughts would be that the former -- machine with 2 raw cores (1 thread) -- will perform better because it doesn't have context switching. Whereas the latter would have overhead on the context switching.

Which machine will perform better?

• Are the threads CPU-bound, or do they spend time waiting for I/O or other resources? Feb 9 at 22:59
• @Pseudonym assuming a generic process, they spend some amount of time waiting for I/O or other resources Feb 9 at 23:02
• but most of the time, processors reach 100% utilization Feb 9 at 23:11
• You don't let on whether to assume said single generic process multi-threaded or not. Feb 10 at 8:15
– D.W.
Feb 15 at 23:30

There's no real way to answer this without a lot of details about both the code to be executed, and the micro-architecture of the CPU executing the code.

A CPU that can execute multiple threads per core will typically start with a pool of instructions, decoded and ready to execute. As instructions enter the pool, a scoreboard1 gets updated to reflect inputs to an instruction, execution resource(s) needed by that instruction, and the output of the instruction.

So you might have an instruction like add r0, r1, r2, meaning add register 0 to register 1 and put the result in register 2. The inputs are registers 0 and 1, the execution resource needed is an integer adder, and the output is register 2.

Then there's a scheduler that looks at the resource usage and tries to find instructions that don't conflict, and each clock cycle, tries to find as many of those as possible to execute. As it does so, it updates the scoreboard so the next clock cycle, it'll know what resources are in use now.

That all leads to the basic question: given the parallel resources provided by this CPU, and the instructions in the streams to be executed, what is the average level of conflict between instructions?

The drastically simplified answer is that more often than not, executing two independent streams of instructions will result in more instructions that can execute with fewer conflicts, so overall speed will increase much more often than not. It's rarely a question of which is faster--only of how much speed you'll gain by executing more threads in parallel, and whether that gain is enough to justify the extra labor to make that work, or whether you'd have gained more by expending more the CPU budget on other things that could have made an even bigger difference (e.g., bigger cache, better branch prediction, etc.)

### Goal

There's also room for a bit of question about your goal here. A single core executing two threads will typically execute each thread a little slower than that thread would execute on a core by itself. On the other hand, the overall throughput of the system will be somewhat greater than if you ran only one thread at a time.

For example, if you had a CPU that was split almost perfectly between two threads, each might run at 60% of the speed it would if it was the only thread running on a core.

So, if you really care almost exclusively about the performance of one thread, then running only one thread per core may well improve the speed of a thread when it is running.

At the same time, if you have two threads each running at 60% the speed it would on its own, your overall speed is 120% of what it would be with each thread running on its own, meaning you're getting about 20% more work done per unit time.

In a game (for one example) it's pretty common to have one thread that really matters, so you really want to optimize performance for one thread. If that's your case, you probably only want one thread per core.

On the other hand, with something like a server you often have lots of requests happening all the time, and one major concern is maximizing overall throughput. In such a case, more threads per core can make a lot more sense (but also note that total throughput isn't usually the only concern even in this case).

### CPU Utilization

Since "CPU Utilization" was mentioned in a comment, I'll comment on it a bit as well. Generally speaking, when an operating system reports something like percentage of CPU utilization, it's basically irrelevant to questions like this.

An OS is basically just reporting what percentage of CPUs have threads assigned to execute on them at any given time. For example, if a single-threaded CPU executes an instruction to read from main memory, it could easily take 50-100 clock cycles to execute a single instruction. According to the OS, that's keeping the CPU 100% busy for those clock cycles--but most of the CPU's actual resources would be available, so it could perfectly well execute other instructions during that time.

1. Well, the early versions were called "scoreboards". More recently there are more complex structures with other names, but I'm going to call all of them scoreboards to keep things simple.
• These make a lot of sense. Unfortunately though, I can not answer the question: What is the average level of conflict between instructions? This is something unknown especially if you are not the developer of the software and just installed it. :( That's why the question I posted here is more of a very generic standpoint. Feb 10 at 10:28

The machine with 2 threads per core will have always have more throughput than a machine with a single thread per core. A machine with more threads will be able to execute more threads concurrently and it reduces the idle time spent by a CPU's resource (example: Arithmetic Logic Unit). It does this by switching to a different thread if the current thread is stalled.

In the unlikely event that there are no threads to switch, there will neither be a performance gain nor a performance penalty since it uses the single thread and there is no context switching overhead. So a machine with more threads per core can never be slower than a machine with lesser threads per core.


text:
Vol. 295, No. 1, 2018

 Recent Issues Vol. 297: 1 Vol. 296: 1  2 Vol. 295: 1  2 Vol. 294: 1  2 Vol. 293: 1  2 Vol. 292: 1  2 Vol. 291: 1  2 Vol. 290: 1  2 Online Archive Volume: Issue:
 The Journal Subscriptions Editorial Board Officers Special Issues Submission Guidelines Submission Form Contacts Author Index To Appear ISSN: 0030-8730 Other MSP Journals
The growth rate of the tunnel number of m-small knots

Tsuyoshi Kobayashi and Yo’av Rieck

Vol. 295 (2018), No. 1, 57–101
Abstract

In a previous paper, we defined the growth rate of the tunnel number of knots, an invariant that measures the asymptotic behavior of the tunnel number under connected sum. In this paper we calculate the growth rate of the tunnel number of m-small knots in terms of their bridge indices.

Keywords
knots, 3-manifolds, Heegaard splittings, tunnel number, growth rate
Mathematical Subject Classification 2010
Primary: 57M25, 57M99


text:
Ask an Expert
Question

In replicate analyses, the carbohydrate content of a glycoprotein ( a protein with sugars attached to it) is found to be 12.6, 11.9, 13.0, 12.7, and 12.5 g of carbohydrate per 100 g of protein. Find the 90% confidence intervals for the carbohydrate content.

Confidence intervals
ANSWERED
asked 2020-12-03
In replicate analyses, the carbohydrate content of a glycoprotein ( a protein with sugars attached to it) is found to be 12.6, 11.9, 13.0, 12.7, and 12.5 g of carbohydrate per 100 g of protein. Find the 90% confidence intervals for the carbohydrate content.

Answers (1)

2020-12-04

Step 1 Data values are given population standard deviation is not known hence we use T Interval. Sample size $$\displaystyle{\left({n}\right)}={5}$$ Degrees of freedom(df): $$\displaystyle{d}{f}={n}-{1}$$
$$\displaystyle={5}-{1}$$
$$\displaystyle={4}$$ Confidence level $$=0.90$$ Use T table or excel command =T.INV.2T $$\displaystyle{\left({1}-{0.90},{4}\right)}$$ to get critical value Critical value $$\displaystyle{\left({t}_{{{c}}}\right)}={2.132}$$

$$\begin{array}{|c|c|} \hline & X & (X−12.54)^{2} \\ \hline & 12.6 & 0.0036 \\ \hline & 11.9 & 0.4096 \\ \hline & 13 & 0.2116 \\ \hline & 12.7 & 0.0256 \\ \hline & 12.5 & 0.0016 \\ \hline Total & 62.7 & 0.652 \\ \hline \end{array}$$

Sample mean: $$\displaystyle\overline{{{x}}}={\frac{{{\sum_{{{i}={1}}}^{{5}}}\xi}}{{{n}}}}$$
$$\displaystyle={\frac{{{62.7}}}{{{5}}}}$$
$$\displaystyle{12.54}$$ Sample standard deviation: $$\displaystyle{s}=\sqrt{{{\frac{{{\sum_{{{i}={1}}}^{{5}}}{\left({x}_{{{i}}}-\overline{{{x}}}\right)}^{{{2}}}}}{{{n}-{1}}}}}}$$
$$\displaystyle=\sqrt{{{\frac{{{\sum_{{{i}={1}}}^{{5}}}{\left({x}_{{{i}}}-{12.54}\right)}^{{{2}}}}}{{{5}-{1}}}}}}$$
$$\displaystyle=\sqrt{{{\frac{{{0.652}}}{{{4}}}}}}$$
$$\displaystyle=\sqrt{{{0.163}}}$$
$$\displaystyle={0.403733}$$ Step 3 $$\displaystyle=\overline{{{x}}}\pm{t}_{{{c}}}{\frac{{{s}}}{{\sqrt{{{n}}}}}}$$
$$\displaystyle={12.54}\pm{2.132}\times{\frac{{{0.403733}}}{{\sqrt{{{5}}}}}}$$
$$\displaystyle={12.54}\pm{2.132}\times{0.180555}$$
$$\displaystyle={12.54}\pm{0.3849}$$
$$\displaystyle={\left({12.54}-{0.3849},{12.54}+{0.3849}\right)}$$
$$\displaystyle={\left({12.1551},{12.9249}\right)}$$

Step 4 Answer: $$90\%$$ confidence interval is ( 12.16, 12.92 )

expert advice

...