App. C, p. 16 — 1 − ½(pa + (1 − p)b) ≥ 1 − δ, a ≥ 0, ½ ≤ p < 1 imply ½((1 − p)a + pb) ≤ (p/(1 − p))δ
ProvedRobustOdds.Tradeoff.final_boundadversarial-robustnessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with and . If
then
In the proof of Theorem 2.1, and ; the left side of the hypothesis is the standard accuracy and the left side of the conclusion is the accuracy against the shift adversary. The paper's "since are probabilities, we can guarantee that " is the hypothesis . This is the closing algebraic step of the proof.
Preamble
import Mathlib import Definitions.Def_RobustOdds_Tradeoff_Setting
Formal statement
namespace RobustOdds.Tradeoff
open MeasureTheory ProbabilityTheory
open scoped ENNReal NNReal
/-- App. C, p. 16: with `a = 1 − p₊₊ + p₋₋ ≥ 0` and `b = 1 − p₋₊ + p₊₋`, standard accuracy
`1 − ½(pa + (1 − p)b) ≥ 1 − δ` and `½ ≤ p < 1` give adversarial accuracy `½((1 − p)a + pb) ≤ (p/(1 − p))δ`. -/
theorem final_bound :
∀ p a b δ : ℝ, 1 / 2 ≤ p → p < 1 → 0 ≤ a →
1 - δ ≤ 1 - 1 / 2 * (p * a + (1 - p) * b) →
1 / 2 * ((1 - p) * a + p * b) ≤ p / (1 - p) * δ := by sorry
end RobustOdds.Tradeoff
Source
Tsipras et al., Robustness May Be at Odds with Accuracy, arXiv:1805.12152v5, p. 16, App. C, proof of Theorem 2.1, last two displays
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.