Pith. sign in

REVIEW 4 major objections 4 minor 13 references

Medix: Out-of-Distribution Detection from Unlabeled Wild Data via Robust Gradient Statistics

T0 review · 4 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Pith's one-line read Medix claims that a median-of-gradients filter can pick out-of-distribution samples out of unlabeled wild data with provably small error, and then train a binary OOD detector without any clean OOD examples.

desk verdict The median-filtering idea is fresh and the empirical results are strong, but the theorems do not analyze the algorithm that is actually run, so the paper's central claim of provable separation is unsupported as written. read the letter →

arxiv 2510.06505 v2 pith:HXXPEEMI submitted 2025-10-07 cs.LG cs.AImath.OCstat.ML

classification cs.LGcs.AImath.OCstat.ML
keywords median-basedoutlierfilteringunlabeledwilddataout-of-distributiondetectiongradientstatisticsHubercontaminationmodelelement-wisemediangreedytheoreticalerrorbounds
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

Medix is built on a simple statistical bet: the element-wise median of per-sample loss gradients, measured against the mean in-distribution gradient, shifts when out-of-distribution samples are present, while remaining stable to a moderate fraction of outliers. The paper claims that finding the wild subset whose element-wise median is closest to the mean in-distribution gradient isolates the in-distribution part of the mixture, so the complement is a usable OOD training set. Theorems 4.1 and 4.2 bound both kinds of filtering mistakes—in-distribution samples wrongly flagged and OOD samples wrongly kept—under sub-Gaussian gradient coordinates and, for the OOD side, a separation between mean gradients. If the claims hold, a deployed model can turn the unlabeled data it naturally encounters into supervision for OOD detection, with no clean OOD dataset required. Empirically the authors report average FPR95 of 0.80% on CIFAR-10 and 5.42% on CIFAR-100, ahead of wild-data baselines.

What carries the argument

Element-wise median (EWM) of per-sample gradients: for each coordinate of the gradient vector, take the median across samples in the current wild set, then compare the resulting vector to the mean InD gradient ∇̄in by L2 distance. Its role is to act as a location statistic with a high breakdown point, so OOD gradients can pull it only when they exceed 50% of the mixture; the greedy top-k removal then scores each sample by the drop in this distance if removed. The same median statistic feeds both the inlier and outlier error bounds, with contamination and concentration effects driving the rates.

What would settle it

On a small synthetic mixture where exhaustive subset search is feasible, compute the exact minimizer of Equation (4) and run Algorithm 1 on the same data. If the greedy output has inlier misclassification above the Theorem 4.1 bound while the exact minimizer satisfies it, then the theorem, as proven, does not govern Medix's actual filtering rule.

Watch

Extended reading notes

Core claim

Under the Huber contamination model Pwild=(1−π)Pin+πPout, Medix first trains an in-distribution classifier fφ, computes the mean gradient ∇̄in over labeled InD data, then computes the element-wise median (EWM) of gradients over the unlabeled wild set. A greedy leave-one-out procedure removes the k samples whose deletion most reduces the L2 distance ∥EWM−∇̄in∥, iterating until the drop falls below ε, and returns the removed set as candidate OOD. The paper's central theoretical claim is that this median rule is two-sided stable: with high probability the fraction of InD points flagged as OOD is bounded by a concentration term plus π/(2(1−π)), and the fraction of OOD points retained as InD is b

Load-bearing premise

The theory assumes that the outlier set Medix actually returns is an exact minimizer of the median-distance objective; the proofs argue by swapping points into an optimal subset of fixed size, while Algorithm 1 is a greedy top-k removal and the stated optimization allows any subset. If the greedy output and the exact optimum diverge, the proved bounds may not describe what Medix returns.

Editorial extensions

If this is right

  • OOD detectors can be trained from a pretrained in-distribution classifier plus unlabeled wild data, with no clean OOD examples, whenever the OOD fraction stays below 50%.
  • Misclassification error on in-distribution samples decays like 1/√min plus a contamination penalty that grows with π/(2(1−π)).
  • OOD samples whose mean gradient is Δ√d away from the InD mean are retained with error that decays exponentially in (Δ−ε)^2/(2σ²_out).
  • Gradient median filtering works under dataset-level random mixing, without requiring the batch-level InD/OOD mixing structure assumed by earlier wild-data methods.
  • In the reported experiments, the method achieves average FPR95 of 0.80% on CIFAR-10 and 5.42% on CIFAR-100, and a 12.5% error rate on a synthetic outlier-extraction demo.

Reading between the lines

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

  • Editorial inference: the median criterion only tracks the location of gradients; an OOD distribution with the same mean gradient as InD but different covariance or tails would be invisible to the filter, so the method's real scope is mean-shift OOD.
  • Editorial inference: the proof's coordinate-wise majority argument is cleanest when gradient coordinates are independent; on real networks, coordinates are correlated, so a whitened or covariance-aware median may need less data to reach the same bounds.
  • Editorial inference: a testable extension is to run per-class or per-layer medians instead of one global EWM, which could catch class-conditional OOD modes that the global median averages away.
  • Editorial inference: because wild-sample gradients are computed with pseudo-labels from the InD classifier, a systematically wrong pseudo-label regime is a natural stress test; the appendix checks low-confidence labels but not structured label error.
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

4 major / 4 minor

Summary. The paper proposes Medix, a two-stage OOD detection method. In the first stage, candidate OOD samples are filtered from unlabeled wild data by comparing the element-wise median (EWM) of wild-data gradients with the mean InD gradient; Algorithm 1 greedily removes the k samples whose removal most reduces the L2 deviation, stopping when the change falls below a threshold epsilon. In the second stage, a binary OOD detector is trained on the labeled InD data plus the extracted candidates. The main theoretical contribution is Theorems 4.1 and 4.2, which are claimed to bound the inlier and outlier misclassification rates of this 'EWM filtering rule' by contamination, concentration, and separation terms. Experiments on CIFAR-10 and CIFAR-100 report state-of-the-art FPR95, e.g., 0.80% and 5.42% average FPR95 respectively.

Significance. If the theoretical claims were sound and the empirical protocol valid, this would be a valuable contribution: a principled, theoretically grounded way to exploit unlabeled wild data for OOD detection without requiring a clean auxiliary OOD set, with surprisingly strong benchmark results. The paper also attempts to relax the sub-Gaussian assumption in Appendix C.3 and states that code is provided. However, the central theorem is not sound as stated: it proves a statement about an exact minimizer of a different optimization problem than the one Algorithm 1 solves, and even for the exact minimizer the proof uses an implicit cardinality assumption that Eq. (4) does not impose. The benchmark gains are also weakened by reporting results with hyperparameters explicitly selected to maximize OOD performance. I cannot recommend acceptance.

major comments (4)
  1. [§4 and Appendix C.1 (Theorems 4.1, 4.2)] The theorems are stated for the 'EWM filtering rule', but the proofs analyze S*, the exact minimizer of Eq. (4), while Algorithm 1 is a greedy top-k removal procedure with a stopping threshold epsilon. No approximation bound connects the algorithm's output to S*. Moreover, the proof's swapping construction 'maintains cardinality: |Ŝ|=|S*|' but then treats the median as being over all m entries of Swild (X^(j)={x_1,...,x_m}). Eq. (4) imposes no cardinality constraint and S* need not have size m; the empty set is even allowed, although EWM(G_S) is undefined there. Thus the optimality contradiction applies to a different, implicitly cardinality-constrained problem, and the claimed guarantee for the method actually run is not established.
  2. [§5.1, Theorem 4.1] At the default experimental contamination rate pi=0.5, the contamination terms in Theorems 4.1 and 4.2 are pi/(2(1-pi)) = 0.5 and (1-pi)/(2pi) = 0.5, respectively. A bound of 0.5 on a misclassification rate is vacuous and does not support the paper's claims of a 'low error rate' or 'rigorous theoretical assurance that Medix minimizes both types of errors'. The text says the bound is controlled for pi<0.5, but the experiments use pi=0.5 and the conclusion claims robustness 'up to 50%' contamination. The theorem therefore does not predict the reported extraction error (12.5%) or FPR95 values.
  3. [§5.2] The hyperparameters epsilon and k are selected 'with the objective of maximizing OOD performance'. These are the stopping threshold and removal batch size of the filtering algorithm, so choosing them by OOD test performance constitutes test-set adaptation. The strong empirical numbers in Tables 1 and 2 are therefore not a clean evaluation of Medix as an unsupervised filtering method. A separate validation-based selection rule, or fixed defaults, is needed before the empirical claims can be assessed.
  4. [Appendix C.1, Eqs. (21)-(22)] There is an algebraic inconsistency in the proof of Theorem 4.1. With epsilon = sigma * sqrt(2 log(2 d m_in)), the union-bound probability 2d exp(-epsilon^2 / (2 sigma^2)) equals 1/m_in. Equation (22) then displays '= 1/m_in + 2 sqrt(log(1/delta)/(2m_in)) + pi/(2(1-pi))', which inserts the contamination term without derivation and drops the factor of two that Step 2's conclusion ERR_in <= 2*eta + pi/(2(1-pi)) would imply for the first term. Either the theorem statement or the proof must be corrected; as written, the displayed bound is not a consequence of the preceding inequalities.
minor comments (4)
  1. [Eq. (4)] The optimization problem is ill-posed as written: it minimizes over all subsets S of Swild, including the empty set, but EWM(G_S) is undefined for empty S. Specify that S must be non-empty or define a convention.
  2. [Algorithm 1] Line 10 sets delta_max to max_{i in S} {delta_i} after S has already been updated, but the delta_i values were computed for the previous S. Clarify whether the stopping condition is evaluated on the pre-removal or post-removal set.
  3. [Theorem C.3] The proof assumes that the coordinates v_j are independent across j, but this assumption is not stated in the theorem. It also switches between treating the mean gradient as the population mean and as the empirical mean defined in Eq. (3); the distinction should be clarified.
  4. [Figure 2 and Table 3] Figure 2 reports an error rate of 12.5% while also stating that 87.5% of actual OOD samples are flagged; these are different quantities and should be defined explicitly. Table 3 reports no standard deviations for the hyperparameter sensitivity results.

Circularity Check

1 steps flagged · score 4.0 of 10

Empirical FPR95 numbers are tuned on the reported OOD metric, but the central theoretical derivation is not definitionally circular.

  1. fitted input called prediction [Section 5.2, Experimental Setup (hyperparameter selection)]
    "Hyperparameters ϵ and k used in the proposed method Medix are selected from the sets {5e-5, 5e-4, 5e-3, 5e-2} and {4k, 7k, 10k, 20k}, respectively, taking into account dataset sizes and with the objective of maximizing OOD performance."

    The OOD performance being maximized is the same FPR95/AUROC reported in Tables 1-2 as evidence that Medix achieves low error. Selecting ϵ and k to maximize the reported metric makes the strong numbers (e.g., 0.80% average FPR95 on CIFAR-10) in-sample optimized values rather than out-of-sample predictions. The theorems cannot supply these numbers: at the default π=0.5 the contamination terms alone are 0.5 in both bounds, so the theory does not predict near-zero FPR95. Thus the empirical validation partly reduces to hyperparameter fitting rather than to the derivation.

full rationale

The core derivation (Eq. 4 through Theorems 4.1/4.2) is not circular by construction: the contamination and concentration bounds follow from sub-Gaussianity, separation, and counting arguments, not from the desired error rates. The only self-citation (Abbas et al. 2025) appears in a related-work list and is not load-bearing. However, the empirical claims are partially circular: Section 5.2 explicitly tunes ϵ and k to maximize OOD performance, and the reported FPR95/AUROC values are then used to substantiate the method's low error, so those numbers are optimized results rather than predictions. Separately, Appendix C.1 analyzes a cardinality-preserving swap for the exact minimizer of Eq. (4), while Algorithm 1 is an unconstrained greedy top-k removal; this is a theorem-to-algorithm correctness gap rather than a definitional circularity, so it is noted here but does not by itself increase the circularity score beyond 4.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities. Its free parameters are the algorithm hyperparameters (k, epsilon, loss weight) and the experimental contamination ratio. The load-bearing assumptions are the Huber mixture model, sub-Gaussian gradients, OOD mean separation, and an implicit cardinality assumption in the proof that is not stated anywhere and is contradicted by the algorithm's own behavior.

free parameters (3)
  • k (top-k removal batch) = 20000 (default; searched over {4k, 7k, 10k, 20k})
    Algorithm 1 removes the k samples with the largest δ_i each iteration; k is selected per dataset 'with the objective of maximizing OOD performance' (§5.2), so the final FPR95 depends on this tuned value.
  • epsilon (stopping threshold) = 0.005 (default; searched over {5e-5, 5e-4, 5e-3, 5e-2})
    The stopping criterion |δ_max| > epsilon in Algorithm 1 is not derived from the theory; it is selected to maximize OOD performance (§5.2), making the empirical claims partly fitting-dependent.
  • binary loss weight = 10
    The OOD detector training in §5.2 weights the binary classification component by 10, a hand-set value that affects the final detector but is not part of the filtering theory.
assumptions (4)
  • domain assumption Huber contamination model: Pwild = (1−π)Pin + πPout
    Section 2, Eq. (1). Assumes wild data is an exact mixture of InD and OOD with known structure, no label noise or corrupted sampling; Section B acknowledges this may be violated in practice.
  • domain assumption Each InD gradient coordinate is i.i.d. sub-Gaussian with variance proxy σ²
    Theorem 4.1 and Appendix C.1 require this to get the concentration term. Remark 4.3 offers only empirical histogram/Q-Q plot evidence from one setting, not a proof. A looser theorem (C.3) still requires finite fourth moments and coordinate independence.
  • domain assumption OOD gradients are i.i.d., sub-Gaussian, and their mean satisfies ||μ_out − ∇in|| ≥ Δ√d
    Theorem 4.2 and Appendix C.2 require this separation condition to get the exponential term. The experiments do not verify this condition for the CIFAR or SVHN gradients used.
  • ad hoc to paper The minimizer S* of Eq. (4) has the same cardinality as the full wild set, so its element-wise median is over m entries
    This is not stated as an assumption but is used throughout the swapping proof in Appendix C.1. Eq. (4) imposes no cardinality constraint, and Algorithm 1 returns a strict subset, so the proof's majoritarian median argument does not apply.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Medix: Out-of-Distribution Detection from Unlabeled Wild Data via Robust Gradient Statistics." pith.science (2026). https://pith.science/paper/HXXPEEMI

@misc{pith2026251006505,
  author       = {Pith},
  title        = {Pith review of: Medix: Out-of-Distribution Detection from Unlabeled Wild Data via Robust Gradient Statistics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HXXPEEMI}},
  note         = {Machine review of arXiv:2510.06505}
}
read the original abstract

Out-of-distribution (OOD) detection plays a crucial role in ensuring the robustness of machine learning systems deployed in real-world applications. Recent approaches have explored the use of unlabeled data, showing potential for enhancing OOD detection capabilities. However, effectively utilizing unlabeled in-the-wild data remains challenging due to the mixed nature of both in-distribution (InD) and OOD samples. The lack of a distinct set of OOD samples complicates the task of training an optimal OOD classifier. In this work, we introduce Medix, a novel framework designed to identify potential outliers from unlabeled data using the median-based robust gradient statistics. We use the median because it provides a stable estimate of the central tendency, as an OOD detection mechanism, due to its robustness against noise and outliers. Using these identified outliers, along with labeled InD data, we train a robust OOD classifier. From a theoretical perspective, we derive error bounds that demonstrate Medix achieves a low error rate. Empirical results further substantiate our claims, as Medix outperforms existing methods across the board in open-world settings.

Figures

Figures reproduced from arXiv: 2510.06505 by the authors.

Figure 1
Figure 1. Distance deviation as we increase OOD samples in Swild. The above optimization problem aims to identify a subset S in Swild that minimizes the distance be￾tween the EWM of the gradients and the average gradient ∇¯ in. According to [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Example of Medix applied to unlabeled wild data. (a) Setup of the InD data [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Comparison of element-wise median (EWM) and geometric median (GM). [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Illustration of InD sample gradients exhibiting sub-Gaussian behavior in each coordinate. [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 4 linked inside Pith

  1. [1]

    Abbas, M., Azmat, M., Horesh, R., and Yurochkin, M. (2025). Out-of-distribution detection using synthetic data generation. InSecond Conference on Language Modeling. Acharya, A., Dhillon, I. S., and Sanghavi, S. (2024). Geometric median (gm) matching for robust data pruning. arXiv preprint arXiv:2406.17188. Acharya, A., Sanghavi, S., Jing, L., Bhushanam, B...

  2. [4]

    Nguyen, A., Yosinski, J., and Clune, J

    Granada. Nguyen, A., Yosinski, J., and Clune, J. (2015). Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 427–436. Niu, G., Du Plessis, M. C., Sakai, T., Ma, Y ., and Sugiyama, M. (2016). Theoretical comparisons of positive-...

  3. [6]

    Malinin, A

    Curran Associates, Inc. Malinin, A. and Gales, M. (2018). Predictive uncertainty estimation via prior networks. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors,Advances in Neural Information Processing Systems, volume

  4. [7]

    Malinin, A

    Curran Associates, Inc. Malinin, A. and Gales, M. (2019). Reverse kl-divergence training of prior networks: Improved uncertainty and adversarial robustness. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R., editors,Advances in Neural Information Processing Systems, volume

  5. [8]

    Meinke, A

    Curran Associates, Inc. Meinke, A. and Hein, M. (2020). Towards neural networks that provably know when they don’t know. In International Conference on Learning Representations. Ming, Y ., Fan, Y ., and Li, Y . (2022). POEM: Out-of-distribution detection with posterior sampling. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato,...

  6. [13]

    For example, in OpenML Saito et al

    in several key ways. For example, in OpenML Saito et al. (2021), the main problem is to handle outliers in semi-supervised learning (SSL) when training a standard classifier, whereas in our setting, the main challenge is to detect OOD samples from unlabeled wild data and train a dedicated OOD detector classifier. In other words, while SSL methods (Saito e...

  7. [29]

    Peng, B., Luo, Y ., Zhang, Y ., Li, Y ., and Fang, Z. (2024). Conjnorm: Tractable density estimation for out-of- distribution detection. InThe Twelfth International Conference on Learning Representations. Plessis, M. D., Niu, G., and Sugiyama, M. (2015). Convex formulation for learning from positive and unlabeled data. In Bach, F. and Blei, D., editors,Pr...

  8. [30]

    Lee, K., Lee, H., Lee, K., and Shin, J

    Curran Associates, Inc. Lee, K., Lee, H., Lee, K., and Shin, J. (2017). Training confidence-calibrated classifiers for detecting out-of- distribution samples.arXiv preprint arXiv:1711.09325. Lee, K., Lee, K., Lee, H., and Shin, J. (2018a). A simple unified framework for detecting out-of-distribution samples and adversarial attacks.Advances in neural infor...

Show all 13 references
  1. [31]

    Letouzey, F., Denis, F., and Gilleron, R

    Curran Associates, Inc. Letouzey, F., Denis, F., and Gilleron, R. (2000). Learning from positive and unlabeled examples. InInternational Conference on Algorithmic Learning Theory, pages 71–85. Springer. Liang, S., Li, Y ., and Srikant, R. (2018). Enhancing the reliability of o...

  2. [32]

    and Zhang, M.-L

    11 Hang, J.-Y . and Zhang, M.-L. (2024). Binary decomposition: A problem transformation perspective for open-set semi-supervised learning. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F., editors,Proceedings of the 41st In...

  3. [101]

    and Kim, H

    Jeong, T. and Kim, H. (2020). Ood-maml: Meta-learning for few-shot out-of-distribution detection and classification. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors,Advances in Neural Information Processing Systems, volume 33, pages 3907–3916. Cur...

  4. [512]

    We use the checkpoints provided by Ming et al. (2023)2. The results, as shown in Table 4, demonstrate that Medix outperforms even these competitive baselines by a significant margin, including those trained with contrastive learning objectives, achieving an average FPR95 of 8....

  5. [2024]

    Table 3: Effect of hyperparameters ϵ and kon OOD detection

    for outlier detection in Medix. Table 3: Effect of hyperparameters ϵ and kon OOD detection. Method FPR95↓ϵ k DICE 88.35 – – ASH 21.36 – – CSI 64.70 – – KNN+ 32.21 – – OE 2.86 – – Energy 2.71 – – Medix 0.16 0.005 20000 Medix 0.20 0.0005 20000 Medix 0.68 0.005 10000 To answer th...

Pith tools

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