Risk Bounds for Learning via Hilbert Coresets

• URL: http://arxiv.org/abs/2103.15569v1
• Date: Mon, 29 Mar 2021 12:39:48 GMT
• Title: Risk Bounds for Learning via Hilbert Coresets
• Authors: Spencer Douglas, Piyush Kumar, R.K. Prasanth
• Abstract summary: We explicitly compute tight and meaningful bounds for complex hypothesis classes. We develop a formalism for constructing upper bounds on the expected full sample risk for supervised classification tasks.
• Score: 1.0312968200748116
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a formalism for constructing stochastic upper bounds on the expected full sample risk for supervised classification tasks via the Hilbert coresets approach within a transductive framework. We explicitly compute tight and meaningful bounds for complex datasets and complex hypothesis classes such as state-of-the-art deep neural network architectures. The bounds we develop exhibit nice properties: i) the bounds are non-uniform in the hypothesis space, ii) in many practical examples, the bounds become effectively deterministic by appropriate choice of prior and training data-dependent posterior distributions on the hypothesis space, and iii) the bounds become significantly better with increase in the size of the training set. We also lay out some ideas to explore for future research.

Related papers

• Stochastic Interpolants in Hilbert Spaces [22.77471216660321]
  interpolants offer a flexible way to bridge arbitrary distributions.<n>This paper establishes a rigorous framework for Hilbert interpolants in infinite-dimensional spaces.<n>We demonstrate the effectiveness of the proposed framework for conditional generation.
  arXiv  Detail & Related papers  (2026-02-02T11:44:34Z)
• Vector-Valued Distributional Reinforcement Learning Policy Evaluation: A Hilbert Space Embedding Approach [5.7161009858370875]
  We propose an (offline) multi-dimensional distributional reinforcement learning framework (KE-DRL)<n>We estimate the kernel mean embedding of the multi-dimensional value distribution under a proposed target policy using Hilbert space mappings.<n> Simulations and empirical results demonstrate robust off-policy evaluation and recovery of the kernel mean embedding.
  arXiv  Detail & Related papers  (2026-01-26T20:46:00Z)
• Lower Bounds for the Algorithmic Complexity of Learned Indexes [5.964436882344729]
  Learned index structures aim to accelerate queries by training machine learning models to approximate the rank function associated with a database attribute.<n>While effective in practice, their theoretical limitations are not fully understood.<n>We present a general framework for proving lower bounds on query time for learned indexes, expressed in terms of their space overhead and parameterized by the model class used for approximation.
  arXiv  Detail & Related papers  (2026-01-10T17:28:57Z)
• Adaptive Partitioning and Learning for Stochastic Control of Diffusion Processes [3.058685580689604]
  We study reinforcement learning for controlled diffusion processes with unbounded continuous state spaces.<n>We introduce a model-based algorithm that adaptively partitions the joint state-action space.<n>This adaptive scheme balances exploration and approximation, enabling efficient learning in unbounded domains.
  arXiv  Detail & Related papers  (2025-12-17T00:52:19Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Model-Free Kernel Conformal Depth Measures Algorithm for Uncertainty Quantification in Regression Models in Separable Hilbert Spaces [9.504740492278003]
  We propose a model-free uncertainty quantification algorithm based on conditional depth measures and an integrated depth measure.<n>New algorithms can be used to define prediction and tolerance regions when predictors and responses are defined in separable Hilbert spaces.<n>We demonstrate the practical relevance of our approach through a digital health application related to physical activity.
  arXiv  Detail & Related papers  (2025-06-10T01:25:37Z)
• Exploring a Principled Framework for Deep Subspace Clustering [9.347670574036563]
  We present a Principled fRamewOrk for Deep Subspace Clustering (PRO-DSC) PRO-DSC is designed to learn structured representations and self-expressive coefficients in a unified manner. We prove that the learned optimal representations under certain condition lie on a union of subspaces.
  arXiv  Detail & Related papers  (2025-03-21T16:38:37Z)
• Statistical Convergence Rates of Optimal Transport Map Estimation between General Distributions [8.326725299573754]
  We aim to broaden the scope of OT map estimation and fill this gap between theory and practice. We introduce a sieve plug-in estimator and establish its convergence rates without the strong convexity assumption on Brenier's potential. We also develop scalable algorithms to efficiently solve the OT map estimation using neural networks.
  arXiv  Detail & Related papers  (2024-12-11T03:18:17Z)
• Blessing of Dimensionality for Approximating Sobolev Classes on Manifolds [14.183849746284816]
  The manifold hypothesis says that natural high-dimensional data is supported on or around a low-dimensional manifold. Recent success of statistical and learning-based methods empirically supports this hypothesis. We provide theoretical statistical complexity results, which directly relates to generalization properties.
  arXiv  Detail & Related papers  (2024-08-13T15:56:42Z)
• Seeing Unseen: Discover Novel Biomedical Concepts via Geometry-Constrained Probabilistic Modeling [53.7117640028211]
  We present a geometry-constrained probabilistic modeling treatment to resolve the identified issues. We incorporate a suite of critical geometric properties to impose proper constraints on the layout of constructed embedding space. A spectral graph-theoretic method is devised to estimate the number of potential novel classes.
  arXiv  Detail & Related papers  (2024-03-02T00:56:05Z)
• 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)
• Distributionally Robust Skeleton Learning of Discrete Bayesian Networks [9.46389554092506]
  We consider the problem of learning the exact skeleton of general discrete Bayesian networks from potentially corrupted data. We propose to optimize the most adverse risk over a family of distributions within bounded Wasserstein distance or KL divergence to the empirical distribution. We present efficient algorithms and show the proposed methods are closely related to the standard regularized regression approach.
  arXiv  Detail & Related papers  (2023-11-10T15:33:19Z)
• Consciousness-Inspired Spatio-Temporal Abstractions for Better Generalization in Reinforcement Learning [83.41487567765871]
  Skipper is a model-based reinforcement learning framework. It automatically generalizes the task given into smaller, more manageable subtasks. It enables sparse decision-making and focused abstractions on the relevant parts of the environment.
  arXiv  Detail & Related papers  (2023-09-30T02:25:18Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• STEERING: Stein Information Directed Exploration for Model-Based Reinforcement Learning [111.75423966239092]
  We propose an exploration incentive in terms of the integral probability metric (IPM) between a current estimate of the transition model and the unknown optimal. Based on KSD, we develop a novel algorithm algo: textbfSTEin information dirtextbfEcted exploration for model-based textbfReinforcement LearntextbfING.
  arXiv  Detail & Related papers  (2023-01-28T00:49:28Z)
• Open-Set Likelihood Maximization for Few-Shot Learning [36.97433312193586]
  We tackle the Few-Shot Open-Set Recognition (FSOSR) problem, i.e. classifying instances among a set of classes for which we only have a few labeled samples. We explore the popular transductive setting, which leverages the unlabelled query instances at inference. Motivated by the observation that existing transductive methods perform poorly in open-set scenarios, we propose a generalization of the maximum likelihood principle.
  arXiv  Detail & Related papers  (2023-01-20T01:56:19Z)
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks [3.198144010381572]
  We study feedforward deep ReLU ANNs with an arbitrarily large number of hidden layers. We prove convergence of the risk of the GD optimization method with randoms in the training of such ANNs. We also study solutions of gradient flow differential equations.
  arXiv  Detail & Related papers  (2021-12-17T18:55:40Z)
• Uncertainty quantification for distributed regression [2.28438857884398]
  We propose a fully data-driven approach to quantify uncertainty of the averaged estimator. Namely, we construct simultaneous element-wise confidence bands for the predictions yielded by the averaged estimator on a given deterministic prediction set. As a by-product of our analysis we also obtain a sup-norm consistency result for the divide-and-conquer Kernel Ridge Regression.
  arXiv  Detail & Related papers  (2021-05-24T17:33:19Z)
• Local Propagation in Constraint-based Neural Network [77.37829055999238]
  We study a constraint-based representation of neural network architectures. We investigate a simple optimization procedure that is well suited to fulfil the so-called architectural constraints.
  arXiv  Detail & Related papers  (2020-02-18T16:47:38Z)

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.