- Rating
- 2
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
By extending ROBOT, this paper proposes an OT-based approach to outlier detection. The outlier model is -model, where the inlier points follows an underlying law while the outlier points are arbitrary. The basic idea is the joint optimization of minimum distance estimation and outlier flagging. The outlier flagging (-optimization) in PW-ROT can be written in closed form in Theorem 3.1, which leads to the standard OT with a transformed cost . After solving this, the outlier set is estimated by enumerating the points that is not "reachable" from other points with high probability under the estimated model . The main theoretical contribution is the exact recovery in Theorem 4.2, where the estimated outlier set is exact under some margin conditions.
Critical strengths
- The extension of ROBOT with the exponent is clear. The exponent originates from the intensity of the outlier flagging weights in Eq. (1). This translates into the cost clipping function in Eq. (2). In Figure 1, we can clearly see that softens the hard clipping . In Section 4.2, the authors discuss that soft may be informed by inliers that are "false positive" (= falsely detected as outliers), while its theoretical benefit has yet to be formalized.
- Fairly strong outlier guarantee since outlier points can be arbitrary.
- Not quite a lot of hyperparameters. Given that the exponent is a fixed hyperparameter, the only hyperparameter that a user needs to choose is , which is the clipping parameter Eq. (1). Theoretically, this should be scaled with as shown in Theorem 4.2. Empirically, the authors use a trimmed validation strategy to choose minimizing the validation squared error after discarding 35% of outlier-like points.
- This "35%" value may be a bit controversial because all the true outlier proportions tested in the experiments are less than 35%, which means that we somewhat have the knowledge that the outlier proportion is no larger than 35%. It might be okay to choose this 35% criterion large enough so that the validation error is not affected by outliers, while the statistical efficiency is lost. Anyway, I don't think there is a sufficient clean solution to this issue (other existing methods have a similar issue more or less), so I would not argue it so significantly.
Critical weaknesses
- The paper is relatively hard to read. For example, there is a long paragraph after Theorem 4.2 to discuss the implication of this theorem but without a clear paragraph structure. Usually we prefer to have a well-separated paragraph structure. In this case, we may consider to split this paragraph into three pieces to discuss (a), (b), and (c), respectively, at least. The same issue persists in appendix too. For example, the proof of Lemma D.5 is compressed significantly. Since this lemma has five arguments, we should at least split into several paragraphs to make it easier to read.
- The above is my suggestion to the authors but not the basis of paper assessment.
- The theoretical contributions mainly consist of the two parts, the estimation error rate (Theorem 4.2(a)) and the exact recovery of the outlier set (Theorem 4.2(b)). I read the overall flow of the proofs, which looks valid while the assumptions looks a bit strong.
- Theorem 4.2(a): Roughly speaking, the main piece of this claim is the rate estimation of , which is a consequence of the Lipschitz continuity shown in Lemma D.4. Given that we consider the Lipschitz cost and OT formulation, the Lipschitz continuity is natural. Also, the boundedness of is crucial to apply McDiarmid's bound. Then the estimation error bound follows. Additionally, the bias rate on comes from the strong convexity assumption of (or by the modulus of continuity, in more general), which is a standard assumption. Overall, the flow is clear, and I think the claim is valid, but it is not very surprising (it is okay).
- Theorem 4.2(b): The crucial assumption is that inlier points are included in the margin set with high probability, while outlier points are included in . These margin sets are defined by whether (model probability of the reachable points from ) is large/small enough. Essentially, this can be read as a tautology to some extent. While the authors discuss the validity of the assumptions after Theorem 4.2, my concern on this point has not been cleared.
If the authors can adequately clarify the assumption validity on Theorem 4.2(b), I am ready to reconsider the evaluation.
Questions for authors
- In Figure 1, why is is plotted instead of itself? In my opinion, we should plot so that its boundedness behavior becomes clear in the figure.
- At some point, we should have a notation table since the paper has a lot of notations with slight variants.
- (Very minor) In L.257, it looks better to write to make it clear that this is the definition.
- In Section 4.2, it is rather unclear what "pull" does mean; although I could guess the overall implication of this subsection.
- In Lemma D.5, it looks is not clearly defined. Probably it suggest the well-specified case as discussed in Remark D.1, which should be made clearer.
2 comments
(1) Theorem 4.2(a): "not very surprising."
We agree and have clarified this point in the revision. Theorem 4.2(a) provides the supporting estimation bound. The transport-specific contributions are the inlier-sampling term, governed by the OT rate through , and the fact that outliers enter the bound only through .
(2) Section 4.2 and the benefit of soft powers.
We agree that this benefit is not formally established. We have revised the abstract and contribution 3 to state only the proven trade-off: softer compression comes at the cost of a bias bound that increases with . Contribution 4 now clarifies that the experiments motivate, but do not theoretically establish, the use of a soft power in the range (we use ) when the contamination geometry is unknown and the threshold must be selected from data.
(3) The 35% trimming level.
We appreciate the reviewer raising this point. We now report a sensitivity analysis in Appendix F.1 (Table 7). When , the results are nearly identical (within numerical variation) for . However, when the contamination level exceeds the trimming level (), the soft powers can degrade. For example, at and , the error is 0.43 for and 0.22 for , while ROBOT is insensitive to this choice. This confirms that an upper bound on the contamination level is needed, as the reviewer anticipated.
(4) Presentation (all changes completed and highlighted in blue).
- The paragraph following Theorem 4.2 is now divided into (a) Estimation, (b) Exact Recovery, (c) Necessity, and the threshold window. The proof of Lemma D.5 is also reorganized into one paragraph per part, and is now defined as the well-specified case of Remark D.1.
- Figure 1 now plots itself, making its boundedness at visible.
- is now explicitly written as a definition.
- The term "pull" is defined at its first occurrence as a nonzero contribution to the gradient of the criterion that moves the estimate toward the point.
- A notation table has been added in Appendix I, along with a short algorithm overview (Algorithm 1) in the main text.
Assumption in Theorem 4.2(b)
Thank you for the careful reading and for identifying the key condition underlying our theoretical guarantee. We agree that the margin-set condition needed a more direct explanation. We address this concern in three parts, with all changes included in the revised PDF (new Appendix D.6, highlighted in blue).
1. What the condition means and why it is not circular.
The margin sets Gλ(t) and Bλ(t) depend only on the model family, λ, the flag level α, the clean parameter θ0, and the margin t. They do not depend on the data, outliers, or estimator. For both targets, these sets can be bounded by explicit balls around θ0 (Remark D.10 and Lemma D.16). Thus, requiring inliers to lie in Gλ(t) is a tail condition on the inlier distribution, while requiring outliers to lie in Bλ(t) is a separation condition.
Theorem D.11(i) is deterministic once these two events hold. The role of Theorem 4.2(b) is to establish them through (a) the estimation bound in Theorem 4.2(a), which places θ^n within distance t of θ0, uniformly over arbitrary outliers, including inlier-dependent ones; and (b) the requirement that none of the n inliers is flagged, which forces λn≳σ2(d+logn)2. This threshold growth is necessary, not an artifact of the proof: no estimator can avoid flagging an inlier below this scale (Theorem 4.2(c); Remark D.18 for the spread target).
2. Explicit conditions for the Gaussian spread model.
For the Gaussian spread target νθ=θ+N(0,Id) and the 95% rule in Section 5, Corollary D.17 replaces the abstract margin-set condition with three explicit conditions independent of the estimator:
(I) λ≥t+qα+d+2log(n/δ), controlling the inlier tail probability.
(S) Every outlier is farther than λ+z1−α+t from θ0, ensuring separation.
(F) A bound on the outlier fraction and inlier fluctuation, which determines t.
We also establish the curvature required by Assumption 3, which the original submission left to be verified for this target. Lemma D.15 gives κ=p12/r and t0=λ/2−1, independently of d.
Consequently, with
λn=4(2d+2log(n/δ))2,outliers at distance at least 1.5λn+z1−α, and
ε<8rp12≈r0.058,the procedure recovers the outlier set exactly with probability at least 1−2δ, at the same threshold scale as the point target.
We acknowledge that these constants are asymptotic and conservative. This corollary does not cover the finite-sample experiments in Section 5 (ε up to 0.3), and its admissible contamination level is substantially below the point-target value of 1/2.
3. The conditions are not vacuous: they predict where recovery fails.
We provide empirical evidence in Appendix F.1 (Tables 8 and 9). In the mean-shift experiment (n=300,d=5,ε=0.2, one-sided), the flag radius R(λ∗) at the selected threshold predicts both swamping and masking. Assuming a perfect parameter estimate, the predicted probabilities are
P(χd2>R2),P(χd2(nc,k2d)≤R2),respectively.
For r=2, predicted versus observed swamping rates are 0.27 versus 0.31 at k=2, and 0.10 versus 0.12 at k=4. The corresponding masking rates are 0.63 versus 0.69 at k=1, and 0.84 versus 0.85 at k=0.5. Across-trial correlations range from 0.83 to 0.99 for swamping and for masking when k≤1. ROBOT and r=1.5,3 show similar agreement, with prediction errors within 0.07.
Swamping at k=2 reflects a violation of (I): the selector optimizes estimation error and chooses R2≈6.5, well below the approximately 17 needed to avoid flagging any inlier (the 1−1/N quantile of χ52, with N=240). The necessary scale max2logN,d≈11 is only a lower bound; even at R2=11, approximately 5% of inliers would still be flagged. Masking at k≤1 reflects a violation of (S), since the outliers lie inside the flag radius.
Consistent with this explanation, exact recovery becomes more frequent as separation increases. At the data-selected threshold, ROBOT recovers the outlier set exactly in 0/50 runs for k≤2, 5/50 at k=3, 22/50 at k=4, and 46/50 at k=6.
We report these results as limitations of the experiments, not as empirical validation of the theoretical constants.