{"id":{"repo_id":"bu","oai_identifier":"oai:open.bu.edu:2144/53188"},"canonical_url":"https://search.ndltd.org/etd/bu/oai:open.bu.edu:2144/53188","repository":{"repo_id":"bu","name":"Boston University","base_url":"https://open.bu.edu/oai/request"},"display":{"title":"Towards efficient and secure AI: Nearest Neighbor Algorithms for transformers and adversarial robustness","abstract":"This 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.","abstract_html":"This 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 &quot;for all&quot; guarantees in randomized algorithms yield efficient solutions in low-dimensional settings.","abstract_has_math":false,"creators":["Haris, Themistoklis"],"institution":"Boston University","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Onak, Krzysztof"],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024","date_published":"2024","updated_at":"2026-11-18T20:05:03Z","subjects":["Computer science","Artificial intelligence","Theoretical mathematics","Adversarial robustness","Nearest Neighbor search","Transformers"],"languages":["en_US"],"rights":["Attribution 4.0 International"],"rights_urls":["http://creativecommons.org/licenses/by/4.0/"],"identifier_entries":[],"person_identifier_entries":[{"key":"dc:identifier.orcid","label":"ORCID","values":["0009-0009-4703-6266"],"render_values":[{"text":"0009-0009-4703-6266","href":"https://orcid.org/0009-0009-4703-6266","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/2144/53188","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/2144/53188","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://open.bu.edu/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aopen.bu.edu%3A2144%2F53188","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Onak, Krzysztof"]},{"key":"dc:creator","label":"Author","values":["Haris, Themistoklis"]},{"key":"dc:identifier.orcid","label":"ORCID","values":["0009-0009-4703-6266"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-06-22T12:51:44Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-06-22T12:51:44Z"]},{"key":"dc:date.issued","label":"Date","values":["2024"]},{"key":"dc:date.updated","label":"Dc Date Updated","values":["2026-06-19T01:02:19Z"]},{"key":"dc:type","label":"Dc Type","values":["Thesis/Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Boston University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science","Artificial intelligence","Theoretical mathematics","Adversarial robustness","Nearest Neighbor search","Transformers"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution 4.0 International"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2144/53188"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["2024"]},{"key":"dc:description.abstract","label":"Abstract","values":["This 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."]},{"key":"dc:title","label":"Title","values":["Towards efficient and secure AI: Nearest Neighbor Algorithms for transformers and adversarial robustness"]}]}],"canonical_facts":{"dc:contributor.advisor":["Onak, Krzysztof"],"dc:creator":["Haris, Themistoklis"],"dc:date.accessioned":["2026-06-22T12:51:44Z"],"dc:date.available":["2026-06-22T12:51:44Z"],"dc:date.issued":["2024"],"dc:date.updated":["2026-06-19T01:02:19Z"],"dc:description":["2024"],"dc:description.abstract":["This 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."],"dc:identifier.orcid":["0009-0009-4703-6266"],"dc:identifier.uri":["https://hdl.handle.net/2144/53188"],"dc:language.iso":["en_US"],"dc:rights":["Attribution 4.0 International"],"dc:rights.uri":["http://creativecommons.org/licenses/by/4.0/"],"dc:subject":["Computer science","Artificial intelligence","Theoretical mathematics","Adversarial robustness","Nearest Neighbor search","Transformers"],"dc:title":["Towards efficient and secure AI: Nearest Neighbor Algorithms for transformers and adversarial robustness"],"dc:type":["Thesis/Dissertation"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Boston University"]},"updated_at":"2026-11-18T20:05:03Z"}