Title: Smoothed-SGDmax: A Stability-Inspired Algorithm to Improve Adversarial Generalization. Abstract: Unlike standard training, deep neural networks can suffer from serious overfitting problems in adversarial settings, which is studied extensively by empirical papers. Recent research (e.g., Xing et al. (2021); Xiao et al. (2022)) show that SGDmax-based adversarial training algorithms with $1/s(T)$ training loss incurs a stability-based generalization bound in $\Theta(c+s(T)/n)$. Here $T$ is the number of iterations, $n$ is the number of samples, $s(T)\rightarrow \infty$ as $T\rightarrow \infty$, and $c$ is a $n$-independent term. This reveals that adversarial training can have nonvanishing generalization errors even if the sample size $n$ goes to infinity. A natural question arises: can we eliminate the nonvanishing term $c$ by designing a more generalizable algorithm? We give an affirmative answer in this paper. First, by an adaptation of information-theoretical lower bound on the complexity of solving Lipschitz-convex problems using randomized algorithms, we show that a minimax lower bound for adversarial generalization gap is $\Omega(s(T)/n)$ given training loss $1/s(T)$. This implies that SGDmax does not achieve the lower bound. Next, by observing that the nonvanishing generalization error term for SGDmax comes from the non-smoothness of the adversarial loss function, we employ a smoothing technique to smooth the adversarial loss function. Based on the smoothed loss function, we design a smoothed SGDmax algorithm achieving generalization bound $\mathcal{O}(s(T)/n)$, which matches the minimax lower bound. Experimentally, we show that our algorithm improves adversarial generalization on common datasets.