In this paper, we study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only $k$ out of $d$ attributes per instance for prediction, which was proved to be NP-hard. Previous work gave polynomial-time algorithms assuming the data matrix satisfies the linear independence of features, the compatibility condition, or the restricted isometry property. We introduce a new polynomial-time algorithm, which significantly improves previous regret bounds (Ito et al., 2017) under the compatibility condition that is weaker than the other two assumptions. The improvements benefit from a tighter convergence rate of the $\ell_1$-norm error of our estimators. Our algorithm leverages the well-studied Dantzig Selector, but importantly with several novel techniques, including an algorithm-dependent sampling scheme for estimating the covariance matrix, an adaptive parameter tuning scheme, and a batching online Newton step with careful initializations. We also give novel and non-trivial analyses, including an induction method for analyzing the $\ell_1$-norm error, careful analyses on the covariance of non-independent random variables, and a decomposition on the regret. We further extend our algorithm to OSLR with additional observations where the algorithms can observe additional $k_0$ attributes after each prediction, and improve previous regret bounds (Kale et al., 2017; Ito et al., 2017).

In this paper, we study the mistake bound of online kernel learning on a budget. We propose a new budgeted online kernel learning model, called Ahpatron, which significantly improves the mistake bound of previous work and resolves an open problem related to upper bounds of hypothesis space constraints. We first present an aggressive variant of Perceptron, named AVP, a model without budget, which uses an active updating rule. Then we design a new budget maintenance mechanism, which removes a half of examples, and projects the removed examples onto a hypothesis space spanned by the remaining examples. Ahpatron adopts the above mechanism to approximate AVP. Theoretical analyses prove that Ahpatron has tighter mistake bounds, and experimental results show that Ahpatron outperforms the state-of-the-art algorithms on the same or a smaller budget.

In this paper, we improve the kernel alignment regret bound for online kernel learning in the regime of the Hinge loss function. Previous algorithm achieves a regret of O((A_TT ln T)^{1/4}) at a computational complexity (space and per-round time) of O((A_TT ln T)^{1/2}), where A_T is called kernel alignment. We propose an algorithm whose regret bound and computational complexity are better than previous results. Our results depend on the decay rate of eigenvalues of the kernel matrix. If the eigenvalues of the kernel matrix decay exponentially, then our algorithm enjoys a regret of O((A_T)^{1/2}) at a computational complexity of O((ln T)^2). Otherwise, our algorithm enjoys a regret of O((A_TT)^{1/4}) at a computational complexity of O((A_TT)^{1/2}). We extend our algorithm to batch learning and obtain a O(T^{-1}(E[A_T])^{1/2}) excess risk bound which improves the previous O(T^{-1/2}) bound.

The trade-off between regret and computational cost is a fundamental problem for online kernel regression, and previous algorithms worked on the trade-off can not keep optimal regret bounds at a sublinear computational complexity. In this paper, we propose two new algorithms, AOGD-ALD and NONS-ALD, which can keep nearly optimal regret bounds at a sublinear computational complexity, and give sufficient conditions under which our algorithms work. Both algorithms dynamically maintain a group of nearly orthogonal basis used to approximate the kernel mapping, and keep nearly optimal regret bounds by controlling the approximate error. The number of basis depends on the approximate error and the decay rate of eigenvalues of the kernel matrix. If the eigenvalues decay exponentially, then AOGD-ALD and NONS-ALD separately achieves a regret of $O(\sqrt{L(f)})$ and $O(\mathrm{d}_{\mathrm{eff}}(\mu)\ln{T})$ at a computational complexity in $O(\ln^2{T})$. If the eigenvalues decay polynomially with degree $p\geq 1$, then our algorithms keep the same regret bounds at a computational complexity in $o(T)$ in the case of $p>4$ and $p\geq 10$, respectively. $L(f)$ is the cumulative losses of $f$ and $\mathrm{d}_{\mathrm{eff}}(\mu)$ is the effective dimension of the problem. The two regret bounds are nearly optimal and are not comparable.

Regret bounds of online kernel selection in a finite kernel set have been well studied, having at least an order O( √ NT) of magnitude after T rounds, where N is the number of candidate kernels. But it is still an unsolved problem to achieve sublinear regret bounds of online kernel selection in a continuous kernel space under different learning frameworks. In this paper, to represent different learning frameworks of online kernel selection, we divide online kernel selection approaches in a continuous kernel space into two categories according to the order of selection and training at each round. Then we construct a surrogate hypothesis space that contains all the candidate kernels with bounded norms and inner products, representing the continuously varying hypothesis space. Finally, we decompose the regrets of the proposed online kernel selection categories into different types of instantaneous regrets in the surrogate hypothesis space, and derive optimal regret bounds of order O( √ T) of magnitude under mild assumptions, independent of the cardinality of the continuous kernel space. Empirical studies verified the correctness of the theoretical regret analyses.

Model selection is one of the fundamental problems in kernel-based algorithms, which is commonly done by minimizing an estimation of generalization error. The notion of stability and cross-validation (CV) error of learning machines consists of two widely used tools for analyzing the generalization performance. However, there are some disadvantages to both tools when applied for model selection: 1) the stability of learning machines is not practical due to the difficulty of the estimation of its specific value and 2) the CV-based estimate of generalization error usually has a relatively high variance, so it is prone to overfitting. To overcome these two limitations, we present a novel notion of kernel stability (KS) for deriving the generalization error bounds and variance bounds of CV and provide an effective approach to the application of KS for practical model selection. Unlike the existing notions of stability of the learning machine, KS is defined on the kernel matrix; hence, it can avoid the difficulty of the estimation of its value. We manifest the relationship between the KS and the popular uniform stability of the learning algorithm, and further propose several KS-based generalization error bounds and variance bounds of CV. By minimizing the proposed bounds, we present two novel KS-based criteria that can ensure good performance. Finally, we empirically analyze the performance of the proposed criteria on many benchmark data, which demonstrates that our KS-based criteria are sound and effective.

Neural networks with random weights (NNRWs) which randomly assign weights to new hidden nodes, provide a new and promising stochastic approach for the research of neural networks, and have been proved to enjoy the universal approximation property. However, the design of existing learning algorithms for NNRWs is only based on the square loss function, which hinders the development of NNRWs. For strictly convex and strongly convex loss functions, it is unclear how to design learning algorithms, and what the convergence rates are. In this paper, we answer the questions affirmatively. First, we propose a new supervisory mechanism for constructing NNRWs, and prove the universal approximation property. Then we design a new learning algorithm and analyze the convergence rates of the algorithm, based on which the time complexities are also analyzed. To be specific, the proposed algorithm enjoys sublinear convergence for smooth and strictly convex loss functions, and linear convergence for smooth and strongly convex loss functions. Finally, experimental results on several real-world datasets verify the convergence rates of the algorithm with different loss functions.

Deep learning has achieved great success in many fields, but they still lack theoretical understandings. Although some recent theoretical and experimental results have investigated the representation power of deep learning, little effort has been devoted to analyzing the generalization ability of deep learning. In this paper, we analyze deep neural networks from a kernel perspective and use kernel methods to investigate the effect of the implicit regularization introduced by gradient descent on the generalization ability. Firstly, we argue that the multi-layer nonlinear feature transformation in deep neural networks is equivalent to a kernel feature mapping and analyze our point from the perspective of the unique mathematical advantages of kernel methods and the method of constructing multi-layer kernel machines, respectively. Secondly, using the representer theorem, we analyze the decision boundary of deep neural networks and prove that the last hidden layers of deep neural networks converge to nonlinear SVMs. Systematical experiments demonstrate that the decision boundaries of neural networks converge to those of nonlinear SVMs.

Online kernel selection in continuous kernel space is more complex than that in discrete kernel set. But existing online kernel selection approaches for continuous kernel spaces have linear computational complexities at each round with respect to the current number of rounds and lack sublinear regret guarantees due to the continuously many candidate kernels. To address these issues, we propose a novel hypothesis sketching approach to online kernel selection in continuous kernel space, which has constant computational complexities at each round and enjoys a sublinear regret bound. The main idea of the proposed hypothesis sketching approach is to maintain the orthogonality of the basis functions and the prediction accuracy of the hypothesis sketches in a time-varying reproducing kernel Hilbert space. We first present an efficient dependency condition to maintain the basis functions of the hypothesis sketches under a computational budget. Then we update the weights and the optimal kernels by minimizing the instantaneous loss of the hypothesis sketches using the online gradient descent with a compensation strategy. We prove that the proposed hypothesis sketching approach enjoys a regret bound of order O(√T) for online kernel selection in continuous kernel space, which is optimal for convex loss functions, where T is the number of rounds, and reduces the computational complexities at each round from linear to constant with respect to the number of rounds. Experimental results demonstrate that the proposed hypothesis sketching approach significantly improves the efficiency of online kernel selection in continuous kernel space while retaining comparable predictive accuracies.

Cross-validation (CV) is a widely adopted approach for selecting the optimal model. However, the computation of empirical cross-validation error (CVE) has high complexity due to multiple times of learner training. In this paper, we develop a novel approximation theory of CVE and present an approximate approach to CV based on the Bouligand influence function (BIF) for kernel-based algorithms. We first represent the BIF and higher order BIFs in Taylor expansions, and approximate CV via the Taylor expansions. We then derive an upper bound of the discrepancy between the original and approximate CV. Furthermore, we provide a novel computing method to calculate the BIF for general distribution, and evaluate BIF criterion for sample distribution to approximate CV. The proposed approximate CV requires training on the full data set only once and is suitable for a wide variety of kernel-based algorithms. Experimental results demonstrate that the proposed approximate CV is sound and effective.

Kernel selection is of fundamental importance for the generalization of kernel methods. This article proposes an approximate approach for kernel selection by exploiting the approximability of kernel selection and the computational virtue of kernel matrix approximation. We define approximate consistency to measure the approximability of the kernel selection problem. Based on the analysis of approximate consistency, we solve the theoretical problem of whether, under what conditions, and at what speed, the approximate criterion is close to the accurate one, establishing the foundations of approximate kernel selection. We introduce two selection criteria based on error estimation and prove the approximate consistency of the multilevel circulant matrix (MCM) approximation and Nyström approximation under these criteria. Under the theoretical guarantees of the approximate consistency, we design approximate algorithms for kernel selection, which exploits the computational advantages of the MCM and Nyström approximations to conduct kernel selection in a linear or quasi-linear complexity. We experimentally validate the theoretical results for the approximate consistency and evaluate the effectiveness of the proposed kernel selection algorithms.

We propose a framework for analyzing and comparing distributions without imposing any parametric assumptions via empirical likelihood methods. Our framework is used to study two fundamental statistical test problems: the two-sample test and the goodness-of-fit test. For the two-sample test, we need to determine whether two groups of samples are from different distributions; for the goodness-of-fit test, we examine how likely it is that a set of samples is generated from a known target distribution. Specifically, we propose empirical likelihood ratio (ELR) statistics for the two-sample test and the goodness-of-fit test, both of which are of linear time complexity and show higher power (i.e., the probability of correctly rejecting the null hypothesis) than the existing linear statistics for high-dimensional data. We prove the nonparametric Wilks’ theorems for the ELR statistics, which illustrate that the limiting distributions of the proposed ELR statistics are chi-square distributions. With these limiting distributions, we can avoid bootstraps or simulations to determine the threshold for rejecting the null hypothesis, which makes the ELR statistics more efficient than the recently proposed linear statistic, finite set Stein discrepancy (FSSD). We also prove the consistency of the ELR statistics, which guarantees that the test power goes to 1 as the number of samples goes to infinity. In addition, we experimentally demonstrate and theoretically analyze that FSSD has poor performance or even fails to test for high-dimensional data. Finally, we conduct a series of experiments to evaluate the performance of our ELR statistics as compared to state-of-the-art linear statistics.

Kernel selection is fundamental to the generalization performance of kernel-based learning algorithms. Approximate kernel selection is an efficient kernel selection approach that exploits the convergence property of the kernel selection criteria and the computational virtue of kernel matrix approximation. The convergence property is measured by the notion of approximate consistency. For the existing Nyström approximations, whose sampling distributions are independent of the specific learning task at hand, it is difficult to establish the strong approximate consistency. They mainly focus on the quality of the low-rank matrix approximation, rather than the performance of the kernel selection criterion used in conjunction with the approximate matrix. In this paper, we propose a novel Nyström approximate kernel selection algorithm by customizing a criterion-driven adaptive sampling distribution for the Nyström approximation, which adaptively reduces the error between the approximate and accurate criteria. We theoretically derive the strong approximate consistency of the proposed Nyström approximate kernel selection algorithm. Finally, we empirically evaluate the approximate consistency of our algorithm as compared to state-of-the-art methods.

Online kernel selection is a more complex problem compared with offline kernel selection, which intermixes training and selection at each round and requires a sublinear regret and low computational complexities. But existing online kernel selection approaches have at least linear time and space complexities at each round with respect to the number of rounds, or lack sublinear regret guarantees for an uncountably infinite number of candidate kernels. To address these issues, we propose a novel online kernel selection approach using tensor sketching, which has constant computational complexities at each round and enjoys a sublinear regret bound for an uncountably infinite number of candidate kernels. We represent the data using the tensor products and construct data sketches using the Taylor series and the Count Sketch matrices, which yields a sketched reproducing kernel Hilbert space (SRKHS). Then we update the optimal kernels and the hypotheses using online gradient descent in SRKHS. We prove that the kernel corresponding to SRKHS satisfies the reproducing property, the hypotheses in SRKHS are convex with respect to the kernel parameter, and the proposed online kernel selection approach in SRKHS enjoys a regret bound of order $O(\sqrtT )$ for an uncountably infinite number of candidate kernels, which is optimal for a convex loss function, where T is the number of rounds. By the fast Fourier transform, the hypotheses in SRKHS can be computed in a quasilinear time complexity and a logarithmic space complexity with respect to the sketch size at each round, where the sketch size is a constant. Experimental results demonstrate that our online kernel selection approach is more accurate and efficient for online kernel learning on high dimension data.

Online kernel ridge regression via existing sampling approaches, which aim at approximating the kernel matrix as accurately as possible, is independent of learning and has a cubic time complexity with respect to the sampling size for updating hypothesis. In this paper, we propose a new online kernel ridge regression via an incremental predictive sampling approach, which has the nearly optimal accumulated loss and performs efficiently at each round. We use the estimated ridge leverage score of the labeled matrix, which depends on the accumulated loss at each round, to construct the predictive sampling distribution, and use this sampling probability for the Nyströ m approximation. To avoid calculating the inverse of the approximated kernel matrix directly, we use the Woodbury formula to accelerate the computation and adopt the truncated incremental singular value decomposition to update the generalized inverse of the intersection matrix. Our online kernel ridge regression has a time complexity of $O(tmk+k^3 )$ for updating hypothesis at round t, where k is the truncated rank of the intersection matrix, and enjoys a regret bound of order $O(\sqrtT )$, where T is the time horizon. Experimental results show that the proposed online kernel ridge regression via the incremental predictive sampling performs more stably and efficiently than the online kernel ridge regression via existing online sampling approaches that directly approximate the kernel matrix.

Randomized sketching has been used in offline kernel learning, but it cannot be applied directly to online kernel learning due to the lack of incremental maintenances for randomized sketches with regret guarantees. To address these issues, we propose a novel incremental randomized sketching approach for online kernel learning, which has efficient incremental maintenances with theoretical guarantees. We construct two incremental randomized sketches using the sparse transform matrix and the sampling matrix for kernel matrix approximation, update the incremental randomized sketches using rank-$1$ modifications, and construct an time-varying explicit feature mapping for online kernel learning. We prove that the proposed incremental randomized sketching is statistically unbiased for the matrix product approximation, obtains a $1 + \epsilon$ relative-error bound for the kernel matrix approximation, enjoys a sublinear regret bound for online kernel learning, and has constant time and space complexities at each round for incremental maintenances. Experimental results demonstrate that the incremental randomized sketching achieves a better learning performance in terms of accuracy and efficiency even in adversarial environments.

We study kernel selection for online kernel learning, also known as online kernel selection which can be treated as a sequential decision problem and thus must balance the regret and the time complexity. Existing online kernel selection approaches via expert advice and classical adversarial bandit model can not meet the issue. In this work, we propose a novel grouped adversarial bandit solution to the problem. We first correspond each candidate kernel to a basic arm of an adversarial bandit problem. Then, all of the kernels are divided into several groups where each group is abstracted as a super arm. At each round, we choose a super arm and a basic kernel within the selected super arm, and make prediction by an online kernel learning algorithm. Besides, we introduce a Bernoulli random variable to decide whether to choose all of the rest super arms. Theoretical analysis shows the proposed approach balances the regret and the time complexity explicitly, which could enjoy better pseudo-regret and high probability regret bound than classical adversarial bandit model and lighter time complexity than expert advice model. Experimental results on benchmark datasets verify that the proposed approach balances the efficiency and effectiveness better.

A sparse representation of Support Vector Machines (sparse SVMs) is desirable for many applications. However, for large-scale problems with high-dimensional features solving sparse SVMs remains a challenging problem, and most of the existing work are heuristic in that there are no performance guarantees and can't effectively control the trade-off between the sparsity and the accuracy of the decision hyperplane. To address this issue, we propose a new method for via relaxation and rounding, which obtains (ε,δ)-approximate solution in Õ(n/εδ) time with probability at least 1-δ. Such regularization explicitly penalizes parameters different from zero with no further restrictions. We first show that learning sparse SVMs with ℓ0norm can be reformulated as an exactly Boolean program by introducing Boolean variables to each parameter. With dual and Boolean relaxation, this Boolean problem can be relaxed as a convex programming. For the ε-approximate solution of this convex programming, we get a feasible solution of the original problem without loss accuracy by a determined rounding. We analyze the proposed method in details and give a provable guarantee which is missing from the previous work. Experimental results on both synthetic data and real world data support our theoretical results and verify the validity of the proposed method.

Kernel selection aims at choosing an appropriate kernel function for kernel-based learning algorithms to avoid either underfitting or overfitting of the resulting hypothesis. One of the main problems faced by kernel selection is the evaluation of the goodness of a kernel, which is typically difficult and computationally expensive. In this paper, we propose a randomized kernel selection approach to evaluate and select the kernel with the spectra of the specifically designed multilevel circulant matrices (MCMs), which is statistically sound and computationally efficient. Instead of constructing the kernel matrix, we construct the randomized MCM to encode the kernel function and all data points together with labels. We build a one-to-one correspondence between all candidate kernel functions and the spectra of the randomized MCMs by Fourier transform. We prove the statistical properties of the randomized MCMs and the randomized kernel selection criteria, which theoretically qualify the utility of the randomized criteria in kernel selection. With the spectra of the randomized MCMs, we derive a series of randomized criteria to conduct kernel selection, which can be computed in log-linear time and linear space complexity by fast Fourier transform (FFT). Experimental results demonstrate that our randomized kernel selection criteria are significantly more efficient than the existing classic and widely-used criteria while preserving similar predictive performance.

Online kernel selection is critical to online kernel learning, but most of the existing online kernel learning methods ignore the online kernel selection process, and instead they empirically preset and fix a kernel or adjust kernel parameters by gradient descent, which is sensitive to the initial setting and has no theoretical guarantee. In this work, we propose an online kernel selection wrapper via the multi-armed bandit model, which can select a kernel at each round from a set of candidate kernels with theoretical guarantee and can be applied to any online kernel learning model. Specifically, the wrapper consists of two layers. In the outer layer, the wrapper corresponds each candidate kernel to an arm of the multi-armed bandit model, and chooses an arm according to the probability distribution maintained by the model at each round. In the inner layer, the wrapper updates the probability distribution according the loss of the selected arm, which is incurred by the prediction of the online kernel learning algorithm. We propose a new online kernel selection regret to measure the performance of the proposed wrapper, and prove that the proposed wrapper enjoys a sub-linear expected online kernel selection regret with respect to the cumulative loss of the optimal kernel among the candidates kernels. Experimental results on benchmark datasets demonstrate the effectiveness of the proposed wrapper.

Although the incremental Nyström method has been used in kernel approximation, it is not suitable for online kernel learning due to the cubic time complexity and the lack of theoretical guarantees. In this paper, we propose a novel incremental Nyström method, which is in a linear time complexity with respect to the sampling size at each round, and enjoys a sublinear regret bound for online kernel learning. We construct the intersection matrix using the ridge leverage score estimator, compute the rank-k approximation of the intersection matrix incrementally via the incremental singular value decomposition, and recalculate the generalized inverse matrix periodically. When applying the proposed incremental Nyström method to online kernel learning, we approximate the kernel matrix using the updated generalized inverse matrix at each round, and formulate the explicit feature mapping by the singular value decomposition of the approximated kernel matrix, yielding the linear classifier for online kernel learning at each round. Theoretically, we prove that our incremental Nyström method has a (1+ε) relative-error bound for kernel matrix approximation, enjoys a sublinear regret bound using online gradient descent method for online kernel learning, and reduces the time complexity of generalized inverse computation from O(m3) to O(mk) at each round, where m is the sampling size and k is the truncated rank. Experimental results show that the proposed incremental Nyström method is accurate and efficient in kernel matrix approximation and is suitable for online kernel learning.

Cross-validation (CV) is the most widely adopted approach for selecting the optimal model. However, the computation of CV has high complexity due to multiple times of learner training, making it disabled for large scale model selection. In this paper, we present an approximate approach to CV based on the theoretical notion of Bouligand influence function (BIF) and the Nystr\"{o}m method for kernel methods. We first establish the relationship between the theoretical notion of BIF and CV, and propose a method to approximate the CV via the Taylor expansion of BIF. Then, we provide a novel computing method to calculate the BIF for general distribution, and evaluate BIF for sample distribution. Finally, we use the Nystr\"{o}m method to accelerate the computation of the BIF matrix for giving the finally approximate CV criterion. The proposed approximate CV requires training only once and is suitable for a wide variety of kernel methods. Experimental results on lots of datasets how that our approximate CV has no statistical discrepancy with the original CV, but can significantly improve the efficiency.

In contrast to offline kernel selection, online kernel selection must rise to the new challenges of passing the training set once, selecting optimal kernels and updating hypotheses at each round, enjoying a sublinear regret bound for online kernel learning, and requiring a constant maintenance time complexity at each round and an efficient overall time complexity integrated with online kernel learning. However, most of existing online kernel selection approaches can not meet the new challenges. To address this issue, we propose a novel online kernel selection approach via the incremental sketched kernel alignment criterion, which meets all the new challenges. We first define the incremental sketched kernel alignment (ISKA) criterion, which estimates the kernel alignment and can be computed incrementally and efficiently. When applying the proposed ISKA criterion to online kernel selection, we adopt the subclass coherence to maintain the hypothesis space, select the optimal kernel at each round using the median of the ISKA criterion estimates, and update the hypothesis following the online gradient decent method. We prove that the ISKA criterion is an unbiased estimate of the maximum mean discrepancy, enjoys the optimal logarithmic regret bound for online kernel learning, and has a constant maintenance time complexity at each round and a logarithmic overall time complexity integrated with online kernel learning. Empirical studies demonstrate that the proposed online kernel selection approach is computationally efficient while maintaining comparable accuracy for online kernel learning.

The study on generalization performance of ranking algorithms is one of the fundamental issues in ranking learning theory. Although several generalization bounds have been proposed based on different measures, the convergence rates of the existing bounds are usually at most O(√1/n), where n is the size of data set. In this paper, we derive novel generalization bounds for the regularized ranking in reproducing kernel Hilbert space via integral operator of kernel function. We prove that the rates of our bounds are much faster than (√1/n). Specifically, we first introduce a notion of local Rademacher complexity for ranking, called local ranking Rademacher complexity, which is used to measure the complexity of the space of loss functions of the ranking. Then, we use the local ranking Rademacher complexity to obtain a basic generalization bound. Finally, we establish the relationship between the local Rademacher complexity and the eigenvalues of integral operator, and further derive sharp generalization bounds of faster convergence rate.

Kernel learning is a fundamental problem both in recent research and application of kernel methods. Existing kernel learning methods commonly use some measures of generalization errors to learn the optimal kernel in a convex (or conic) combination of prescribed basic kernels. However, the generalization bounds derived by these measures usually have slow convergence rates, and the basic kernels are finite and should be specified in advance. In this paper, we propose a new kernel learning method based on a novel measure of generalization error, called principal eigenvalue proportion (PEP), which can learn the optimal kernel with sharp generalization bounds over the convex hull of a possibly infinite set of basic kernels. We first derive sharp generalization bounds based on the PEP measure. Then we design two kernel learning algorithms for finite kernels and infinite kernels respectively, in which the derived sharp generalization bounds are exploited to guarantee faster convergence rates, moreover, basic kernels can be learned automatically for infinite kernel learning instead of being prescribed in advance. Theoretical analysis and empirical results demonstrate that the proposed kernel learning method outperforms the state-of-the-art kernel learning methods.

Kernel selection is a fundamental problem of kernel-based learning algorithms. In this paper, we propose an approximate approach to automatic kernel selection for regression from the perspective of kernel matrix approximation. We first introduce multilevel circulant matrices into automatic kernel selection, and develop two approximate kernel selection algorithms by exploiting the computational virtues of multilevel circulant matrices. The complexity of the proposed algorithms is quasi-linear in the number of data points. Then, we prove an approximation error bound to measure the effect of the approximation in kernel matrices by multilevel circulant matrices on the hypothesis and further show that the approximate hypothesis produced with multilevel circulant matrices converges to the accurate hypothesis produced with kernel matrices. Experimental evaluations on benchmark datasets demonstrate the effectiveness of approximate kernel selection.

The selection of kernel function which determines the mapping between the input space and the feature space is of crucial importance to kernel methods. Existing kernel selection approaches commonly use some measures of generalization error, which are usually difficult to estimate and have slow convergence rates. In this paper, we propose a novel measure, called eigenvalues ratio (ER), of the tight bound of generalization error for kernel selection. ER is the ration between the sum of the main eigenvalues and that of the tail eigenvalues of the kernel matrix. Defferent from most of existing measures, ER is defined on the kernel matrxi, so it can be estimated easily from the available training data, which makes it usable for kernel selection. We establish tight ER-based generalization error bounds of order $O(\frac{1}{n})$ for several kernel-based methods under certain general conditions, while for most of existing measures, the convergence rate is at most $O(\frac{1}{\sqrt{n}})$. Finally, to guarantee good generalization performance, we propose a novel kernel selection criterion by minimizing the derived tight generalization error bounds. Theoretical analysis and experimental results demonstrate that our kernel selection criterion is a good choice for kernel seletion.

Column-based low-rank matrix approximation is a useful method to analyze and interpret data in machine learning and data mining. However existing methods will face some accuracy and scalability problems when dealing with large-scale data. In this paper we propose a new parallel framework for column-based low-rank matrix approximation based on divide-and-conquer strategy. It consists of three stages: (1) Dividing the original matrix into several small submatrices. (2) Performing column-based low-rank matrix approximation to select columns on each submatrix in parallel. (3) Combining these columns into the final result. We prove that the new parallel framework has (1+ $$\epsilon $$ ) relative-error upper bound. We also show that it is more scalable than existing work. The results of comparison experiments and application in kernel methods demonstrate the effectiveness and efficiency of our method on both synthetic and real world datasets.

Model selection in kernel methods is the problem of choosing an appropriate hypothesis space for kernel-based learning algorithms to avoid either underfitting or overfitting of the resulting hypothesis. One of main problems faced by model selection is how to control the sample complexity when designing the model selection criterion. In this paper, we take balls of reproducing kernel Hilbert spaces (RKHSs) as candidate hypothesis spaces and propose a novel model selection criterion via minimizing the empirical optimal error in the ball of RKHS and the covering number of the ball. By introducing the covering number to measure the capacity of the ball of RKHS, our criterion could directly control the sample complexity. Specifically, we first prove the relation between expected optimal error and empirical optimal error in the ball of RKHS. Using the relation as the theoretical foundation, we give the definition of our criterion. Then, by estimating the expectation of optimal empirical error and proving an upper bound of the covering number, we represent our criterion as a functional of the kernel matrix. An efficient algorithm is further developed for approximately calculating the functional so that the fast Fourier transform (FFT) can be applied to achieve a quasi-linear computational complexity. We also prove the consistency between the approximate criterion and the accurate one for large enough samples. Finally, we empirically evaluate the performance of our criterion and verify the consistency between the approximate and accurate criterion.

Model selection is one of the key issues both in recent research and application of kernel methods. Cross-validation is a commonly employed and widely accepted model selection criterion. However, it requires multiple times of training the algorithm under consideration, which is computationally intensive. In this paper, we present a novel strategy for approximating the cross-validation based on the Bouligand influence function (BIF), which only requires the solution of the algorithm once. The BIF measures the impact of an infinitesimal small amount of contamination of the original distribution. We first establish the link between the concept of BIF and the concept of cross-validation. The BIF is related to the first order term of a Taylor expansion. Then, we calculate the BIF and higher order BIFs, and apply these theoretical results to approximate the cross-validation error in practice. Experimental results demonstrate that our approximate cross-validation criterion is sound and efficient.

In this paper, we cluster a unlabeled human wrist pulse signal data set via a multiple criteria decision making (MCDM) framework to mine useful information for further study. First, a preprocessing scheme is performed and spatial features are extracted to represent a pulse signal. Then, a list of clustering algorithms are initialized to generate a number of clustering alternatives. The goodness of these clustering alternatives are sequentially comprehensively evaluated by 11 criteria, including ten internal cluster validation indices and an ad-hoc index, the robustness to noise, which is proposed for assessing the clustering alternatives of the pulse data set with spatial features. Taking the evaluation results as inputs, the technique for order preference by similarity to ideal solution (TOPSIS) method is employed to solve the resulting MCDM model. According to the TOPSIS rank, clustering the data set into thirteen clusters via k-means is optimal. Samples drawn from each cluster have similar patterns, corresponding to specific pulse type in traditional Chinese pulse diagnosis. The thirteen clusters are segregated into two groups, namely the healthy and the unhealthy, which can be further applied for unhealthy pulse detection.

Kernel selection is one of the key issues both in recent research and application of kernel methods. This is usually done by minimizing either an estimate of generalization error or some other related performance measure. It is well known that a kernel matrix can be interpreted as an empirical version of a continuous integral operator, and its eigenvalues converge to the eigenvalues of integral operator. In this paper, we introduce new kernel selection criteria based on the eigenvalues perturbation of the integral operator. This perturbation quantifies the difference between the eigenvalues of the kernel matrix and those of the integral operator. We establish the connection between eigenvalues perturbation and generalization error. By minimizing the derived generalization error bounds, we propose the kernel selection criteria. Therefore the kernel chosen by our proposed criteria can guarantee good generalization performance. To compute the values of our criteria, we present a method to obtain the eigenvalues of integral operator via the Fourier transform. Experiments on benchmark datasets demonstrate that our kernel selection criteria are sound and effective.

We propose a new leaning method for Multiple Kernel Learning (MKL) based on the upper bounds of the leave-one-out error that is an almost unbiased estimate of the expected generalization error. Specifically, we first present two new formulations for MKL by minimizing the upper bounds of the leave-one-out error. Then, we compute the derivatives of these bounds and design an efficient iterative algorithm for solving these formulations. Experimental results show that the proposed method gives better accuracy results than that of both SVM with the uniform combination of basis kernels and other state-of-art kernel learning approaches.

Ising mean field is a basic variational inference method for Ising model, which can provide an effective approximate solution for large-scale inference problem. The main idea is to transform a probabilistic inference problem into a functional extremum problem by variational calculus, and solve the functional extremum problem to obtain approximate marginal distributions. The process of solving the functional extremum is an important step and a computational core for variational inference. But the traditional full variational iteration methods make the variable information intercross with each other deeply. From the view of incomplete variational iterations, we propose a message family propagation method for Ising mean field to compute a marginal distribution family of object variable.