Sparse Representer Theorems for Learning in Reproducing Kernel Banach Spaces

• URL: http://arxiv.org/abs/2305.12584v2
• Date: Thu, 7 Mar 2024 16:04:12 GMT
• Title: Sparse Representer Theorems for Learning in Reproducing Kernel Banach Spaces
• Authors: Rui Wang, Yuesheng Xu, Mingsong Yan
• Abstract summary: Sparsity of a learning solution is a desirable feature in machine learning. Certain reproducing kernel Banach spaces (RKBSs) are appropriate hypothesis spaces for sparse learning methods.
• Score: 7.695772976072261
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sparsity of a learning solution is a desirable feature in machine learning. Certain reproducing kernel Banach spaces (RKBSs) are appropriate hypothesis spaces for sparse learning methods. The goal of this paper is to understand what kind of RKBSs can promote sparsity for learning solutions. We consider two typical learning models in an RKBS: the minimum norm interpolation (MNI) problem and the regularization problem. We first establish an explicit representer theorem for solutions of these problems, which represents the extreme points of the solution set by a linear combination of the extreme points of the subdifferential set, of the norm function, which is data-dependent. We then propose sufficient conditions on the RKBS that can transform the explicit representation of the solutions to a sparse kernel representation having fewer terms than the number of the observed data. Under the proposed sufficient conditions, we investigate the role of the regularization parameter on sparsity of the regularized solutions. We further show that two specific RKBSs: the sequence space $\ell_1(\mathbb{N})$ and the measure space can have sparse representer theorems for both MNI and regularization models.

Related papers

• Scalable unsupervised alignment of general metric and non-metric structures [21.29255788365408]
  Aligning data from different domains is a fundamental problem in machine learning with broad applications across very different areas. We learn a related well-scalable linear assignment problem (LAP) whose solution is also a minimizer of the quadratic assignment problem (QAP) We evaluate our approach on synthetic and real datasets from single-cell multiomics and neural latent spaces.
  arXiv  Detail & Related papers  (2024-06-19T12:54:03Z)
• Hypothesis Spaces for Deep Learning [7.695772976072261]
  This paper introduces a hypothesis space for deep learning that employs deep neural networks (DNNs) By treating a DNN as a function of two variables, we consider the primitive set of the DNNs for the parameter variable located in a set of the weight matrices and biases determined by a prescribed depth and widths of the DNNs. We prove that the Banach space so constructed is a kernel reproducing Banach space (RKBS) and construct its reproducing kernel.
  arXiv  Detail & Related papers  (2024-03-05T22:42:29Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Measuring dissimilarity with diffeomorphism invariance [94.02751799024684]
  We introduce DID, a pairwise dissimilarity measure applicable to a wide range of data spaces. We prove that DID enjoys properties which make it relevant for theoretical study and practical use.
  arXiv  Detail & Related papers  (2022-02-11T13:51:30Z)
• Analysis of Regularized Learning for Linear-functional Data in Banach Spaces [3.160070867400839]
  We study the whole theory of regularized learning for linear-functional data in Banach spaces. We show the convergence of the approximate solutions to the exact solutions by the weak* topology of the Banach space. The theorems of the regularized learning are applied to solve many problems of machine learning.
  arXiv  Detail & Related papers  (2021-09-07T15:51:12Z)
• Solving PDEs on Unknown Manifolds with Machine Learning [8.220217498103315]
  This paper presents a mesh-free computational framework and machine learning theory for solving elliptic PDEs on unknown manifold. We show that the proposed NN solver can robustly generalize the PDE on new data points with errors that are almost identical to generalizations on new data points.
  arXiv  Detail & Related papers  (2021-06-12T03:55:15Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• Dimension Free Generalization Bounds for Non Linear Metric Learning [61.193693608166114]
  We provide uniform generalization bounds for two regimes -- the sparse regime, and a non-sparse regime. We show that by relying on a different, new property of the solutions, it is still possible to provide dimension free generalization guarantees.
  arXiv  Detail & Related papers  (2021-02-07T14:47:00Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.