The sketch-and-project, as a general archetypal algorithm for solving linear systems, unifies a variety of randomized iterative methods such as the randomized Kaczmarz and randomized coordinate descent. However, since it aims to find a least-norm solution from a linear system, the randomized sparse Kaczmarz can not be included. This motivates us to propose a more general framework, called sketched Bregman projection (SBP) method, in which we are able to find solutions with certain structures from linear systems. To generalize the concept of adaptive sampling to the SBP method, we show how the progress, measured by Bregman distance, of single step depends directly on a sketched loss function. Theoretically, we provide detailed global convergence results for the SBP method with different adaptive sampling rules. At last, for the (sparse) Kaczmarz methods, a group of numerical simulations are tested, with which we verify that the methods utilizing sampling Kaczmarz–Motzkin rule demands the fewest computational costs to achieve a given error bound comparing to the corresponding methods with other sampling rules.
1 September 2021 in Computers in Biology and Medicine
Graph convolutional network (GCN) is a powerful deep model in dealing with graph data. However, the explainability of GCN remains a difficult problem since the training behaviors for graph neural networks are hard to describe. In this work, we show that for GCN with wide hidden feature dimension, the output for semisupervised problem can be described by a simple differential equation. In addition, the dynamics of the behavior of output is decided by the graph convolutional neural tangent kernel (GCNTK), which is stable when the width of hidden feature tends to be infinite. And the solution of node classification can be explained directly by the differential equation for a semisupervised problem. The experiments on some toy models speak to the consistency of the GCNTK model and GCN.