Calibration is insufficient for the TRADES surrogate bound
Theoretically Principled Trade-off between Robustness and Accuracy ↗
2019 · arXiv:1901.08573v3, 24 June 2019; ICML 2019 paper and supplement · Reviewed 09 September 2026
Paper context
Overview
TRADES studies the tension between ordinary prediction accuracy and resistance to adversarial perturbations. It decomposes robust error into ordinary error and a boundary-related term, then uses surrogate losses to motivate a training objective balancing accurate predictions with stability under perturbation.
Role of the theoretical result
The selected upper bound is part of the theoretical justification for replacing the difficult robust-error objective with a tractable surrogate. Its assumptions determine how broadly that justification applies to alternative losses and input spaces.
Original paper ↗01 / Summary
Summary of the result
The second inequality of Theorem 3.1 requires pointwise domination of the wrong-sign indicator by the surrogate loss. Classification calibration, nonnegativity and φ(0)≥1 do not imply φ(u)≥1 for all u≤0. A nonnegative C² calibrated loss with φ(−1)=1/2 violates the bound on the permitted two-point instance space. Non-increasing margin losses with the stated normalization satisfy the additional condition.
02 / Statement
Statement under review
Theorem 3.1 upper-bounds robust excess error for any nonnegative classification-calibrated loss with φ(0)≥1, any measurable predictor and the stated instance space.
Relevant assumptions ↘
- Instance space X={−1,+1}⊂R, uniform data and deterministic label Y=X; f(x)=x.
- Adversarial radius ε=2, with balls intersected with X as the paper defines; λ=1.
- Define S(u)=0 for u≤0, S(u)=6u⁵−15u⁴+10u³ for 0<u<1, and S(u)=1 for u≥1.
- Use φ(t)=1−S(t) for t≥0 and φ(t)=1/2+S(t+1)/2 for t<0. This is nonnegative, C² and satisfies φ(0)=1.
03 / Derivation
Counterexample and derivation
- 01
The chosen loss has φ(1)=0, φ(−1)=1/2 and φ(0)=1. Its first two derivatives match at the piecewise junctions.
- 02
For conditional label probability η, the best positive score has risk (1−η)/2 and the best negative score has risk η/2. Therefore H(η)=min(η,1−η)/2.
- 03
For η≠1/2, forcing the wrong sign gives H−(η)=max(η,1−η)/2>H(η), so the loss satisfies the printed calibration assumption. Its calibration transform is ψ(θ)=θ/2.
- 04
The predictor classifies both points correctly with zero surrogate risk. The optimal natural risk and surrogate excess are both zero.
- 05
Every adversarial ball contains the opposite point, so robust error is one. The boundary surrogate is max{φ(1),φ(−1)}=1/2.
- 06
The claimed upper bound is consequently 1≤1/2. The proof's step from a wrong-sign indicator to φ(u) fails at u=−1.
Counterexample
The two-point construction has zero surrogate excess risk, robust error one and boundary surrogate 1/2. The second inequality therefore reduces to 1≤1/2.
04 / Implications
Implications and proposed correction
Affected result
Refutes the universal second inequality of Theorem 3.1 under its printed loss and instance-space assumptions. The first risk decomposition/calibration inequality is not refuted.
Relation to reported experiments
Does not refute the usual TRADES algorithm or its benchmark results. Common non-increasing margin losses, with the stated normalization, satisfy the extra domination property.
Sufficient conditions and revised bound
Add φ(u)≥1 for every nonpositive u. A sufficient, stronger condition is that φ is non-increasing and φ(0)≥1. Then the wrong-sign indicator is pointwise bounded by the surrogate, restoring the disputed step. For u≤0 the added condition supplies the required unit penalty; for u>0 the indicator is zero and nonnegativity suffices. Taking the same maxima and expectation preserves the inequality.
Implementation implications
When adapting the binary TRADES guarantee to a new loss or a discrete input domain, verify wrong-sign domination rather than calibration alone. No change to a standard loss that already satisfies this condition is implied.
Limits of this review
- On a connected perturbation domain with a continuous predictor, an intermediate zero score may restore the boundary surrogate. The theorem explicitly permits the two-point domain used here.
- The witness loss is deliberately non-monotone; the printed theorem does not require monotonicity.
- The scope is binary population theory, not an empirical multiclass robustness certificate.
- This repairs the selected upper-bound step. It does not independently establish the paper's lower-bound tightness theorem or its multiclass practical objective.
05 / References
Sources and correction history
- 01Current primary paper ↗
Section 2.1; Theorem 3.1 p6; Appendix B.1 p20
- 02Official ICML version ↗
Main paper and supplementary proof of Theorem 3.1
- 03Author repository discussion ↗
Earlier same-day issue/comment inventory; binary/multiclass and loss-implementation discussions distinguished
Correction search · 09 September 2026
2026-09-09 Rechecked current v3, the relative-ball domain and the rendered theorem hypotheses. Revisited the official PMLR proof and earlier same-day inventory of 33 repository issues/PRs with available comments. Repeated theorem/calibration/monotonicity/domination/counterexample correction searches. No retrieved source adds the needed wrong-sign domination condition to this printed universal statement. The search is bounded and does not establish priority. Generic analyses of adversarial calibration or a different loss do not automatically correct this exact statement.
A bounded search is not evidence of priority or proof that no correction exists.
Entirely AI-generated analysis, including cross-checks by separate AI agents; no independent human verification. Authors have not been contacted. Review standard.
Suggest a correction with a source ↗