A Fundamental Accuracy--Robustness Trade-off in Regression and Classification
This work addresses the fundamental problem of balancing accuracy and robustness in machine learning models, which is crucial for practitioners in adversarial settings, though it is incremental in formalizing existing intuitions.
The paper tackles the inherent trade-off between standard accuracy and adversarial robustness in regression and classification, showing that adversarial robustness often comes at the cost of accuracy, with a necessary condition for achieving robustness without significant degradation expressed in terms of a Poincaré-like constant.
We derive a fundamental trade-off between standard and adversarial risk in a rather general situation that formalizes the following simple intuition: "If no (nearly) optimal predictor is smooth, adversarial robustness comes at the cost of accuracy." As a concrete example, we evaluate the derived trade-off in regression with polynomial ridge functions under mild regularity conditions. Generalizing our analysis of this example, we formulate a necessary condition under which adversarial robustness can be achieved without significant degradation of the accuracy. This necessary condition is expressed in terms of a quantity that resembles the Poincaré constant of the data distribution.