Genetic Column Generation for Computing Lower Bounds for Adversarial Classification
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationMulti-class ClassificationSimilar Papers 제목 키워드 기반
Computing the Bounds of the Number of Reticulations in a Tree-Child Network That Displays a Set of Trees
Phylogenetic network is an evolutionary model that uses a rooted directed acyclic graph (instead of a tree) to model an evolutionary history of species in which reticulate events (e.g., hybrid speciation or horizontal ge…
Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nyström method
The Column Subset Selection Problem (CSSP) and the Nystr\"om method are among the leading tools for constructing small low-rank approximations of large datasets in machine learning and scientific computing. A fundamental…
Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method
The Column Subset Selection Problem (CSSP) and the Nystrom method are among the leading tools for constructing small low-rank approximations of large datasets in machine learning and scientific computing. A fundamental q…
Sound Probabilistic Safety Bounds for Large Language Models
We propose a novel framework for computing rigorous bounds on the probability that a large language model (LLM) generates harmful output to a given prompt. We study a new application of the Clopper-Pearson confidence int…
Bounds on the Expected Size of the Maximum Agreement Subtree
We prove polynomial upper and lower bounds on the expected size of the maximum agreement subtree of two random binary phylogenetic trees under both the uniform distribution and Yule-Harding distribution. This positively …