App. C, p. 14 — for ε ≥ 2η ≥ 0, ℓ∞ robust accuracy ≤ accuracy against the fixed shift adversary
ProvedRobustOdds.Tradeoff.robustAcc_le_shiftAccadversarial-robustnessclassificationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
In the data model (3) with parameters , let be any function. Let be its robust accuracy at radius and its accuracy against the fixed adversary that replaces by for each (both defined in the Setting file). If and , then
The fixed perturbation has norm (or when ), so it is one of the perturbations the worst-case adversary may choose. This is the step "fix the adversary" of the proof of Theorem 2.1, which reduces the worst case over the ball to one explicit adversary.
Formalization Note No measurability of is needed: the robust event is contained in the event that is correct on the shifted input, and the measure applied to the robust event is its outer measure.
Preamble
import Mathlib import Definitions.Def_RobustOdds_Tradeoff_Setting
Formal statement
namespace RobustOdds.Tradeoff
open MeasureTheory ProbabilityTheory
open scoped ENNReal NNReal
/-- App. C, p. 14: for `ε ≥ 2η ≥ 0` the fixed adversary `shiftAdv` lies in the `ℓ∞` ball of radius `ε`,
so `ℓ∞`-robust accuracy is at most the accuracy against that adversary. -/
theorem robustAcc_le_shiftAcc (d : ℕ) (p η ε : ℝ) (hη : 0 ≤ η) (hε : 2 * η ≤ ε)
(f : (Fin (d + 1) → ℝ) → ℝ) :
robustAcc d p η f ε ≤ shiftAcc d p η f := by sorry
end RobustOdds.Tradeoff
Source
Tsipras et al., Robustness May Be at Odds with Accuracy, arXiv:1805.12152v5, p. 14, App. C, proof of Theorem 2.1 ("fix the adversary that replaces x_i by x_i − yε")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.