Algorithm

The algorithm to generate AugMax images from clean images (i.e., to solve Eq. (4)) is summarized in Algorithm 1, where we employ an accelerated adversarial attack method [28] to reduce complexity. The basic idea behind the acceleration is to early-stop gradient ascend when misclassification has already occurred in kiterations. For all our experiments, we use k = 1, n= 5and α= 0.1. Output: AugMax image x 1 Randomly initialize m [0,1]and p Rb. 2 w σ(p) // σ()is softmax function. Output: Learned parameter θfor f(). 1 Randomly initialize θ. 2 for t 1 to T do 3 Sample images and corresponding labels {(xi,yi)}Bi=1 from D. 4 for i 1 to Bdo 5 Generate AugMax image x i from xi following Algorithm 1. 6 end 7 θ θ ρ θ 1B PB i=1{ 1 The algorithm to train a robust classifier with AugMax images (i.e., to solve Eq. (5)) is summarized in Algorithm 2. For AdvMix and AdvMax, we use the worst-of-k method [71] to do adversarial attack on the augmentation hyperparameters such as rotation angles and translation pixel numbers, where k is set to 5. Specifically, for AdvMix, we first randomly select augmentation operations types and mixing parameters as done in AugMix.