.png){kind=icon}
.png){kind=icon}
Return
Sparse solutions of the kernel herding algorithm by improved gradient approximation
.png){kind=icon}
PRE
AI
DOI：10.1007/s13160-026-00768-z.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The kernel herding algorithm is one of the methods to construct quadrature rules in a Reproducing Kernel Hilbert Space (RKHS). While computational efficiency of the algorithm and stability of the output quadrature formulas are advantages of this method, the convergence speed of the integration error for the number of nodes is not fast compared to other quadrature methods. In this research, we propose a modified kernel herding algorithm whose framework was introduced in Combettes and Pokutta (in: International conference on machine learning, PMLR, 2020) and aim to get sparser solutions with preserving the advantages of kernel herding. In the proposed algorithm, the negative gradient is approximated by several vertex directions and the current solution is updated by moving in the approximate descent direction in each iteration. We show that the convergence speed of the integration error is directly determined by the cosine of the angle between the negative gradient and approximate gradient. Based on this, we propose new gradient approximation algorithms and analyze them theoretically, which includes convergence analysis. In numerical experiments, we confirm the effectiveness of the proposed algorithms in terms of the sparsity of nodes and computational efficiency. Moreover, we provide a new theoretical analysis of the kernel quadrature rules with fully-corrective weights, which realizes faster convergence speeds than those of previous studies.
Keywords:
Kernel herding
Frank-Wolfe algorithm
Kernel quadrature
Numerical integration
Kernel methods
Sampling
Journal
J
IF:
1.1
Papers:
62
Citations:
0
Organization
No organization information available