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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [§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.
- [§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.
- [§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.
- [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)
- [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.
- [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.
- [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.
- [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
Empirical FPR95 numbers are tuned on the reported OOD metric, but the central theoretical derivation is not definitionally circular.
-
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
free parameters (3)
- k (top-k removal batch) =
20000 (default; searched over {4k, 7k, 10k, 20k})
- epsilon (stopping threshold) =
0.005 (default; searched over {5e-5, 5e-4, 5e-3, 5e-2})
- binary loss weight =
10
assumptions (4)
- domain assumption Huber contamination model: Pwild = (1−π)Pin + πPout
- domain assumption Each InD gradient coordinate is i.i.d. sub-Gaussian with variance proxy σ²
- domain assumption OOD gradients are i.i.d., sub-Gaussian, and their mean satisfies ||μ_out − ∇in|| ≥ Δ√d
- 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
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
Reference graph
Works this paper leans on
-
[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...
arXiv 2025
-
[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-...
2015
-
[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
2018
-
[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
2019
-
[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,...
2020
-
[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...
2021
-
[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...
arXiv 2024
-
[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...
arXiv 2017
Show all 13 references
-
[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...
2000
-
[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...
2024 arXiv
-
[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...
2020
-
[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....
2023
-
[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...
2021
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.