Genetic Column Generation for Computing Lower Bounds for Adversarial Classification
This work addresses a computational bottleneck in adversarial classification, offering a solution for researchers and practitioners dealing with high-dimensional data, though it appears incremental as it builds on existing techniques.
The paper tackles the curse of dimensionality in computing minimal adversarial risk for multi-class classification by adapting Genetic Column Generation from optimal transport, achieving a method that overcomes this computational barrier.
Recent theoretical results on adversarial multi-class classification showed a similarity to the multi-marginal formulation of Wasserstein-barycenter in optimal transport. Unfortunately, both problems suffer from the curse of dimension, making it hard to exploit the nice linear program structure of the problems for numerical calculations. We investigate how ideas from Genetic Column Generation for multi-marginal optimal transport can be used to overcome the curse of dimension in computing the minimal adversarial risk in multi-class classification.