---
abstract: |
    Adversarial robustness measures the susceptibility of a classifier to imperceptible perturbations made to the inputs at test time.  In this work we highlight the benefits of natural low rank representations that often exist for real data such as images, for training neural networks with certified robustness guarantees. 

    Our first contribution is for certified robustness to perturbations measured in $\ell_2$ norm.  We exploit low rank data representations to provide improved guarantees over state-of-the-art randomized smoothing-based approaches on standard benchmark datasets such as CIFAR-10 and CIFAR-100. 

    Our second contribution is for the more challenging setting of certified robustness to perturbations measured in $\ell_\infty$ norm.  We demonstrate empirically that natural low rank representations have inherent robustness properties, that can be leveraged to provide significantly better guarantees for certified robustness to $\ell_\infty$ perturbations in those representations.  Our certificate of $\ell_\infty$ robustness relies on a natural quantity involving the $\infty \to 2$ matrix operator norm associated with the representation, to translate robustness guarantees from $\ell_2$ to $\ell_\infty$ perturbations.  A key technical ingredient for our certification guarantees is a fast algorithm with provable guarantees based on the multiplicative weights update method to provide upper bounds on the above matrix norm.  Our algorithmic guarantees improve upon the state of the art for this problem, and may be of independent interest. 
author:
- 'Pranjal Awasthi[^1]'
- 'Himanshu Jain[^2]'
- 'Ankit Singh Rawat[^3]'
- 'Aravindan Vijayaraghavan[^4]'
bibliography:
- 'advrobustness.bib'
title: Adversarial robustness via robust low rank representations
---

Methods for Certified $\ell_\infty$ Robustness {#sec:linf:methods}
==============================================

Conclusion
==========

In this paper, we have shown significant benefits in leveraging natural structure that exists in real-world data e.g., low-rank or sparse representations, for obtaining certified robustness guarantees under both $\ell_2$ perturbations and $\ell_\infty$ perturbations in natural data representations.  Our experiments involving imperceptibility in the DCT basis for images suggest that further study of $\ell_\infty$ robustness for other natural basis (apart from the co-ordinate basis) would be useful for different data domains like images, audio etc.  We also gave faster algorithms for approximately solving semi-definite programs for quadratic programming (with provable guarantees that improve the state-of-the-art), to obtain certified $\ell_\infty$ robustness guarantees.  Such problem-specific fast approximate algorithms for powerful algorithmic techniques like SDPs and other convex relaxations may lead to more scalable certification procedures with better guarantees.  Finally it would be interesting to see if our ideas and techniques involving the $\infty \to 2$ operator norm can be adapted into the training phase, in order to achieve better certified $\ell_\infty$ robustness in any desired basis without compromising much on natural accuracy. 

Broader Impact {#broader-impact .unnumbered}
==============

Our work provides efficient algorithms for training neural networks with certified robustness guarantees.  This can have significant positive societal impact considering the importance of protecting AI systems against malicious adversaries.  A classifier with certified robustness guarantees can give a sense of security to the end user.  On the other hand, our methods achieve robustness at the expense of a small loss in natural test accuracy as compared to non-adversarial training.  It is unclear how this loss in accuracy is distributed across the population.  This could have a negative societal impact if the loss in accuracy is disproportionately on data points/individuals belonging to a specific demographic group based on say race or gender.  That said, robustness to perturbations also corresponds to a natural notion of individual fairness since data points with similar features need to be treated similarly by a robust classifier.  Hence, a careful study must be done to understand these effects before a large scale practical deployment of systems based on our work. 

[^1]: Google Research and Department of Computer Science, Rutgers University.  The author acknowledges support from the NSF HDR TRIPODS award CCF-1934924. [ pranjal.awasthi@rutgers.edu]{}. 

[^2]: Google Research

[^3]: Google Research

[^4]: Department of Computer Science, Northwestern University.  Supported by the National Science Foundation (NSF) under Grant No.  CCF-1652491 and CCF-1637585. [ aravindv@northwestern.edu]{}.