summaries: This paper proposes a unified alternating projected gradient descent-ascent (APGDA) attack by considering the min-max operation for adversarial attack settings. The proposed method can be applied in generating model ensemble attacks, universal adversarial attacks, and robust attacks over data transformations. Extensive results show that the proposed method can achieve better attack performances for these three applications.

summaries: This paper proposed a APGDA attack method, in which the model ensemble attack, universal attack, and robust attack are unified. The authors proved their APGDA's superiority in theory, ${i.e.}$, convergence rate and strong attacking ability. All of the mentioned tasks (ensemble attack, universal attack, robust attack) are investigated through experiments.

summaries: The paper provides a general min-max framework to formulate several popular problems in the literature including Ensemble attack over multiple models, Universal Perturbation over multiple examples, and adversarial attack over data transformations. For each case, a standard first-order approach converging to a stationary point of the problem is provided. The effectiveness of the min-max approach compared to the standard empirical risk minimization has been demonstrated by extensive experiments.

summaries: This paper adapts the min-max problem proposed for multi-domain robust optimization [45] to the problem of generating adversarial attacks. They show how several adversarial attacks scenarios can be formulated using this min-max, for example they show that this min-max formulation can be used to find successful attacks against an ensemble of models. They also show how this min-max can also be used to train robust models against multiple $\ell_p$ attacks. They show experimentally that the approach outperforms several baseline in several setting.

summaries: The work proposes a min-max framework APGDA that can take in different models related to adversarial robustness. APGDA can generate model ensemble attack, universal attack over multiple images, and robust attack over data transformations. They perform experiments to evaluate their method.

abstractText: The worst-case training principle that minimizes the maximal adversarial loss, also known as adversarial training (AT), has shown to be a state-of-the-art approach for enhancing adversarial robustness. Nevertheless, min-max optimization beyond the purpose of AT has not been rigorously explored in the adversarial context. In this paper, we show how a general framework of min-max optimization over multiple domains can be leveraged to advance the design of different types of adversarial attacks. In particular, given a set of risk sources, minimizing the worst-case attack loss can be reformulated as a min-max problem by introducing domain weights that are maximized over the probability simplex of the domain set. We showcase this unified framework in three attack generation problems – attacking model ensembles, devising universal perturbation under multiple inputs, and crafting attacks resilient to data transformations. Extensive experiments demonstrate that our approach leads to substantial attack improvement over the existing heuristic strategies as well as robustness improvement over state-of-the-art defense methods trained to be robust against multiple perturbation types. Furthermore, we find that the self-adjusted domain weights learned from our min-max framework can provide a holistic tool to explain the difficulty level of attack across domains. Code is available at https://github.com/wangjksjtu/minmax-adv.

authors:
M. Andriushchenko
F. Croce
N. Flammarion
M. Hein

title: Square attack: A query-efficient black-box adversarial attack via random search

venue: ECCV (23), volume 12368 of Lecture Notes in Computer Science, pages 484–501. Springer

authors:
A. Araujo
R. Pinot
B. Negrevergne
L. Meunier
Y. Chevaleyre
F. Yger
J. Atif

title: Robust neural networks using randomized adversarial training

venue: arXiv preprint arXiv:1903.10219

authors:
A. Athalye
N. Carlini
D. Wagner

title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples

venue: arXiv preprint arXiv:1802.00420

authors:
A. Athalye
L. Engstrom
A. Ilyas
K. Kwok

title: Synthesizing robust adversarial examples

venue: ICML, volume 80 of Proceedings of Machine Learning Research, pages 284–293. PMLR

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
A. Athalye
I. Sutskever

venue: ICML

authors:
A.J. Bose
G. Gidel
H. Berard
A. Cianflone
P. Vincent
S. Lacoste-Julien
W.L. Hamilton

title: Adversarial example games

venue: NeurIPS

authors:
S. Boyd
L. Vandenberghe

title: Convex optimization

venue: Cambridge university press

authors:
W. Brendel
J. Rauber
M. Bethge

title: Decision-based adversarial attacks: Reliable attacks against black-box machine learning models

venue: arXiv preprint arXiv:1712.04248

authors:
T.B. Brown
D. Mané
A. Roy
M. Abadi
J. Gilmer

title: Adversarial patch

authors:
N. Carlini
A. Athalye
N. Papernot
W. Brendel
J. Rauber
D. Tsipras
I.J. Goodfellow
A. Madry
A. Kurakin

title: On evaluating adversarial robustness

authors:
N. Carlini
P. Mishra
T. Vaidya
Y. Zhang
M. Sherr
C. Shields
D. Wagner
W. Zhou

title: Hidden voice commands

venue: USENIX Security Symposium, pages 513–530

authors:
N. Carlini
D. Wagner

title: Towards evaluating the robustness of neural networks

venue: Security and Privacy (SP), 2017 IEEE Symposium on, pages 39–57. IEEE

authors:
N. Carlini
D.A. Wagner

title: Audio adversarial examples: Targeted attacks on speech-to-text

venue: IEEE Symposium on Security and Privacy Workshops, pages 1–7. IEEE Computer Society

authors:
H. Chen
H. Zhang
P.-Y. Chen
J. Yi
C.-J. Hsieh

title: Attacking visual language grounding with adversarial examples: A case study on neural image captioning

venue: Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, volume 1, pages 2587–2597

authors:
J.M. Cohen
E. Rosenfeld
J.Z. Kolter

title: Certified adversarial robustness via randomized smoothing

venue: ICML, volume 97 of Proceedings of Machine Learning Research, pages 1310– 1320. PMLR

authors:
F. Croce
M. Hein

title: Provable robustness against all adversarial lp-perturbations for p 1

venue: arXiv preprint arXiv:1905.11213

title: Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks

venue: ICML, volume 119 of Proceedings of Machine Learning Research, pages 2206–2216. PMLR

authors:
Y. Dong
F. Liao
T. Pang
H. Su
J. Zhu
X. Hu
J. Li

title: Boosting adversarial attacks with momentum

venue: CVPR, pages 9185–9193. IEEE Computer Society

authors:
K. Eykholt
I. Evtimov
E. Fernandes
B. Li
A. Rahmati
C. Xiao
A. Prakash
T. Kohno
D. Song

title: Robust physical-world attacks on deep learning visual classification

venue: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1625–1634

venue: CVPR, pages 1625–1634. IEEE Computer Society

authors:
I. Goodfellow
J. Shlens
C. Szegedy

title: Explaining and harnessing adversarial examples

venue: 2015 ICLR, arXiv preprint arXiv:1412.6572

authors:
I.J. Goodfellow
J. Shlens
C. Szegedy

venue: arXiv preprint arXiv:1412.6572

authors:
K. He
X. Zhang
S. Ren
J. Sun

title: Deep residual learning for image recognition

venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770– 778

authors:
M. Hein
M. Andriushchenko

title: Formal guarantees on the robustness of a classifier against adversarial manipulation

venue: Advances in Neural Information Processing Systems, pages 2266– 2276

authors:
S. Huang
N. Papernot
I.J. Goodfellow
Y. Duan
P. Abbeel

title: Adversarial attacks on neural network policies

venue: ICLR (Workshop). OpenReview.net

authors:
R. Jia
P. Liang

title: Adversarial examples for evaluating reading comprehension systems

venue: EMNLP, pages 2021–2031. Association for Computational Linguistics

authors:
D. Kang
Y. Sun
D. Hendrycks
T. Brown
J. Steinhardt

title: Testing robustness against unforeseen adversaries

venue: arXiv preprint arXiv:1908.08016

authors:
H. Karimi
J. Nutini
M. Schmidt

title: Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition

venue: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795–811. Springer

authors:
Y. Lecun
L. Bottou
Y. Bengio
P. Haffner

title: Gradient-based learning applied to document recognition

authors:
Q. Lei
L. Wu
P.-Y. Chen
A.G. Dimakis
I.S. Dhillon
M. Witbrock

title: Discrete adversarial attacks and submodular optimization with applications to text classification

venue: SysML

authors:
T. Lin
C. Jin
M.I. Jordan

title: On gradient descent ascent for nonconvex-concave minimax problems

venue: ICML, volume 119 of Proceedings of Machine Learning Research, pages 6083– 6093. PMLR

authors:
Y. Lin
Z. Hong
Y. Liao
M. Shih
M. Liu
M. Sun

title: Tactics of adversarial attack on deep reinforcement learning agents

venue: IJCAI, pages 3756–3762. ijcai.org

authors:
J. Liu
W. Zhang
N. Yu

title: CAAD 2018: Iterative ensemble adversarial attack

authors:
S. Liu
S. Lu
X. Chen
Y. Feng
K. Xu
A. Al-Dujaili
M. Hong
U. Obelilly

title: Min-max optimization without gradients: Convergence and applications to adversarial ML

authors:
Y. Liu
X. Chen
C. Liu
D. Song

title: Delving into transferable adversarial examples and black-box attacks

venue: ICLR. OpenReview.net

authors:
S. Lu
R. Singh
X. Chen
Y. Chen

title: and M

venue: Hong. Understand the dynamics of GANs via primal-dual optimization

authors:
S. Lu
I. Tsaknakis
M. Hong

title: Block alternating optimization for non-convex min-max problems: Algorithms and applications in signal processing and communications. 2018

title: Block alternating optimization for non-convex min-max problems: algorithms and applications in signal processing and communications

venue: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

authors:
A. Madry
A. Makelov
L. Schmidt
D. Tsipras
A. Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: arXiv preprint arXiv:1706.06083

authors:
P. Maini
E. Wong
J.Z. Kolter

title: Adversarial robustness against the union of multiple perturbation models

venue: ICML, volume 119 of Proceedings of Machine Learning Research, pages 6640–6650. PMLR

authors:
D. Meng
H. Chen

title: Magnet: a two-pronged defense against adversarial examples

venue: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 135–147. ACM

authors:
J.H. Metzen
M.C. Kumar
T. Brox
V. Fischer

title: Universal adversarial perturbations against semantic image segmentation

venue: ICCV, pages 2774–2783. IEEE Computer Society

authors:
S.-M. Moosavi-Dezfooli
A. Fawzi
O. Fawzi
P. Frossard

title: Universal adversarial perturbations

venue: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 86–94

authors:
S.M. Moosavi Dezfooli
A. Fawzi
P. Frossard

title: Deepfool: a simple and accurate method to fool deep neural networks

venue: Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), number EPFL-CONF-218057

authors:
M. Nouiehed
M. Sanjabi
J.D. Lee
M. Razaviyayn

title: Solving a class of non-convex min-max games using iterative first order methods

venue: arXiv preprint arXiv:1902.08297

authors:
N. Papernot
P. McDaniel
I. Goodfellow
S. Jha
Z.B. Celik
A. Swami

title: Practical black-box attacks against machine learning

venue: Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pages 506–519. ACM

authors:
N. Papernot
P. McDaniel
S. Jha
M. Fredrikson
Z.B. Celik
A. Swami

title: The limitations of deep learning in adversarial settings

venue: Security and Privacy (EuroS&P), 2016 IEEE European Symposium on, pages 372–387. IEEE

authors:
N. Parikh
S. Boyd

title: et al

venue: Proximal algorithms. Foundations and Trends R in Optimization, 1(3):127–239

authors:
Q. Qian
S. Zhu
J. Tang
R. Jin
B. Sun
H. Li

title: Robust optimization over multiple domains

authors:
H. Rafique
M. Liu
Q. Lin
T. Yang

title: Non-convex min-max optimization: Provable algorithms and applications in machine learning

venue: arXiv preprint arXiv:1810.02060

authors:
J. Rauber
W. Brendel

title: and M

venue: Bethge. Foolbox v0.8.0: A python toolbox to benchmark the robustness of machine learning models. CoRR, abs/1707.04131

authors:
L. Rice
E. Wong
J.Z. Kolter

title: Overfitting in adversarially robust deep learning

venue: ICML, volume 119 of Proceedings of Machine Learning Research, pages 8093–8104. PMLR

authors:
J. Rony
L.G. Hafemann
L.S. Oliveira
I.B. Ayed
R. Sabourin
E. Granger

title: Decoupling direction and norm for efficient gradient-based L2 adversarial attacks and defenses

venue: CVPR, pages 4322–4330. Computer Vision Foundation / IEEE

authors:
L. Schott
J. Rauber
M. Bethge
W. Brendel

title: Towards the first adversarially robust neural network model on MNIST

venue: ICLR (Poster). OpenReview.net

authors:
A. Shafahi
M. Najibi
Z. Xu
J.P. Dickerson
L.S. Davis
T. Goldstein

title: Universal adversarial training

authors:
F. Sheikholeslami
A. Lotfi
J.Z. Kolter

title: Provably robust classification of adversarial examples with detection

authors:
K. Simonyan
A. Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: ICLR

authors:
A. Sinha
H. Namkoong
J. Duchi

title: Certifying some distributional robustness with principled adversarial training

title: A disciplined approach to neural network hyper-parameters: Part 1 - learning rate

venue: batch size, momentum, and weight decay. CoRR, abs/1803.09820

authors:
J.T. Springenberg
A. Dosovitskiy
T. Brox
M.A. Riedmiller

title: Striving for simplicity: The all convolutional net

venue: ICLR (Workshop)

authors:
D. Su
H. Zhang
H. Chen
J. Yi
P.-Y. Chen
Y. Gao

title: Is robustness the cost of accuracy?–a comprehensive study on the robustness of 18 deep image classification models

venue: Proceedings of the European Conference on Computer Vision (ECCV), pages 631–648

authors:
C. Szegedy
W. Liu
Y. Jia
P. Sermanet
S.E. Reed
D. Anguelov
D. Erhan
V. Vanhoucke
A. Rabinovich

title: Going deeper with convolutions

venue: CVPR, pages 1–9. IEEE Computer Society

authors:
C. Szegedy
W. Zaremba
I. Sutskever
J. Bruna
D. Erhan
I. Goodfellow
R. Fergus

title: Intriguing properties of neural networks

venue: arXiv preprint arXiv:1312.6199

authors:
F. Tramèr
D. Boneh

title: Adversarial training and robustness for multiple perturbations

venue: arXiv preprint arXiv:1904.13000

authors:
F. Tramèr
A. Kurakin
N. Papernot
I. Goodfellow
D. Boneh
P. McDaniel

title: Ensemble adversarial training: Attacks and defenses

venue: 2018 ICLR, arXiv preprint arXiv:1705.07204

authors:
F. Tramèr
N. Papernot
I. Goodfellow
D. Boneh
P. McDaniel

title: The space of transferable adversarial examples

venue: arXiv preprint arXiv:1704.03453

authors:
E. Wong
L. Rice
J.Z. Kolter

title: Fast is better than free: Revisiting adversarial training

authors:
C. Xiao
B. Li
J.-Y. Zhu
W. He
M. Liu
D. Song

title: Generating adversarial examples with adversarial networks

venue: arXiv preprint arXiv:1801.02610

authors:
C. Xiao
J.-Y. Zhu
B. Li
W. He
M. Liu
D. Song

title: Spatially transformed adversarial examples

venue: International Conference on Learning Representations

authors:
C. Xie
J. Wang
Z. Zhang
Z. Ren
A. Yuille

title: Mitigating adversarial effects through randomization

venue: arXiv preprint arXiv:1711.01991

authors:
K. Xu
S. Liu
P. Zhao
P.-Y. Chen
H. Zhang
Q. Fan
D. Erdogmus
Y. Wang
X. Lin

title: Structured adversarial attack: Towards general implementation and better interpretability

authors:
K. Xu
G. Zhang
S. Liu
Q. Fan
M. Sun
H. Chen
P. Chen
Y. Wang
X. Lin

title: Adversarial t-shirt! evading person detectors in a physical world

venue: ECCV (5), volume 12350 of Lecture Notes in Computer Science, pages 665–681. Springer

authors:
W. Xu
D. Evans
Y. Qi

title: Feature squeezing: Detecting adversarial examples in deep neural networks

venue: NDSS. The Internet Society

authors:
S. Zagoruyko
N. Komodakis

title: Wide residual networks

venue: BMVC. BMVA Press

authors:
H. Zhang
Y. Yu
J. Jiao
E.P. Xing
L.E. Ghaoui
M.I. Jordan

title: Theoretically principled trade-off between robustness and accuracy

venue: arXiv preprint arXiv:1901.08573

authors:
Z. Zhao
D. Dua
S. Singh

title: Generating natural adversarial examples

heading: 1 Introduction

text:
Training a machine learning model that is capable of assuring its worst-case performance against possible adversaries given a specified threat model is a fundamental and challenging problem, especially for deep neural networks (DNNs) [64, 22, 13, 69, 70]. A common practice to train an adversarially robust model is based on a specific form of min-max training, known as adversarial training (AT) [22, 40], where the minimization step learns model weights under the adversarial loss constructed at the maximization step in an alternative training fashion. In practice, AT has achieved the state-of-the-art defense performance against `p-norm-ball input perturbations [3].
Although the min-max principle is widely used in AT and its variants [40, 59, 76, 65], few work has studied its power in attack generation. Thus, we ask: Beyond AT, can other types of min-max formulation and optimization techniques advance the research in adversarial attack generation? In this paper, we give an affirmative answer corroborated by the substantial performance gain and the ability of self-learned risk interpretation using our proposed min-max framework on several tasks for adversarial attack.
⇤Equal contributions.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We demonstrate the utility of a general formulation for minimizing the maximal loss induced from a set of risk sources (domains). Our considered min-max formulation is fundamentally different from AT, as our maximization step is taken over the probability simplex of the set of domains. Moreover, we show that many problem setups in adversarial attacks can in fact be reformulated under this general min-max framework, including attacking model ensembles [66, 34], devising universal perturbation to input samples [44] and data transformations [6, 10]. However, current methods for solving these tasks often rely on simple heuristics (e.g., uniform averaging), resulting in significant performance drops when comparing to our proposed min-max optimization framework.
Contributions ¨ With the aid of min-max optimization, we propose a unified alternating onestep projected gradient descent-ascent (APGDA) attack method, which can readily be specified to generate model ensemble attack, universal attack over multiple images, and robust attack over data transformations. ≠ In theory, we show that APGDA has an O(1/T ) convergence rate, where T is the number of iterations. In practice, we show that APGDA obtains 17.48%, 35.21% and 9.39% improvement on average compared with conventional min-only PGD attack methods on CIFAR-10. Æ More importantly, we demonstrate that by tracking the learnable weighting factors associated with multiple domains, our method can provide tools for self-adjusted importance assessment on the mixed learning tasks. Ø Finally, we adapt the idea of the domain weights into a defense setting [65], where multiple `p-norm perturbations are generated, and achieve superior performance as well as intepretability.

heading: 1.1 Related work

text:
Recent studies have identified that DNNs are highly vulnerable to adversarial manipulations in various applications [64, 12, 27, 33, 26, 14, 77, 20, 15, 31], thus leading to an arms race between adversarial attacks [13, 3, 23, 48, 45, 72, 1, 18] and defenses [40, 59, 76, 65, 42, 71, 74, 68, 53, 16]. One intriguing property of adversarial examples is the transferability across multiple domains [36, 67, 47, 62], which indicates a more challenging yet promising research direction – devising universal adversarial perturbations over model ensembles [66, 34], input samples [44, 43, 56] and data transformations [3, 6, 10].
Besides, many recent works started to produce physical realizable perturbations that expose real world threats. The most popular approach [4, 21], as known as Expectation Over Transformation (EOT), is to train the attack under different data transformation (e.g., different view angles and distances). However, current approaches suffer from a significant performance loss for resting on the uniform averaging strategy or heuristic weighting schemes [34, 56]. We will compare these works with our min-max method in Sec. 4. As a natural extension following min-max attack, we study the generalized AT under multiple perturbations [65, 2, 28, 17]. Finally, our min-max framework is adapted and inspired by previous literature on robust optimization over multiple domains [50, 51, 38, 37].
To our best knowledge, only few works leverage min-max principle for adversarial attack generation while the idea of producing the worst-case example across multiple domains is quite natural. Specifically, [7] considered the non-interactive blackbox adversary setting and proposed a framework that models the crafting of adversarial examples as a min-max game between a generator of attacks and a classifier. [57] introduced a min-max based adaptive attacker’s objective to craft perturbation so that it simultaneously evades detection and causes misclassification. Inspired by our work, the min-max formulation has also been extended to zero-order blackbox attacks [35] and physically realizable attacks [73, Adversarial T-shirt]. We hope our unified formulation can stimulate further research on applying min-max principle and interpretable domain weights in more attack generation tasks that involve in evading multiple systems.

heading: 2 Min-Max Across Domains

text:
Consider K loss functions {Fi(v)} (each of which is defined on a learning domain), the problem of robust learning over K domains can be formulated as [50, 51, 38]
minimize v2V maximize w2P
P K
i=1 wiFi(v), (1)
where v and w are optimization variables, V is a constraint set, and P denotes the probability simplex P = {w |1Tw = 1, wi 2 [0, 1], 8i}. Since the inner maximization problem in (1) is a linear function
of w over the probabilistic simplex, problem (1) is thus equivalent to minimize
v2V maximize i2[K] Fi(v), (2)
where [K] denotes the integer set {1, 2, . . . ,K}.
Benefit and Challenge from (1). Compared to multi-task learning in a finite-sum formulation which minimizes K losses on average, problem (1) provides consistently robust worst-case performance across all domains. This can be explained from the epigraph form of (2),
minimize v2V,t t, subject to Fi(v)  t, i 2 [K], (3) where t is an epigraph variable [8] that provides the t-level robustness at each domain.
In computation, the inner maximization problem of (1) always returns the one-hot value of w, namely, w = ei, where ei is the ith standard basis vector, and i = argmaxi{Fi(v)}. However, this one-hot coding reduces the generalizability to other domains and induces instability of the learning procedure in practice. Such an issue is often mitigated by introducing a strongly concave regularizer in the inner maximization step to strike a balance between the average and the worst-case performance [38, 50].
Regularized Formulation. Following [50], we penalize the distance between the worst-case loss and the average loss over K domains. This yields
minimize v2V maximize w2P
P K
i=1 wiFi(v) 2 kw 1/Kk 2 2, (4)
where > 0 is a regularization parameter. As ! 0, problem (4) is equivalent to (1). By contrast, it becomes the finite-sum problem when ! 1 since w ! 1/K. In this sense, the trainable w provides an essential indicator on the importance level of each domain. The larger the weight is, the more important the domain is. We call w domain weights in this paper.

heading: 3 Min-Max Power in Attack Design

text: To the best of our knowledge, few work has studied the power of min-max in attack generation. In this section, we demonstrate how the unified min-max framework (4) fits into various attack settings. With the help of domain weights, our solution yields better empirical performance and explainability. Finally, we present the min-max algorithm with convergence analysis to craft robust perturbations against multiple domains.

heading: 3.1 A Unified Framework for Robust Adversarial Attacks

text:
The general goal of adversarial attack is to craft an adversarial example x0 = x0 + 2 Rd to mislead the prediction of machine learning (ML) or deep learning (DL) systems, where x0 denotes the natural example with the true label t0, and is known as adversarial perturbation, commonly subject to `p-norm (p 2 {0, 1, 2,1}) constraint X := { | k kp  ✏, x0 + 2 [0, 1]d} for a given small number ✏. Here the `p norm enforces the similarity between x0 and x0, and the input space of ML/DL systems is normalized to [0, 1]d.
Ensemble Attack over Multiple Models. Consider K ML/DL models {Mi}Ki=1, the goal is to find robust adversarial examples that can fool all K models simultaneously. In this case, the notion of ‘domain’ in (4) is specified as ‘model’, and the objective function Fi in (4) signifies the attack loss f( ;x0, y0,Mi) given the natural input (x0, y0) and the model Mi. Thus, problem (4) becomes
minimize 2X maximize w2P
P K
i=1 wif( ;x0, y0,Mi) 2 kw 1/Kk 2 2, (5)
where w encodes the difficulty level of attacking each model.
Universal Perturbation over Multiple Examples. Consider K natural examples {(xi, yi)}Ki=1 and a single model M, our goal is to find the universal perturbation so that all the corrupted K examples can fool M. In this case, the notion of ‘domain’ in (4) is specified as ‘example’, and problem (4) becomes
minimize 2X maximize w2P
P K
i=1 wif( ;xi, yi,M) 2 kw 1/Kk 2 2, (6)
where different from (5), w encodes the difficulty level of attacking each example.
Adversarial Attack over Data Transformations. Consider K categories of data transformation {pi}, e.g., rotation, lightening, and translation, our goal is to find the adversarial attack that is robust to data transformations. Such an attack setting is commonly applied to generate physical adversarial examples [5, 20]. Here the notion of ‘domain’ in (4) is specified as ‘data transformer’, and problem (4) becomes
minimize 2X maximize w2P
P K
i=1 wiEt⇠pi [f(t(x0 + ); y0,M)] 2 kw 1/Kk 2 2, (7)
where Et⇠pi [f(t(x0+ ); y0,M)] denotes the attack loss under the distribution of data transformation pi, and w encodes the difficulty level of attacking each type of transformed example x0. We remark that if w = 1/K, then problem (7) reduces to the existing expectation of transformation (EOT) setup used for physical attack generation [5].
Benefits of Min-Max Attack Generation with Learnable Domain Weights w: We can interpret (5)-(7) as finding the robust adversarial attack against the worst-case environment that an adversary encounters, e.g., multiple victim models, data samples, and input transformations. The proposed min-max design of adversarial attacks leads to two main benefits. First, compared to the heuristic weighting strategy (e.g., clipping thresholds on the importance of individual attack losses [56]), our proposal is free of supervised manual adjustment on domain weights. Even by carefully tuning the heuristic weighting strategy, we find that our approach with self-adjusted w consistently outperforms the clipping strategy in [56] (see Table 2). Second, the learned domain weights can be used to assess the model robustness when facing different types of adversary. We refer readers to Figure 1c and
Figure 6 for more details.

heading: 3.2 Min-Max Algorithm for Adversarial Attack Generation

text:
Algorithm 1 APGDA to solve problem (4) 1: Input: given w(0) and (0). 2: for t = 1, 2, . . . , T do 3: outer min.: fixing w = w(t 1), call
PGD (8) to update (t) 4: inner max.: fixing = (t), update w(t) with projected gradient ascent (9) 5: end for
We propose the alternating projected gradient descent-ascent (APGDA) method (Algorithm 1) to solve problem (4). For ease of presentation, we write problems (5), (6), (7) into the general form minimize
2X maximize w2P
PK i=1 wiFi( ) 2 kw 1/Kk 2 2,
where Fi denotes the ith individual attack loss. We show that at each iteration, APGDA takes only one-step PGD for outer minimization and one-step projected gradient ascent for inner maximization.
Outer Minimization Considering w = w(t 1) and F ( ) := P K
i=1 w (t 1) i
Fi( ) in (4), we perform one-step PGD to update at iteration t,
(t) = projX (t 1) ↵r F ( (t 1)) , (8)
where proj(·) denotes the Euclidean projection operator, i.e., projX (a) = argminx2X kx ak22 at the point a, ↵ > 0 is a given learning rate, and r denotes the first-order gradient w.r.t. . If p = 1, then the projection function becomes the clip function. In Proposition 1, we derive the solution of projX (a) under different `p norms for p 2 {0, 1, 2}. Proposition 1. Given a point a 2 Rd and a constraint set X = { |k kp  ✏, č   ĉ}, the Euclidean projection ⇤ = projX (a) has a closed-form solution when p 2 {0, 1, 2}, where the specific form is given by Appendix A.
Inner Maximization By fixing = (t) and letting (w) := P K
i=1 wiFi( (t)) 2 kw 1/Kk 2 2
in problem (4), we then perform one-step PGD (w.r.t. ) to update w,
w(t) = projP ⇣ w(t 1) + rw (w
(t 1))| {z } b
⌘ = (b µ1)+ , (9)
where > 0 is a given learning rate, rw (w) = (t) (w 1/K), and (t) := [F1( (t)), . . . , FK( (t))]T . In (9), the second equality holds due to the closed-form of projection operation onto the probabilistic simplex P [49], where (x)+ = max{0, x}, and µ is the root of the equation 1T (b µ1)+ = 1. Since 1T (b mini{bi}1 + 1/K)+ 1T1/K = 1, and 1T (b maxi{bi}1 + 1/K)+  1T1/K = 1, the root µ exists within the interval [mini{bi} 1/K,maxi{bi} 1/K] and can be found via the bisection method [8].
Convergence Analysis We remark that APGDA follows the gradient primal-dual optimization framework [37], and thus enjoys the same optimization guarantees. Theorem 1. Suppose that in problem (4) Fi( ) has L-Lipschitz continuous gradients, and X is a convex compact set. Given learning rates ↵
1 L and < 1 , then the sequence { (t),w(t)}T t=1
generated by Algorithm 1 converges to a first-order stationary point 2 in rate O 1 T .
Proof : Note that the objective function of problem (4) is strongly concave w.r.t. w with parameter , and has -Lipschitz continuous gradients. Moreover, we have kwk2  1 due to w 2 P . Using these facts and Theorem 1 in [37] or [39] completes the proof. ⇤

heading: 4 Experiments on Adversarial Exploration

text: In this section, we first evaluate the proposed min-max optimization strategy on three attack tasks. We show that our approach leads to substantial improvement compared with state-of-the-art attack methods such as average ensemble PGD [34] and EOT [3, 10, 5]. We also demonstrate the effectiveness of learnable domain weights in guiding the adversary’s exploration over multiple domains.

heading: 4.1 Experimental setup

text: We thoroughly evaluate our algorithm on MNIST and CIFAR-10. A set of diverse image classifiers (denoted from Model A to Model H) are trained, including multi-layer perceptron (MLP), All-CNNs [61], LeNet [30], LeNetV2, VGG16 [58], ResNet50 [24], Wide-ResNet [40, 75] and GoogLeNet [63]. The details about model architectures and training process are provided in Appendix D.1. Note that problem formulations (5)-(7) are applicable to both untargeted and targeted attack. Here we focus on the former setting and use C&W loss function [13, 40] with a confidence parameter  = 50. The adversarial examples are generated by 20-step PGD/APGDA unless otherwise stated (e.g., 50 steps for ensemble attacks). APGDA algorithm is relatively robust and will not be affected largely by the choices of hyperparameters (↵, , ). Apart from absolute attack success rate (ASR), we also report the relative improvement or degradationon the worse-case performance in experiments: Lift("). The details of crafting adversarial examples are available in Appendix D.2.

heading: 4.2 Ensemble Attack over Multiple Models

text:
We craft adversarial examples against an ensemble of known classifiers. Recent work [34] proposed an average ensemble PGD attack, which assumed equal importance among different models, namely, wi = 1/K in problem (5). Throughout this task, we measure the attack performance via ASRall - the attack success rate (ASR) of fooling model ensembles simultaneously. Compared to the average PGD attack, our approach results in 40.79% and 17.48% ASRall improvement averaged over different `p-norm constraints on MNIST and CIFAR-10, respectively. In what follows, we provide more detailed results and analysis.
In Table 1 and Table 3, we show that AMGDA significantly outperforms average PGD in ASRall. Taking `1-attack on MNIST as an example, our min-max attack leads to a 90.16% ASRall, which
2The stationarity is measured by the `2 norm of gradient of the objective in (4) w.r.t. ( ,w).
largely outperforms 48.17%. The reason is that Model C, D are more difficult to attack, which can be observed from their higher test accuracy on adversarial examples. As a result, although the adversarial examples crafted by assigning equal weights over multiple models are able to attack {A, B} well, they achieve a much lower ASR in {C, D}. By contrast, APGDA automatically handles the worst case {C, D} by slightly sacrificing the performance on {A, B}: 31.47% averaged ASR improvement on {C, D} versus 0.86% degradation on {A, B}. The choices of ↵, , for all experiments and more results on CIFAR-10 are provided in Appendix D.2 and Appendix E.
Effectiveness of learnable domain weights:
Figure 1 depicts the ASR of four models under average/min-max attacks as well as the distribution of domain weights during attack generation. For average PGD (Figure 1a), Model C and D are attacked insufficiently, leading to relatively low ASR and thus weak ensemble performance. By contrast, APGDA (Figure 1b) will encode the difficulty level to attack different models based on the current attack loss. It dynamically adjusts the weight wi as shown in Figure 1c. For
instance, the weight for Model D is first raised to 0.45 because D is difficult to attack initially. Then it decreases to 0.3 once Model D encounters the sufficient attack power and the corresponding attack performance is no longer improved. It is worth noticing that APGDA is highly efficient because wi converges after a small number of iterations. Figure 1c also shows wc > wd > wa > wb – indicating a decrease in model robustness for C, D, A and B, which is exactly verified by AccC > AccD > AccA > AccB in the last row of Table 1 (`1-norm). As the perturbation radius ✏ varies, we also observe that the ASR of min-max strategy is consistently better or on part with the average strategy (see Figure 2).
Comparison with stronger heuristic baselines Apart from average strategy, we compare minmax framework with stronger heuristic weighting scheme in Table 2 (MNIST) and Table 4 (CIFAR10). Specifically, with the prior knowledge of robustness of given models (C > D > A > B), we devised several heuristic baselines including: (a) wc+d: average PGD on models C and D only; (b) wa+c+d: average PGD on models A, C and D only; (c) wclip: clipped version of C&W loss (threshold = 40) to balance model weights in optimization as suggested in [56]; (d) wprior: larger weights on the more robust models, wprior = [wA, wB , wC , wD] = [0.2, 0.1, 0.4, 0.3]; (e) wstatic: the converged mean weights of min-max (APGDA) ensemble attack. For `2 (✏ = 3.0) and `1 (✏ = 0.2) attacks, wstatic = [wA, wB , wC , wD] are [0.209, 0.046, 0.495, 0.250] and [0.080, 0.076, 0.541, 0.303], respectively. Table 2 shows that our approach achieve substantial improvement over baselines consistently. Moreover, we highlight that the use of learnable w avoids supervised manual adjustment on
the heuristic weights or the choice of clipping threshold. Also, we show that even adopting converged min-max weights statically leads to a huge performance drop on attacking model ensembles, which again verifies the power of dynamically optimizing domain weights during attack generation process.

heading: 4.3 Multi-Image Universal Perturbation

text:
We evaluate APGDA in universal perturbation on MNIST and CIFAR-10, where 10,000 test images are randomly divided into equal-size groups (K images per group) for universal perturbation. We measure two types of ASR (%), ASRavg and ASRall. Here the former represents the ASR averaged over all images in all groups, and the latter signifies the ASR averaged over all groups but a successful attack is counted under a more restricted condition: images within each group must be successfully attacked simultaneously by universal perturbation. In Table 5, we compare the proposed min-max strategy with the averaging strategy on the attack performance of generated universal perturbations. APGDA always achieves higher ASRall for different values of K. When K = 5, our approach achieves 42.63% and 35.21% improvement over the averaging strategy under MNIST and CIFAR-10. The universal perturbation generated from APGDA can successfully attack ‘hard’ images (on which the average-based PGD attack fails) by self-adjusting domain weights, and thus leads to a higher ASRall.
Interpreting “image robustness” with domain weights w: The min-max universal perturbation also offers interpretability of “image robustness” by associating domain weights with image visualization. Figure 6 shows an example in which the large domain weight corresponds to the MNIST letter with clear appearance (e.g., bold letter). To empirically verify the robustness of image, we report two metrics to measure the difficulty of attacking single image: dist. (C&W `2) denotes the the minimum distortion of successfully attacking images using C&W (`2) attack; ✏min (`1) denotes the minimum perturbation magnitude for `1-PGD attack.

heading: 4.4 Robust Attack over Data Transformations

text:
EOT [5] achieves state-of-the-art performance in producing adversarial examples robust to data transformations. From (7), we could derive EOT as a special case when the weights satisfy wi = 1/K (average case). For each input sample (ori), we transform the image under a series of functions, e.g., flipping horizontally (flh) or vertically (flv), adjusting brightness (bri), performing gamma correction
(gam) and cropping (crop), and group each image with its transformed variants. Similar to universal perturbation, ASRall is reported to measure the ASR over groups of transformed images (each group is successfully attacked signifies successfully attacking an example under all transformers). In Table 7, compared to EOT, our approach leads to 9.39% averaged lift in ASRall over given models on CIFAR-10 by optimizing the weights for various transformations. We leave the the results under randomness (e.g., flipping images randomly w.p. 0.8; randomly clipping the images at specific range) in Appendix E

heading: 5 Extension: Understanding Defense over Multiple Perturbation Domains

text: In this section, we show that the min-max principle can also be used to gain more insights in generalized adversarial training (AT) from a defender’s perspective. Different from promoting robustness of adversarial examples against the worst-case attacking environment (Sec. 3), the generalized AT promotes model’s robustness against the worst-case defending environment, given by the existence of multiple `p attacks [65]. Our approach obtains better performance than prior works [65, 41] and interpretability by introducing the trainable domain weights.

heading: 5.1 Adversarial Training under Mixed Types of Adversarial Attacks

text:
Conventional AT is restricted to a single type of norm-ball constrained adversarial attack [40]. For example, AT under `1 attack yields:
minimize ✓ E(x,y)2D maximize k k1✏ ftr(✓, ;x, y), (10)
where ✓ 2 Rn denotes model parameters, denotes ✏-tolerant `1 attack, and ftr(✓, ;x, y) is the training loss under perturbed examples {(x+ , y)}. However, there possibly exist blind attacking spots across multiple types of adversarial attacks so that AT under one attack would not be strong enough against another attack [2]. Thus, an interesting question is how to generalize AT under multiple types of adversarial attacks [65]. One possible way is to use the finite-sum formulation in the inner maximization problem of (10), namely, maximize{ i2Xi} 1 K P K
i=1 ftr(✓, i;x, y), where i 2 Xi is the ith type of adversarial perturbation defined on Xi, e.g., different `p attacks.
Since we can map ‘attack type’ to ‘domain’ considered in (1), AT can be generalized against the strongest adversarial attack across K attack types in order to avoid blind attacking spots:
minimize ✓ E(x,y)2D maximize i2[K] maximize i2Xi ftr(✓, i;x, y). (11)
In Lemma 1, we show that problem (11) can be equivalently transformed into the min-max form. Lemma 1. Problem (11) is equivalent to:
minimize ✓ E(x,y)2D maximize w2P,{ i2Xi}
KX
i=1
wiftr(✓, i;x, y), (12)
where w 2 RK represent domain weights, and P has been defined in (1).
The proof of Lemma 1 is provided in Appendix B. Similar to (4), a strongly concave regularizer /2kw 1/Kk22 can be added into the inner maximization problem of (12) for boosting the stability of the learning procedure and striking a balance between the max and the average attack performance:
minimize ✓ E(x,y)2D maximize w2P,{ i2Xi} (✓,w, { i})
(✓,w, { i}) := P K i=1 wiftr(✓, i;x, y) 2 kw 1/Kk 2 2
(13)
Algorithm 2 AMPGD to solve problem (13) 1: Input: given ✓(0), w(0), (0) and K > 0. 2: for t = 1, 2, . . . , T do 3: given w(t 1) and (t 1), perform SGD to
update ✓(t)
4: given ✓(t), perform R-step PGD to update w(t) and (t) 5: end for We propose the alternating multi-step projected gradient descent (AMPGD) method (Algorithm 2) to solve problem (13). Since AMPGD also follows the min-max principles, we defer more details of this algorithm in Appendix C. We finally remark that our formulation of generalized AT under multiple perturbations covers prior work [65] as special cases ( = 0 for max case and = 1 for average case).

heading: 5.2 Generalized AT vs. Multiple `p Attacks

text:
Compared to vanilla AT, we show the generalized AT scheme produces model robust to multiple types of perturbation, thus leads to stronger “overall robustness”. We present experimental results of generalized AT following [41] to achieve simultaneous robustness to `1, `2, and `1 perturbations on the MNIST and CIFAR-10 datasets. To the best of our knowledge, MSD proposed in [41] is the state-of-the-art defense against multiple types of `p attacks. Specifically, we adopted the same architectures as [41] four layer convolutional networks on MNIST and the pre-activation version of the ResNet18 [24]. The perturbation radius ✏ for (`1, `2, `1) balls is set as (0.3, 2.0, 10) and (0.03, 0.5, 12) on MNIST and CIFAR-10 following [41]. Apart from the evaluation `p PGD attacks, we also incorporate the state-of-the-art AutoAttack [18] for a more comprehensive evaluation under mixed `p perturbations.
The adversarial accuracy results are reported (higher the better). As shown in Table 8 and 9, our approach outperforms the state-of-the-art defense MSD consistently (4⇠6% and 2% improvements on MNIST and CIFAR-10). Compared to MSD that deploys an approximate arg max operation to select the steepest-descent (worst-case) universal perturbation, we leverage the domain weights to self-adjust the strengthens of diverse `p attacks. Thus, we believe that this helps gain supplementary robustness from individual attacks.
Effectiveness of Domain Weights: Figure 3 shows the robust accuracy curves of MSD and AMPGD on MNIST. As we can see, the proposed AMPGD can quickly adjust the defense strengths to focus on more difficult adversaries - the gap of robust accuracy between three attacks is much smaller. Therefore, it achieves better results by avoiding the trade-off that biases one particular perturbation model at the cost of the others. In Figure 4, we offer deeper insights on how the domain weights work as the strengths of adversary vary. Specifically, we consider two perturbation models on MNIST: `2 and `1. During the training, we fix the ✏ for `1 attack during training as 0.2, and change the ✏ for `2 from 1.0 to 4.0. As shown in Figure 4, the domain weight w increases when the `2-attack becomes stronger i.e., ✏(`2) increases, which is consistent with min-max spirit – defending the strongest attack.

heading: 5.3 Additional Discussions

text:
More parameters to tune for min-max? Our min-max approaches (APGDA and AMPGD) introduce two more hyperparameters - and . However, our proposal performs reasonably well by choosing the learning rate ↵ same as standard PGD and using a large range of regularization coefficient 2 [0, 10]; see Fig. A5 in Appendix. For the learning rate to update domain weights, we found 1/T is usually a very good practice, where T is the total number of attack iterations.
Time complexity of inner maximization? Our proposal achieves significant improvements at a low cost of extra computation. Specifically, (1) our APGDA attack is 1.31⇥ slower than the average PGD; (2) our AMPGD defense is 1.15⇥ slower than average or max AT [65].
How efficient is the APGDA (Algorithm 1) for solving problem (4)? We remark that the minmax attack generation setup obeys the nonconvex + strongly concave optimization form. Our proposed APGDA is a single-loop algorithm, which is known to achieve a nearly optimal convergence rate for nonconvex-strongly concave min-max optimization [32, Table 1]. Furthermore, as our solution gives a natural extension from the commonly-used PGD attack algorithm by incorporating the inner maximization step (9), it is easy to implement based on existing frameworks.
Clarification on contributions: Our contribution is not to propose a new or more efficient optimization approach for solving min-max optimization problems. Instead, we focus on introducing this formulation to the attack design domain, which has not been studied systematically before. We believe this work is the first solid step to explore the power of min-max principle in the attack design and achieve superior performance on multiple attack tasks.

heading: 6 Conclusion

text:
In this paper, we revisit the strength of min-max optimization in the context of adversarial attack generation. Beyond adversarial training (AT), we show that many attack generation problems can be re-formulated in our unified min-max framework, where the maximization is taken over the probability simplex of the set of domains. Experiments show our min-max attack leads to significant improvements on three tasks. Importantly, we demonstrate the self-adjusted domain weights not only stabilize the training procedure but also provides a holistic tool to interpret the risk of different domain sources. Our min-max principle also helps understand the generalized AT against multiple adversarial attacks. Our approach results in superior performance as well as intepretability.
Broader Impacts
Our work provides a unified framework in design of adversarial examples and robust defenses. The generated adversarial examples can be used to evaluate the robustness of state-of-the-art deep learning vision systems. In spite of different kinds of adversaries, the proposed defense solves one for all by taking into account adversaries’ diversity. Our work is a beneficial supplement to building trustworthy AI systems, in particular for safety-critical AI applications, such as autonomous vehicles and camera surveillance. We do not see negative impacts of our work on its ethical aspects and future societal consequences.

heading: Acknowledgement

text: We sincerely thank the anonymous reviewers for their insightful suggestions and feedback. This work is partially supported by the NSF grant No.1910100, NSF CNS 20-46726 CAR, NSF CAREER CMMI-1750531, NSF ECCS-1609916, and the Amazon Research Award. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.

title: Adversarial Attack Generation Empowered by Min-Max Optimization


summaries: This paper studies the problem of sparse tensor PCA (a generalization of sparse PCA and tensor PCA). The main result is an algorithm that -- for the highly sparse regime in which the sparsity is at most the square root of the signal dimension -- naturally interpolates between a poly-time efficient algorithm and exponential exhaustive search. This result is complemented by lower bounds for the rather popular computational model captured by low-degree polynomials. The lower bounds match the algorithm guarantees (although for the different problem of distinguishability) in the regime of constant tensor order $p$.   The results of this paper recover several results of the literature, and provide a non-trivial extension.

summaries: # Review for "The Complexity of Sparse Tensor PCA"  This paper studies the "Sparse Tensor PCA" problem, which is a common generalization of two well-studied problems: sparse principal component analysis and tensor principal component analysis. The problem is as follows: given a "single-spike" tensor of the form  $T = \lambda \cdot x^{\otimes p} + W$  where $W$ has i.i.d. Gaussian entries, $\lambda > 0$ is the "signal strength", and $x \in R^n$ is $k$-sparse for some $k \ll n$, find $x$. (The problem can be generalized to more than one spike $x$; this is treated carefully in the paper.)  The paper contains interesting new algorithms and computational lower bounds for this problem.

summaries: The authors propose a family of algorithms for solving the sparse tensor PCA problems, which is based on smooth interpolation between a polynomial-time algorithm and exponential-time search algorithm. Improved results are achieve for sparce PCA in the lower signal/noise ratio regime in distinct sparse signal cases, compared with existing guarantees. Lower bound analysis is also provided for the proposed algorithm.

summaries: This paper focuses on the tradeoff between computational complexity and conditions for recovery in a symmetric sparse tensor estimation problem. There has been a great deal of work on related problems recently in the case of matrices (order 2 tensors) and the case of tensors (without necessarily imposing sparsity constraints). The main achievability result (Theorem 1) provides sufficient condition for single spike model in terms of the ambient dimension, the order the tensors, the degree of sparsity, the signal strength, and an integer parameter the interpolates between a ````"low complexity" algorithm  "high complexity" algorithm (essentially brute force search). Similar results of for a multiple spike model are given in Theorem 2.   Necessary conditions for a certain testing problem are considered in Theorem 3 which provides necessary conditions such that a polynomial of bounded degree can "distinguish" between a planted model (with a signal of a given strength) and a null mull of only Gaussian noise. Here the criterion for distinguishability is a certain L2 test.  While similar results have been obtained in the literature, the authors argue that their results improve upon the existing ones in a number of ways.

summaries: This paper studies the estimation of a rank-one (or more generally a low-rank) tensor $x^{\otimes p}$ ($x \in \mathbb{R}^n$ is assumed to have unit norm) given $Y = \lambda x^{\otimes p} + W$, where $\lambda > 0$ and $W$ is a Gaussian noise tensor. Here the signal vector $x$ is assumed to have only $k$ non-zero entries.  The main contribution of the paper is an algorithm that recovers with high probability the support of $x$ in time $O(n^{p+t})$ provided that $\lambda \geq O(\sqrt{t} (k/t)^{p/2})$. The number $t$ can be arbitrarily chosen between $1$ and $k$, illustrating a tradeoff between statistical constraints on the signal-to-noise ratio $\lambda$ and runtime constraints on the estimation algorithm. This generalizes to the 'tensor settings' previous results obtained about sparse PCA.  The authors also prove an information-theoretic lower bound for low-degree polynomials. More precisely, they prove that no test based on polynomial of degree at most $D$ can distinguish between the planted model $Y = \lambda x^{\otimes p} + W$ and the pure noise model $Y=W$, when $\lambda$ is smaller than some quantity depending on $D, n, k, p$. This bound generalizes previously obtained results for PCA and tensor PCA. This bound is tight for low-degree polynomials. However there is a gap with the  bound $\lambda \geq O(\sqrt{t} (k/t)^{p/2})$ needed for the algorithm that recovers the support.

abstractText: We study the problem of sparse tensor principal component analysis: given a tensor Y = W + λx⊗p with W ∈ ⊗R having i.i.d. Gaussian entries, the goal is to recover the k-sparse unit vector x ∈ R. The model captures both sparse PCA (in its Wigner form) and tensor PCA. For the highly sparse regime of k ≤ √ n, we present a family of algorithms that smoothly interpolates between a simple polynomial-time algorithm and the exponential-time exhaustive search algorithm. For any 1 ≤ t ≤ k, our algorithms recovers the sparse vector for signal-tonoise ratio λ ≥ Õ( √ t · (k/t)) in time Õ(n), capturing the state-of-the-art guarantees for the matrix settings (in both the polynomial-time and sub-exponential time regimes). Our results naturally extend to the case of r distinct k-sparse signals with disjoint supports, with guarantees that are independent of the number of spikes. Even in the restricted case of sparse PCA, known algorithms only recover the sparse vectors for λ ≥ Õ(k ·r) while our algorithms require λ ≥ Õ(k). Finally, by analyzing the low-degree likelihood ratio, we complement these algorithmic results with rigorous evidence illustrating the trade-offs between signal-to-noise ratio and running time. This lower bound captures the known lower bounds for both sparse PCA and tensor PCA. In this general model, we observe a more intricate three-way trade-off between the number of samples n, the sparsity k, and the tensor power p.

authors:
Gerard Ben Arous
Song Mei
Andrea Montanari
Mihai Nica

title: The landscape of the spiked tensor model

venue: Communications on Pure and Applied Mathematics,

authors:
Arash A Amini
Martin J Wainwright

title: High-dimensional analysis of semidefinite relaxations for sparse principal components

venue: IEEE International Symposium on Information Theory,

authors:
Matthew Brennan
Guy Bresler

title: Reducibility and statistical-computational gaps from secret leakage

venue: In Conference on Learning Theory, COLT 2020,

authors:
Joachim M Buhmann
Luca Corinzia
Paolo Penna
Wojciech Szpankowski

title: Recovery of a Planted k-Densest Sub-Hypergraph, 2020

venue: Available at: https: //www.cs.purdue.edu/homes/spa/papers/isit20-clique.pdf

authors:
Vijay Bhattiprolu
Venkatesan Guruswami
Euiwoong Lee

title: Sum-of-squares certificates for maxima of random tensors on the sphere

venue: arXiv preprint arXiv:1605.00903,

authors:
Boaz Barak
Samuel Hopkins
Jonathan Kelner
Pravesh K Kothari
Ankur Moitra
Aaron Potechin

title: A nearly tight sum-of-squares lower bound for the planted clique problem

venue: SIAM Journal on Computing,

authors:
Afonso S. Bandeira
Dmitriy Kunisky
Alexander S. Wein

title: Computational hardness of certifying bounds on constrained PCA problems

venue: In 11th Innovations in Theoretical Computer Science Conference,

authors:
Quentin Berthet
Philippe Rigollet

title: Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

venue: In Conference on Learning Theory, pages 1046–1066,

title: OPTIMAL DETECTION OF SPARSE PRINCIPAL COMPONENTS IN HIGH DIMENSION

venue: The Annals of Statistics,

title: Locally asymptotically normal families

venue: Univ. California Publ. Statist.,

authors:
T Tony Cai
Zongming Ma
Yihong Wu

title: SPARSE PCA: OPTIMAL RATES AND ADAPTIVE ESTIMATION

authors:
Luca Corinzia
Paolo Penna
Luca Mondada
Joachim M Buhmann

title: Exact Recovery for a Family of Community-Detection Generative Models

venue: IEEE International Symposium on Information Theory (ISIT),

authors:
Luca Corinzia
Paolo Penna
Wojciech Szpankowski
Joachim M. Buhmann

title: Statistical and computational thresholds for the planted k-densest

venue: sub-hypergraph problem,

authors:
Alexandre d’Aspremont
Laurent El Ghaoui
Michael I. Jordan
Gert R.G. Lanckriet

title: A direct formulation for sparse PCA using semidefinite programming

venue: SIAM Review,

authors:
Tommaso d’Orsi
Pravesh K. Kothari
Gleb Novikov
David Steurer

title: Sparse PCA: Algorithms, Adversarial Perturbations and Certificates, 2020

venue: To appear in FOCS 2020

authors:
Yunzi Ding
Dmitriy Kunisky
Alexander S Wein
Afonso S Bandeira

title: Subexponential-Time Algorithms for Sparse PCA

venue: arXiv preprint arXiv:1907.11635,

authors:
Yash Deshpande
Andrea Montanari

title: Sparse PCA via Covariance Thresholding

venue: The Journal of Machine Learning Research,

title: Lecture Notes for Statistics 311/Electrical engineering 377, 2016

authors:
Delphine Féral
Sandrine Péché

title: The Largest Eigenvalue of Rank One Deformation of Large Wigner Matrices

venue: Communications in mathematical physics,

authors:
Samuel B Hopkins
Pravesh K Kothari
Aaron Potechin
Prasad Raghavendra
Tselil Schramm
David Steurer

title: The power of sum-of-squares for detecting hidden structures

venue: IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS),

authors:
Christopher J Hillar
Lek-Heng Lim

title: Most tensor problems are np-hard

venue: Journal of the ACM (JACM),

title: STATISTICAL INFERENCE AND THE SUM OF SQUARES METHOD

venue: PhD thesis, Cornell University,

authors:
Samuel B Hopkins
David Steurer

title: Efficient Bayesian estimation from few samples: community detection and related problems

authors:
Samuel B Hopkins
Jonathan Shi
David Steurer

title: Tensor principal component analysis via sum-of-squares proofs

venue: In Conference on Learning Theory,

authors:
Samuel B Hopkins
Tselil Schramm
Jonathan Shi

title: A robust spectral algorithm for overcomplete tensor decomposition

authors:
Guy Holtzman
Adam Soffer
Dan Vilenchik

title: A greedy anytime algorithm for sparse PCA

authors:
Justin Holmgren
Alexander S Wein

title: Counterexamples to the low-degree conjecture

venue: arXiv preprint arXiv:2004.08454,

authors:
Iain M Johnstone
Arthur Yu Lu

title: On Consistency and Sparsity for Principal Components Analysis in High Dimensions

venue: Journal of the American Statistical Association,

authors:
Dmitriy Kunisky
Alexander S Wein
Afonso S Bandeira

title: Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

venue: arXiv preprint arXiv:1907.11636,

authors:
Yuetian Luo
Anru Zhang

title: Tensor clustering with planted structures: Statistical optimality and computational limits

authors:
Andrea Montanari
Emile Richard

title: A statistical model for tensor PCA

venue: In Advances in Neural Information Processing Systems, pages 2897–2905,

authors:
Tengyu Ma
Jonathan Shi
David Steurer

title: Polynomial-time tensor decompositions with sum-of-squares

venue: IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS),

authors:
J. Neyman
E.S. Pearson

title: On the problem of the most efficient tests of statistical hypotheses

venue: Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character,

authors:
Jonathan Niles-Weed
Ilias Zadik

title: The all-or-nothing phenomenon in sparse tensor pca

venue: Advances in Neural Information Processing Systems,

title: The all-or-nothing phenomenon in sparse tensor PCA

venue: In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems

title: Analysis of boolean functions

authors:
Amelia Perry
Alexander S. Wein
Afonso S. Bandeira

title: Statistical limits of spiked tensor models

authors:
Amelia Perry
Alexander S Wein
Afonso S Bandeira

venue: In Annales de l’Institut Henri Poincaré, Probabilités et Statistiques,

authors:
Jonathan Scarlett
Volkan Cevher

title: An Introductory Guide to Fano’s Inequality with Applications in Statistical Estimation

venue: arXiv preprint arXiv:1901.00555,

authors:
Tselil Schramm
David Steurer

title: Fast and robust tensor decomposition with applications to dictionary learning

venue: arXiv preprint arXiv:1706.08672,

title: Topics in random matrix theory, volume 132

venue: American Mathematical Soc.,

title: Metric entropy analogues of sum set theory, 2014

title: An Introduction to Matrix Concentration Inequalities

venue: arXiv preprint arXiv:1501.01571,

authors:
Ryota Tomioka
Taiji Suzuki

title: Spectral norm of random tensors

venue: arXiv preprint arXiv:1407.1870,

title: High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47

text:
√ n,
we present a family of algorithms that smoothly interpolates between a simple polynomial-time algorithm and the exponential-time exhaustive search algorithm. For any 1 ≤ t ≤ k, our algorithms recovers the sparse vector for signal-tonoise ratio λ ≥ Õ( √ t · (k/t)p/2) in time Õ(np+t), capturing the state-of-the-art guarantees for the matrix settings (in both the polynomial-time and sub-exponential time regimes). Our results naturally extend to the case of r distinct k-sparse signals with disjoint supports, with guarantees that are independent of the number of spikes. Even in the restricted case of sparse PCA, known algorithms only recover the sparse vectors for λ ≥ Õ(k ·r) while our algorithms require λ ≥ Õ(k). Finally, by analyzing the low-degree likelihood ratio, we complement these algorithmic results with rigorous evidence illustrating the trade-offs between signal-to-noise ratio and running time. This lower bound captures the known lower bounds for both sparse PCA and tensor PCA. In this general model, we observe a more intricate three-way trade-off between the number of samples n, the sparsity k, and the tensor power p.

heading: 1 Introduction

text:
Sparse tensor principal component analysis is a statistical primitive generalizing both sparse PCA2 and tensor PCA3. We are given multi-linear measurements in the form of a tensor
Y = W + λx⊗p ∈ ⊗pRn (SSTM) for a Gaussian noise tensorW ∈ ⊗pRn containing i.i.d. N(0, 1) entries4 and signal-to-noise ratio λ > 0. Our goal is to estimate the “structured” unit vector x ∈ Rn. The structure we enforce on x is sparsity: |supp(x)| ≤ k. The model can be extended to include multiple spikes in a natural way: Y = W + ∑r q=1 λqx ⊗p (q), and even general order-p tensors: Y = W + ∑r q=1 λqX(q) for X(q) = x(q,1) ⊗ · · · ⊗ x(q,p) ∈ ⊗pRn. In this introduction, we focus on the simplest single spike setting of SSTM.
It is easy to see that sparse PCA corresponds to the setting with tensor order p = 2. On the other hand, tensor PCA is captured by effectively removing the sparsity constraint: |supp(x)| ≤ n. In ∗Part of the work was done while the author was in ETH Zürich. 2Often in the literature, the terms sparse PCA and spiked covariance model refer to the sparse spiked Wishart model. However, here we consider the sparse spiked Wigner matrix model. 3Tensor PCA is also known as the spiked Wigner tensor model, or simply the spiked tensor model. 4Throughout the paper, we will write random variables in boldface.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
recent years, two parallel lines of work focused respectively on sparse PCA [JL09, AW08, BR13a, DM16, HKP+17, DKWB19, HSV20, dKNS20] and tensor PCA [MR14, HSS15, MSS16, HKP+17, KWB19, AMMN19], however no result captures both settings. The appeal of the sparse spiked tensor model (henceforth SSTM) is that it allows one to study the computational and statistical aspects of these other fundamental statistical primitives in a unified framework, understanding the computational phenomena at play from a more general perspective.
In this work, we investigate SSTM from both algorithmic and computational hardness perspectives. Our algorithm improves over known tensor algorithms whenever the signal vector is highly sparse. We also present a lower bound against low-degree polynomials which extends the known lower bounds for both sparse PCA and tensor PCA, leading to a more intricate understanding of how all three parameters (n, k and p) interact.

heading: 1.1 Related work

text: Disregarding computational efficiency, it is easy to see that optimal statistical guarantees can be achieved with a simple exhaustive search (corresponding to the maximum likelihood estimator): find a k-sparse unit vector maximizing 〈Y , x⊗p〉. This algorithm returns a k-sparse unit vector x̂ achieving constant squared correlation5 with the signal x as soon as λ & √ k · log(np/k). That is, whenever λ & max‖x‖=1,‖x‖0=k〈W ,x ⊗p〉. Unfortunately, this approach runs in time exponential in k and takes super-polynomial time when p . k.6 As such, we assume p ≤ k from now on. Taking into account computational aspects, the picture changes. A good starting point to draw intuition for SSTM is the literature on sparse PCA and tensor PCA. We briefly outline some known results here. To simplify the discussion, we hide absolute constant multiplicative factors using O(·), Ω(·), ., and &, and hide multiplicative factors logarithmic in n using Õ(·).

heading: 1.1.1 Sparse PCA (Wigner noise)

text:
Sparse PCA with Wigner noise exhibits a sharp phase transition in the top eigenvalue of Y for λ ≥ √ n [FP07]. In this strong signal regime, the top eigenvector7 v of Y correlates8 with x with high probability, thus the following spectral method achieves the same guarantees as the exhaustive search suggested above: compute a leading eigenvector of Y and restrict it to the top k largest entries in absolute value. Conversely, when λ < √ n, the top eigenvector of Y does not correlate with the signal x. In this weak signal regime, [JL09] proposed a simple algorithm known as diagonal thresholding: compute the top eigenvector of the principal submatrix defined by the k largest diagonal entries of Y . This algorithm recovers the sparse direction when λ & Õ(k), thus requiring almost an additional √ k factor when compared to inefficient algorithms. More refined polynomial-time algorithms (low-degree polynomials [dKNS20], covariance thresholding [DM16] and the basic SDP relaxation [dGJL07, dKNS20]) only improve over diagonal thresholding by a logarithmic factor in the regime n1−o(1) . k2 . n. Interestingly, multiple results suggest that this information-computation gap is inherent to the sparse PCA problem [BR13a, BR13b, DKWB19, dKNS20]. Subexponential time algorithms and lower bounds have also been shown. For instance, [DKWB19, HSV20] presented smooth trade-offs between signal strength and running time.9
5One could also aim to find a unit vector with correlation approaching one or, in the restricted setting of x ∈ {0,±1/ √ k}, aim to recover the support of x. At the coarseness of our discussion here, these goals could be considered mostly equivalent. 6Note that the problem input is of size np. So when p & k, exhaustive search takes nO(p) time which is polynomial in np. Thus, the interesting parameter regimes occur when p . k. 7By “top eigenvector” or “leading eigenvector”, we mean the eigenvector corresponding to “largest (in absolute value) eigenvalue”. 8More precisely, the vector consisting of the k largest (in absolute value) entries of v. 9Both works studied the single spike matrix setting. [HSV20] only considers the Wishart noise model and thus its guarantees cannot be compared to ours. [DKWB19] studied both the Wishart and Wigner noise models. In the Wishart noise model setting, both [HSV20] and [DKWB19] observe the same tradeoff between running time and signal-to-noise ratio. In the Wigner noise model setting, our algorithm and the algorithm of [DKWB19] offer the same smooth-trade off between running time and signal strength, up to universal constants.

heading: 1.1.2 Tensor PCA

text: In tensor settings, computing max‖x‖=1〈Y , x⊗p〉 is NP-hard already for p = 3 [HL13]. For even tensor powers p, one can unfold the tensor Y into a np/2-by-np/2 matrix and solve for the top eigenvector [MR14]. However, this approach is sub-optimal for odd tensor powers. For general tensor powers p, a successful strategy to tackle tensor PCA has been the use of semidefinite programming [HSS15, BGL16, HSS19]. Spectral algorithms inspired by the insight of these convex relaxations have also been successfully applied to the problem [SS17]. These methods succeed in recovering the single-spike x when λ & Õ ( np/4 ) , thus exhibiting a large gap when compared to exhaustive search algorithms. Matching lower bounds have been shown for constant degrees in the Sum-of-Squares hierarchy [BGL16, HKP+17] and through average case reductions [BB20].

heading: 1.1.3 Sparsity-exploiting algorithms and tensor algorithms

text:
It is natural to ask how do the characteristics of sparse PCA and tensor PCA extend to the more general setting of SSTM. In particular, there are two main observations to be made. The first observation concerns the sharp computational transition that we see for k . √ n in sparse PCA. In these highly sparse settings, the top eigenvector of Y does not correlate with the signal x and so algorithms primarily based on spectral methods fail to recover it. Indeed, the best known guarantees are achieved through algorithms that crucially exploit the sparsity of the hidden signal. These algorithms require the signal strength to satisfy λ ≥ Õ( √ k), with only logarithmic dependency on the ambient dimension. To exemplify this to an extreme, notice how the following algorithm can recover the support of xxT with the same guarantees as diagonal thresholding, essentially disregarding the matrix structure of the data: zero all but the k2 largest (in absolute value) entries of Y . A natural question to ask is whether a similar phenomenon may happen for higher order tensors. In the highly sparse settings where k . √ n, can we obtain better algorithms exploiting the sparsity of the hidden vector? Recently, a partial answer appeared in [LZ20] with a polynomial time algorithm recovering the hidden signal for λ ≥ Õ(p · kp/2), albeit with suboptimal dependency on the tensor order p. The second observation concerns the computational-statistical gap in the spiked tensor model. As p grows, the gap between efficient algorithms and exhaustive search widens with the polynomial time algorithms requiring signal strength λ ≥ Õ ( np/4 ) while exhaustive search succeeds when λ ≥ Õ( √ n) [MR14]. The question here is: how strong is the dependency on p for efficient algorithms in sparse signal settings?
In this work, we investigate these questions in the high order tensors regime p ∈ ω(1). We present a family of algorithms with a smooth trade-off between running time and signal-to-noise ratio. Even restricting to polynomial-time settings, our algorithms improve over previous results. Furthermore, through the lens of low-degree polynomials, we provide rigorous evidence of an exponential gap in the tensor order p between algorithms and lower bounds. Remark. The planted sparse densest sub-hypergraph model [CPMB19, BCPS20, CPSB20] is closely related to SSTM. We discuss this model in Appendix E.

heading: 1.2 Results

heading: 1.2.1 Single spike setting

text:
Consider first the restricted, but representative, case where the planted signal is a (k,A)-sparse unit vector with k non-zero entries having magnitudes in the range [ 1
A √ k , A√ k
] for some constant A ≥ 1.
We say that the signal is flat when A = 1 and approximately flat when A ≥ 1. Our first result is a limited brute force algorithm – informally, an algorithm that smoothly interpolates between some brute force approach and some “simple” polynomial time algorithm – that exactly recovers the signal support of the planted signal10. Theorem 1 (Algorithm for single spike sparse tensor PCA, Informal). Let A ≥ 1 be a constant. Consider the observation tensor
Y = W + λx⊗p
10A similar algorithm was analyzed by [DKWB19] for the special case of p = 2 and r = 1.
where the additive noise tensorW ∈ ⊗pRn contains i.i.d. N(0, 1) entries and the signal x ∈ Rn is a (k,A)-sparse unit vector with signal strength λ > 0. Let 1 ≤ t ≤ k be an integer. Suppose that
λ & √ t ( 2A2k
t
)p lnn .
Then, there exists an algorithm that runs in O(pnp+t) time and, with probability 0.99, outputs the support of x.
Let’s first consider Theorem 1 in its simplest setting where A = 1 and t is a fixed constant. For k . √ n, the theorem succeed when λ ≥ Õ(kp/2), thus improving over the guarantees of known
tensor PCA methods which require λ ≥ Õ(np/4). In addition, since support recovery is exact, one can obtain a good estimate11 of the planted signal by running any known tensor PCA algorithm on the subtensor corresponding to its support. Indeed, the resulting subtensor will be of significantly smaller dimension and the requirement needed on the signal strength by single-spike tensor PCA algorithms are weaker than the requirement we impose on λ (see Remark 9 for details). As a result, our algorithm recovers the guarantees of diagonal thresholding in the matrix (p = 2) setting. Our polynomial-time algorithm also improves over the result of [LZ20], which required λ & √ pkp log n, by removing the polynomial dependency of the tensor order p in the signal strength λ.12
Consider now the limited brute force parameter t. From the introductory exposition, we know that one can obtain a statistically optimal algorithm by performing a brute force search over the space of k-sparse flat vectors in Rn. The limited brute force algorithm is a natural extension that takes into account computational constraints by searching over the smaller set of t-sparse flat vectors, for 1 ≤ t ≤ k, to maximize 〈Y , u⊗p〉. The parametric nature of the algorithm captures both the brute force search algorithm (when t = k) and the idea of diagonal thresholding (when t = 1 and p = 2). As long as t ≤ k, using a larger t represents a direct trade-off between running time and the signal-to-noise ratio. Extending the result to approximately flat vectors, the dependency on A in the term ( 2A2 )p can be removed by increasing the computational budget to some value t′ ≥ 2A2t.

heading: 1.2.2 Multiple spikes

text:
Theorem 2 (Algorithm for multi-spike sparse tensor PCA, Informal). Let A ≥ 1 be a constant. Consider the observation tensor
Y = W + r∑ q=1 λqx ⊗p (q)
where the additive noise tensor W ∈ ⊗pRn contains i.i.d. N(0, 1) entries and the signals x(1), . . . , x(r) ∈ Rn are (k,A)-sparse unit vectors with disjoint supports and corresponding signal strengths λ1 ≥ . . . ≥ λr > 0. Let 1 ≤ t ≤ k be an integer and 0 < ≤ 1/2. Suppose that
λr & 1 · √ t ( 2A2k
t
)p lnn and λr & A2p · (2 )p−1 · λ1 .
Then, there exists an algorithm that runs in O(rpnp+t) time and, with probability 0.99, outputs the individual signal supports of x(π(1)), . . . , x(π(r)) for some unknown bijection π : [r]→ [r].
Theorem 2 requires two assumptions on the signals: (1) signals have disjoint support; (2) there is a bounded signal strength gap of λr & A2p · (2 )p−1 · λ1. In the context of sparse PCA, algorithms that recover multiple spikes (e.g. [JL09, DM16]) only require the sparse vectors to be orthogonal. However, their guarantees are of the form λr ≥ Õ
(∣∣∣⋃q∈[r] supp (x(q))∣∣∣). That is, when the r signals have disjoint supports, they require the smallest signal to satisfy λr ≥ Õ (k · r). In comparison, already for constant t, Theorem 2 successfully recovers the supports when λr ≥ Õ(k),
11Recovery is up to a global sign flip since 〈u, v〉p = 〈u,−v〉p for even tensor powers p. 12The result of [LZ20] extends to the settings where Y = W + λX for an approximately flat tensor
X ∈ ⊗pRn. Both Theorem 1 and Theorem 2 can also be extended to these settings (see Appendix B.2).
thus removing the dependency on the number of signals and improving the bound by a 1/r factor13. Meanwhile, the bounded signal strength gap assumption is a common identifiability assumption (e.g. see [CMW13, DM16]). We remark that Theorem 2 provides a tradeoff between this signal strength gap assumption and the signal strengths: we can recover the supports with a smaller gap if the signal strengths are increased proportionally – increasing λr by a multiplicative factor α enables the algorithm to succeed with gap that is smaller by a multiplicative factor of 1/α. As an immediate consequence, we also obtain a tradeoff between gap assumption and running time: every time we double t (while ensuring 1 ≤ t ≤ k), λr increases by a factor of (1/ √ 2)p−1 and thus the algorithm can succeed with a smaller gap. Finally, as in the single spike case, the exact support recovery allow us to obtain good estimate of each signal by running known tensor PCA algorithms.
Remark We remark that these results can be extended to the general tensor settings
Y = W + r∑ q=1 λqX(q)
where for q ∈ [r], X(q) = x(q,1) ⊗ · · · ⊗ x(q,p) ∈ ⊗pRn in a natural way. See Appendix B.2.

heading: 1.2.3 An exponential gap between lower bounds and algorithms

text:
SSTM generalizes both sparse PCA and tensor PCA. Hence, a tight hardness result for the model is interesting as it may combine and generalize the known bounds for these special cases. Here, we give a lower bound for the restricted computational model captured by low-degree polynomials. Originally developed in the context of the sum of squares hierarchy, this computational model appears to accurately predict the current best-known guarantees for problems such as sparse PCA, tensor PCA, community detection, and planted clique (e.g. see [HS17, HKP+17, Hop18, BHK+19, DKWB19, KWB19, dKNS20]).
Theorem 3 (Lower bound for low-degree polynomials, Informal). Let 1 ≤ D ≤ 2n/p and ν be the distribution of Z ∈ ⊗pRn with i.i.d. entries from N(0, 1). Then, there exists a distribution µ over tensors Y ∈ ⊗pRn of the form
Y = W + λx⊗p
where W ∈ ⊗pRn is a noise tensor with i.i.d. N(0, 1) entries, the marginal distribution of x is supported on vectors with entries { ±1/ √ k, 0 }n
, and x and W are distributionally independent, such that whenever
λ .
√ D
2p min
{( n
pD
)p/4 , ( k
pD
( 1 + ∣∣∣∣ln(npDek2 )∣∣∣∣))p/2 } ,
µ is indistinguishable14 from ν with respect to all polynomials of degree at most D.
Theorem 3 states that for certain values of λ, low-degree polynomials cannot be used to distinguish between the distribution of Y andW as typical values of low-degree polynomials are the same (up to a vanishing difference) under both distributions. The theorem captures known results in both sparse and tensor PCA settings. When p = 2, our bound reduces to λ . min {√ n, k√
D
( 1 + ∣∣ln ( 2nDek2 )∣∣)}, matching known low-degree bounds of [DKWB19] in the sparse PCA setting. Meanwhile, in the
tensor PCA settings (p ≥ 2, k = n), Theorem 3 implies a bound of the form λ . √ D ( n pD )p/4 , thus recovering the results of [KWB19].
13It is an intriguing question whether an improvement of 1/r can be achieved in the more general settings of orthogonal spikes. Our approach relies on the signals having disjoint support and we expect it to not be generalizable to orthogonal signals. This can be noticed in the simplest settings with brute-force parameter t = 1 and p = 2 where the criteria of Algorithm 3 for finding an entry of a signal vector is to look at the diagonal entries of the data matrix. In this case, the algorithm may be fooled since the largest diagonal entry can depend on more than one spike. Nevertheless, we are unaware of any fundamental barrier suggesting that such guarantees are computationally hard to achieve.
14In the sense that for any low-degree polynomial p(Y ) we have Eµp(Y )−Eνp(Y )√ Vp(Y ) ∈ o(1). See Appendix A.4.2.
For constant power p and k . √ n, our lower bound suggests that no estimator captured by polynomials of degree D . t log n can improve over our algorithmic guarantees by more than a logarithmic factor. However, for p ∈ ω(1), an exponential gap appears between the bounds of Theorem 3 and state-of-the-art algorithms (both in the sparse settings as well as in the dense settings).15 As a concrete example, let us consider the setting where p = n0.1 < k. The polynomial time algorithm of Theorem 1 requires λ ≥ Õ(kp/2) while according to Theorem 3 it may be enough to have λ ≥ Õ ( k/n0.1 )p/2 . Similarly, for k & √ np, known tensor algorithms recovers the signal for
λ ≥ Õ(np/4) while our lower bound only rules out algorithms for λ ≤ Õ ( n0.9·p/4 ) .
Surprisingly, for the distinguishing problem considered in Theorem 3, these bounds appear to be tight. For a wide range of parameters (in both the dense and sparse settings) there exists polynomial time algorithms that can distinguish the distributions ν and µ right at the threshold considered in Theorem 3 (see Appendix C). It remains a fascinating open question whether sharper recovering algorithms can be designed or stronger lower bounds are required.
Finally, we would like to highlight that this non-trivial dependency on p is a purely computational phenomenon as it does not appear in information-theoretic bounds (see Appendix D).
Remark Note that Theorem 3 is not in itself a lower bound for the recovery problem. However, any algorithm which obtains a good estimation of the signal vector x for signal strength λ ≥ √ k log n can be used to design a probabilistic algorithm which solve the distinguishing problem for signal strength Op(λ). Let us elaborate. Consider an algorithm that given Y = W + λx⊗p outputs a vector x̂ such that |〈x̂, x〉| ≥ 0.9. With high probability, max|z|2=1,|z|0=k |〈W , z ⊗p〉| ≤ Õ( √ k) and thus
|〈Y , x̂⊗p〉| ≥ λ · (0.9)p − Õ( √ k). Therefore, one can solve the distinguishing problem as follows: output “planted” if |〈Y , x̂⊗p〉| & √ k log n and “null” otherwise.

heading: 1.3 Notation and outline of paper

text:
We write random variables in boldface and the set {1, . . . , n} as [n]. We hide absolute constant multiplicative factors and multiplicative factors logarithmic in n using standard notations: O(·), Ω(·), ., &, and Õ(·). We denote by e1, . . . , en ∈ Rn the standard basis vectors. For x ∈ Rn, we use supp(x) ⊆ [n] to denote the set of support coordinates. We say that x is a (k,A)-sparse vector if k ∈ [n], constant A ≥ 1, |supp(x)| = k, and 1
A √ k ≤ |x`| ≤ A√k for ` ∈ supp(x). When A = 1, we
say that x is a k-sparse flat vector and may omit the parameter A. For general A ≥ 1, we say that x is approximately flat. For an integer t ≥ 1, we define Ut = { u ∈ { − 1√
t , 0, 1√ t
}n : |supp(u)| = t } as the set of t-sparse flat vectors. For a tensor T ∈ ⊗pRn and a vector u ∈ Rn, their inner product is defined as 〈T, u⊗p〉 =
∑ i1,...,ip∈[n] Ti1,...,ipui1 . . . uip .
The rest of the paper is organized as follows: In Section 2, we introduce the main ideas behind Theorem 1 and Theorem 2. In Section 3, we flesh out some concrete unresolved research questions. Appendix A contains preliminary notions. We formally prove Theorem 1 and Theorem 2 in Appendix B. The lower bound Theorem 3 is given in Appendix C. We present an information theoretic bound in Appendix D. Appendix E discusses the planted sparse densest sub-hypergraph model. Finally, Appendix F contains any deferred technical proofs required throughout the paper.

heading: 2 Recovering signal supports via limited brute force searches

text:
We describe here the main ideas behind our limited brute force algorithm. We consider the model
Model 4 (Sparse spiked tensor model). For A ≥ 1, r ≥ 1, k ≤ n we observe a tensor of the form
Y = W + r∑ q=1 λqx ⊗p (q) ∈ ⊗ pRn
15In particular, in the sparse settings k ≤ √np, the p−p/2 factor could not be seen in the restricted case of sparse PCA (as this factor is a constant when p = 2).
where W ∈ ⊗pRn is a noise tensor with i.i.d. N(0, 1) entries, λ1 ≥ . . . ≥ λr > 0 are the signal strengths, and x(1), . . . , x(r) are k-sparse flat unit length signal vectors.
We first look at the simplest setting of a single flat signal (i.e. A = 1 and r = 1). Then, we explain how to extend the analysis to multiple flat signals. For a cleaner discussion, we assume here that all the non-zero entries of the sparse vector x and vectors in the set Ut have positive sign. Our techniques also easily extend to approximately flat vectors (where A ≥ 1) and general signal tensors x(1) ⊗ · · · ⊗ x(p) ∈ ⊗pRn. We provide details for these extensions in Appendix B.

heading: 2.1 Single flat signal

text:
Limited-brute force As already mentioned in the introduction, a brute force search over Uk for the vector maximizing 〈Y , u⊗p〉 returns the signal vector x (up to a global sign flip) with high probability whenever λ & √ k log n. This algorithm provides provably optimal guarantees but requires exponential time (see Appendix D for an information-theoretic lower bound). The idea of a limited brute force search is to search over a smaller set Ut (1 ≤ t ≤ k) instead, and use the maximizer v∗ to determine the signal support supp (x). The hope is that for a sufficiently large signal-to-noise ratio, this t-sparse vector v∗ will still be non-trivially correlated with the hidden vector x. Indeed as t grows, the requirement on λ decreases towards the information-theoretic bound, at the expense of increased running time.
As a concrete example, consider the matrix settings (p = 2). It is easy to generalize the classic diagonal thresholding algorithm ([JL09]) into a limited brute-force algorithm. Recall that diagonal thresholding identifies the support of x by picking the indices of the largest k diagonal entries of Y . In other words, the algorithm simply computes 〈Y , e⊗2i 〉 for all i ∈ [n] and returns the largest k indices. From this perspective, the algorithm can be naturally extended to t > 1 by computing the( k t ) vectors u ∈ Ut maximizing 〈Y , u⊗2〉 and reconstructing the signal from them. For t = k, the algorithm corresponds to exhaustive search.
With this intuition in mind, we now introduce our family of algorithms, heavily inspired16 by [DKWB19]. We first apply a preprocessing step to obtain two independent copies of the data.
Algorithm 1 Preprocessing Input: Y . Sample a Gaussian tensor Z ∈ ⊗pRn where each entry is an i.i.d. standard Gaussian N(0, 1). Return two independent copies Y (1) and Y (2) of Y as follows:
Y (1) = 1√ 2 (Y +Z) and Y (2) = 1√ 2 (Y −Z)
Algorithm 1 effectively creates two independent copies of the observation tensor Y . To handle the noise variance, the signal-to-noise ratio is only decreased by the constant factor 1/ √ 2. For simplicity, we will ignore this constant factor in the remainder of the section.
Algorithm 2 Single spike limited brute force Input: k, t and Y (1),Y (2) obtained from Algorithm 1. Compute v∗ := argmaxu∈Ut〈Y
(1), u⊗p〉. Compute the vector α ∈ Rn with entries α` := 〈Y (2), v⊗p−1∗ ⊗ e`〉 for every ` ∈ [n]. Return the indices of the largest k entries of α.
16The algorithm in [DKWB19] is a specialization of ours (with comparable guarantees) in the simplest setting of p = 2 and a single spike. However, looking at [DKWB19], it is a priori unclear how to generalize the result to the settings of our interest. This is especially true in the tensor settings (p ≥ 3) with multiple spikes, where signals may interfere with each other.
The signal support recovery process outlined in Algorithm 2 has two phases. In the first phase, we search over Ut to obtain a vector v∗ that is correlated with the signal x. In the second phase, we use v∗ to identify supp(x). The correctness of the algorithm follows from these two claims:
(i) The t-sparse maximizer v∗ shares a large fraction of its support coordinates with signal x.
(ii) The k largest entries of α belong to the support supp(x) of signal x.
Crucial to our analysis is the following standard concentration bound on Gaussian tensors. We directly use Lemma 5 in our exposition here, and formally prove a more general form in Appendix F.1.
Lemma 5. Let p ≤ n, t > 0 be an integer, andW ∈ ⊗pRn be a tensor with i.i.d. N(0, 1) entries. Then, with high probability, for any u ∈ Ut,
〈W ,u⊗p〉 . √ t log n .
For some constant 0 < ≤ 1/2, suppose that
λ & 1
· (1− )p−1 ·
√ t ( k
t
)p log n . (1)
For any u ∈ Ut with support supp(u) ⊆ supp(x), we have
〈Y (1), u⊗p〉 = λ〈x, u〉p + 〈W (1), u⊗p〉 ≥ λ · ( t
k
) p 2 −O (√ t log n ) .
On the other hand, any u ∈ Ut with support satisfying |supp(u) ∩ supp(x)| ≤ (1− ) · t has small correlation with Y (1) in the sense that
〈Y (1), u⊗p〉 = λ〈x, u〉p + 〈W (1), u⊗p〉 ≤ λ · (1− )p · ( t
k
) p 2 +O (√ t log n ) .
By Eq. (1), with high probability, v∗ will have at least a fraction (1− ) of its support contained in supp(x), yielding the first claim. Observe that v∗ does not completely overlap with x. A priori, this might seem to be an issue. However, it turns out that we can still use v∗ to exactly reconstruct the support of x. Indeed, for all ` ∈ supp(x),
α` = λ · x` · 〈x,v∗〉p−1 + 〈W (2), v⊗p−1∗ ⊗ e`〉
≥ λ · (1− ) p−1
√ k
· ( t
k
) p−1 2
+ 〈W (2), v⊗p−1∗ ⊗ e`〉
& 1 · √
log n+ 〈W (2), v⊗p−1∗ ⊗ e`〉 .
Now, by independence ofW (2) and v∗, 〈W (2), v⊗p−1∗ ⊗ e`〉 behaves like a standard Gaussian. Thus, with high probability, ∣∣∣〈W (2), v⊗p−1∗ ⊗ e`〉∣∣∣ . √log n and α` & √log n. Conversely, if ` is not in the support of the signal, then α` . √ log n. So, the vector α acts as indicator of the support of x!
Remark 6. In its simplest form of t = 1, Algorithm 2 does not exploit the tensor structure of the data: it performs entry-wise search for the largest (in magnitude) over a subset of Y . However, this is no longer true as t grows. For t = k, the algorithm computes the k-sparse flat unit vector u maximizing 〈Y (1), u⊗p〉.

heading: 2.2 Multiple flat signals with disjoint signal supports

text:
Consider now the setting with r > 1 spikes. Recall that we assumed the vectors x(1), . . . , x(r) to have non-intersecting supports. We also assumed that for any q, q′ ∈ [r] and some fixed scalar 0 ≤ κ ≤ 1, if λq ≥ λq′ , then λq′ ≥ κ · λq. We remark that we may not recover the signal supports in a known
order, but we are guaranteed to recover all of them exactly. For simplicity of discussion, let us assume here that we recover the vector x(i) at iteration i.
The idea to recover the r spikes is essentially to run Algorithm 2 r times. At first, we compute the t-sparse vector v∗ by maximizing the product 〈Y (1), v⊗p∗ 〉. Then, using v∗, we compute the vector α to obtain a set I1 ⊆ [n]. With high probability, we will have I1 = supp ( x(1) ) and so we will exactly recover the support of x(1). In the second iteration of the loop, we repeat the same procedure with the additional constraint of searching only over the n− k dimensional subset of Ut containing vectors with disjoint support from I1. Similarly, at iteration i, we search over the subset of Ut containing vectors with disjoint support from
⋃ 1≤j<i Ij . As before, we first preprocess the data to create two
independent copies Y (1) and Y (2). Concretely:
Algorithm 3 Multi-spike limited brute force Input: k, t, r and Y (1),Y (2) obtained from Algorithm 1. Repeat for i = 1 to r:
Compute v∗ := argmaxu∈Ut〈Y (1), u⊗p〉 subject to supp (v∗) ∩ ( ⋃ 1≤j<i Ij ) = ∅. Compute the vector α ∈ Rn with entries α` := 〈Y (2), v⊗p−1∗ ⊗ e`〉 for every ` ∈ [n]. Let Ii be the set of indices of the largest k entries of α.
Return I1, . . . , Ir.
The proof structure is similar to that of Algorithm 2 and essentially amounts to showing that the claims (i) and (ii) described in Section 2.1 hold in each iteration.
Let λmin = minq∈[r] λq and λmax = maxq∈[r] λq. For some 0 < ≤ 1/2, let κ & (
1−
)p−1 such
that λmin ≥ κ · λmax. Suppose that
λmin & 1
· (1− )p ·
√ t ( k
t
)p log n and λmin & (
1−
)p−1 · λmax . (2)
Consider an arbitrary iteration i and suppose that we exactly recovered the support of one signal in each of the previous iterations. Without loss of generality, assume that λmax is the largest signal strength among the yet to be recovered signals, and let x(max) be one such corresponding signal.
For u ∈ Ut satisfying supp(u) ⊆ supp(x(max)), we have
〈Y (1), u⊗p〉 = λmax〈x(max), u〉p + 〈W (1), u⊗p〉 ≥ λmax · ( t
k
) p 2 −O (√ t log n ) .
On the other hand, for any u ∈ Ut such that ∣∣supp (u) ∩ supp (x(q))∣∣ ≤ (1− ) · t for all q ∈ [r],
〈Y (1), u⊗p〉 = ∑ q∈[r] λq〈x(q), u〉p + 〈W (1), u⊗p〉
≤ λmax · ( t
k
) p 2 · ((1− )p + p) +O (√ t log n )
≤ λmax · ( t
k
) p 2 · (1− )p−1 +O (√ t log n ) .
Thus, as in Section 2.1, it follows that v∗ satisfies ∣∣supp (v∗) ∩ supp (x(i))∣∣ ≥ (1− ) · t for some signal x(i). Note that x(i) may not be x(max). Even though v∗ does not exactly overlap with any of the signal vectors, we will not accumulate an error at each iteration. This is because, analogous to the single spike setting, we can exactly identify the support of a signal through α. For any
` ∈ supp ( x(i) ) , it holds that α` & √ log n as before because ∣∣∣〈W (2), v⊗p−1∗ ⊗ e`〉∣∣∣ . √log n. Conversely, since signal supports are disjoint, we see that for ` /∈ supp ( x(i) ) ,
α` = ∑ q∈[r] λq · x(q),` · 〈x(q), v∗〉p−1 + 〈W (2), v⊗p−1∗ ⊗ e`〉
≤ λmax · p−1√ k · ( t k ) p−1 2 +O (√ log n )
≤ λmin κ · p−1 √ k · ( t k ) p−1 2 +O (√ log n )
. √ log n .
So, once again, α exactly identifies the support of x(i) with high probability. Remark 7 (On the strength of the assumption on κ). As already briefly discussed in Section 1.2, the algorithm provides a three-way trade-off between signal gap κ, signal-to-noise ratio λ and running time. By appropriately choosing the constant > 0, the algorithm can tolerate different values of
κ. Indeed, the above analysis holds as long as κ & (
1−
)p−1 . This suggests two ways in which
we can loosen the requirement λmin ≥ κ · λmax and still successfully recover the signals through Algorithm 3. One is increase the running time, so that we can decrease without increasing the signal-to-noise ratio λmin. The other is to decrease and increase the value of λmin accordingly. Remark 8 (On independent copies of Y ). To clarify why it suffices to have 2 independent copies of Y even for multiple iterations, observe that at each iteration i, the choice of the set Ii depends only on the vector v∗ with high probability. Consider the following thought experiment where we are given a fresh copy Y (i) of Y in the second phase of each iteration i of the algorithm (while still using only a single copy Y (1)for all the first phases). Even with fresh randomness, the result is the same as Algorithm 3 with high probability because at each iteration the choice of maximizer v∗ causes the same output. Remark 9 (Reconstructing the signals from their supports). After recovering individual signal supports, one can reconstruct signals using known tensor PCA algorithms (e.g. [MR14, HSS15]) on the subtensor defined by each recovered support. The signal strength required for this new subproblem is weaker and is satisfied by our recovery assumptions. For instance, by concatenating our algorithm with [HSS15, Theorem 7.1], one obtains vectors x̂(1), . . . , x̂(r) such that
∣∣〈x̂(i), x(i)〉∣∣ ≥ 0.99, for any i ∈ [r], with probability 0.99.

heading: 3 Open questions

text:
Open question 1. Theorem 2 improves over existing sparse PCA multi-spike recovery algorithms (which only assumed orthogonal spikes) by a factor of 1/r in the case where these planted signals have disjoint support. Can one still obtain an improvement of 1/r if we only assume orthogonality? Open question 2. For p ∈ ω(1), there is an exponential gap between the bounds of Theorem 3 and state-of-the-art algorithms. A natural question is whether one can design better recover algorithms or prove stronger lower bounds for this range of tensor power p ∈ ω(1)?
Remark (Societal impact). This work does not present any foreseeable negative societal consequence.
Acknowledgments and Disclosure of Funding
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 815464). This research/project is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG-PhD/2021-08-013). We thank David Steurer for several helpful conversations. We thank Luca Corinzia and Paolo Penna for useful discussions about the planted sparse densest sub-hypergraph model.

title: The Complexity of Sparse Tensor PCA