Boston University
Towards efficient and secure AI: Nearest Neighbor Algorithms for transformers and adversarial robustness
Abstract
dc:description.abstractThis thesis explores Nearest Neighbor Algorithms across diverse areas of Machine Learning and Theoretical Computer Science. First, it advances the theoretical understanding of Sparse Transformer architectures that leverage k Nearest Neighbor primitives. Second, it introduces novel algorithms to enhance the adversarial robustness of efficient nearest neighbor search methods. Transformers have revolutionized machine learning, but their quadratic self-attention complexity poses challenges for long-sequence processing. To address this limitation, k-Nearest-Neighbor (kNN) attention enables each token to attend only to its k closest tokens, achieving improved efficiency. However, the theoretical foundations of kNN attention remain underexplored. This work establishes a rigorous framework for kNN attention, reformulating self-attention as expectations over softmax distributions and leveraging lazy Gumbel sampling with kNN indices for efficient approximation. Building on this framework, we propose novel sub-quadratic algorithms that approximate self-attention gradients using techniques such as Markov Chain-based estimation. Empirical experiments validate the effectiveness of these methods, demonstrating benefits in both training and inference. In parallel, we investigate adversarial robustness guarantees for computational search problems, particularly Approximate Nearest Neighbor Search via Locality Sensitive Hashing (LSH). While adversarial robustness has primarily focused on estimation problems, little attention has been given to protecting internal algorithmic randomness when returning specific data points. We extend the adversarial robustness framework by integrating differential privacy with fair near-neighbor algorithms to secure search problems under adversarial conditions. Additionally, we propose an alternative approach that foregoes fair algorithms, leveraging deterministic exhaustive searches on small data subsets. Furthermore, we demonstrate how "for all" guarantees in randomized algorithms yield efficient solutions in low-dimensional settings.
Degree
thesis:*- Name thesis:degree_name
- Master of Science
- Level thesis:degree_level
- masters
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Boston University
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Haris, Themistoklis
- Advisor dc:contributor.advisor
-
- Onak, Krzysztof
- ORCID dc:identifier.orcid
Subjects
dc:subject × 6Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53188