Timezone: »
Poster
RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval
Yihan Wu · Hongyang Zhang · Heng Huang
Recent research works have shown that image retrieval models are vulnerable to adversarial attacks, where slightly modified test inputs could lead to problematic retrieval results. In this paper, we aim to design a provably robust image retrieval model which keeps the most important evaluation metric Recall@1 invariant to adversarial perturbation. We propose the first 1-nearest neighbor (NN) image retrieval algorithm, RetrievalGuard, which is provably robust against adversarial perturbations within an $\ell_2$ ball of calculable radius. The challenge is to design a provably robust algorithm that takes into consideration the 1-NN search and the high-dimensional nature of the embedding space. Algorithmically, given a base retrieval model and a query sample, we build a smoothed retrieval model by carefully analyzing the 1-NN search procedure in the high-dimensional embedding space. We show that the smoothed retrieval model has bounded Lipschitz constant and thus the retrieval score is invariant to $\ell_2$ adversarial perturbations. Experiments on on image retrieval tasks validate the robustness of our RetrievalGuard method.
Author Information
Yihan Wu (University of Pittsburgh)
Hongyang Zhang (University of Waterloo)
Heng Huang (University of Pittsburgh & JD Finance America Corporation)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Spotlight: RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval »
Wed. Jul 20th 05:25 -- 05:30 PM Room Room 310
More from the Same Authors
-
2022 : Causal Balancing for Domain Generalization »
Xinyi Wang · Michael Saxon · Jiachen Li · Hongyang Zhang · Kun Zhang · William Wang -
2023 Poster: Tighter Analysis for ProxSkip »
Zhengmian Hu · Heng Huang -
2023 Poster: Understanding the Impact of Adversarial Robustness on Accuracy Disparity »
Yuzheng Hu · Fan Wu · Hongyang Zhang · Han Zhao -
2023 Poster: A Law of Robustness beyond Isoperimetry »
Yihan Wu · Heng Huang · Hongyang Zhang -
2023 Poster: Beyond Lipschitz Smoothness: A Tighter Analysis for Nonconvex Optimization »
Zhengmian Hu · Xidong Wu · Heng Huang -
2022 Poster: On the Convergence of Local Stochastic Compositional Gradient Descent with Momentum »
Hongchang Gao · Junyi Li · Heng Huang -
2022 Poster: Building Robust Ensembles via Margin Boosting »
Dinghuai Zhang · Hongyang Zhang · Aaron Courville · Yoshua Bengio · Pradeep Ravikumar · Arun Sai Suggala -
2022 Spotlight: On the Convergence of Local Stochastic Compositional Gradient Descent with Momentum »
Hongchang Gao · Junyi Li · Heng Huang -
2022 Spotlight: Building Robust Ensembles via Margin Boosting »
Dinghuai Zhang · Hongyang Zhang · Aaron Courville · Yoshua Bengio · Pradeep Ravikumar · Arun Sai Suggala -
2022 Poster: Detached Error Feedback for Distributed SGD with Random Sparsification »
An Xu · Heng Huang -
2022 Spotlight: Detached Error Feedback for Distributed SGD with Random Sparsification »
An Xu · Heng Huang -
2021 Poster: On the Random Conjugate Kernel and Neural Tangent Kernel »
Zhengmian Hu · Heng Huang -
2021 Spotlight: On the Random Conjugate Kernel and Neural Tangent Kernel »
Zhengmian Hu · Heng Huang -
2020 Poster: Momentum-Based Policy Gradient Methods »
Feihu Huang · Shangqian Gao · Jian Pei · Heng Huang -
2020 Poster: Adversarial Nonnegative Matrix Factorization »
lei luo · yanfu Zhang · Heng Huang -
2020 Poster: Sparse Shrunk Additive Models »
guodong liu · Hong Chen · Heng Huang -
2020 Poster: Can Stochastic Zeroth-Order Frank-Wolfe Method Converge Faster for Non-Convex Problems? »
Hongchang Gao · Heng Huang -
2020 Poster: Fast OSCAR and OWL Regression via Safe Screening Rules »
Runxue Bao · Bin Gu · Heng Huang -
2019 Poster: Demystifying Dropout »
Hongchang Gao · Jian Pei · Heng Huang -
2019 Oral: Demystifying Dropout »
Hongchang Gao · Jian Pei · Heng Huang -
2019 Poster: Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization »
Feihu Huang · Songcan Chen · Heng Huang -
2019 Oral: Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization »
Feihu Huang · Songcan Chen · Heng Huang -
2018 Poster: Faster Derivative-Free Stochastic Algorithm for Shared Memory Machines »
Bin Gu · Zhouyuan Huo · Cheng Deng · Heng Huang -
2018 Poster: Decoupled Parallel Backpropagation with Convergence Guarantee »
Zhouyuan Huo · Bin Gu · Qian Yang · Heng Huang -
2018 Oral: Decoupled Parallel Backpropagation with Convergence Guarantee »
Zhouyuan Huo · Bin Gu · Qian Yang · Heng Huang -
2018 Oral: Faster Derivative-Free Stochastic Algorithm for Shared Memory Machines »
Bin Gu · Zhouyuan Huo · Cheng Deng · Heng Huang