Understanding the fundamental limits of robust supervised learning has emerged as a problem of immense interest, from both practical and theoretical standpoints. In particular, it is critical to determine classifier-agnostic bounds on the training loss to establish when learning is possible. In this paper, we determine optimal lower bounds on the cross-entropy loss in the presence of test-time adversaries, along with the corresponding optimal classification outputs. Our formulation of the bound as a solution to an optimization problem is general enough to encompass any loss function depending on soft classifier outputs. We also propose and provide a proof of correctness for a bespoke algorithm to compute this lower bound efficiently, allowing us to determine lower bounds for multiple practical datasets of interest. We use our lower bounds as a diagnostic tool to determine the effectiveness of current robust training methods and find a gap from optimality at larger budgets. Finally, we investigate the possibility of using of optimal classification outputs as soft labels to empirically improve robust training.

本文探讨了在存在测试时对抗情况下的分类器损失的最优下限和对应最优分类输出的确定，并使用自适应算法以高效地计算此下限，进而将其作为诊断工具来确定当前鲁棒性训练方法的有效性，并探讨使用最优分类输出作为软标签以经验地改善鲁棒性训练。

测试时对手存在下交叉熵损失的下限