Nonparametric Regression on Fixed-Cardinality Subsets:Minimax Risk and Random-Design Effects
Abstract
We study regression with subsets as covariates. The response is an unknown function of the input subset, and observations consist of noisy evaluations at uniformly sampled subsets, each containing exactly k items from a ground set of size d. This problem arises in combination screening, bundle preference modeling, and other settings in which outcomes depend on collections of prescribed size. The fixed-cardinality constraint couples the membership coordinates, so standard product-domain notions of interaction and smoothness cannot be imported unchanged. We use the harmonic decomposition of the Johnson graph to define an intrinsic Johnson--Sobolev scale and determine the exact dimensions of low-order interaction spaces. We derive finite-sample risk bounds for harmonic projection and establish a nonasymptotic minimax characterization when the Johnson--Sobolev energy budget is controlled relative to the noise variance. We also show that stable least squares removes the signal-dependent fluctuation of empirical projection when the empirical Gram matrix is sufficiently well conditioned. For arbitrary signal-to-noise ratios, a rank-deficiency analysis quantifies the components left unidentified by the random design. Together, the rank-deficiency analysis and a centered completion estimator yield minimax bounds that match up to constants whenever min(k,d−k) and the smoothness order are fixed. Numerical experiments reported in the Supplementary Material illustrate estimation under different interaction profiles and distinguish the effects of observation noise, random-design fluctuation, and incomplete coverage.
Related
- Scalable Nonparametric Change-Plane Regression with Random Features: Estimation and Inference
- Improved Variance Estimation in Homoskedastic Nonparametric Random-Design Regression via a Two-Scale Approach
- Nonparametric hazard rate estimation with associated kernels and minimax bandwidth choice
- Nonparametric In-Context Learning under Growing Geometric Complexity: Minimax Optimality and Local Geometry-Adaptivity of Transformers
- On the minimax-rate optimality of approximate Bayesian computation in nonparametric problems
BibTeX
@misc{biau2026nonparametric,
title = {{Nonparametric Regression on Fixed-Cardinality Subsets:Minimax Risk and Random-Design Effects}},
author = {Gérard Biau},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15592},
eprint = {2609.15592},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15592},
}
RIS
TY - UNPB
TI - Nonparametric Regression on Fixed-Cardinality Subsets:Minimax Risk and Random-Design Effects
AU - G{é}rard Biau
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15592
UR - https://arxiv.org/abs/2609.15592
AB - We study regression with subsets as covariates. The response is an unknown function of the input subset, and observations consist of noisy evaluations at uniformly sampled subsets, each containing exactly k items from a ground set of size d. This problem arises in combination screening, bundle preference modeling, and other settings in which outcomes depend on collections of prescribed size. The fixed-cardinality constraint couples the membership coordinates, so standard product-domain notions of interaction and smoothness cannot be imported unchanged. We use the harmonic decomposition of the Johnson graph to define an intrinsic Johnson--Sobolev scale and determine the exact dimensions of low-order interaction spaces. We derive finite-sample risk bounds for harmonic projection and establish a nonasymptotic minimax characterization when the Johnson--Sobolev energy budget is controlled relative to the noise variance. We also show that stable least squares removes the signal-dependent fluctuation of empirical projection when the empirical Gram matrix is sufficiently well conditioned. For arbitrary signal-to-noise ratios, a rank-deficiency analysis quantifies the components left unidentified by the random design. Together, the rank-deficiency analysis and a centered completion estimator yield minimax bounds that match up to constants whenever min(k,d−k) and the smoothness order are fixed. Numerical experiments reported in the Supplementary Material illustrate estimation under different interaction profiles and distinguish the effects of observation noise, random-design fluctuation, and incomplete coverage.
ER -