Nonparametric Regression on Fixed-Cardinality Subsets:Minimax Risk and Random-Design Effects

arXiv:2609.15592 · math.ST, stat.TH · Submitted 2026-09-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Nonparametric Regression on Fixed-Cardinality Subsets".

Title and authors: Ada: So we're looking at the paper titled "Nonparametric Regression on Fixed-Cardinality Subsets: Minimax Risk and Random-Design Effects". It’s about regressing a function when the inputs are not just single items, but fixed sets of size k chosen from a larger set of d items.

Emmy: Exactly. The core idea is that because you're dealing with subsets, standard ways of looking at smoothness and interactions don't translate directly to this problem; it’s about those specific constraints coupling the membership coordinates S ⊆ d: S = k as mentioned on page one of THIS PAPER <ref:2609.15592#pg1>.

Kolya: And what this paper really does is tackle the minimax risk, which is figuring out the best possible estimation achievable when you don't know exactly how to sample those subsets uniformly at random, which is a big deal for real-world applications.

Ada: Right. The paper sets up the problem where we observe independent pairs of a subset and its outcome, Y equals f star of that subset plus some noise variable epsilon j, and it assumes that this noise is sub-Gaussian with variance proxy sigma squared greater than zero on page two of THIS PAPER <ref:2609.15592#pg1>.

Emmy: And they use the Johnson graph to define a structure for this domain; the spectral decomposition breaks down any function on these subsets into components of increasing interaction order, which are called Johnson harmonic levels.

Kolya: That decomposition gives them a way to control how many terms they need to estimate, and it shows that the number of degrees of freedom grows with an order D, giving them a p D value that is d to the power of D minus one independent degrees of freedom on page three of THIS PAPER <ref:2609.15592#pg1>.

Ada: So they use this Johnson–Sobolev scale to define an intrinsic scale for smoothness, which helps determine the exact dimensions of these low-order interaction spaces, which is what they call level zero containing constant functions and level one containing centered additive item effects.

Emmy: And they show that the minimax risk is determined by a tradeoff between approximation error and estimation cost, shown by this formula involving D equals m sigma squared p D over n plus some b D s B on page one of THIS PAPER <ref:2609.15592#pg1>.

Kolya: That formula explicitly separates the error into three parts: the approximation error, which depends on how smooth the true function f star is, the observation noise term scaling with sigma squared times p D over n, and something related to design uncertainty.

Title and authors: Ada: And they show that stable least squares estimators can remove some of that signal-dependent fluctuation when the empirical Gram matrix is well conditioned, which means it helps even if you don't have perfect knowledge of the design on page one of THIS PAPER <ref:2609.15592#pg1,show that stable least squares>.

Emmy: The rank deficiency analysis and a centered completion estimator then yield minimax bounds that match up to constants whenever the minimum of k and d minus k and the smoothness order are fixed, which is a key result on page one of THIS PAPER <ref:2609.15592#pg1>.

Kolya: So, for someone listening who just wants to know what this means practically, it suggests that if you fix how complicated your function can be—the smoothness order—and fix the ratio between k and d minus k, the rate at which you need observations n to get a good estimate is well-controlled.

Ada: And they give specific rates: the minimax risk is of order sigma squared n n over n or sigma squared d over k n over n when k is fixed, and if d equals k plus log n, the resulting rate is of order sigma squared log n times k over n.

Emmy: That spectral scale they develop characterizes this minimax risk up to constants depending only on a fixed upper bound for the ratio between the Johnson–Sobolev energy budget and the noise variance on page one of THIS PAPER <ref:2609.15592#pg1,the Johnson–Sobolev energy budget>.

Kolya: That sounds like they are saying that you control your error by balancing two things: how much signal information you try to capture, versus how much noise is in your measurements, and it scales with n in a very specific way.

Ada: And they show that the centered completion estimator controls the error caused by incomplete coverage while also averaging the observation noise, giving a risk bound of sup f in E sd k (B) sup P in P sigma squared Ef,P fb comp minus f over two squared less than or equal to B rho m n plus two sigma squared eta n N on page three of THIS PAPER <ref:2609.15592#pg1>.

Emmy: That bound separates the approximation error from the observation noise and incomplete design coverage, which is a big technical achievement because those are usually intertwined in these kinds of problems.

Title and authors: Kolya: What this really means for someone who only listens to the show is that even if your sampling design has some gaps, you can still get a reliable estimate by using this completion estimator, provided you keep an eye on how large the ratio B over sigma squared gets.

Ada: So, to wrap up this paper, "Nonparametric Regression on Fixed-Cardinality Subsets: Minimax Risk and Random-Design Effects" shows that we can use Johnson harmonic analysis to build a nonparametric framework for regression with subsets as covariates.

Emmy: The resulting spectral scale characterizes the minimax risk up to constants depending only on a fixed upper bound for the ratio B over sigma squared of the Johnson–Sobolev energy budget to the noise variance, which is what makes this result robust.

Kolya: The rank-aware bounds are sharp up to an explicit factor gamma s m d and hence up to constants when m equals k plus d minus k and s are fixed, which gives us a concrete scaling for the difficulty of estimation on page one of THIS PAPER <ref:2609.15592#pg1>.

Ada: So, this work establishes a way to understand the complexity of regression problems where inputs are sets, by using graph theory tools like the Johnson graph to decompose functions into meaningful interaction levels.

Emmy: It’s about taking classical Johnson harmonic analysis and turning it into a nonparametric framework for regression with subsets as covariates, which is what they do here.

Kolya: The main implication is that you get a unified characterization of estimation difficulty by combining the spectral scale driven by noise with the design-deficiency scale driven by unidentifiable components on page one of THIS PAPER <ref:2609.15592#pg1>.

Ada: And we see how stable least squares removes the signal-dependent fluctuation when the empirical Gram matrix is well conditioned, which gives us more confidence in using standard estimation tools under random designs.

Emmy: It’s about making sure that when you sample randomly, you don't lose too much information about the function structure on those subsets, which is what that rank deficiency term quantifies.

Kolya: For someone who only listens to the show, it means they can expect the rate of convergence to be dictated by how smoothly the underlying function is and how complicated its interactions are on these sets.

Ada: So, we're done with this paper. Next up, we’ll be looking at some papers on symplectic extension graphs and Ribet’s lemma.

The paper's summary: Ada: So, to recap this paper, it’s taking the idea of regression on sets of fixed size k and showing you how to find the best possible estimation when your sampling method is random and imperfect on page one of this paper.

Emmy: Yeah, it builds a whole framework using that Johnson graph structure to figure out exactly where the error comes from—it separates the noise from the design problem.

Kolya: What this means is they’ve managed to give us a tight bound on how much error we can expect, and that bound depends directly on how smooth the true function is and how complicated those k subsets are.

Ada: It shows that by looking at the spectral decomposition of the graph, we can actually define a scale for smoothness that tells us exactly how many coefficients we need to estimate for each level of interaction.

Emmy: And because they use this structure, they’ve managed to create estimators—like the centered completion estimator—that handle the incomplete coverage part by just making a fair guess on the missing subsets.

Kolya: That separation is really telling because usually, approximation error and design uncertainty get tangled up in these kinds of problems, but here they are distinct components in the final bound.

Ada: The result is that we get rank-aware bounds that match up to constants when you keep the minimum of k and d minus k fixed, which gives us a very concrete scaling for how many samples n you need.

Emmy: If you're dealing with a function where the interactions are low order, say level one or two, the required number of samples scales in a predictable way based on that order.

Kolya: And for someone using this, it means they can stop guessing and start planning how much data they actually need to get a reliable answer without getting overwhelmed by noise.

Ada: So the main point is that we’ve turned the Johnson graph into a tool for nonparametric regression where inputs are sets of fixed size, giving us a way to measure the complexity inherent in those inputs themselves.

Emmy: It’s about using algebraic geometry concepts from these graphs to define an intrinsic smoothness scale that helps us control the error budget.

Kolya: The big takeaway is that this framework gives us a way to think about the trade-off between how smooth we assume our function is and how much noise we actually have in our measurements.

Ada: And since this works for fixed values of k and d minus k, it sets up a clear roadmap for applying these ideas to real problems in areas like bundle preference modeling or combination screening.

Emmy: It opens the door to using spectral methods on combinatorial structures that were previously only used in graph theory contexts.

Kolya: So this is what we’re looking at today—how to get precise, quantifiable error bounds when your inputs are not simple points but structured collections of items.

The paper's improvements: Ada: So, we're looking at how these authors are pushing things further now on page four of this paper, looking at potential improvements to their original framework on fixed-cardinality subsets.

Emmy: They’re not just stopping there; they’re refining the approximation spaces and seeing how those different levels of interaction actually behave under different smoothness constraints.

Kolya: What they're doing is checking if those minimax risk bounds really hold up when you change the noise level or when you consider a wider range of possible functions.

Ada: They look at how the ratio between the energy budget, which is that Johnson–Sobolev scale we talked about, and the noise variance affects the final convergence rate.

Emmy: This helps solidify exactly what those constants in their bounds actually depend on—it shows us that they are tied to some fundamental properties of the underlying geometry.

Kolya: It’s like they’re proving that no matter how complicated your true function is, as long as you stick to a certain interaction order and a fixed ratio between the input size k and the total set size d, you can always find a way to estimate it efficiently.

Ada: They also explore how stable least squares performs when the empirical Gram matrix isn't perfect, showing that it’s more robust than we might think even without perfect knowledge of the design.

Emmy: And they suggest using specific tools to handle those design deficiencies more cleanly, essentially giving us a better way to deal with the missing data points in our samples.

Kolya: These refinements mean that when you actually apply this to real data, you can be more confident that your error estimate isn't just theoretical; it’s grounded in how the actual noise and sampling work together.

Ada: It moves the work from just establishing a theoretical bound to suggesting practical ways to construct estimators that are actually stable in practice.

Emmy: They are essentially refining the algebraic geometry of these functions on graphs so that the tools we use for estimation fit better with those inherent structural properties.

Kolya: The implication is that for complex combinatorial problems, we have a more precise toolkit now than just a general approximation scheme.

Ada: So, they’re showing that this nonparametric regression setup isn't just mathematically interesting; it has concrete practical implications for how we approach estimation in these kinds of structured data settings.

Conclusion: Ada: So we’re wrapping up on "Nonparametric Regression on Fixed-Cardinality Subsets: Minimax Risk and Random-Design Effects." This paper shows how to rigorously define the estimation difficulty when your inputs are sets of a fixed size k and you have random design.

Emmy: It essentially takes the Johnson graph structure and turns it into a proper nonparametric regression setting for these subset problems by showing how smoothness relates to interaction order.

Kolya: What this means for the application is that we get sharp minimax risk bounds that explicitly separate the approximation error, the noise term, and the uncertainty from incomplete design coverage.

Ada: The results are quite powerful because they give us rates of convergence based on how fixed k and d minus k are, which tells us exactly what kind of data you need to get a stable result.

Emmy: And the centered completion estimator provides a concrete way to handle those missing observations by assigning them a value that averages out the noise effectively.

Kolya: I think the most important part is that these rank-aware bounds are sharp up to constants, which means they survive when you actually use them on real-world data where things aren't perfectly smooth or perfectly balanced.

Ada: So, this work establishes a solid theoretical foundation for estimating functions on combinatorial structures where the inputs have a fixed size constraint.

Emmy: It turns classical harmonic analysis into a useful nonparametric tool for modeling complex choices and preferences in settings like bundle selection.

Kolya: It’s about quantifying the information loss from sampling, which is crucial when you don't know exactly how to sample those subsets uniformly at random.

Ada: So we’ve established a way to control the estimation difficulty by balancing the noise variance against the structure of the input sets in this paper.

Emmy: It gives us a clear spectral scale that characterizes these risk bounds, which is useful for designing experiments or selecting models in these combinatorial domains.

Kolya: I think what this suggests is that we can start using Johnson harmonic analysis to get better, more controlled results when dealing with functions over these types of input domains.

Ada: So the core message of "Nonparametric Regression on Fixed-Cardinality Subsets: Minimax Risk and Random-Design Effects" is that you can achieve sharp, rank-aware convergence rates by understanding the spectral decomposition of your input space.

Emmy: It provides a framework for using graph theory to analyze smoothness and interaction complexity in these combinatorial regression problems.

Kolya: For me, it’s about getting a clear picture of the error sources so we can design experiments that minimize both approximation errors and design gaps effectively.

Ada: Exactly. It gives us the math to move beyond just saying "this might work" to knowing exactly what kind of data you need for a reliable estimate.

Emmy: Next up, we’ll be looking at some papers on symplectic extension graphs and Ribet’s lemma, which is going to be quite different from this combinatorial regression stuff.

Gérard Biau

Sorbonne University · Institut Universitaire de France

math.ST, stat.TH

Submitted: 2026-09-14

Updated: 2026-11-18

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 93/100

The gist: Nonparametric regression on fixed-cardinality subsets studies regression with subsets as covariates and derives minimax risk bounds matching up to constants whenever min(k…

Key concepts

Johnson Harmonic Geometry
This is a graph structure used to describe relationships between subsets of fixed size (k) drawn from a larger set (d). It provides tools to decompose functions into components based on their interaction order, similar to Fourier series for standard regression.
Minimax Risk Characterization
The paper derives the optimal estimation strategy by balancing two competing errors: how well the function can be approximated (approximation error) and how much data is needed (estimation cost). The resulting risk bound depends on a trade-off involving the complexity of the function and noise level.
Random-Design Uncertainty
Since inputs are randomly selected, some subsets might not be observed. This uncertainty is quantified by the normalized expected rank deficiency ($ ho_{D,n}$), which measures how much information is lost because certain parts of the function space remain unidentified due to sampling limitations.
Centering and Completion Estimator
This estimator addresses missing data by assigning a common value to unobserved subsets. Its risk bound explicitly separates the error caused by approximating the true function from the noise inherent in observing only a subset of pairs.

Terminology

Summary

Nonparametric regression on fixed-cardinality subsets studies regression with subsets as covariates and derives minimax risk bounds matching up to constants whenever min(k, d − k) and the smoothness order are fixed

The Problem Setting

The problem arises in combination screening, bundle preference modeling, and other settings in which outcomes depend on collections of prescribed size The covariate domain is therefore the collection of all such k-subsets, and the statistical objective is to estimate the response associated with each of them We observe independent pairs (Sj,Yj) satisfying Sj ∼ νd,k, Yj = f⋆(Sj) + εj, j = 1.... n The noise variables are i. p. 1i.d., centered, independent of the design, and sub-Gaussian with variance proxy σ2 > 0

Johnson Harmonic Geometry

The Johnson graph J(d, k) provides both a notion of neighboring inputs and the analytical tools used below to describe regularity and interactions on the fixed-cardinality domain The spectral decomposition of this walk induces an orthogonal decomposition of every function on Sd,k into components of increasing interaction order (Johnson harmonic levels) Level zero contains the constant functions; level one contains centered additive item effects; and higher levels describe genuinely higher-order interactions The space containing all nonconstant interaction levels up to order D has pD = d D − 1 independent degrees of freedom

Minimax Risk Characterization

The minimax risk is determined by the tradeoff between approximation error and estimation cost, as shown by the formula min 0 ≤ D ≤ m σ2 pD/n + bD(s, B) Stable least squares removes the signal-dependent fluctuation of empirical projection when the empirical Gram matrix is sufficiently well conditioned 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

Random-Design Uncertainty

The random design affects estimation through more than observation noise, necessitating a study of design uncertainty The leverage score is constant in the Johnson setting, implying that the empirical Gram matrix is well conditioned with high probability once n is of order pD log(2pD) The normalized expected rank deficiency ρD,n quantifies the information lost when sampled evaluations leave part of the fitted space unidentified

Centering and Completion Estimator

The centered completion estimator controls the error caused by incomplete coverage while also averaging the observation noise The risk bound is given by sup f∈Esd,k(B) sup P∈Pσ2 Ef,P fbcomp − f 2 2 ≤ Bρm,n + 2σ2 ηn,N This bound separates approximation error from observation noise and incomplete design coverage

Conclusion

The results turn classical Johnson harmonic analysis into a nonparametric framework for regression with subsets as covariates The resulting spectral scale characterizes the minimax risk up to constants depending only on a fixed upper bound for the ratio B/σ2 of the Johnson–Sobolev energy budget to the noise variance The rank-aware bounds are sharp up to the explicit factor γs m,d, and hence up to constants when m = min(k, d − k) and s are fixed The minimax risk is of order σ2 Nn/n or σ2 d/k n/n when k is fixed If dn = k + log n, the resulting rate is of order σ2 (log n) k/n

Supplementary Material

The supplementary material contains the numerical experiments, the canonical frame construction, and proofs of all results stated in the main article The numerical study has two parts. We first compare predictive performance under the pairwise and diffuse target profiles The third panel compares centered empirical projection fb proj squared and stable least squares over W2 as the signal strength increases relative to the observation noise The final panel illustrates the incomplete-coverage mechanism using the exact expression (23)

References

Balcan, M.-F., Constantin, F., Iwata, S., and Wang, L. (2012). Learning valuation functions. p. 4 In Mannor, S., Srebro, N., and Williamson, R. C., editors, Proc. 25th COLT

Balcan, M.-F., Vitercik, E., and White, C. (2016). Learning combinatorial functions from pairwise comparisons. p. 5 In Feldman, V., Rakhlin, A., and Shamir, O., editors, Proc. 29th COLT

Bannai, E. and Ito, T. p. 2 (1984). Algebraic Combinatorics I: Association Schemes. p. 6 Benjamin/Cummings

Benavoli, A., Azzimonti, D., and Piga, D. (2023). Learning choice functions with Gaussian processes. p. 4 In Evans, R. J. and Shpitser, I., editors, Proc. 39th UAI

Brouwer, A. E., Cohen, A. p. 5 M., and Neumaier, A. (1989). Distance-Regular Graphs

Cohen, A., Davenport, M. A., and Leviatan, D. (2013). On the stability and accuracy of least squares approximations

Cohen, A., Davenport, M. A., and Leviatan, D. (2019). Correction to: On the stability and accuracy of least squares approximations

De, A. and Chakrabarti, S. p. 5 (2022). Neural estimation of submodular functions with applications to differentiable subset selection

Dolhansky, B. W. and Bilmes, J. p. 5 A. (2016). Deep submodular functions: Definitions and learning

Filmus, Y. (2016). An orthogonal basis for functions over a slice of the Boolean hypercube

Gottlieb, D. H. (1966). A certain class of incidence matrices

Green, A., Balakrishnan, S., and Tibshirani, R. J. (2021). Minimax optimal regression over Sobolev spaces via Laplacian regularization on neighborhood graphs

Iglesias, R. and Natale, M. p. 6 (2022). A fast Fourier transform for the Johnson graph

Kirichenko, A. and van Zanten, H. p. 5 p. 5 (2017). Estimating a smooth function on a large graph by Bayesian Laplacian regularisation

Kirichenko, A. and van Zanten, H. (2018). Minimax lower bounds for function estimation on graphs

Liang, H., Wan, X., and Dong, X. (2024). Bayesian optimization of functions over node subsets in graphs

Massart, P. (2007). Concentration Inequalities and Model Selection

O’Donnell, R. (2014). Analysis of Boolean Functions

Oh, C., Tomczak, J. M., Gavves, E., and Welling, M. (2019). Combinatorial Bayesian optimization using the graph Cartesian product

Puy, G., Tremblay, N., Gribonval, R., and Vandergheynst, P. (2018). Random sampling of bandlimited signals on graphs

Qian, C., Shi, J.-C., Yu, Y., Tang, K., and Zhou, Z.-H. (2017). Subset selection under noise

Shi, Z., Balasubramanian, K., and Polonik, W. (2024). Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regression

Stobbe, P. and Krause, A. p. 5 (2012). Learning Fourier sparse set functions. p. 4 In Lawrence, N. D., and Girolami, M., editors, Proc. 15th AISTATS

Tsybakov, A. B. (2009). Introduction to Nonparametric Estimation

Wagstaff, E., Fuchs, F., Engelcke, M., Posner, I., and Osborne, M. A. (2019). On the limitations of representing functions on sets

Zaheer, M., Kottur, S., Ravanbakhsh, S., Póczos, B., Salakhutdinov, R., and Smola, A. J. (2017).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved estimation of response functions via Johnson harmonic decomposition allows for explicit approximation spaces based on interaction order D, which determines how many coefficients must be estimated (pD).

  2. The framework provides nonasymptotic minimax risk bounds that explicitly separate three distinct error sources: approximation error (bD), observation noise (sigma squared pD/n), and incomplete design coverage (rhoDn).

  3. Stable least squares estimators can be used to remove the signal-dependent fluctuation of empirical projection when the empirical Gram matrix is well conditioned, ensuring that even without observation noise, estimation remains stable under random design.

  4. A centered completion estimator can be constructed to handle incomplete coverage by assigning a common value to unobserved subsets, and its risk bound is shown to account for both approximation error and the noise variance of the observed cell means.

  5. The rank-aware minimax bounds combine the spectral scale (driven by noise) and the design-deficiency scale (driven by unidentifiable components), leading to a unified characterization of estimation difficulty, especially when B/sigma squared is unbounded.

Related papers