  Our work targets at searching feasible adversarial perturbation to attack a
classifier with high-dimensional categorical inputs in a domain-agnostic
setting. This is intrinsically an NP-hard knapsack problem where the
exploration space becomes explosively larger as the feature dimension
increases. Without the help of domain knowledge, solving this problem via
heuristic method, such as Branch-and-Bound, suffers from exponential
complexity, yet can bring arbitrarily bad attack results. We address the
challenge via the lens of multi-armed bandit based combinatorial search. Our
proposed method, namely FEAT, treats modifying each categorical feature as
pulling an arm in multi-armed bandit programming. Our objective is to achieve
highly efficient and effective attack using an Orthogonal Matching Pursuit
(OMP)-enhanced Upper Confidence Bound (UCB) exploration strategy. Our
theoretical analysis bounding the regret gap of FEAT guarantees its practical
attack performance. In empirical analysis, we compare FEAT with other
state-of-the-art domain-agnostic attack methods over various real-world
categorical data sets of different applications. Substantial experimental
observations confirm the expected efficiency and attack effectiveness of FEAT
applied in different application scenarios. Our work further hints the
applicability of FEAT for assessing the adversarial vulnerability of
classification systems with high-dimensional categorical inputs.
