Pith. sign in

REVIEW 3 major objections 6 minor 1 cited by

Sample Complexity of Bias Detection with Subsampled Point-to-Subspace Distances

T0 review · 3 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that random bin subsampling gives a PAC guarantee for supremum-norm bias detection, with false positives below delta and no false negatives.

desk verdict The main PAC guarantee is false as stated—the condition and the proof argue from opposite sides of the violation threshold—so the paper's central claim does not hold up. read the letter →

arxiv 2502.02623 v1 pith:WECQAESY submitted 2025-02-04 cs.LG cs.AImath.STstat.TH

German Martinez Matilla , Jakub Marecek This is my paper · ORCID
classification cs.LGcs.AImath.STstat.TH MSC 68Q32
keywords biasdetectionsamplecomplexitypoint-to-subspacedistancesupremumnormsubsamplingPAClearningepsilon-netVCdimension
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Bias detection between a test distribution and a reference distribution is usually treated as a distance-estimation problem, and standard distances such as Wasserstein-2 suffer from a curse of dimensionality. This paper reformulates bias detection as a point-to-subspace query in the supremum norm over histogram bins, and shows that the query can be answered from a small uniform random subset of the bins. The main theorem bounds the probability of a false positive by $\delta$ using $s = O\!\left(\frac{n\log n}{\epsilon}\log\frac{n\log n}{\epsilon} + \frac{1}{\epsilon}\log\frac{1}{\delta}\right)$ random bin checks, where $n$ is the number of encoded features and $\epsilon$ the tolerated fraction of violating bins. That means a single-subgroup bias audit, which regulation may require for exponentially many subgroups, can have per-subgroup sample complexity growing almost linearly in the number of features rather than exponentially in it. The authors corroborate the theory with experiments on recidivism and census-derived datasets showing that error drops quickly with sample size and rises only mildly with dimension.

What carries the argument

The central object is the subsampled point-to-subspace query: a discrete test measure $\alpha_0$ is compared coordinate-wise against a histogram approximation of a subspace $V$, and Algorithm 2 returns TRUE unless at least one sampled bin fails $|\alpha_0(x_i) - a_i| < \Delta$. The carrying theoretical device is the epsilon-net theorem: the family of possible violation sets (bins where $|\alpha_0(\text{bin}) - a_{\text{bin}}| \geq \Delta$) is treated as a range space, and if its VC dimension is $d$, then $s = O\!\left(\frac{d}{\epsilon}\log\frac{d}{\epsilon} + \frac{1}{\epsilon}\log\frac{1}{\delta}\right)$ uniform random bins form an $\epsilon$-net with probability at least $1-\delta$, bounding the false-positive probability. The proof bounds $d$ by $O(n\log n)$ by viewing each inequality as a halfspace in $\mathbb{R}^n$, applying the halfspace VC-dimension bound $n+1$ to each of the two absolute-value faces, and then applying a union bound for the combination. The threshold $\Delta$ doubles as the uncertainty interval around reference histogram bins, so survey-sampling uncertainty is built directly into the query.

What would settle it

Take a small feature count, say $n=2$ or $n=3$, with many bins per feature, and compute the VC dimension of the family of violation sets $\{\text{bins}: |\alpha_0(\text{bin}) - a_{\text{bin}}| \geq \Delta\}$ as the test measure and reference histogram range over the simplex. If that dimension grows with the number of bins $N$ rather than staying $O(n\log n)$, the epsilon-net argument in Theorem 8 cannot deliver the stated bound. A cheaper test is to adversarially construct a test measure whose violation bins are arranged in a pattern not separable by halfspaces in feature space, run Algorithm 2 many times with the claimed sample count, and check whether the false-positive rate exceeds $\delta$.

Watch

Extended reading notes

Core claim

The paper claims that testing whether a test measure belongs to a histogram-defined subspace of probability measures, under the supremum norm, is PAC-learnable by uniform subsampling of bins. Concretely, if at most an $\epsilon$ fraction of the $N$ bin inequalities $|\alpha_0(\text{bin}) - a_{\text{bin}}| \geq \Delta$ are violated, then Algorithm 2, which checks only $s = O\!\left(\frac{n\log n}{\epsilon}\log\frac{n\log n}{\epsilon} + \frac{1}{\epsilon}\log\frac{1}{\delta}\right)$ randomly chosen bins, reports a false positive with probability at most $\delta$. The argument identifies the set of violating bins as a range space over the $n$ encoded features, bounds its VC dimension by $O(n\log n)$ as a union of two halfspace range spaces in $\mathbb{R}^n$, and applies the epsilon-net theorem. The authors also observe that false negatives cannot occur: if the test measure truly lies in the subspace, no sampled bin can violate the threshold, so the algorithm always returns TRUE. Experiments on two benchmark data sources show error probabilities that decrease with sample size and increase only slowly with dimension, matching the shape of the bound.

Load-bearing premise

The load-bearing premise is that the family of bin sets that would count as violations is no more complex than halfspace cuts in feature space, so the random-sampling guarantee applies with a complexity that grows like $n\log n$ rather than with the number of bins; if the true family is more complex because the inequalities live on the probability simplex, the claimed sample count is unsupported.

Editorial extensions

If this is right

  • A single bias check on one subgroup can be run with sample complexity polynomial in the number of encoded features, so auditing exponentially many protected subgroups remains feasible when each subgroup is tested independently.
  • Because false negatives are impossible, the subsampled test is conservative: if it says the subgroup is inside the tolerance subspace, the full check would agree, and the only error is the bounded false-positive rate $\delta$.
  • Uncertainty in the reference population, such as survey sampling error, can be encoded as bin-wise intervals of width $\Delta$, and the same PAC guarantee covers all reference histograms consistent with those intervals.
  • The error probability grows only mildly with the number of encoded features, in contrast to Wasserstein-2 and related distances whose sample complexity suffers the curse of dimensionality.
  • The paired $\epsilon$ and $\delta$ control lets an auditor choose the sample size to meet a desired statistical error bound for a fixed test set, such as a fixed set of cases obtained through a freedom-of-information request.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the same subsampling argument should apply to any coordinate-wise threshold test whose violation sets form a range space of bounded VC dimension, not only to histogram bins in the supremum norm.
  • Editorial inference: defining the range space directly on the simplex of bin masses would make the proof self-contained and would pin down the exact VC dimension for small $n$ and varying bin counts.
  • Editorial inference: adaptive or stratified bin sampling informed by prior violation estimates could reduce the constant in the sample bound while preserving the epsilon-net argument, provided the sampling density is bounded away from zero on every violation range.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes a method for bias detection by testing whether a test measure lies within a subspace of probability measures defined by histogram bins with tolerance Δ. It reformulates the problem as a point-to-subspace query under the supremum norm, and introduces Algorithm 2, which samples a subset of the N histogram bins uniformly at random. The main theoretical contribution is Theorem 8, which claims a PAC-style bound on the false-positive probability as a function of the sample size s, independent of N, under the assumption that the number of violating bins is at most εN. The paper also reports experiments on the Adult and folktables datasets comparing the error rate of the proposed subsampling scheme with the Wasserstein-2 distance.

Significance. If the main theorem were correct, the paper would provide a practically valuable result: bias detection with sample complexity polynomial in the number of encoded features n and 1/ε, avoiding the exponential dependence on ambient dimension that affects many distribution distances. The reformulation of bias detection as a point-to-subspace query is conceptually appealing, and the experiments on well-known datasets give the paper a concrete grounding. However, the central claim is not established: Theorem 8 is false as stated, and the proof misapplies epsilon-net machinery. The paper does make falsifiable predictions (e.g., error rates increase as ε decreases), and its experimental results appear to confirm those predictions, but this does not compensate for the failure of the load-bearing theoretical result.

major comments (3)
  1. [Section 5, Theorem 8] The theorem assumes that the number of violating bins is at most εN (ℓ0(vhist(α)) ≤ εN), but the proof requires at least εN violations. If there is exactly one violating bin, the hypothesis is satisfied for every ε ≥ 1/N. A uniform sample of s bins misses this single violation with probability (1−1/N)^s (or (N−s)/N when sampling without replacement), which tends to 1 as N→∞ for any fixed s. Since the claimed bound on s does not depend on N, the asserted false-positive probability δ cannot hold uniformly. The proof sketch itself switches to 'an input with εN distances greater than the threshold', which is the opposite inequality from the statement. The theorem is therefore false as stated.
  2. [Section 5, proof of Theorem 8] The epsilon-net argument is applied in the wrong direction: the standard epsilon-net theorem guarantees that each range of measure at least ε is hit, whereas the set of violating bins is assumed to have measure at most ε. Even if the inequality were reversed, the identification of the ranges as halfspaces in R^n is not established; the inequality (10) involves N bin-specific constraints on the combined space of test measures and reference histograms, and the paper does not show that the induced family of violation sets has VC dimension O(n log n). The proof cites [28] for the technique but does not supply the required reduction, so the advertised sample complexity does not follow from the given argument.
  3. [Section 6.2, Figure 5] The experimental results are actually consistent with the failure of Theorem 8. The text reports that for ε = 0.001 the one-sided error is 'more than half the time' for the sample sizes used. This is exactly what one expects when the number of violating bins is small: uniform subsampling misses them with high probability. Thus the experiments do not corroborate the PAC claim; instead they illustrate its breakdown at small ε.
minor comments (6)
  1. [Section 4, Definition 4] The projection α|S uses the notation δ{S}, which is undefined; it should be δ_x for each sampled point x in S.
  2. [Section 2] The notation α0(xi) is used for the mass of the atomic measure at point xi, but α0 is a measure rather than a function; this shorthand should be defined explicitly.
  3. [Section 5, proof sketch] The sentence 'the polyhedron in R^n delimited by the inequalities in (10)' appears to confuse the number of inequalities: (10) contains N inequalities (one per bin), not 2n halfspaces, and the ambient dimension is not specified.
  4. [Section 6] The word 'Wassertein' in the opening sentence of Section 6 should be 'Wasserstein'.
  5. [Section 5, Theorem 8] The phrase 'with probability δ' is ambiguous; it presumably means 'with probability at most δ'.
  6. [General] The code used for the experiments is not provided, which limits reproducibility; a link to a public repository would be helpful.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: Theorem 8 is an independent PAC bound, and the sole self-citation [28] contributes a proof technique rather than the theorem itself.

full rationale

The derivation chain is not circular in any of the enumerated senses. Theorem 8 is a new sample-complexity claim about Algorithm 2, and its intended proof depends on the standard epsilon-net theorem [29,30,31,32] and the textbook VC-dimension bound for halfspaces [33,34]; the authors' own reference [28] is used only to borrow the proof idea of viewing the inequality checks as a range space. That self-citation is not load-bearing as an external fact, because the cited paper is not the source of the PAC guarantee or of the VC-dimension bound. No parameter is fitted to a subset of the data and then renamed a prediction, and the false-positive event is not defined in terms of the sample-size bound being proved. The theorem is explicitly labelled a proof sketch, which is a completeness concern rather than a circularity one. A separate reviewer worry, also distinct from circularity, is that the epsilon-net step appears to require hitting ranges of mass at least epsilon*N while the hypothesis bounds the violating set by epsilon*N; if that gap is real, the theorem would fail honestly rather than assume its conclusion as an input. Consistent with the rubric, the one minor self-citation that is not load-bearing gives a low score rather than a finding of circularity.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The central claim rests on two assumptions: a range-space VC-dimension bound that is asserted but not proven, and a fixed-histogram model that ignores the survey uncertainty mentioned in the abstract. There are no fitted free parameters and no invented entities.

assumptions (2)
  • ad hoc to paper The set of bins violating |alpha0(bin) - a_bin| >= Delta over all test measures and reference histograms forms a range space with VC dimension O(n log n), where n is the number of features.
    Asserted in the proof sketch of Theorem 8 (Section 5) without rigorous demonstration; the identification with halfspaces in R^n conflates feature count with bin count.
  • domain assumption The reference histogram and test histogram are fixed and exact; all statistical uncertainty in estimating them from data is captured by the tolerance Delta.
    Section 2 introduces uncertainty intervals around histogram bins, but the theorem treats the histograms as given and analyzes only the error from subsampling bins, not from estimating the histograms from finite survey samples.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sample Complexity of Bias Detection with Subsampled Point-to-Subspace Distances." pith.science (2026). https://pith.science/paper/WECQAESY

@misc{pith2026250202623,
  author       = {Pith},
  title        = {Pith review of: Sample Complexity of Bias Detection with Subsampled Point-to-Subspace Distances},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WECQAESY}},
  note         = {Machine review of arXiv:2502.02623}
}
read the original abstract

Sample complexity of bias estimation is a lower bound on the runtime of any bias detection method. Many regulatory frameworks require the bias to be tested for all subgroups, whose number grows exponentially with the number of protected attributes. Unless one wishes to run a bias detection with a doubly-exponential run-time, one should like to have polynomial complexity of bias detection for a single subgroup. At the same time, the reference data may be based on surveys, and thus come with non-trivial uncertainty. Here, we reformulate bias detection as a point-to-subspace problem on the space of measures and show that, for supremum norm, it can be subsampled efficiently. In particular, our probabilistically approximately correct (PAC) results are corroborated by tests on well-known instances.

Figures

Figures reproduced from arXiv: 2502.02623 by the authors.

Figure 1
Figure 1. Whole COMPAS dataset by decile score (a) Finite vectors h˜j ∈ R10 + spanning discrete subspace D ⊂ R10 + (b) Infinite histograms ˜a j ∈ Σ10 or subspace V ⊂ M1 +(R) [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Whole population approximation by decile score 2 A Motivating Example and Problem Defini￾tion Let us consider a motivating example. In the COMPAS [19] dataset, there are ≈ 7 · 103 instances, which surely do not account for the people sentenced using the COMPAS system, but we take to be a representative sample. Focusing on the attribute decile score, which tries to predict the recidivism risk, we can consider the res… view at source ↗
Figure 3
Figure 3. Test measure, α0 Algorithm 1 Point-to-subspace query in the supremum norm Input: Test measure α0 ∈ M1 +(R), histogram h ∈ R 10 + Parameter: ∆ ∈ R. Output: True/False 1: a ← normalise h. 2: for i=1 to 10 do 3: if |α0(xi) − ai | ≥ ∆ then 4: return FALSE 5: end if 6: end for 7: return TRUE Next, we look at the normalised histograms in the light of measure theory. The 10 different coordinates corresponding to the 10 bin… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: decile score and age relative frequencies with error bars of length ∆ where Σ10×10 ∈ a˜ k ij = ([aij − ∆, aij + ∆])ij ,    k = 1, . . . , ∞ i = 1, . . . , 10 j = 1, . . . , 10 Upon which we will compare the test measure P10 i=1 P10 j=1 a 0 ij δ{xi,yj } = α 0 ∈ M1 +(…
Figure 5
Figure 5. Figure 5: Probability of one-sided error for Wasserstein-2 and point-to-subspace dis [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: Probability of one-sided error for point-to-subspace distance in the supremum [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. humancompatible.detect: a Python Toolkit for Detecting Bias in AI Models

    cs.AI 2025-09 conditional novelty 4.0 of 10

    A Python toolkit, humancompatible.detect, finds the most biased subgroups and tests specified subgroups against a threshold using MSD and subsampled ℓ∞ distances.

Reference graph

Works this paper leans on

40 extracted references · 36 canonical work pages · cited by 1 Pith paper

  1. [28]

    Low-rank methods in event detection with subsampled point-to-subspace proximity tests,

    J. Marecek, S. Maroulis, V. Kalogeraki, and D. Gunopulos, “Low-rank methods in event detection with subsampled point-to-subspace proximity tests,” IEEE Access, vol. 10, p. 32525–32536, 2022

    work page 2022

  2. [1]

    Nonparametric estimators,

    A. B. Tsybakov, “Nonparametric estimators,” Introduction to Nonparamet- ric Estimation , pp. 1–76, 2009. 13 Figure 6: Probability of one-sided error for point-to-subspace distance in the supremum norm as a function of the sample size on folktables [37]

    work page 2009

  3. [2]

    Markov processes over denumerable products of spaces, describing large systems of automata,

    L. N. Vaserstein, “Markov processes over denumerable products of spaces, describing large systems of automata,” Problemy Peredachi Informatsii , vol. 5, no. 3, pp. 64–72, 1969

    work page 1969

  4. [3]

    The speed of mean glivenko-cantelli convergence,

    R. M. Dudley, “The speed of mean glivenko-cantelli convergence,” The Annals of Mathematical Statistics , vol. 40, no. 1, pp. 40–50, 1969

    work page 1969

  5. [4]

    A kernel two-sample test,

    A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Sch¨ olkopf, and A. Smola, “A kernel two-sample test,” The Journal of Machine Learning Research , vol. 13, no. 1, pp. 723–773, 2012

    work page 2012

  6. [5]

    Statistical estimation of ergodic markov chain kernel over discrete state space,

    G. Wolfer and A. Kontorovich, “Statistical estimation of ergodic markov chain kernel over discrete state space,” 2021

    work page 2021

  7. [6]

    Neue begr¨ undung der theorie quadratischer formen von un- endlichvielen ver¨ anderlichen.,

    E. Hellinger, “Neue begr¨ undung der theorie quadratischer formen von un- endlichvielen ver¨ anderlichen.,”Journal f¨ ur die reine und angewandte Math- ematik, vol. 1909, no. 136, pp. 210–271, 1909

    work page 1909

  8. [7]

    On the rate of convergence in wasserstein distance of the empirical measure,

    N. Fournier and A. Guillin, “On the rate of convergence in wasserstein distance of the empirical measure,” Probability theory and related fields , vol. 162, no. 3, pp. 707–738, 2015

    work page 2015

Show all 40 references
  1. [8]

    Sharp asymptotic and finite-sample rates of conver- gence of empirical measures in wasserstein distance,

    J. Weed and F. Bach, “Sharp asymptotic and finite-sample rates of conver- gence of empirical measures in wasserstein distance,” 2019

    2019

  2. [9]

    Statistical aspects of wasserstein dis- tances,

    V. M. Panaretos and Y. Zemel, “Statistical aspects of wasserstein dis- tances,” Annual review of statistics and its application , vol. 6, no. 1, pp. 405–431, 2019

    2019

  3. [10]

    On the rate of convergence of empirical measure in ∞-wasserstein distance for unbounded density function,

    A. Liu, J.-G. Liu, and Y. Lu, “On the rate of convergence of empirical measure in ∞-wasserstein distance for unbounded density function,” arXiv preprint arXiv:1807.08365, 2018. 14

    2018 arXiv

  4. [11]

    The total variation distance between high-dimensional gaussians with the same mean,

    L. Devroye, A. Mehrabian, and T. Reddad, “The total variation distance between high-dimensional gaussians with the same mean,” arXiv preprint arXiv:1810.08693, 2018

    2018 arXiv

  5. [12]

    Polynomial time and private learning of unbounded gaussian mixture models,

    J. Arbas, H. Ashtiani, and C. Liaw, “Polynomial time and private learning of unbounded gaussian mixture models,” in International Conference on Machine Learning, pp. 1018–1040, PMLR, 2023

    2023

  6. [13]

    Sample com- plexity of sinkhorn divergences,

    A. Genevay, L. Chizat, F. Bach, M. Cuturi, and G. Peyr´ e, “Sample com- plexity of sinkhorn divergences,” in The 22nd international conference on artificial intelligence and statistics , pp. 1574–1583, PMLR, 2019

    2019

  7. [14]

    Convergence and finite sample approximations of entropic regularized wasserstein distances in gaussian and rkhs settings,

    M. H. Quang, “Convergence and finite sample approximations of entropic regularized wasserstein distances in gaussian and rkhs settings,” arXiv preprint arXiv:2101.01429, 2021

    2021 arXiv

  8. [15]

    Minimax esti- mation of maximum mean discrepancy with radial kernels,

    I. O. Tolstikhin, B. K. Sriperumbudur, and B. Sch¨ olkopf, “Minimax esti- mation of maximum mean discrepancy with radial kernels,” in Advances in Neural Information Processing Systems (D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, eds.), vol. 29, Curran Associates...

    2016

  9. [16]

    Sample complexity of probability divergences under group symmetry,

    Z. Chen, M. Katsoulakis, L. Rey-Bellet, and W. Zhu, “Sample complexity of probability divergences under group symmetry,” in International Con- ference on Machine Learning , pp. 4713–4734, PMLR, 2023

    2023

  10. [17]

    Sample complexity bounds for estimating the wasserstein distance under invariances,

    B. Tahmasebi and S. Jegelka, “Sample complexity bounds for estimating the wasserstein distance under invariances,” 2023. https://arxiv.org/abs/2311.02868

    2023

  11. [18]

    Computability of optimizers,

    Y. Lee, H. Boche, and G. Kutyniok, “Computability of optimizers,” IEEE Transactions on Information Theory , 2023

    2023

  12. [19]

    How we analyzed the compas recidivism algorithm

    J. Angwin, L. Kirchner, S. Mattu, and J. Larson, “How we analyzed the compas recidivism algorithm.” ProPublica, 2016

    2016

  13. [20]

    It’s compaslicated: The messy rela- tionship between rai datasets and algorithmic fairness benchmarks,

    M. Bao, A. Zhou, S. Zottola, B. Brubach, S. Desmarais, A. Horowitz, K. Lum, and S. Venkatasubramanian, “It’s compaslicated: The messy rela- tionship between rai datasets and algorithmic fairness benchmarks,” arXiv preprint arXiv:2106.05498, 2021

    2021 arXiv

  14. [21]

    A kernel method for the two-sample problem,

    A. Gretton, K. Borgwardt, M. J. Rasch, B. Scholkopf, and A. J. Smola, “A kernel method for the two-sample problem,” 2008

    2008

  15. [22]

    R. M. Dudley, Real analysis and probability , vol. 74 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2002. Revised reprint of the 1989 original

    2002

  16. [23]

    Berlinet and C

    A. Berlinet and C. Thomas-Agnan, Reproducing kernel Hilbert spaces in probability and statistics. Kluwer Academic Publishers, Boston, MA, 2004. With a preface by Persi Diaconis. 15

    2004

  17. [24]

    Computational optimal transport,

    G. Peyr´ e and M. Cuturi, “Computational optimal transport,” 2020

    2020

  18. [25]

    Monge, M´ emoire sur la th´ eorie des d´ eblais et des remblais

    G. Monge, M´ emoire sur la th´ eorie des d´ eblais et des remblais. Imprimerie royale, 1781

  19. [26]

    On the translocation of masses,

    L. V. Kantorovich, “On the translocation of masses,” Journal of Mathe- matical Science, vol. 133, p. 1381–1382, 2006

    2006

  20. [27]

    On the uniform convergence of relative frequencies of events to their probabilities,

    V. N. Vapnik and A. Y. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities,” in Measures of com- plexity, pp. 11–30, Springer, Cham, 1971. Reprint of Theor. Probability Appl. 16 (1971), 264–280

    1971

  21. [29]

    ϵ-nets and simplex range queries,

    D. Haussler and E. Welzl, “ ϵ-nets and simplex range queries,” Discrete Comput. Geom., vol. 2, no. 2, pp. 127–151, 1987

    1987

  22. [30]

    Epsilon-nets and simplex range queries,

    D. Haussler and E. Welzl, “Epsilon-nets and simplex range queries,” in Proceedings of the Second Annual Symposium on Computational Geometry, SCG ’86, (New York, NY, USA), p. 61–71, Association for Computing Machinery, 1986

    1986

  23. [31]

    Further applications of random sampling to computational geometry,

    K. L. Clarkson, “Further applications of random sampling to computational geometry,” in Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing , STOC ’86, (New York, NY, USA), p. 414–423, As- sociation for Computing Machinery, 1986

    1986

  24. [32]

    New applications of random sampling in computational geometry,

    K. L. Clarkson, “New applications of random sampling in computational geometry,” Discrete Comput. Geom. , vol. 2, no. 2, pp. 195–222, 1987

    1987

  25. [33]

    Lecture notes: Geom- etry: Combinatorics and Algorithms

    L. Barba, B. G¨ artner, M. Hoffmann, and E. Welzl, “Lecture notes: Geom- etry: Combinatorics and Algorithms.” https://geometry.inf.ethz.ch/, August, 2019

    2019

  26. [34]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal, Probability and computing . Cambridge University Press, Cambridge, second ed., 2017. Randomization and prob- abilistic techniques in algorithms and data analysis

    2017

  27. [35]

    Pot: Python optimal transport,

    R. Flamary, N. Courty, A. Gramfort, M. Z. Alaya, A. Boisbunon, S. Cham- bon, L. Chapel, A. Corenflos, K. Fatras, N. Fournier, L. Gautheron, N. T. Gayraud, H. Janati, A. Rakotomamonjy, I. Redko, A. Rolet, A. Schutz, V. Seguy, D. J. Sutherland, R. Tavenard, A. Tong, and T. Vayer...

    2021

  28. [36]

    Becker and R

    B. Becker and R. Kohavi, “Adult.” UCI Machine Learning Repository,

  29. [37]

    Retiring adult: New datasets for fair machine learning,

    F. Ding, M. Hardt, J. Miller, and L. Schmidt, “Retiring adult: New datasets for fair machine learning,” Advances in Neural Information Processing Sys- tems, vol. 34, 2021

    2021

  30. [38]

    Minimax estimation of maximum mean discrepancy with radial kernels,

    B. Sch¨ olkopf, I. Tolstikhin, and B. Sriperumbudur, “Minimax estimation of maximum mean discrepancy with radial kernels,” NIPS, 2016

    2016

  31. [39]

    On the sample complexity of learning functions with bounded variation,

    P. M. Long, “On the sample complexity of learning functions with bounded variation,” in Proceedings of the eleventh annual conference on Computa- tional learning theory , pp. 126–133, 1998. 17

    1998

  32. [1996]

    DOI: https://doi.org/10.24432/C5XW20. 16

    doi

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.