A quantum active learning algorithm for sampling against adversarial attacks
This work addresses security vulnerabilities in autonomous systems by providing a method to verify robustness, but it is incremental as it builds on existing theoretical conditions and offers a quantum speedup that may not be fully practical due to dequantization.
The paper tackles the problem of ensuring machine learning robustness against adversarial attacks by determining the minimum distance between classes, as required by the Khoury-Hadfield-Menell theorem, through a theoretical framework for active learning. It introduces a quantum algorithm with polylogarithmic complexity in dimension and data size, achieving an exponential speedup over classical methods, though it can be dequantized to a polynomial advantage.
Adversarial attacks represent a serious menace for learning algorithms and may compromise the security of future autonomous systems. A theorem by Khoury and Hadfield-Menell (KH), provides sufficient conditions to guarantee the robustness of machine learning algorithms, but comes with a caveat: it is crucial to know the smallest distance among the classes of the corresponding classification problem. We propose a theoretical framework that allows us to think of active learning as sampling the most promising new points to be classified, so that the minimum distance between classes can be found and the theorem KH used. Additionally, we introduce a quantum active learning algorithm that makes use of such framework and whose complexity is polylogarithmic in the dimension of the space, $m$, and the size of the initial training data $n$, provided the use of qRAMs; and polynomial in the precision, achieving an exponential speedup over the equivalent classical algorithm in $n$ and $m$. This algorithm may be nevertheless `dequantized' reducing the advantage to polynomial.