检索结果-内蒙古大学图书馆

Radial Basis Function Approximation with Distributively Stored Data on Spheres

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Feng, Han Lin, Shao-Bo Zhou, Ding-Xuan Department of Mathematics City University of Hong Kong Hong Kong Center for Intelligent Decision-Making and Machine Learning School of Management Xi'an Jiaotong University Xi'An China School of Mathematics and Statistics University of Sydney SydneyNSW Australia

This paper proposes a distributed weighted regularized least squares algorithm (DWRLS) with radial basis functions to tackle spherical data that are stored across numerous local servers and cannot be shared with each other. Via developing a novel integral operator approach based on spherical quadrature rules, we succeed in deriving optimal approximation rates for DWRLS and theoretically demonstrate that DWRLS performs similarly as running a weighted regularized least squares algorithm on the whole data stored on a large enough machine. This interesting finding implies that distributed learning is capable of sufficiently exploiting potential values of distributively stored spherical data, even though local servers cannot access the whole data. Copyright © 2021, The Authors. All rights reserved.

关键词： Spheres

Exact Decomposition of Joint Low Rankness and Local Smoothness Plus Sparse Matrices

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Peng, Jiangjun Wang, Yao Zhang, Hongying Wang, Jianjun Meng, Deyu School of Mathematics and Statistics Ministry of Education Key Lab of Intelligent Networks and Network Security Xi'an Jiaotong University Shaan'xi Xi’an710049 China The Center for Intelligent Decision-making and Machine Learning School of Management Xian Jiaotong University Shaan'xi Xi’an China The College of Artificial Intelligence Southwest University Chongqing400715 China Macau Institute of Systems Engineering Macau University of Science and Technology Taipa China

It is known that the decomposition in low-rank and sparse matrices (L+S for short) can be achieved by several Robust PCA techniques. Besides the low rankness, the local smoothness (LSS) is a vitally essential prior for many real-world matrix data such as hyperspectral images and surveillance videos, which makes such matrices have low-rankness and local smoothness property at the same time. This poses an interesting question: Can we make a matrix decomposition in terms of L&LSS +S form exactly? To address this issue, we propose in this paper a new RPCA model based on three-dimensional correlated total variation regularization (3DCTV-RPCA for short) by fully exploiting and encoding the prior expression underlying such joint low-rank and local smoothness matrices. Specifically, using a modification of Golfing scheme, we prove that under some mild assumptions, the proposed 3DCTV-RPCA model can decompose both components exactly, which should be the first theoretical guarantee among all such related methods combining low rankness and local smoothness. In addition, by utilizing Fast Fourier Transform (FFT), we propose an efficient ADMM algorithm with a solid convergence guarantee for solving the resulting optimization problem. Finally, a series of experiments on both simulations and real applications are carried out to demonstrate the general validity of the proposed 3DCTV-RPCA model. Copyright © 2022, The Authors. All rights reserved.

关键词： Fast Fourier transforms

Angle-Based Cost-Sensitive Multicategory Classification

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Yang, Yi Guo, Yuxuan Chang, Xiangyu Center of Intelligent Decision-Making and Machine Learning School of Management Xi’an Jiaotong University China School of Statistics Renmin University of China China

Many real-world classification problems come with costs which can vary for different types of misclassification. It is thus important to develop cost-sensitive classifiers which minimize the total misclassification cost. Although binary cost-sensitive classifiers have been well-studied, solving multicategory classification problems is still challenging. A popular approach to address this issue is to construct K classification functions for a K-class problem and remove the redundancy by imposing a sum-to-zero constraint. However, such method usually results in higher computational complexity and inefficient algorithms. In this paper, we propose a novel angle-based cost-sensitive classification framework for multicategory classification without the sum-to-zero constraint. Loss functions that included in the angle-based cost-sensitive classification framework are further justified to be Fisher consistent. To show the usefulness of the framework, two cost-sensitive multicategory boosting algorithms are derived as concrete instances. Numerical experiments demonstrate that proposed boosting algorithms yield competitive classification performances against other existing boosting approaches. Copyright © 2020, The Authors. All rights reserved.

关键词： Computational complexity

Randomized spectral clustering in large-scale stochastic block models

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Zhang, Hai Guo, Xiao Chang, Xiangyu Center for Modern Statistics School of Mathematics Northwest University China Center for Intelligent Decision-Making and Machine Learning School of Management Xi'An Jiaotong University China

Spectral clustering has been one of the widely used methods for community detection in networks. However, large-scale networks bring computational challenges to the eigenvalue decomposition therein. In this paper, we study the spectral clustering using randomized sketching algorithms from a statistical perspective, where we typically assume the network data are generated from a stochastic block model that is not necessarily of full rank. To do this, we first use the recently developed sketching algorithms to obtain two randomized spectral clustering algorithms, namely, the random projection-based and the random sampling-based spectral clustering. Then we study the theoretical bounds of the resulting algorithms in terms of the approximation error for the population adjacency matrix, the misclassification error, and the estimation error for the link probability matrix. It turns out that, under mild conditions, the randomized spectral clustering algorithms lead to the same theoretical bounds as those of the original spectral clustering algorithm. We also extend the results to degree-corrected stochastic block models. Numerical experiments support our theoretical findings and show the efficiency of randomized methods. A new R package called Rclust is developed and made available to the public. Copyright © 2020, The Authors. All rights reserved.

关键词： Population dynamics

Adaptive stopping rule for kernel-based gradient descent algorithms

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Chang, Xiangyu Lin, Shao-Bo Center of Intelligence Decision-Making and Machine Learning School of Management Xi'an Jiaotong University Xi'an China

In this paper, we propose an adaptive stopping rule for kernel-based gradient descent (KGD) algorithms. We introduce the empirical effective dimension to quantify the increments of iterations in KGD and derive an implementable early stopping strategy. We analyze the performance of the adaptive stopping rule in the framework of learning theory. Using the recently developed integral operator approach, we rigorously prove the optimality of the adaptive stopping rule in terms of showing the optimal learning rates for KGD equipped with this rule. Furthermore, a sharp bound on the number of iterations in KGD equipped with the proposed early stopping rule is also given to demonstrate its computational advantage. Copyright © 2020, The Authors. All rights reserved.

关键词： Gradient methods

Kernel-based L2-boosting with structure constraints

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Wang, Yao Guo, Xin Lin, Shao-Bo Center of Intelligent Decision-Making and Machine Learning School of Management Xi’an Jiaotong University Xi’an China Department of Applied Mathematics Hong Kong Polytechnic University Kowloon Hong Kong

Developing efficient kernel methods for regression is very popular in the past decade. In this paper, utilizing boosting on kernel-based weaker learners, we propose a novel kernel-based learning algorithm called kernel-based re-scaled boosting with truncation, dubbed as KReBooT. The proposed KReBooT benefits in controlling the structure of estimators and producing sparse estimate, and is near overfitting resistant. We conduct both theoretical analysis and numerical simulations to illustrate the power of KReBooT. Theoretically, we prove that KReBooT can achieve the almost optimal numerical convergence rate for nonlinear approximation. Furthermore, using the recently developed integral operator approach and a variant of Talagrand’s concentration inequality, we provide fast learning rates for KReBooT, which is a new record of boosting-type algorithms. Numerically, we carry out a series of simulations to show the promising performance of KReBooT in terms of its good generalization, near over-fitting resistance and structure constraints. Copyright © 2020, The Authors. All rights reserved.

关键词： machine learning

Kernel interpolation of high dimensional scattered data

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Lin, Shao-Bo Chang, Xiangyu Sun, Xingping Center for Intelligent Decision-Making and Machine Learning School of Management Xi'an Jiaotong University Xi'an710049 China Department of Mathematics Missouri State University SpringfieldMO65897 United States

Data sites selected from modeling high-dimensional problems often appear scattered in non-paternalistic ways. Except for sporadic-clustering at some spots, they become relatively far apart as the dimension of the ambient space grows. These features defy any theoretical treatment that requires local or global quasi-uniformity of distribution of data sites. Incorporating a recently-developed application of integral operator theory in machine learning, we propose and study in the current article a new framework to analyze kernel interpolation of high dimensional data, which features bounding stochastic approximation error by the spectrum of the underlying kernel matrix. Both theoretical analysis and numerical simulations show that spectra of kernel matrices are reliable and stable barometers for gauging the performance of kernel-interpolation methods for high dimensional data. Copyright © 2020, The Authors. All rights reserved.

关键词： Approximation theory

Fully-corrective gradient boosting with squared hinge: Fast learning rates and early stopping

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Zeng, Jinshan Zhang, Min Lin, Shao-Bo School of Computer and Information Engineering Jiangxi Normal University Nanchang330022 China Center of Intelligent Decision-Making and Machine Learning School of Management Xi’an Jiaotong University Xi’an710049 China

Boosting is a well-known method for improving the accuracy of weak learners in machine learning. However, its theoretical generalization guarantee is missing in literature. In this paper, we propose an efficient boosting method with theoretical generalization guarantees for binary classification. Three key ingredients of the proposed boosting method are: a) the fully-corrective greedy (FCG) update in the boosting procedure, b) a differentiable squared hinge (also called truncated quadratic) function as the loss function, and c) an efficient alternating direction method of multipliers (ADMM) algorithm for the associated FCG optimization. The used squared hinge loss not only inherits the robustness of the well-known hinge loss for classification with outliers, but also brings some benefits for computational implementation and theoretical justification. Under some sparseness assumption, we derive a fast learning rate of the order O((m/log m)−1/4) for the proposed boosting method, which can be further improved to O((m/log m)−1/2) if certain additional noise assumption is imposed, where m is the size of sample set. Both derived learning rates are the best ones among the existing generalization results of boosting-type methods for classification. Moreover, an efficient early stopping scheme is provided for the proposed method. A series of toy simulations and real data experiments are conducted to verify the developed theories and demonstrate the effectiveness of the proposed method. Copyright © 2020, The Authors. All rights reserved.

关键词： machine learning

Distributed Kernel Ridge Regression with Communications

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Lin, Shao-Bo Wang, Di Zhou, Ding-Xuan Center of Intelligent Decision-Making and Machine Learning School of Management Xi’an Jiaotong University Xi’an China School of Data Science Department of Mathematics City University of Hong Kong Kowloon Hong Kong

This paper focuses on generalization performance analysis for distributed algorithms in the framework of learning theory. Taking distributed kernel ridge regression (DKRR) for example, we succeed in deriving its optimal learning rates in expectation and providing theoretically optimal ranges of the number of local processors. Due to the gap between theory and experiments, we also deduce optimal learning rates for DKRR in probability to essentially reflect the generalization performance and limitations of DKRR. Furthermore, we propose a communication strategy to improve the learning performance of DKRR and demonstrate the power of communications in DKRR via both theoretical assessments and numerical experiments. Copyright © 2020, The Authors. All rights reserved.

关键词： Regression analysis