{"id":"af4ed92c-eb70-4cdc-9696-dca9863372a0","arxiv_id":"2502.04170","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives an SVM sample-complexity bound for learned collision detection in terms of configuration-space clearance, but the proposed guarantee algorithm rests on an unjustified monotonicity assumption in its termination proof.","lead":"This paper derives sample-complexity bounds for SVM-based learned collision detection, linking a robot's configuration-space clearance to the feature-space margin. It also proposes an adaptive algorithm that claims statistical error guarantees, but the convergence proof relies on a questionable monotonicity assumption.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's monotonicity assertion is false: along Algorithm 2's trajectory m·δ = const, Eq. (2) makes the required sample count grow like δ^{-9d/4}, so the loop can enter an infeasible region and never terminate.","rationale":"The reader's weakest-assumption diagnosis is correct and, in fact, decisive. Lemma 2 is the only bridge between the existence result (Lemma 1) and the paper's advertised algorithm-level guarantee. Its proof relies on a monotonicity premise that is not merely unproved but is contradicted by the paper's own Eq. (2). The invariant m·δ of Algorithm 2 is a hyperbola in (δ,m)-space, whereas condition (C2) requires m to lie above the curve m ∼ δ^{-9d/4}; since the latter is steeper for every d ≥ 1, the two curves cross at most once, and the search path can be on the wrong side for all small δ. This is not a matter of missing constants: it is a structural mismatch between the search schedule and the sample-complexity scaling. The cell-labeling issue in Appendix B is also serious, but the Lemma 2 failure alone is sufficient to invalidate the central claim that Algorithm 2 returns an LCD with a finite-time statistical guarantee. The experimental section does not test termination and cannot repair a broken proof. Therefore the rejection is warranted. The framework may be salvageable by redesigning Algorithm 2's search schedule — for instance, increasing m much faster than it decreases δ — but the current manuscript does not support the stated claim.","tokens_in":13780,"tokens_out":11160,"duration_ms":111381,"concrete_test":"Run a deterministic numeric check of condition (C2) along Algorithm 2's trajectory for a 1D C-space X=[0,1], with the simple partition Xfree=(0.5,1], Xforb=[0,0.5]. Fix ε=0.2, ξ=0.1, initial guesses m₀=10, δ₀=1. At each iteration k, set δ=2^{-k}, m=10·2^k and evaluate the lower bound on required samples from Eq. (2), using the optimistic value εXδ=ε (the true tolerable interior error is at most ε, so this only underestimates the requirement). If at any k the inequality m < (1/ε²)[(9^9/4^4)(√d/δ)^{9d/4} + 8ln(2/ξ)] holds, then Algorithm 1 must return 'Fail' at that iteration. Show that this inequality holds for all k ≥ 3 and remains true for all larger k because the RHS grows as δ^{-9/4} while m grows only as δ^{-1}. This contradicts Lemma 2's claim of finite termination for arbitrary initial guesses.","verdict_should_be":"REJECT","load_bearing_attack":"The central guarantee of the paper — that Algorithm 2 always terminates with a statistically correct LCD — rests entirely on Lemma 2 (Sec. V-B). Its proof asserts, without proof, that 'the same guarantees hold for any δ ≤ δ′ and m ≥ m′' once (δ′,m′) satisfies Lemma 1. This monotonicity is false under the paper's own sample-complexity bound. Eq. (2) gives m_{Xδ}(ε,ξ) = (1/ε²)[C(√d/δ)^{9d/4} + 8ln(2/ξ)], which grows like δ^{-9d/4}. Meanwhile, Algorithm 2 updates m ← 2m and δ ← δ/2, so m·δ is invariant along the search. Thus at a fixed iterate, the sample size available is m = K/δ, while the sample complexity required by condition (C2) is at least C′δ^{-9d/4}. Since 9d/4 > 1 for all d ≥ 1, the required sample size grows faster than the available sample size as δ → 0: once δ is small enough, K/δ < C′δ^{-9d/4}, and condition (C2) fails permanently for all subsequent iterations. Concretely, for d=1, if δ′=0.5 and m′=100 satisfy (C2), then δ=0.05 and m=200 satisfy δ≤δ′ and m≥m′, yet m_{Xδ} ≈ 0.05^{-2.25} ≈ 844 > 200, so (C2) fails. The existence of some feasible pair (δ′,m′) from Lemma 1 does not imply that the specific curve m=m₀δ₀/δ intersects the feasible set; indeed it may miss it entirely. Therefore Lemma 2's termination proof is invalid and the advertised statistical guarantee for Algorithm 2 is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies learned collision detection (LCD) in robot motion planning. The authors define a Gaussian feature map over a grid discretization of the configuration space, prove (Theorem 1) that clearance in configuration space implies a margin in feature space, and use a standard hard-SVM generalization bound to derive an explicit sample-complexity estimate (Theorem 2, Eq. (2)) for classification over the δ-interior. They then propose Algorithm 1, which trains an SVM on samples with clearance exceeding δ and fails when the tolerable interior error or sample count is insufficient, and Algorithm 2, which iteratively halves δ and doubles m until Algorithm 1 succeeds. The headline claim (Lemma 2) is that for every ε>0 and confidence 1−ξ, Algorithm 2 terminates and returns an LCD whose 0-1 error on a random configuration from X is at most ε with confidence at least 1−ξ.","tokens_in":14041,"tokens_out":10558,"duration_ms":111015,"significance":"If the proof gaps could be closed, the paper would supply a rare formal connection between geometric clearance and feature-space margin for a practical collision-detection surrogate, with an explicit sample-complexity formula rather than an order-of-magnitude statement. The analysis is not circular: Theorem 2 is derived from an external SVM generalization theorem together with the new margin construction, no constants are fit to data, and the feature-map parameters are set analytically from δ. The paper also candidly acknowledges the exponential dependence on d and 1/δ as a limitation. These strengths make the contribution potentially valuable. However, the central termination guarantee is currently unsupported because of the failure of the monotonicity assertion in Lemma 2, and Theorem 1's proof contains a false cell-homogeneity claim; both must be repaired before the advertised guarantees can be relied upon.","major_comments":[{"comment":"The proof of Lemma 2 rests on the assertion that if (δ′,m′) satisfies Lemma 1 then 'the same guarantees hold for any δ ≤ δ′ and m ≥ m′'. This monotonicity is false under the paper's own Eq. (2). For fixed ε and ξ, the value of m_{Xδ}(εXδ,ξ) used in condition (C2) diverges like δ^{-9d/4} as δ→0 (εXδ tends to ε as the empirical interior probability p̂ tends to 1). Algorithm 2 updates m←2m and δ←δ/2, so mδ is invariant. Thus after enough halvings the available number of interior samples, O(m) = O(1/δ), is smaller than the threshold m_{Xδ} that Algorithm 1 itself tests, and condition (C2) fails permanently; the loop never terminates. Even if some feasible pair exists (Lemma 1), the proof does not show that the particular curve m = m0δ0/δ intersects the feasible region. The termination and correctness guarantee for Algorithm 2 is therefore not established, and this is the main advertised contribution of the paper.","section":"Sec. V-B, Lemma 2"},{"comment":"The definition g(i)=+1 if there exists x∈CELL_i with f(x)=+1 and g(i)=-1 if there exists x∈CELL_i with f(x)=-1 is claimed to be well defined because no cell can contain both a free and a forbidden configuration. This is not correct for cells crossing the free/forbidden boundary: such a cell may contain both classes, and the two configurations can have clearance exactly δ and lie at opposite corners at distance equal to the cell diameter δ=√d/n. The proof needs a repair, for example by defining labels only for cells that intersect Xδ and by choosing n strictly larger than √d/δ (or using a strict-clearance convention) to guarantee a positive separation between opposite-class points in a cell.","section":"Appendix B, Eq. (5), proof of Theorem 1"},{"comment":"Lemma 1 establishes existence of some feasible pair (δ*, m*), but it does not provide the monotonicity needed by Lemma 2; in fact, the proof's choice m* := max(κ1, κ2) is tailored to the single clearance value δ* and does not imply that the same m* works for smaller δ. The divergence of Eq. (2) as δ→0 is precisely what makes the transition from Lemma 1 to Lemma 2 fail. A revised argument should either choose m as a function of δ according to Eq. (2) or prove that the feasible region is visited by the search schedule; neither is currently supplied.","section":"Sec. V-A, Lemma 1 and Eq. (3)"}],"minor_comments":[{"comment":"References [17] and [24] are the same paper (Das and Yip, 'Forward kinematics kernel for improved proxy collision checking') and should be merged or one removed.","section":"References"},{"comment":"The acknowledgments spell the first author's name as 'S. Tubbul'; this appears to be a typo for 'S. Tubul' and should be corrected.","section":"Acknowledgments"},{"comment":"The caption says 'the boundary between Xforb and Xforb dashed', which appears to be a typo; presumably it should refer to the boundary between Xfree and Xforb.","section":"Fig. 2(c) caption"},{"comment":"The constant 9^9/4^4 in Eq. (2) is not derived in the main text; adding a pointer to the appendix computation would help readers verify the algebra.","section":"Eq. (2) and Sec. IV-C"}],"recommendation":"major_revision","confidential_remarks":"I agree with the spirit of the reader's report: the termination claim in Lemma 2 is the weakest point and is not supported by the proof. I do not see circularity or fitted constants; the issue is a genuine proof gap rather than a mismatch with consensus. Because both gaps appear repairable (a different search schedule and a corrected cell-labeling argument), I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The core idea is new and worth taking seriously: encode the configuration space with a Gaussian grid feature map, turn clearance into feature-space margin, and then apply standard SVM sample-complexity theory. I believe this is the first formal sample-complexity analysis for learned collision detection, and Eq. (2) is a concrete, unfitted bound. The authors are also honest about its exponential dependence on dimension and inverse clearance.\n\nBut two proof gaps break the advertised guarantee, and I agree with the stress-test note that the second one is decisive.\n\nFirst, Theorem 1's cell-labeling function g in Appendix B is not well-defined. With n = sqrt(d)/delta, each grid cell has diameter delta, so a cell can contain a point with clearance exactly delta and, on the other side of the boundary, a forbidden point. The definition of g then assigns both +1 and -1 to that cell. The claim that every cell is homogeneous is false for cells straddling the boundary. This might be fixable—label straddling cells 0 and rework the constants—but the proof as written does not go through.\n\nSecond, and more seriously, Lemma 2's convergence proof assumes monotonicity: if (delta', m') satisfies Lemma 1, then any delta <= delta' and m >= m' also works. That is contradicted by the paper's own Eq. (2), where the required sample count grows like delta^{-9d/4}. Algorithm 2 keeps m * delta constant along its search, so as delta shrinks, the available sample size grows only linearly in 1/delta while the requirement grows faster. The search can walk out of the feasible region and never terminate. The proof gives no argument that the specific curve m = m0 * delta0 / delta intersects the feasible set, and in general it need not. So the statistical guarantee for Algorithm 2 is not established.\n\nThe experiments are illustrative only and do not test the convergence claim, so they do not rescue this.\n\nWho is this for? A theory-minded robotics or ML reader curious about what guarantees are possible for learned collision detection. I would send this to a serious referee rather than desk-reject it: the construction is novel, the flaws are pinpointable, and a corrected cell labeling plus a different search schedule could plausibly salvage the framework. But as it stands, the paper's central promise—an algorithm that always terminates with a guaranteed LCD—is unsupported. I would not accept the current version.","headline":"A genuinely new clearance-to-margin construction, but the paper's central guarantee rests on a monotonicity claim that its own sample-complexity formula contradicts.","tokens_in":14664,"tokens_out":5769,"would_cite":false,"duration_ms":56813,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that learned collision detection can carry a statistical guarantee: a bounded number of labeled configurations suffices to certify a misclassification rate below any target ε.","keywords":["sample complexity","support vector machines","collision detection","motion planning","clearance","margin","configuration space","statistical guarantees"],"falsifier":"Take a C-space with a known obstacle ball, choose $\\varepsilon$ and $\\xi$, and instrument Algorithm 2 to record at each iteration whether conditions (C1) and (C2) hold. If there is an iteration where a pair $(\\delta,m)$ succeeds but the next pair $(\\delta/2,2m)$ fails condition (C2), the monotonicity assumption behind Lemma 2 is false and the algorithm is not guaranteed to terminate; this is a direct calculation from Eq. (2) and the environment's volume function.","tokens_in":13443,"feed_emoji":"🤖","tokens_out":8392,"duration_ms":86266,"temperature":0.7,"pith_summary":"Motion planning relies on fast collision checks, and learned collision detectors trained with SVMs promise to speed them up, but until now there has been no theory saying how much data is enough or how often the learned classifier will be wrong. This paper tries to close that gap by proving a sample-complexity bound for a hard-margin SVM whose feature vectors are derived from the robot's configuration-space clearance. The main claim is that for any desired error $\\varepsilon$ and confidence $1-\\xi$, there is a labeled sample size, explicitly bounded in Eq. (2), that yields an LCD whose 0-1 error on the $\\delta$-interior of the configuration space is at most $\\varepsilon$. The paper then builds an adaptive algorithm that claims to extend this guarantee from the $\\delta$-interior to the whole configuration space, so a user receives a collision detector with a statistical contract: misclassification probability at most $\\varepsilon$, with confidence at least $1-\\xi$.","feed_headline":"Learned collision detection gets a provable error bound","feed_subtitle":"A new sample-complexity formula ties robot clearance to SVM margin, telling planners how much data is enough.","key_machinery":"The load-bearing construction is the feature map $\\phi^\\sigma$ (Eq. 1): overlay a grid of $n^d$ cells on the unit cube $[0,1]^d$, and for each cell center $c_i$ define $h_i(x) = \\exp(-\\|c_i-x\\|^2/\\sigma^2)$, so $\\phi(x)$ is the vector of a configuration's influence on every cell. Theorem 1 labels each cell free, forbidden, or boundary, and builds a separating direction $\\alpha$ from those labels; the margin bound follows because a point in the $\\delta$-interior is dominated by its own cell's feature and the neighboring opposite-class cells are at least roughly $1.5\\delta$ away. This clearance-to-margin transfer is what lets the authors recycle SVM margin theory to obtain Eq. (2). Algorithm 1 then combines that sample-complexity check (condition C2) with a binomial-proportion estimate of the $\\delta$-interior's size (condition C1), and Algorithm 2's loop is the mechanism intended to turn the interior guarantee into an all-of-configuration-space guarantee.","core_discovery":"The paper's central discovery is a bridge between two notions of separation: clearance, the Euclidean distance from a configuration to the boundary between free and forbidden space, and margin, the distance between classes in the SVM's feature space. Theorem 1 constructs a feature map $\\phi^\\sigma$ whose coordinates are Gaussian bumps centered on a grid over the configuration space, and proves that configurations with clearance at least $\\delta$ are linearly separable in that feature space with margin $\\gamma^* \\ge 8/(9^{9/8} n^{5d/8})$ when $n = \\sqrt{d}/\\delta$. Feeding this margin into a standard SVM sample-complexity theorem yields Eq. (2), which bounds the number of labeled samples needed to learn the $\\delta$-interior to accuracy $\\varepsilon$ at confidence $1-\\xi$. Algorithm 1 uses this bound, plus an estimate of how much of the configuration space lies in the $\\delta$-interior, to filter training samples; Lemma 1 states that good parameters always exist; and Lemma 2 states that Algorithm 2, which repeatedly halves $\\delta$ and doubles $m$, terminates and returns an LCD with the requested global error guarantee.","pith_inferences":["The monotonicity premise in Lemma 2 is the point to attack first: the bound in Eq. (2) suggests the required sample count grows like $\\delta^{-9d/4}$, while Algorithm 2 only doubles $m$ each time $\\delta$ is halved, so a direct verification on a simple environment would either confirm termination or reveal an infinite loop.","The feature vector's dimension is $n^d = (\\sqrt{d}/\\delta)^d$, so the same geometry that gives the margin also drives the sample bound's exponential cost; a practical route to usable guarantees will need a lower-dimensional or kernel-based feature map that preserves the clearance-to-margin link.","The guarantee is distribution-dependent: the paper notes that training and testing must draw from the same distribution over configurations, so applying the LCD inside a planner that samples non-uniformly, such as near obstacles or along edges, requires reweighting or a new analysis.","A concrete falsifiable test is to instantiate Algorithm 2 on a 2D or 3D disk-in-box environment and check whether halving $\\delta$ and doubling $m$ always keeps condition (C2) satisfied; if not, Lemma 2's claim of finite termination does not follow from the stated bounds."],"forward_implications":["For any clear obstacle geometry and any requested $(\\varepsilon, \\xi)$, the theory identifies a finite dataset size that is sufficient in the worst case for a hard-margin SVM collision classifier to meet the error bound on the $\\delta$-interior.","The explicit bound $m_{X_\\delta}(\\varepsilon,\\xi) \\le \\frac{1}{\\varepsilon^2}\\left[\\frac{9^9}{4^4}\\left(\\frac{\\sqrt{d}}{\\delta}\\right)^{9d/4} + 8\\ln\\frac{2}{\\xi}\\right]$ tells practitioners how data requirements scale with dimension, clearance, and confidence: exponentially in $d$ and in inverse clearance, but only logarithmically in $1/\\xi$.","If Lemma 2's guarantee holds, a planner can replace exact collision checks with the returned LCD and know that a random query from the same distribution is misclassified with probability at most $\\varepsilon$, at confidence level $1-\\xi$.","The framework opens a path to end-to-end probabilistic path guarantees: a planner could aggregate per-configuration error probabilities over a planned sequence and certify collision-freeness with high probability."],"supporting_citations":[{"why":"Supplies the SVM margin sample-complexity theorem (Thm. 15.4) from which Eq. (2) is derived.","marker":"[21]"},{"why":"Introduces Fastron, the SVM-based learned collision detector that defines the LCD task this paper analyzes.","marker":"[14]"},{"why":"Provides the normal critical values used to estimate the size of the $\\delta$-interior in Algorithm 1's condition.","marker":"[35]"},{"why":"Underpins the binomial-proportion confidence interval in Lemma 3, which justifies the empirical estimate of $|X^\\delta|$.","marker":"[36]"}],"fun_headline_variants":["Clearance to margin: a data bound for collision learning","How much data for safe collision checks? A new formula","Bridging clearance and margin to guarantee collision detection","Provable sample bounds for collision-aware planners","Sample complexity bound for learning collision checks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Algorithm 2 is promised to terminate because the paper assumes that 'smaller clearance plus more samples' is always at least as good as a working pair; if that monotonicity fails, the loop may never find a feasible pair.","fun_headline_variants_meta":{"raw":{"variants":["Clearance to margin: a data bound for collision learning","How much data for safe collision checks? A new formula","Bridging clearance and margin to guarantee collision detection","Provable sample bounds for collision-aware planners","Sample complexity bound for learning collision checks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00104,"raw_usage":{"total_tokens":4383,"prompt_tokens":958,"completion_tokens":3425,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":3352}},"tokens_in":574,"tokens_out":3425,"duration_ms":25385,"temperature":1.0,"reasoning_tokens":3352,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T23:18:35.524278+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a C-space with a known obstacle ball, choose $\\varepsilon$ and $\\xi$, and instrument Algorithm 2 to record at each iteration whether conditions (C1) and (C2) hold. If there is an iteration where a pair $(\\delta,m)$ succeeds but the next pair $(\\delta/2,2m)$ fails condition (C2), the monotonicity assumption behind Lemma 2 is false and the algorithm is not guaranteed to terminate; this is a direct calculation from Eq. (2) and the environment's volume function.","supporting_citations":[{"cited_title":"Shalev-Shwartz and S","cited_arxiv_id":null,"evidence_quote":"Supplies the SVM margin sample-complexity theorem (Thm. 15.4) from which Eq. (2) is derived."},{"cited_title":"Learning-based proxy collision detection for robot motion planning applications,","cited_arxiv_id":null,"evidence_quote":"Introduces Fastron, the SVM-based learned collision detector that defines the LCD task this paper analyzes."},{"cited_title":"Wackerly, W","cited_arxiv_id":null,"evidence_quote":"Provides the normal critical values used to estimate the size of the $\\delta$-interior in Algorithm 1's condition."},{"cited_title":"Approximate is better than “exact","cited_arxiv_id":null,"evidence_quote":"Underpins the binomial-proportion confidence interval in Lemma 3, which justifies the empirical estimate of $|X^\\delta|$."}],"review_version":1}