Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries
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.
Code (1)
Tasks
DiagnosticSimilar Papers 제목 키워드 기반
PAC-Bayesian Generalization Bounds for MultiLayer Perceptrons
We study PAC-Bayesian generalization bounds for Multilayer Perceptrons (MLPs) with the cross entropy loss. Above all, we introduce probabilistic explanations for MLPs in two aspects: (i) MLPs formulate a family of Gibbs …
Generalization BoundsVariational InferenceLower Bounds on Adversarial Robustness for Multiclass Classification with General Loss Functions
We consider adversarially robust classification in a multiclass setting under arbitrary loss functions and derive dual and barycentric reformulations of the corresponding learner-agnostic robust risk minimization problem…
Adversarial RobustnessQuantum Cross Entropy and Maximum Likelihood Principle
Quantum machine learning is an emerging field at the intersection of machine learning and quantum computing. Classical cross entropy plays a central role in machine learning. We define its quantum generalization, the qua…
BIG-bench Machine LearningQuantum Machine LearningRelationCross-Entropy Loss Functions: Theoretical Analysis and Applications
Cross-entropy is a widely used loss function in applications. It coincides with the logistic loss applied to the outputs of a neural network, when the softmax is used. But, what guarantees can we rely on when using cross…
Adversarial RobustnessContinuity of Generalized Entropy and Statistical Learning
We study the continuity property of the generalized entropy as a function of the underlying probability distribution, defined with an action space and a loss function, and use this property to answer the basic questions …
Decision MakingLearning Theory