# GANash - A GAN approach to steganography

Venkatesh Subramaniyan
Vagheesan A K  SSN College of engineering
Chennai, India
<EMAIL_ADDRESS>SSN College of engineering
Chennai, India
<EMAIL_ADDRESS>Vignesh Sivakumar
Dr. K.J Jegadish Kumar  SSN College of engineering
Chennai, India
<EMAIL_ADDRESS>Associate Professor, ECE Department
SSN College of engineering
Chennai, India
<EMAIL_ADDRESS>S.Sakthivelan
Dr. K.K.Nagarajan  SSN College of engineering
Chennai, India
<EMAIL_ADDRESS>Associate Professor, ECE Department
SSN College of engineering
Chennai, India
<EMAIL_ADDRESS>
###### Abstract

Data security is of the utmost concern of a communication system. Since the
early days, many developments have been made to improve the performance of the
system. PSNR of the received signal, secure transmission channel, quality of
encoding used, etc. are some of the key attributes of a good system. To ensure
security, the most commonly used technique is cryptography in which the
message is altered with respect to a key and using the same, the encoded
message is decoded at the receiver side. A complementary technique that is
popularly used to insure security is steganography. The advancements in
Artificial Intelligence(AI) have paved way for performing steganography in an
intelligent, tamper-proof manner. The recent discovery by researchers in the
field of Deep Learning(DL), an unsupervised learning network known as the
Generative Adversarial Networks(GAN) has improved the performance of this
technique exponentially. It has been demonstrated that deep neural networks
are highly sensitive to tiny perturbations of input data, giving rise to
adversarial examples. Though this property is usually considered a weakness of
learned models, it could be beneficial if used appropriately. The work that
has been accomplished by MIT for this purpose, a deep-neural model by the name
of SteganoGAN, has shown obligation for using this technique for
steganography. In this work, we have proposed a novel approach to improve the
performance of the existing system using latent space compression on the
encoded data. This theoretically would improve the performance exponentially.
Thus, the algorithms used to improve the system’s performance and the results
obtained have been enunciated in this work. The results indicate the level of
dominance this system could achieve to be able to diminish the difficulties in
solving real-time problems in terms of security, deployment and database
management.

###### Index Terms:

Steganography, Generative Adversarial Network(GAN), Nash-equilibrium.

##  I Introduction

Since World war II, encryption has played a very crucial role in secure
transmission of data. The two most popular techniques used to transmit data
securely over a channel are cryptography and steganography. These are
comparable to the two sides of a coin where the former inconceivably encrypts
the message while the latter intends to hide the traces of a communication
itself. In older days, these techniques were done manually but since the
arrival of the digital era, computers have been used to do the same.
Cryptography has improved drastically over the years, but steganography has
been used comparatively less and there is scope for significant improvements.

Steganography could be classified primitively on the basis of the type of
message used which includes text, images, audio and video. It could be further
classified based on the technique used namely spatial domain techniques and
transform domain techniques. These techniques employ statistical approaches to
hide a message which could be easily detected by intruders. The digital age
has led to the discovery of Neural Networks which tries to mimic human
knowledge to be able to solve real-time problems in unanticipated ways. The
same has been used to perform steganography to overcome the disadvantages of
the conventional methodologies. Researchers have discovered and developed
algorithms in this regard. Thus, the intrications of neural networks have been
understood from their primitives.

Advancements in neural networks have led to the discovery of Generative
Adversarial Networks(GANs) [1]. GAN is a category of machine learning
framework in which two neural networks compete against each other to achieve
the specified objective. GAN is the most commonly used steganography technique
in recent times. GAN has been efficient in achieving excellent results in
various fields. One such field is steganography where the induction of GAN has
proved to be authoritative compared to the conventional algorithms. The most
recent work using GAN for performing steganography has been accomplished by
researchers at MIT known by the name of SteganoGAN [2]. This model shows
promise in terms of security with the ability to hide more amount of data in a
given cover image compared to the conventional techniques. Another popular
work known as Deep steganography [3] also adds value to the same. Thus, they
are effective in terms of security.

The major downside of the above mentioned systems is the computation cost. The
applications of steganography not only comprises secrecy but also expands to
various other things such as protection of data alteration, data storage,
digital content distribution, etc. In such cases, the technique needs to be
computationally effective to be used in real-time. A well designed
steganographic network must be able to withstand great amount of intrusions.
Thus, the system has to be secure and also deployable. In this work, a
lightweight model is built using GAN to perform image steganography with
latent space compression. The main objective of this work is to improve the
performance in terms of time taken to encode and decode, which is imperative
in case of deployment. The model has been named GANash since GAN is used to
perform steganography on a given data and achieve a state of Nash equilibrium.

##  II Related Work

There are various methods of implementing the technique of Image
steganography. The 3 major types of image steganography techniques used are -
Conventional Steganography, Convolutional Neural Network(CNN) based
steganography and Generative Adversarial Network(GAN) based steganography. In
this section the various algorithms and architectures used are discussed.

###  II-A Conventional Steganography

Conventional steganography is an old technique which involves bit manipulation
of images, that is, the pixel values are altered to embed the information.
These manipulations can either be a wavelet transform, a simple Least
Significant Bit (LSB) or a bitwise XOR operation. They involve basic spatial
domain or frequency domain operation in order to output steganographic images.

Neeta D.et al(2006) [4] proposed a steganography method where the Least
Significant Bit(LSB) gets manipulated by bitwise OR operation. This method can
be used efficiently for images with 8 bits and 24 bits. According to this
method, by changing two least significant bits, the human eye perception could
be deceived. Yuan-Hui Yu et.al [5] proposed a method where a true color image
can be embedded with grey scale and color image. The embedded image data are
then subjected to standard DES cryptography algorithm. This methodology proved
to be better compared to [4]. Al Atabi et.al [6] proposed a method which uses
wavelet transform. In this method, the information is translated with respect
to wavelet transform coefficients.

These methods are conventional in nature and are mathemathical based
transforms, which might be efficient to some extent but are easily detectable
by statistical analysis and could get unveiled easily. Thus, the robustness of
neural networks comes into play in which the bit manipulation is quite hard to
track.

###  II-B Convolutional Neural Network based Steganography

In this type of steganography, the ability of neural network, a sophisticated
mathematical model, is used. One such type of network that is popularly used
on images is the Convolutional Neural Network(CNN), which uses convolution
operation with the help of kernels(filters) to extract and compress the
information present in the original image.

Pin Wu et.al [7] proposed a steganography method which utilizes both deep
convolutional neural network and image-image translation [8]. In this approach
the end-to-end mapping between cover and embedded image, hidden image and
decoded image could be learnt. Hence this method is more robust and has high
capacity compared to the traditional ones. Tang et.al [9] presented a novel
method of steganography which used an approach called adversarial
embedding(ADV-EMB) that could accomplish the criteria of hiding a stego
message while at the same time surviving a convolutional neural network (CNN)
based steganalyzer.

The above works discuss only about steganography or the process of embedding
data but the work accomplished by Qian Y et.al [10] discusses about the
process of steganalysis using deep learning models. The proposed model has the
capability to learn complicated features in the image, which steganalysis uses
to detect steganography. Contrasted with the current schemes ,Just with a few
convolutional layers this model can easily learn complex dependencies. Since
the process of feature extraction and classification are carried under the
single architecture,the knowledge of classification can be utilized in feature
extraction as well. Hence this learnt feature can be used to identify whether
the steganography has been performed or not.

###  II-C GAN based Steganography

Generative adversarial network is a class of neural networks where two neural
networks compete to minimise the loss. Due to its generative and
discrimininative properties, it finds a wide range of applications which also
includes steganography.

Volkhonskiy et al. [11] proposed a new model for generating image-like cover
based on Deep Convolutional Generative Adversarial Networks (DCGAN)[12] and
this method is secure from steganalysis. In this network architecture, a
generative model is trained for image stego-cover by challenging it with two
deep convolutional adversaries: a discriminator network, which optimizes the
output to look like samples from the real dataset, and a steganographic
analyzer, which aims at detecting if an image conceals a hidden message.

Shi et.al [13] proposed a novel strategy of Secure Steganography based on
Generative Adversarial Network. The proposed architecture has one generative
network, and two discriminative networks. The generative network essentially
assesses the visual nature of the generated images from steganography, and the
discriminative network are utilized to assess their appropriateness for data
hiding.

Zhang et.al [2] proposed a novel procedure for concealing binary information
in images using generative adversarial network. This technique improves the
cognitive nature of the images created by this model and accomplishes best in
class payloads of 4.4 bits per pixel. In addition, this also dodges discovery
by steganalysis tools and is compelling on images from various datasets.

##  III Generative Adversarial Networks

Generative Adversarial Network(GAN) is a class of machine learning framework
invented by Ian Goodfellow and his colleagues in 2014 [1]. In this
architecture, two neural networks try to reach a common objective by treating
each other as an adversary. Given a training set, this technique learns to
generate new data with the same statistics as the training set. GAN uses semi-
supervised learning to learn any kind of data distribution. It aims at
learning the true data distribution $p_{real}$ of the training records so as
to generate synthetic data records with some minimal variations in the learnt
distribution $p_{g}$ while the discriminator tries to assign the probability
score for the target $P(Y|X)$ with the given training samples. GANs are
formulated as a minimax game, where the Discriminator is trying to minimize
its reward $V(D,G)$ and the Generator is trying to maximize its loss. It can
be mathematically described using the formula

$V(D,G)=E_{x\sim p_{data}(x)}[logD(x)]+E_{z\sim p_{z}(x)}[log(1-D(G(z))]$ (1)

###  III-A Nash-equilibrium

The intention of GAN is to minimize the divergence caused by true and learnt
data distributions. Consider two distribution functions $f$ and $g$. Assume
$g$ is the generated distribution from $f$ and $D$ is a divergence function.
$D$ takes $f$ and $g$ as inputs and measures the divergence value and $D$
satisfies the condition $D(f,f)=0$.

$\min_{\theta}(f_{0},g_{\theta})$ (2)

Equation (2) shows the optimization objective, where $f_{0}$ is real
distribution with fixed parameters and $g_{\theta}$ is the generated
distribution with $\theta$ parameters. Adapting SimGA from [14], the local
Nash-equilibrium point $(\bar{\psi},\bar{\theta})$ is derived by

$\displaystyle\bar{\psi}\in\operatorname*{argmax}_{\psi}f(\psi,\bar{\theta})$
(3)
$\displaystyle\bar{\theta}\in\operatorname*{argmax}_{\theta}f(\theta,\bar{\psi})$

##  IV Data pipeline

In this section, the data pipeline and the design choices for optimizing the
performance is discussed.

###  IV-A Pre-processing data pipeline

The main focus here is on reducing the RAM over-usage while designing the pre-
processing pipeline. It is known that CPU cores can perform on different
instructions (MIMD) in parallel at a given time. This is leveraged in the
below stated pipeline. Some of the standard computer architecture aspects to
be considered beforehand for getting the best results are :

  1. 1.

CPUs are optimized based on memory access time(latency optimization) while
GPUs are optimized based on bandwidth.

  2. 2.

CPUs can carry out optimized and sophisticated tasks whereas GPUs could face
bottleneck issue i.e. transferring a huge amount data to the GPU is time
consuming.

Based on these standards, the data pre-processing is performed on the CPU and
model’s mathematical computations are performed on the GPU.

###  IV-B Datasets

####  IV-B1 DIV2K

It is a novel 2K resolution benchmarking data set [15]. This data set is
chosen for its high resolution details and its large diversity of contents
including people, handmade objects and environments such as flora and fauna.

####  IV-B2 MS COCO

It is a state-of-the-art object recognition data set [16] which consists of
everyday scenes containing common objects and these multi class object data
sets can improve GANash’s stego abilities among realistic image environment.

###  IV-C Text to bits conversion

Text to bits converstion is adapted from [2]. Reed-Solomon technique [17] has
been proved to be effective in error correction while translating from decoded
message bits into text. One disadvantage in using this technique is that it
introduces data redundancy in message bits.

###  IV-D Parallelization

Tensorflow data API is used to perform parallel level transformation. This API
enables the pipeline to choose the number of threads needed for data level
mapping. The addresses of the training images is loaded and only a mini-batch
of it will be selected as load into the pipeline. Because of this, only a
small amount of RAM is occupied during each iteration. Hence, this efficiently
improves the performance of the pipeline.

##  V Model Architecture

In this work, a GAN based model with an encoder, a decoder and a critic has
been proposed. In this section, the design choices for GANash and its loss
functions are discussed in detail.

###  V-A Critic

The architecture of the critic network is shown in fig 1. It consists of 4
stages. The first 3 stages include a series of convolutional layer with
$3\times 3$ kernels, a leaky relu layer and followed by a batch normalization
layer. The last stage is a convolutional layer with $1\times 1$ kernels and is
further reduced to its average mean $p(Y)$.

Figure 1: Critic Network

The Critic network tries to maximize the convergence between the two
distributions. Let $R_{0}$ represent the real distribution and $E_{\theta}$
represent the encoder distribution. The critic network helps to minimize the
divergence of $E_{\theta}$ with $R_{0}$ using (2). It takes $Y$ as input,
which could either be the cover image $I$ or the stego image $S$ and returns
the probability score $p(Y)$.

###  V-B Encoder

The encoder architecture consists of 4 stages as shown in fig 2. The first 3
stages consist of a convolutional layer with $3\times 3$ kernels followed by a
batch normalization layer. The final stage is a convolutional layer consisting
of $3\times 3$ kernels with tanh activation.

Figure 2: Encoder Network

Based on the critic network’s feedback, the encoder learns to hide the message
within the cover image and accordingly it changes the parameters $\theta$ of
its distribution $E_{\theta}$. It takes Input image $I_{n}$, Message to hide
$M_{n}$ and using the trained parameters $\bar{\theta}$, it generates the
stego image $S_{n}$.

###  V-C Decoder

The decoder architecture also consists of 4 stages as shown in fig 3. The
first 3 stages consist of a convolutional layer with $3\times 3$ kernels
followed by a batch normalization layer. The final layer is a convolutional
layer with kernel size $3\times 3$ and number of filters equal to data depth.

Figure 3: Decoder Network

The decoder network learns to unravel the message from the stego image. Based
on the data depth D, the final layer of the decoder should be changed to
B$\times$H$\times$W$\times$D, where B is the mini-batch size, H and W are the
height and width of the cover image respectively. It takes $S$ as input and
returns the message $M$.

In addition to this, a global steganographic model can be prepared by pre-
training GANash on higher data dimension D, so that the model can be fine-
tuned for varying dimensions.

###  V-D Loss functions

The loss functions for encoder, decoder and critic are given in (4). Mean
Squared Error(MSE) is used to calculate the encoder and the critic loss.
Sigmoid Cross-Entropy(SCE) is used to calculate the decoder loss.

$\displaystyle l_{enc}=\frac{1}{N}\sum_{i=1}^{N}(I-S)^{2}$ (4) $\displaystyle
l_{dec}=-\sum D(M).log(D(M))$ $\displaystyle l_{critic}=MSE[p(S)-p(I)]$
$\displaystyle l_{T}=l_{enc}+l_{dec}+l_{critic}$

where $I$, $S$ and $M$ are the input image, stego image and message
respectively and $D$ represents the decoder objective function. Section V-E
briefs the process of adversarial training with these loss functions.

###  V-E Training

The model is trained on a 12 core CPU machine with GTX 1050ti-16GB GPU. The
encoder-decoder network and the critic network are iteratively optimized using
the loss functions presented in section V-D. The objective of this training is
to maximize the convergence between true and fake distributions. This is
ensured by the following three steps :

  1. 1.

Critic is optimized based on the probability scores on the two distributions
until it stations the model at Nash-equilibrium .

  2. 2.

Decoder is optimized depending on the decoder loss $l_{d}$.

  3. 3.

Finally, the gradients of the encoder, decoder and critic variables are
updated based on the total loss $l_{T}$.

Result: $E_{\theta}\mathrel{\mathop{\mathchar 58\relax}}I\mapsto S$, Given
$\min_{\theta}(f_{0},g_{\theta})\mapsto 0$

Initialize;

Require: total loss $l_{t}$ and decoder loss $l_{d}$;

while  _not converged_ do

1\. Compute gradient for Critic;

$x_{\psi}\leftarrow\nabla_{\psi}R(\theta;\psi)$ ;

$x_{\theta}\leftarrow\nabla_{\theta}E(\theta;\psi)$ ;

Update the variables;

$\theta\leftarrow\theta+\eta x_{\theta}$ ; $\psi\leftarrow\psi+\eta x_{\psi}$
;

2\. Compute gradient for Decoder;

$x_{d}\leftarrow\nabla_{d}D(l_{d};d)$ ;

Update the variables;

$d\leftarrow d+\eta x_{d}$ ;

3\. Overall model optimization ;

$x_{e,d,c}\leftarrow\nabla_{e,d,c}T(l_{t};e,d,c)$ ;

update encoder $e$, decoder $d$ and critic $c$ variables

end while

Algorithm 1 Triplet training

###  V-F Hyperparameters

The parameters are set on the basis of experimentation. The final set of
hyper-parameters used in training the GAN with which the required results are
obtained is given in table I.

TABLE I: Hyperparameters parameters |  value
---|---
Learning rate - Critic |  1e-5
Learning rate - Decoder |  1e-2
Learning rate - Total |  1e-5
Gradient clip rate |  (-0.1,0.1)
Hidden dims |  32
Data depth |  [3,4,5]
Kernel size |  3
Coworkers |  4
Buffer |  8

##  VI Evaluation metrics

The model is evaluated based on the standard metrics used for a steganography
system. The metrics used are listed below.

###  VI-A Payload

It is defined as the ratio of the number of message bits to the size of the
cover image.

$Payload=\frac{Number\;of\;bits\;in\;message}{Size\;of\;the\;cover\;image}$
(5)

where size of cover image = H$\times$W.

###  VI-B Time To Enocde (T2E)

It is the time elapsed to encode the message into cover image to obtain the
stego image.

###  VI-C Time To Decode (T2D)

It is the time elapsed to decode the stego image to obtain the message.

###  VI-D Mean Square Error (MSE)

It is defined as the average squared difference between the cover and stego
image.

$MSE=\sum_{j=1}^{H}\sum_{k=1}^{W}\frac{[C(j,k)-S(j,k)]^{2}}{H\times W}$ (6)

where C is Cover image, S is Stego image.

###  VI-E Peak Signal To Noise ratio (PSNR)

The percentage of noise present in the stego image is defined as the Peak
Signal to noise ratio.

$PSNR=10log_{10}\frac{(2^{n}-1)^{2}}{MSE}$ (7)

where n is the number of bits used to represent a pixel in the cover image.

###  VI-F Cross-Correlation Coefficient (r)

It is a metric that compares the similarity between the cover image and the
stego image.

$r=\frac{(C-m_{1})(S-m_{2})}{\sqrt{(C-m_{1})^{2}(S-m_{2})^{2}}}$ (8)

where $m_{1}$ and $m_{2}$ are the mean of the cover and stego image
respectively.

###  VI-G Security

It is a measure of immunity of the encoding technique against intrusion.

##  VII Results and Discussion

This section showcases the results obtained using the various evaluation
metrics listed in section VI. The cover image used for hiding the message to
obtain the stego image is that of Lenna Forsén. The dimension of the image is
$360\times 360$ thus containing a total of 1,29,600 pixels. Fig 4 shows the
stego image obtained using the various techniques listed in this paper which
are LSB, MIT’s Steganogan and the model implemented through this work, GANash.

Figure 4: Qualitative validation of the stego image using (a)LSB with a payload of 2.315 bits/pixel (b)SteganoGAN with a payload of 4 bits/pixel (c)GANash with a payload of 4 bits/pixel TABLE II: Quantitative result Metric |  LSB |  SteganoGAN |  GANash
---|---|---|---
Max. payload (bits/pixels) |  1 |  4 |  4
Time to Encode (secs) |  3.56 |  1.968 |  0.129
Time to Decode (secs) |  2.3 |  46.12 |  0.174
Mean Squared Error(MSE) |  0.00237 |  0.00304 |  0.000361
PSNR (dB) |  77.375 |  76.28 |  85.5410
Cross-Correlation coefficient |  0.98684 |  0.98731 |  0.99326
Security |  low |  high |  high

From the results obtained, it is evident that GANash and SteganoGAN are
superior compared to LSB. In addition, GANash has proved to be effective
compared to SteganoGAN in terms of Time to encode and decode, Mean Squared
Error and PSNR.

##  VIII Conclusion

In this work, a lightweight, cost-effective, intelligent model has been
introduced to perform steganography in a robust and automated manner that is
compatible with low specification computing engines. Further, our model is
trained in a way that the encoding and decoding parts are distinguishable
without any loss in the training information. In addition to this, we
efficiently handled our model training to concentrate more on lossless message
decoding. It is evident from the results obtained that the model presented in
this work is ten times more powerful compared to the existing model.

## Acknowledgements

We would like to thank Raviteja Vuppaladhadiyam and Harine Govindarajan from
Sri Sivasubramaniya Nadar College of Engineering for assisting and
proofreading the work.

## References

  * [1] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial networks,” 2014.
  * [2] K. A. Zhang, A. Cuesta-Infante, L. Xu, and K. Veeramachaneni, “Steganogan: High capacity image steganography with gans,” 2019.
  * [3] S. Baluja, “Hiding images in plain sight: Deep steganography,” in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017.
  * [4] D. Neeta, K. Snehal, and D. Jacobs, “Implementation of lsb steganography and its evaluation for various bits,” in _2006 1st International Conference on Digital Information Management_ , 2007, pp. 173–178.
  * [5] Y.-H. Yu, C.-C. Chang, and I.-C. Lin, “A new steganographic method for color and grayscale image hiding,” _Computer Vision and Image Understanding_ , vol. 107, no. 3, pp. 183–194, 2007.
  * [6] A. Al-Ataby and F. Al-Naima, “A modified high capacity image steganography technique based on wavelet transform,” _The International Arab Journal of Information Technology_ , vol. 7, no. 4, 2010.
  * [7] “Stegnet: Mega image steganography capacity with deep convolutional network,” vol. 10.
  * [8] C. Chu, A. Zhmoginov, and M. Sandler, “Cyclegan, a master of steganography,” 2017\.
  * [9] W. Tang, B. Li, S. Tan, M. Barni, and J. Huang, “Cnn-based adversarial embedding for image steganography,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 8, pp. 2074–2087, 2019.
  * [10] Y. Qian, J. Dong, W. Wang, and T. Tan, “Deep learning for steganalysis via convolutional neural networks,” in _Media Watermarking, Security, and Forensics 2015_ , A. M. Alattar, N. D. Memon, and C. D. Heitzenrater, Eds., vol. 9409, International Society for Optics and Photonics. SPIE, 2015, pp. 171 – 180.
  * [11] D. Volkhonskiy, I. Nazarov, and E. Burnaev, “Steganographic generative adversarial networks,” 2019.
  * [12] A. Radford, L. Metz, and S. Chintala, “Unsupervised representation learning with deep convolutional generative adversarial networks,” 2016.
  * [13] H. Shi, J. Dong, W. Wang, Y. Qian, and X. Zhang, “Ssgan: Secure steganography based on generative adversarial networks,” 2018.
  * [14] L. Mescheder, S. Nowozin, and A. Geiger, “The numerics of gans,” 2018.
  * [15] E. Agustsson and R. Timofte, “Ntire 2017 challenge on single image super-resolution: Dataset and study,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , 2017, pp. 1122–1131.
  * [16] T.-Y. Lin, M. Maire, S. Belongie, L. Bourdev, R. Girshick, J. Hays, P. Perona, D. Ramanan, C. L. Zitnick, and P. Dollár, “Microsoft coco: Common objects in context,” 2015.
  * [17] I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” _Journal of The Society for Industrial and Applied Mathematics_ , vol. 8, pp. 300–304, 1960.


Recent studies demonstrated that the adversarially robust learning under $\ell_\infty$ attack is harder to generalize to different domains than standard domain adaptation.
How to transfer robustness across different domains has been a key question in domain adaptation field.
To investigate the fundamental difficulty behind adversarially robust domain adaptation (or robustness transfer), we propose to analyze a key complexity measure that controls the cross-domain generalization: the adversarial Rademacher complexity over symmetric difference hypothesis space $\mathcal{H} \Delta \mathcal{H}$.
For linear models, we show that adversarial version of this complexity is always greater than the non-adversarial one, which reveals the intrinsic hardness of adversarially robust domain adaptation.
We also establish upper bounds on this complexity measure.
Then we extend them to the ReLU neural network class by upper bounding the adversarial Rademacher complexity in the binary classification setting.
Finally, even though the robust domain adaptation is provably harder, we do find positive relation between robust learning and standard domain adaptation.  We explain how adversarial training helps domain adaptation in terms of standard risk.
We believe our results initiate the study of the generalization theory of adversarially robust domain adaptation, and could shed lights on distributed adversarially robust learning from heterogeneous sources, e.g., federated learning scenario.

§ INTRODUCTION

Domain adaptation is a key learning scenario where one tries to generalize the model learnt on a source domain to a target domain. How to predict target accuracy using source accuracy has been a longstanding research topic in both theory [3, 30, 2, 23, 4, 37, 38] and application community [21, 31, 36]. From a theoretical perspective,  this problem can be attacked by establishing bounds on the generalization  of the source-domain-learnt model on target domain, using different complexity measures including  the VC-dimension [3, 2, 38] and Rademacher complexity [23, 37]. In particular, the latter works [23, 37] study a loss class defined over symmetric difference hypothesis space ($\cH \Delta \cH$ class for short):

Given a symmetric loss function $\ell(\cdot,\cdot): \cY \times \cY \mapsto \R$ and a hypothesis class $\cH=\{h_\bw: \mathcal{X} \mapsto \mathcal{Y}\}$, the loss class over symmetric difference hypothesis space is defined as the set:

\begin{align}
\ell \circ \cH \Delta \cH := \left\{ \ell(h_{\bw}(\bx), h_{\bw'}(\bx)) :  h_{\bw},h_{\bw'} \in \cH   \right\}.\label{eq:loss over HDH}
\end{align}

This loss class measures the discrepancy over any pair of two hypotheses in $\cH$, and in [23, 37], they further define the Rademacher complexity over $\ell \circ \cH \Delta \cH$ to bound the gap between source and target generalization risks.

Let hypothesis space $\cH$ be a set of real (vector)-valued  functions defined over input space $\mathcal{X}$ and label space $\mathcal{Y}$: $\cH=\{h_\bw: \mathcal{X} \mapsto \mathcal{Y}\}$ each parameterized by $\bw \in \mathcal{W} \subseteq \mathbb{R}^d$, and $\ell: \mathcal{Y}\times \mathcal{Y} \mapsto \mathbb{R}_{+}$ be the loss function.
Given a dataset $\hat\cD = \{\bx_1,...,\bx_n\}$  sampled i.i.d. from distribution $\cD$ defined over $\mathcal{X}$, the empirical Rademacher complexity of $\cH \Delta \cH$ over this dataset is defined as follows:

\begin{align}
\label{eq:rademacher_complexity_over_h_delta_h_class}
&{\frakR}_{\hat{\cD}} ({\ell} \circ \cH \Delta \cH) = \mathbb{E}_{\sigma} \left[\sup_{h_\mathbf{w},h_{\mathbf{w}'}\in \mathcal{H}} \frac{1}{n}\sum_{i=1}^{n} \sigma_i   \ell(h_\mathbf{w} (\mathbf{x}_i ),h_{\mathbf{w}'}(\mathbf{x}_i )) \right] \enspace,
\end{align}

where $\sigma_1, \ldots, \sigma_n$ are Rademacher random variables with $\Prob \{ \sigma_i = 1 \} = \Prob \{ \sigma_i = -1 \} = \frac{1}{2}$.

Intuitively, above quantity measures how well the loss vector realized by two hypotheses within $\mathcal{H}$  correlates with random vectors.
The better correlation will imply a richer hypothesis class. However, unlike the classical Rademacher complexity whose loss vector is computed between predictions made by a hypothesis  and true labels, Eq. (<ref>) is defined merely over predictions made by two hypotheses.
Authors of [23, 37] have shown that this complexity measure controls the domain adaptation generalization bound. Unfortunately, none of those works give the precise analysis of $ {\frakR}_{\hat\cD} ({\ell} \circ \cH \Delta \cH)$.
To our best knowledge, [18] is the only prior work to analyze $ {\frakR}_{\hat\cD} ({\ell} \circ \cH \Delta \cH)$ on linear classifier class, but their analysis is not tight.
Due to the importance of such complexity measure, we are interested in characterizing how large this complexity measure can be in terms of model dimension and data diversity, even on some toy model, e.g., linear model. Hence, the first question we investigate in this paper is: for linear models, what quantities control the Rademacher complexity over $\cH \Delta \cH$ function class?

Meanwhile, in modern machine learning, practitioners are not only interested in transferring standard model accuracy to another domain, but also in transferring robustness.
Consider adversarially robust risk over domain $\cD$:

$$ \widetilde{\cR}^{label}_{\cD}(h_\mathbf{w},y_\cD) = \mathbb{E}_{\mathbf{x}\sim \cD} \left[\max_{\|\boldsymbol{\delta}\|_\infty\leq \epsilon}\ell (h_\mathbf{w}(\mathbf{x}+\boldsymbol{\delta}), y_\cD(\mathbf{x}))\right],$$

where $y_{\cD}(\cdot)$ is the labeling function.
In the adversarially robust domain adaptation problem, we are interested in the robust risk when the same model $h_\bw$ is evaluated on a new domain $\cD'$. Unfortunately, as shown  empirically  [33, 14, 9], robust model learnt on source domain will lose its robustness catastrophically on a different domain.
That is, the gap between robust risks on the old domain and new domains can be dramatically huge, compared to the standard risk.  This observation naturally leads to the question Why is the robust risk harder to adapt to different domains?, which we aim to examine in this paper. To answer this question, inspired by the Rademacher complexity over $\cH \Delta \cH$ function class, we properly extend this complexity measure to the adversarial learning setting, and  propose the adversarial Rademacher complexity over the $\cH \Delta \cH$ class.
We show that, the adversarial version complexity is always greater than its non-adversarial counterpart, similar to the results proven in [35] in the single domain setting.
Relying on this new complexity measure, we explained by robust domain adaptation is harder than standard one.

Even though we show that robust risk transfer is provably hard, we also find that robust training can have benefits in terms of standard domain adaptation. As observed in recent studies [32, 6], the model trained adversarially on the source domain, usually entails better standard accuracy on target domain, compared to the normally trained model. In this paper, We show that given large enough adversarial budget, small source adversarially robust risk will almost guarantee small target domain standard risk, with the residual error controlled by $\epsilon$. This connection between source robust risk and target standard risk theoretically supports the advantage of performing robust training in domain adaptation tasks.

Our contributions are summarized as follows:

* We study the Rademacher complexity over $\cH \Delta \cH$ class, and propose the adversarial variant of it, which is a new complexity measure towards better understanding the domain adaptation in adversarial learning. In both linear classification and regression settings, we first show that adversarial Rademacher complexity over $\cH \Delta \cH$ class is greater than its non-adversarial counterpart.

We also show that adversarial complexity is bounded by its non-adversarial counterpart plus residual terms polynomially depending on data dimension, model norm and adversarial budget.

* We generalize our results to ReLU neural networks, where we derive an upper bound of adversarial $\cH \Delta \cH$ Rademacher complexity of a 2-layer ReLU neural network for binary classification.

* Although we proved that robust risk transfer is hard, we discover a positive result when we evaluate target domain standard risk of the robust trained model on source domain. We show that, small source robust risk will imply a small target standard risk with adversarial budget dependent variance.  This establish the connection between robust learning and standard domain adaptation, which helps explain the widely-observed phenomena that adversarially trained models can have good generalization performance on different domains.

* We support our theoretical analysis by providing experiments illustrating how adversarial training can help domain adaptation, especially with $\ell_1$ regularization.
We also highlight numerically the difficulty of transferring adversarial robustness across domains.

§ RELATED WORK

Here, we briefly discuss some relevant prior works. But before we would like to highlight the key differences between robust learning, standard domain adaptation, and adversarially robust domain adaptation.  In  adversarially robust learning, we are interested in the gap between population robust risk and empirical robust risk, on the same domain; while in standard domain adaptation, we consider the gap between the (standard) risk on the target domain and the risk on the source domain on which the model is trained on. In adversarially robust domain adaptation, we examine the relation between adversarially robust risks on target and source domains.

Discrepancy Based Domain Adaptation Theory   A significant category of the domain adaptation study is discrepancy based generalization analysis.
[3] borrowed the $\mathcal{A}$-discrepancy from seminal work [17], and gave the target domain generalization in terms of source domain error and this discrepancy measure. Afterwards, [2] proposed $\cH\Delta\cH$ discrepancy, which is easier to estimate from unlabeled data, and also proved VC-dimenson-based generalization bound. [23] also consider $\cH\Delta\cH$ discrepancy, while their analysis depends on Rademacher complexity over $\cH\Delta\cH$ function class. They claim that in some situations, their learning bound is superior to [2]'s bound. [25] proposed $\mathcal{Y}$-discrepancy which is a labeling function dependent measure, but hence it cannot be estimated from unlabeled data. [18] advocated a source-guided discrepancy and showed that it is a tighter discrepancy measure than $\cH\Delta\cH$ discrepancy. [38] proposed a localized discrepancy measure, where they argued that when defining a discrepancy measure, considering the whole hypothesis class may be too pessimistic, so they chose to incorporate risk level as well into the discrepancy definition.

Generalization of Adversarially Robust Learning
To characterize the generalization of adversarially robust learning, a line of researches [16, 35, 1] are conducted via Rademacher complexity point of view. [16] is among the first to examine the adversarial Rademacher complexity under $\ell_\infty$ attack, and as a concurrent work, [35] characterized the upper and lower bound of it, and claim that adversarially robust is at least as hard as standard ERM learning. [1] further extended [35]'s results to adversary set under arbitrary norm constraint, and analyze the complexity of neural network as well. Another category of generalization studies of robust learning is based on PAC learning framework. [5] proved that empirical robust risk minimization is a successful robust PAC learner. [27] show that the function classes with finite VC dimension are adversarially robustly PAC learnable, with the sample complexity related to dual VC dimension, which could be exponentially larger than vanilla VC dimension. [8] proved the lower sample complexity bound for robust PAC learning under hybrid attack. They show that a sample complexity exponentially in the adversary budget is unavoidable. [11] also studied the hardness of robust classification under PAC learning framework, and proved some impossibility results regarding the adversary budget.
[7] investigated different adversarial risk definitions, and proved negative results on the uniform distribution.
[29] also analyzed the existing adversarial risk notions, and discovered the difference and connections among them.

Robustness Transfer
Robustness transfer is a newly initiated research area.
[33] discovered that by fine-tuning the network on the target domain, robustness can be inherited by the new model. [14] considered the federated learning scenario, where they wish to transfer robust models from computationally rich users to users that cannot afford adversarial training. They proposed a batch-normalization based method to share robustness among different clients. [9] studied when the robust features learned in contrastive learning can be transferred to different tasks. Another orthogonal line to transfer robustness is continually fine-tuning models on new samples in an unsupervised manner [13], which however cannot defend against adversarial attacks.

§ PROBLEM SETUP

We adapt the following notations throughout this paper.
We use lower case bold letter to denote vector, e.g., $\bw$, and use upper case bold letter to denote matrix, e.g., $\mM$.
We use $\|\bw\|_p$ and $\|\mM\|_p$ to denote $\ell_p$-norm of vector $\bw$ and matrix $\mM$ respectively.
We define the $(p,q)$-group norm as the $\norm{\mM}_{p, q} \eqdef \|(\norm{\mathbf{m}_1}_p, \ldots, \norm{\mathbf{m}_n}_p)^\top \|_q$ where the $\mathbf{m}_i$s are the columns of $\mM$.

We use $\cD: \mathcal{X} \mapsto \mathbb{R}$ to denote a data distribution (domain) defined over instance space $\mathcal{X}$, and $\hat{\cD}$ be the empirical distribution with $n_{\cD}$ samples drawn i.i.d. from $\cD$.
We let $\cH:=\{h_\bw: \mathcal{X}\mapsto\mathcal{Y}\}$ be the hypothesis space, and vector $\bw \in \mathcal{W} \subseteq \mathbb{R}^d$ denotes the model parametrization of $h_\bw$.
Given a loss function $\ell: \mathcal{Y}\times\mathcal{Y} \mapsto \mathbb{R} $, and a data distribution $\cD$, we let

\begin{equation*}
\cR_{\cD}(h_\mathbf{w},h_{\mathbf{w}'}) \eqdef \mathbb{E}_{\mathbf{x}\sim \cD} [\ell (h_\mathbf{w}(\bx),h_{\mathbf{w}'}(\bx))]
\end{equation*}

be the risk of the disagreement between models $h_\mathbf{w}$ and $h_{\mathbf{w}'}$ on domain $\cD$.
Specially, when the second argument of $\cR_{\cD}(\cdot,\cdot)$ is the labeling function over $\cD$, it becomes the commonly used risk function.
We also define two adversarially robust risks: (1) Model-label robust risk  as
$$\widetilde\cR_{\cD}^{label}(h_\mathbf{w},y) \eqdef \mathbb{E}_{\mathbf{x}\sim \cD} \left[\max_{\|\boldsymbol{\delta}\|_\infty\leq \epsilon}\ell (h_\mathbf{w}(\mathbf{x}+\boldsymbol{\delta}), y(\mathbf{x} ))\right]$$

and (2) Model-model robust risk[$\widetilde\cR_{\cD}^{ label}$ and $\widetilde\cR_{\cD} $ are also called constant-in-ball risk and exact-in-ball risk in [11]. ]  as

\begin{align*}
\widetilde\cR_{\cD}& (h_\mathbf{w},h_{\mathbf{w}'})  \eqdef\mathbb{E}_{\mathbf{x}\sim \cD} \left[\max_{\|\boldsymbol{\delta}\|_\infty\leq \epsilon}\ell (h_\mathbf{w}(\mathbf{x}+\boldsymbol{\delta}), h_{\mathbf{w}'}(\mathbf{x}+\boldsymbol{\delta}))\right].
\end{align*}

In the domain adaptation scenario, we consider source domain $\cS$ and target domain $\cT$ distributions,  and let $\hat{\cS}$ and $\hat{\cT}$ be the empirical source and target distributions with $n_{\cS}$ and $n_\cT$ samples. A key quantity that controls the generalization in domain adaptation is the following discrepancy measure:

Given a hypothesis class $\cH$, risk function $\cR_\cD(\cdot, \cdot)$,  $\mathcal{H}\Delta\mathcal{H}$ discrepancy between distributions $\cS$ and $\cT$ is defined by:

\begin{align}
\label{eq:def_hdeltah_discrepancy}
&disc_{\mathcal{H}\Delta\mathcal{H}} (\cS,\cT)  = \max_{h_\bw,h_{\bw'}\in\mathcal{H}} |\cR_\cS(h_\bw,h_{\bw'})-\cR_\cT(h_\bw,h_{\bw'})|.
\end{align}

The $\cH \Delta \cH$ discrepancy defines a semi-distance over two distributions, and it does not depend on the labeling function of two distributions hence invariant to potential model shift across domains. Another advantage of it, is that it can be efficiently estimated by finite samples, if the Rademacher complexity over $\cH \Delta \cH$ is finite.

Hence based on Definitions <ref> and <ref>, [23] derived the following generalization bound among source and target domains.

Let $\cS$ and $\cT$ be respectively source and target distributions, and let $\hat{\cS}$ and $\hat{\cT}$ be their empirical counterpart with $n_{\cS}$ and $n_\cT$ samples.
Assume that the loss function $ {\ell}$ is symmetric and obeys the triangle inequality. We further assume $ {\ell}$ is bounded by $M$. Then $\forall h_\bw \in \mathcal{H}$ , the following holds with probability at least $1-c$:

\begin{align*}
\cR_\cT(h_\mathbf{w},y_\cT) &\leq \cR_\cS ( h_\bw , h_{\bw^*_\cS}) + disc_{\cH\Delta\cH}(\cS, \cT)+\lambda  +2M\frakR_{\hat\cS}({\ell}\circ \cH \Delta \cH)
+2M{\frakR}_{\hat\cT}({\ell}\circ \cH \Delta \cH) \\
&  \quad+\Bigg(3M\sqrt{\frac{\log(1/c)}{n_\cS}} + 3M\sqrt{\frac{\log(1/c)}{n_\cT}}\Bigg) \, ,
\end{align*}

where $y_\cT$ is the labeling function on target domain, $h_{\bw^*_\cT} , h_{\bw^*_\cS}$ are the best target and source models in $\cH$, i.e., $h_{\bw^*_\cS}= \arg\min_{h\in\cH} \cR_\cS(h,y_\cS)$ and $h_{\bw^*_\cT}= \arg\min_{h\in\cH} \cR_\cT(h,y_\cT)$, and $\lambda = \cR_\cT ( h_{\bw^*_\cT} , h_{\bw^*_\cS} ) + \cR_\cT ( h_{\bw^*_\cT} , y_\cT )$.

The above bound successfully connects the target risk and source risk, with the help of Rademacher complexity over $\cH \Delta \cH$ and $disc_{\cH \Delta \cH}$ distance. It turns out that, $\frakR_{\cS}({\ell}\circ \cH \Delta \cH)$ and ${\frakR}_{\cT}({\ell}\circ \cH \Delta \cH)$ are the key complexity measures that control the generalization between different domains. Hence, to study the generalization of domain adaptation in the adversarial setting, it naturally motivates us to consider the following adversarial robust variant of this  measure as defined below.

Let $\cH$ be a set of real-valued hypothesis functions: $\cH=\{h_\bw: \mathcal{X} \mapsto \mathcal{Y}\}$, and $\ell(\cdot,\cdot): \mathcal{Y}\times \mathcal{Y} \mapsto \mathbb{R}$ be the loss function.
Given a dataset $\hat{\cD} = \{\bx_1,...,\bx_n\}$ sampled from distribution $\cD$, the empirical adversarial Rademacher complexity of $\cH \Delta \cH$ over this dataset is defined as follows

\begin{align}
\label{eq:adversarial_rademacher_complexity_over_h_delta_h_class}
&{\frakR}_{\hat{\cD}} ( \tilde{\ell} \circ \cH \Delta \cH)   = \mathbb{E}_\sigma \left[\sup_{\substack{h_\mathbf{w},h_{\mathbf{w}'}\\ \in \mathcal{H}}} \frac{1}{n}\sum_{i=1}^{n} \sigma_i \tilde{\ell}  (h_\mathbf{w} (\mathbf{x}_i ),h_{\mathbf{w}'}(\mathbf{x}_i )) \right] \enspace,
\end{align}

where $\tilde{\ell}:= \max_{\|\boldsymbol{\delta}\|_\infty\leq \epsilon} \ell(h_\mathbf{w} (\mathbf{x}_i+\boldsymbol{\delta}),h_{\mathbf{w}'}(\mathbf{x}_i+\boldsymbol{\delta}))  $, $\sigma_1, \ldots, \sigma_n$ are Rademacher random variables with $\Prob \{ \sigma_i = 1 \} = \Prob \{ \sigma_i = -1 \} = \frac{1}{2}$.

As we can see, (<ref>) is the adversarial perturbed version of Rademacher complexity of $\ell \circ \cH \Delta \cH$.
We will see later how this quantity controls the generalization of adversarial domain adaptation. We also generalize $\cH\Delta\cH$ discrepancy to the adversarial setting:

Given a hypothesis class $\cH$ and an adversarial risk function ${\widetilde\cR}_\cD(\cdot, \cdot)$, the adversarial $\mathcal{H}\Delta\mathcal{H}$ discrepancy distance between two distributions $\cS$ and $\cT$ is defined by:

\begin{align}
\label{eq:def_adversarial_hdeltah_discrepancy}
&disc^{adv}_{\mathcal{H}\Delta\mathcal{H}} (\cS,\cT) \eqdef \max_{h_\bw,h_{\bw'}\in\mathcal{H}} |{\widetilde\cR}_\cS(h_\bw,h_{\bw'})-{\widetilde\cR}_\cT(h_\bw,h_{\bw'})| \enspace.
\end{align}

The definition of adversarial $\mathcal{H}\Delta\mathcal{H}$ discrepancy is analogous to standard one, and for linear models can indeed be estimated as a function of the latter.
We defer this result to Appendix <ref>, Lemma <ref>.

Let $\cS$ and $\cT$ be respectively source and target distributions, and let $\hat{\cS}$ and $\hat{\cT}$ be their empirical counterpart with $n_{\cS}$ and $n_\cT$ samples.
Assume that the loss function $ {\ell}$ is symmetric and obeys the triangle inequality. We further assume $\tilde{\ell}:= \max_{\|\boldsymbol{\delta}\|_\infty\leq \epsilon} \ell(h_\mathbf{w} (\mathbf{x}_i+\boldsymbol{\delta}),h_{\mathbf{w}'}(\mathbf{x}_i+\boldsymbol{\delta})) $ is bounded by $M$. Then, for any hypothesis $\bw \in \mathcal{H}$ , the following holds:

\begin{align*}
{\widetilde\cR^{label}}_\cT(h_\mathbf{w},y_\cT) &\leq {\widetilde\cR^{label}}_\cS ( h_\bw , y_\cS)   + disc^{adv}_{\cH\Delta\cH}(\cT, \cS) + \lambda  +2M\frakR_{\hat\cS}(\tilde{\ell}\circ \cH \Delta \cH) + 2M{\frakR}_{\hat\cT}(\tilde{\ell}\circ \cH \Delta \cH) \\
&\quad + \Bigg(3M\sqrt{\frac{\log(1/c)}{n_\cS}} + 3M\sqrt{\frac{\log(1/c)}{n_\cT}}\Bigg) ,
\end{align*}

where $y_\cT$ and $y_\cS$ are labeling functions on target and source domain, $h_{\bw^*_\cT}$ and $h_{\bw^*_\cS}$ the best target and source robust models in $\cH$, i.e., $h_{\bw^*_\cS}= \arg\min_{h\in\cH} \widetilde{\cR}^{label}_\cS(h,y_\cS)$ and $h_{\bw^*_\cT}= \arg\min_{h\in\cH} \cR_\cT(h,y_\cT)$, and $\lambda = {\widetilde\cR^{label}}_\cS (  h_{\bw^*_\cS}, y_\cS)+ {\widetilde\cR }_\cT ( h_{\bw^*_\cT} , h_{\bw^*_\cS} ) + {\widetilde\cR^{label}}_\cT ( h_{\bw^*_\cT} , y_\cT )$.

The proof of <Ref> is deferred to Appendix <ref>.
Here we establish the relation between source adversarially robust risk and target adversarially robust risk. It shows that the adversarial discrepancy and adversarial complexity measure $\hat{\frakR}_\cD(\tilde{\ell}\circ \cH \Delta \cH)$ on source and target domains are the two key quantities controlling the deviation between the model's performance on the two domains. Hence, to answer our previously proposed question, why the robust risk is harder to adapt to different domain, it is essential to study the connection between adversarial  and non-adversarial Rademacher complexities over $\cH\Delta\cH$ class.

§ MAIN RESULTS

§ EXTENSION TO NEURAL NETWORKS WITH RELU ACTIVATION

We next extend our analysis methods to more complicated neural network function class.
In this section, we will present our results for two-layer ReLU neural networks.
That is, we consider the following hypothesis class

\begin{align}\label{eq: NN class}
\cH \! \eqdef \! \left\{
\begin{aligned}
& \bx \mapsto  \ba^\top \text{ReLU}(\mW \bx): \\
& \ba \in \mathbb{R}^m, \mW \in \mathbb{R}^{m\times d} : \|\ba\|_1\leq A, \norm{\bw (r)}_{p} \leq W
\end{aligned}
\right\},
\end{align}

where $\bw (r)^\top$ are the rows of $\mW$ for $r=1,\ldots, m$.
The following theorem establishes the relation between Adversarial Rademacher complexity and non-adversarial version in classification setting.
As in <Ref>, we consider the same classification loss functions of the form $\ell (h_{\bw} (\bx), y) \eqdef \phi(y h_{\bw} (\bx))$ .

Let $\cH$ be the set of two-layer ReLU neural networks with bounded weights as defined in (<ref>).
Then, the following statement holds true for adversarial Rademacher complexity over $\cH\Delta \cH$ function class, with classification loss

\begin{align*}
% \label{eq:final_bound_nn_binary_classif}
&{\frakR}_{\hat\cD} (\tilde{f} \circ \cH \Delta \cH) \leq O \Bigg( \frac{A^2 W^2}{n} \sqrt{\sum_{i=1}^n\pare{  \norm{  \bx_i  }_q^2+{d}^{2/q} \epsilon^2 }^2} \sqrt{  md\log (n)} + \frac{A^2 W^2}{n} \max_{i\in[n]} \norm{\bx_i}_q^2 + d^{2/q} \epsilon^2 \Bigg) \enspace.
\end{align*}

The proof of <Ref> is deferred to <Ref>.

As we can see from the above theorem, we get the similar upper bound for ReLU neural network class to what we showed in the linear model case. The upper bound of adversarial Rademacher can be bounded by non-adversarial version plus terms depending on the norm of each layer, and the norm of data points. We leave the lower bound analysis as promising future works.

§ ADVERSARIAL TRAINING HELPS TRANSFER TO DIFFERENT DOMAIN

Even though robust risk is provably harder to transfer in domain adaptation, adversarially robust model does bring benefits, if we consider standard risk on target domain as criteria.
In this section, we will provide a positive result connecting standard ERM learning and adversarially robust learning.
As observed by prior works [32, 6], if a model is adversarially trained on the source domain, then its standard accuracy on target domain is sometimes better than if it had been fitted via vanilla ERM on source domain.

In this section, we try to explain this phenomena from adversarially robust domain adaptation perspective.
We found that, when adversarial budget is large enough, small source adversarial risk almost guarantees the small target domain standard risk.
First, we need to introduce the following optimization problem.

Let $\mathbf{p}$ and $\mathbf{p}'$ be two vectors on the $N$-dimensional simplex and let $\boldsymbol{\ell}$ be a 0-1 vector.
Let also $\Lambda$ be an arbitrary subset of $[N] \eqdef \{1, \ldots, N\}$.
The Subset Sum Problem with Structural Objective can be defined as solving the following combinatorial optimization problem:

\begin{align*}
\left\lbrace
\begin{aligned}
\min_{\tilde{\boldsymbol{\ell}} \in \{0,1\}^N} \quad & \left| \mathbf{p}^\top \tilde{\boldsymbol{\ell}} - \mathbf{p}'^\top  \boldsymbol{\ell} \right| \\
\textrm{s.t.} \quad & \tilde{{\ell}}_i = {\ell}_i,  \  \forall \ i \in [N] \setminus \Lambda \\
% &\xi\geq0    \\
\end{aligned}
\right. \enspace.
%  \text{Subject to:} \ \tilde{{\ell}}_i \subset \{0,1\}, \ &\text{if} \ i \in \Lambda; \quad \tilde{{\ell}}_i = {\ell}_i,  \  \text{if} \ i \in [N] \setminus \Lambda.
\end{align*}

We denote its optimal value as $V^* (\mathbf{p}',\mathbf{p},\boldsymbol{\ell},\Lambda)$.

The above problem is a variant of Subset Sum Problem [12], which is also NP-complete.
We look for a subset of coordinates of a simplex vector $\mathbf{p}$, such that their sum is closest to a given goal.
The given goal has special structure: it is defined as sum of a subset of coordinates in another simplex vector $\mathbf{p}'$.
If the constraint set $\Lambda_\epsilon$ has more indices, the optimal value will be smaller since we can determine the value on more coordinates of $\tilde{\boldsymbol{\ell}}$.
In the following lemma, we explain how this combinatorial measure helps us to connect adversarially robust and standard risks for the binary classification task.

Consider binary classification task, with sign linear classifier class $\cH=\{h_\bw: h_\bw = \sign (\bw^\top \bx), \|\bw\|_p \leq W\}$ and 0-1 loss function $\phi(x,y) = \frac{1}{2}|x-y|$.
Assume all domains share the same labeling function $y(\bx)\in\{-1,1\}$. The following statement holds for any $\cT'$:

\begin{align*}
\cR_{\cT'}(h_\mathbf{w},y) \leq \widetilde\cR^{label}_{\cT}(h_\mathbf{w},y) + V^* (\mathbf{p}',\mathbf{p},\boldsymbol{\ell},\Lambda_\epsilon),
\end{align*}

where $\boldsymbol{\ell}$ is the loss vector such that $\ell_i = \frac{1}{2}|\sign(\bw^\top \bx_i) - y(\bx_i)|$, with $\bx_i \in \cX$.
The vectors $\mathbf{p}$, $\mathbf{p}'$ are probability mass vectors of $\cT$ and $\cT'$, i.e., $\mathbf{p}(\bx) = \mathbb{P}_{X\sim \cT} (X=\bx), \bx \in \cX$ and $\mathbf{p}'(\bx) = \mathbb{P}_{X\sim \cT'} (X=\bx), \bx \in \cX$
Moreover, $\Lambda_\epsilon = \{i: |\bw^\top \bx_i| \leq \epsilon \|\bw\|_1, \bx_i \in \cX, \forall \bw, \|\bw\|_p \leq W\}$.

The corresponding proof is given in Appendix <ref>.
Lemma <ref> shows that, the standard risk on domain $\cT'$ can be bounded by robust risk on domain $\cT$, plus the quantity controlled by $\epsilon$.
Since the set $\Lambda_\epsilon$ stores all indices $i$ such that we can choose to flip $\tilde{\ell}_i$'s value between $0$ and $1$,
then if we have larger adversarial budget $\epsilon$, there will be more indices in $\Lambda_\epsilon$, which means there are more coordinates in $\tilde{\boldsymbol{\ell}}$ we can play with, and hence smaller value of $V^*$.

Comparison with ERM model

Lemma <ref> also apply to standard risk on $\cT$, which means $\epsilon = 0$:

\begin{align*}
\cR_{\cT'}(h_\mathbf{w},y) \leq \cR_{\cT}(h_\mathbf{w},y) + V^* (\mathbf{p}',\mathbf{p},\boldsymbol{\ell},\Lambda_0).
\end{align*}

In this case, $V^*$ become large, since for any $\epsilon >0$, we have $|\Lambda_\epsilon| \geq |\Lambda_0|$ holding. It turns out that, a small source (standard) risk may not imply a small target risk. Hence the ERM model will yield looser generalization guarantee to different domain, than robust ERM model.

§ CONCLUSION

In this paper we propose and analyze the adversarial Rademacher complexity over $\cH \Delta \cH$ class, which is proven to be the key factor controlling the generalization of adversarially robust risk to different domains.
We theoretically explain why adversarial domain adaptation is harder than standard domain adaptation.
We also characterize the standard accuracy of a given model on any target domain, using its adversarial accuracy on the source domain, which helps explaining the recent observation regarding the superiority of adversarially training in standard domain adaptation.

§ ACKNOWLEDGEMENT

This work was supported in part by NSF grant 1956276.

[1]
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri.
Adversarial learning guarantees for linear hypotheses and neural
In International Conference on Machine Learning, pages
431–441. PMLR, 2020.

[2]
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and
Jennifer Wortman Vaughan.
A theory of learning from different domains.
Machine learning, 79(1):151–175, 2010.

[3]
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira.
Analysis of representations for domain adaptation.
Advances in neural information processing systems, 19, 2006.

[4]
Corinna Cortes, Mehryar Mohri, and Andrés Muñoz Medina.
Adaptation algorithm and theory based on generalized discrepancy.
In Proceedings of the 21th ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, pages 169–178, 2015.

[5]
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal.
Pac-learning in the presence of adversaries.
Advances in Neural Information Processing Systems, 31, 2018.

[6]
Zhun Deng, Linjun Zhang, Kailas Vodrahalli, Kenji Kawaguchi, and James Y Zou.
Adversarial training helps transfer learning via better
Advances in Neural Information Processing Systems,
34:25179–25191, 2021.

[7]
Dimitrios Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody.
Adversarial risk and robustness: General definitions and implications
for the uniform distribution.
Advances in Neural Information Processing Systems, 31, 2018.

[8]
Dimitrios I Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody.
Lower bounds for adversarially robust pac learning.
arXiv preprint arXiv:1906.05815, 2019.

[9]
Lijie Fan, Sijia Liu, Pin-Yu Chen, Gaoyuan Zhang, and Chuang Gan.
When does contrastive learning preserve adversarial robustness from
pretraining to finetuning?
Advances in Neural Information Processing Systems,
34:21480–21492, 2021.

[10]
Yaroslav Ganin and Victor Lempitsky.
Unsupervised domain adaptation by backpropagation.
In International Conference on Machine Learning, pages
1180–1189. PMLR, June 2015.

[11]
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell.
On the hardness of robust classification.
The Journal of Machine Learning Research, 22(1):12521–12549,

[12]
Juris Hartmanis.
Computers and intractability: a guide to the theory of
np-completeness (michael r. garey and david s. johnson).
Siam Review, 24(1):90, 1982.

[13]
Junyuan Hong, Lingjuan Lyu, Jiayu Zhou, and Michael Spranger.
Mecta: Memory-economic continual test-time model adaptation.
International Conference on Learning Representations, 2023.

[14]
Junyuan Hong, Haotao Wang, Zhangyang Wang, and Jiayu Zhou.
Federated robustness propagation: Sharing adversarial robustness in
federated learning.
arXiv preprint arXiv:2106.10196, 2021.

[15]
Jonathan J. Hull.
A database for handwritten text recognition research.
IEEE Transactions on Pattern Analysis and Machine Intelligence,
16(5):550–554, May 1994.

[16]
Justin Khim and Po-Ling Loh.
Adversarial risk bounds via function transformation.
arXiv preprint arXiv:1810.09519, 2018.

[17]
Daniel Kifer, Shai Ben-David, and Johannes Gehrke.
Detecting change in data streams.
In VLDB, volume 4, pages 180–191. Toronto, Canada, 2004.

[18]
Seiichi Kuroki, Nontawat Charoenphakdee, Han Bao, Junya Honda, Issei Sato, and
Masashi Sugiyama.
Unsupervised domain adaptation based on source-guided discrepancy.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 33, pages 4122–4129, 2019.

[19]
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.
Gradient-based learning applied to document recognition.
Proceedings of the IEEE, 86(11):2278–2324, November 1998.

[20]
Michel Ledoux and Michel Talagrand.
Probability in Banach Spaces: Isoperimetry and Processes.
Springer Science & Business Media, 2013.

[21]
Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan.
Learning transferable features with deep adaptation networks.
In International conference on machine learning, pages 97–105.
PMLR, 2015.

[22]
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and
Adrian Vladu.
Towards deep learning models resistant to adversarial attacks.
International Conference on Learning Representations, 2018.

[23]
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.
Domain adaptation: Learning bounds and algorithms.
arXiv preprint arXiv:0902.3430, 2009.

[24]
Pascal Massart.
Some applications of concentration inequalities to statistics.
In Annales de la Faculté des sciences de Toulouse:
Mathématiques, volume 9, pages 245–303, 2000.

[25]
Mehryar Mohri and Andres Muñoz Medina.
New analysis and algorithm for learning with drifting distributions.
In International Conference on Algorithmic Learning Theory,
pages 124–138. Springer, 2012.

[26]
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.
Foundations of machine learning.
MIT press, 2018.

[27]
Omar Montasser, Steve Hanneke, and Nathan Srebro.
Vc classes are adversarially robustly learnable, but only improperly.
In Conference on Learning Theory, pages 2512–2530. PMLR, 2019.

[28]
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y.
Reading digits in natural images with unsupervised feature learning.
In NIPS Workshop on Deep Learning and Unsupervised Feature
Learning 2011, 2011.

[29]
Muni Sreenivas Pydi and Varun Jog.
The many faces of adversarial risk.
arXiv preprint arXiv:2201.08956, 2022.

[30]
Joaquin Quinonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D
Dataset shift in machine learning.
Mit Press, 2008.

[31]
Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada.
Maximum classifier discrepancy for unsupervised domain adaptation.
In Proceedings of the IEEE conference on computer vision and
pattern recognition, pages 3723–3732, 2018.

[32]
Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry.
Do adversarially robust imagenet models transfer better?
Advances in Neural Information Processing Systems,
33:3533–3545, 2020.

[33]
Ali Shafahi, Parsa Saadatpanah, Chen Zhu, Amin Ghiasi, Christoph Studer, David
Jacobs, and Tom Goldstein.
Adversarially robust transfer learning.
arXiv preprint arXiv:1905.08232, 2019.

[34]
Joel A Tropp et al.
An introduction to matrix concentration inequalities.
Foundations and Trends® in Machine Learning,
8(1-2):1–230, 2015.

[35]
Dong Yin, Ramchandran Kannan, and Peter Bartlett.
Rademacher complexity for adversarially robust generalization.
In International conference on machine learning, pages
7085–7094. PMLR, 2019.

[36]
Kaichao You, Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I Jordan.
Universal domain adaptation.
In Proceedings of the IEEE/CVF conference on computer vision and
pattern recognition, pages 2720–2729, 2019.

[37]
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan.
Bridging theory and algorithm for domain adaptation.
In International Conference on Machine Learning, pages
7404–7413. PMLR, 2019.

[38]
Yuchen Zhang, Mingsheng Long, Jianmin Wang, and Michael I Jordan.
On localized discrepancy for domain adaptation.
arXiv preprint arXiv:2008.06242, 2020.

§ USEFUL LEMMAS

In this section, we present necessary lemmas that are used further in the proof of our main results.

§.§ Matrix concentration inequality

Let us denote by $\norm{.}_2$ the spectral norm of matrix.
Consider a finite sequence of $n$ independent, random matrices $\mZ_i$ with common dimension $d_1 \times d_2$.
Assume that

\begin{equation*}
% \EE[\sigma]{\mZ_i}
\EE{\mZ_i} = 0 \quad \text{and} \quad \norm{\mZ_i}_2 \leq L, \quad \forall i \in [n] \enspace.
\end{equation*}

Let $\mY \eqdef \sum_{i=1}^n \mZ_i$. Then,

\begin{equation}
\label{eq:matrix_bernstein_inequality}
\EE{\norm{\mY}_2} = \EE{\norm{\sum_{i=1}^n \mZ_i}_2} \leq \sqrt{2 \Var (\mY) \log (d_1 + d_2)} + \frac{1}{3} L \log (d_1 + d_2) \enspace,
\end{equation}

where the matrix variance is given by

\begin{align*}
\Var(\mY) \eqdef& \max \left\{ \norm{\EE{\mY \mY^\top}}_2, \norm{\EE{\mY^\top \mY}}_2 \right\} \\
=& \max \left\{ \norm{\sum_{i=1}^n \EE{\mZ_i \mZ_i^\top}}_2, \norm{\sum_{i=1}^n \EE{\mZ_i^\top \mZ_i}}_2 \right\} \, .
\end{align*}

§.§ Basic lemmas

For any vector $a, b$, we have that $\displaystyle \norm{a-b}_2^2 \leq 2 \norm{a}_2^2 + 2 \norm{b}_2^2$.

Let $p \in \R$ such that $1 < p < \infty$. Let $p^*$ be its conjugate, that is if $1 < p < \infty$, $p^*$ is such that $\frac{1}{p} + \frac{1}{p^*} = 1$.
Let $\bv, \bw \in \R^d$, then the following inequality holds

\begin{equation*}
|\inprod{\bv}{\bw}| \leq \norm{\bv}_p \norm{\bw}_{p^*} \enspace.
\end{equation*}

If $p=1$, we set $p^* = \infty$.

Let $q > p \geq 1$, then for all $\bv \in \R^d$ we have $\norm{\bv}_q \leq \norm{\bv}_p \leq d^{1/p - 1/q} \norm{\bv}_q$.
It also holds for $q= \infty$, that is $\norm{\bv}_{\infty} \leq \norm{\bv}_p \leq d^{1/p} \norm{\bv}_{\infty}$.

The $\ell_{\infty}$ and $\ell_1$ norms are duals of each other. That is:

\begin{equation}
\max_{\norm{x}_{\infty} \leq \epsilon} z^\top x = \epsilon \norm{z}_1 \enspace,
\end{equation}

and this maximum is attained for $x^* = \epsilon \sgn (z)$, where $\sgn$ denotes the element-wise sign function.

Hölder inequality implies that for all $z, x \in \real^p$,

\begin{equation*}
z^\top x \leq |z^\top x| \leq \norm{x}_{\infty} \norm{z}_1 \leq \epsilon \norm{z}_1 \enspace.
\end{equation*}

Finally, we notice this upper bound is reached for $x^* = \epsilon \sgn (z)$ as

\begin{equation*}
z^\top x^* = \epsilon z^\top \sgn (z) = \epsilon \sum_{i=1}^p z_i \sgn (z_i) = \epsilon \norm{z}_1 \enspace.
\end{equation*}

Let $z \in \R^d$, the solution of

\begin{equation}
\min_{\norm{x}_{\infty} \leq \epsilon} z^\top x = - \epsilon \norm{z}_1 \enspace,
\end{equation}

is attained at $x^* = - \epsilon \sgn (z)$.

Same reasoning as in <Ref>.

Let $z \in \R^d$, the solution of

\begin{equation}
\label{eq:lower_bound_min_quadratic_over_infinity_ball}
\min_{\norm{x}_{\infty} \leq \epsilon} \inprod{u}{x} \inprod{v}{x}
\geq - \epsilon^2 \norm{u}_1 \norm{v}_1\enspace,
\end{equation}

Let $x \in B_{\infty} (0_d, \epsilon)$ which denotes the $\ell_{\infty}$ centered ball of radius $\epsilon > 0$.
Hölder's inequality for dual norms applied twice gives us:

\begin{equation*}
|\inprod{u}{x} \inprod{v}{x}| \leq \norm{x}_{\infty}^2 \norm{u}_1 \norm{v}_1 \leq \epsilon^2 \norm{u}_1 \norm{v}_1 \enspace,
\end{equation*}

which directly implies that

\begin{equation*}
\min_{\norm{x}_{\infty} \leq \epsilon} \inprod{u}{x} \inprod{v}{x}
\geq - \epsilon^2 \norm{u}_1 \norm{v}_1 \enspace.
\end{equation*}

We make several comments on the above <Ref>:

* Note that if $v = u$, then the objective becomes positive and $0$ is a simpler and sharp lower bound as it is reached for $x=0_d$.

* Else if $v = -u$, then applying <Ref> implies that the minimum is reached and equals $- \epsilon^2 \norm{u}_1 ^2$ which means the lower bound in (<ref>) is sharp.

* Else if $v \bot u$, then one should be able to prove that the minimum is reached at something like $x^* = \epsilon \frac{u-v}{\norm{u-v}_{\infty}}$, which correspond to an objective equaling: $\inprod{u}{x^*} \inprod{v}{x^*} = - \epsilon^2 \frac{\norm{u}_2^2 \norm{v}_2^2}{\norm{u-v}_{\infty}^2}$.

We have that

\begin{equation}
\max_{\norm{x}_{\infty} \leq \epsilon} (z^\top x)^2 = \epsilon^2 \norm{z}_1^2 \enspace,
\end{equation}

and this maximum is attained for $x \in \{\epsilon \sgn (z), -\epsilon \sgn (z)\}$, where $\sgn$ denotes the element-wise sign function.

Hölder inequality implies that for all $z, x \in \real^p$,

\begin{equation*}
(z^\top x)^2 \leq \norm{x}_{\infty}^2 \norm{z}_1^2 \leq \epsilon^2 \norm{z}_1^2 \enspace.
\end{equation*}

Finally, we notice this upper bound is reached for $x^* = \pm \epsilon \sgn (z)$ as

\begin{equation*}
(z^\top x^*)^2 = \epsilon^2 (z^\top \sgn (z))^2 = \epsilon^2 \norm{z}_1^2 \enspace.
\end{equation*}

Let $\mA$ be a symmetric matrix, we have that

\begin{align*}
\sup_{\norm{\bw}_2 \leq W, \norm{\bw'}_2 \leq W} \bw^\top \mathbf{A} \bw' = \norm{\mA}_2 \enspace.
\end{align*}

Let $\bw, \bw'$ with $\ell_2-$norm smaller than $W$.
By Cauchy-Schwarz's inequality we directly get that

\begin{equation}
\label{eq:upper_bound_wAwprime}
%\sup_{\bw,\bw' \in B_2 (0, W)}
\bw^\top \mA \bw' \leq |\inprod{\bw}{\mA \bw'}| \overset{\text{Cauchy-Schwarz}}{\leq} \norm{\mA}_2 \norm{\bw}_2 \norm{\bw'}_2 \leq  W^2 \norm{\mA}_2 \enspace.
\end{equation}

We then perform eigendecomposition on $\mA$:

\begin{equation*}
\bw^\top \mA \bw' = \bw^\top \mU \mSigma \mU^\top \bw' = W^2 \by^\top \mSigma \by' \enspace,
\end{equation*}

where $\mSigma$ is a diagonal matrix containing eigenvalues $\lambda_i$'s of $\mA$, $\mU$ is an orthogonal matrix since $\mA$ is symmetric, $\by \eqdef \frac{1}{W} \mU^\top \bw$ and $\by' \eqdef \frac{1}{W} \mathbf{U}^\top \bw'$.
In this orthogonal basis, let $i^*$ be the coordinate of the eigenvalue $\lambda_{i^*}$ with largest magnitude in absolute value.
We denote by $(\be_i)_{i \in [d]}$ the canonical basis of $\R^d$.
Let $\by = \be_{i^*}$ and $\by' = \sgn(\lambda_{i^*}) \by$, we get

\begin{equation*}
\by^\top \mSigma \by' = |\lambda_{i^*}| = \sqrt{\max_{i \in [d]} \lambda_i (\mA)^2} = \sqrt{\lambda_{\max} (\mA^2)} = \norm{\mA}_2 \enspace.
\end{equation*}

Thus, the upper bound in (<ref>) is attained by inverting the change of variable from $\by, \by'$ to $\bw, \bw'$.

Let $\mA \in \R^{d\times d}$. Then the following statements hold:

\begin{equation}
\label{eq:upper_bound_quadratic_form_norm_equiv_p_2}
\sup_{\|\bw\|_p \leq W,\|\bw'\|_p \leq W}  \bw^\top \mA \bw' \leq \sup_{\|\bw\|_2 \leq W,\|\bw'\|_2 \leq W} \bw^\top \mA \bw' \cdot
\begin{cases}
1, &\text{if } 1 \leq p \leq 2\\
d^{1-2/p}, & \text{else if } p > 2
\end{cases}
\enspace,
\end{equation}

\begin{equation}
\label{eq:lower_bound_quadratic_form_norm_equiv_p_2}
\sup_{\|\bw\|_p \leq W,\|\bw'\|_p \leq W}  \bw^\top \mA \bw' \geq  \sup_{\|\bw\|_2 \leq W,\|\bw'\|_2 \leq W} \bw^\top \mA \bw' \cdot
\begin{cases}
d^{1-2/p}, & \text{if } 1 \leq p \leq 2 \\
1, \quad  & \text{else if } p > 2
\end{cases}
\enspace.
\end{equation}

We begin with proving the first inequality. If $1 \leq p \leq 2$, we know that:

\begin{align*}
\cB_p(W) \subseteq \cB_2(W).
\end{align*}

Hence $\sup_{\|\bw\|_p \leq W,\|\bw'\|_p \leq W}  \bw^\top \mA \bw' \leq \sup_{\|\bw\|_2 \leq W,\|\bw'\|_2 \leq W} \bw^\top \mA \bw'$.

If $p > 2$, since $\frac{1}{d^{1/2-1/p}}\|\bw\|_2 \leq \|\bw\|_p $, we know that $\|\bw\|_p \leq W$ implies $\frac{1}{d^{1/2-1/p}}\|\bw\|_2 \leq W$. So we have:

\begin{align*}
\cB_p(W) \eqdef \{\bw : \norm{\bw}_p \leq W\} \subseteq \{\bw: \frac{1}{d^{1/2-1/p}}\|\bw\|_2 \leq W\}
\subseteq \cB_2(W d^{1/2-1/p}).
\end{align*}

\begin{align*}
\sup_{\|\bw\|_p \leq W,\|\bw'\|_p \leq W} \bw^\top \mA \bw' &\leq \sup_{\|\bw\|_2 \leq  Wd^{1/2-1/p},\|\bw'\|_2 \leq  W d^{1/2-1/p}} \bw^\top \mA \bw' \\
&\leq \sup_{\|\bw\|_2 \leq  W,\|\bw'\|_2 \leq   W} \bw^\top \mA \bw' \cdot d^{1-2/p} \enspace.
\end{align*}

Now we switch to prove the second inequality.
If $1 \leq p \leq 2$, then $\|\bw\|_2 \geq \frac{1}{d^{1/p -1/2}} \|\bw\|_p$, so we know

\begin{align*}
\cB_2 (W) \eqdef \{\bw : \norm{\bw}_2 \leq W\} \subseteq \{\bw: \frac{1}{d^{1/p -1/2}}\|\bw\|_p \leq W\}
= \cB_p(d^{1/p -1/2} W  ).
\end{align*}

\begin{align*}
\sup_{\|\bw\|_2 \leq W,\|\bw'\|_2 \leq W}  \bw^\top \mA \bw' &\leq \sup_{\|\bw\|_p \leq d^{1/p -1/2} W ,\|\bw'\|_p \leq d^{1/p -1/2} W } \bw^\top \mA \bw' \\
&\leq d^{2/p - 1} \sup_{\|\bw\|_p \leq  W,\|\bw'\|_p \leq   W} \bw^\top \mA \bw' \enspace.
\end{align*}

If $p > 2$, then we have

\begin{align*}
\cB_2(W) \subseteq \cB_p(W),
\end{align*}

so we can conclude the relation:

\begin{align*}
\sup_{\|\bw\|_2 \leq W,\|\bw'\|_2 \leq W}  \bw^\top \mA \bw'  \leq  \sup_{\|\bw\|_p \leq  W,\|\bw'\|_p \leq   W} \bw^\top \mA \bw'  .
\end{align*}

Let us define $\cA\eqdef\{-1,+1\}^N$. Then, there must be an equal partition of $\cA = \cA^+ + \cA^-$, such that $\cA^-$ is obtained by multiplying $-1$ on each vector in $\cA^+$. That is, $|\cA^+| = |\cA^-|$ and $\cA^- = \{-\ba, \ba \in \cA^+ \}$.

We prove by induction.
When $N=1$, we have $\cA_1 = \{-1,1\}$, and we can partition it as $\cA^+ = \{1\}$, and $\cA^- = \{-1\}$;

The we assume the hypothesis holds for $N=k$, that is, $\cA_k\eqdef\{-1,+1\}^k$ can be partition as $\cA_k = \cA^+_k + \cA^-_k$ such that $|\cA^+_k| = |\cA^-_k|$ and $\cA^-_k = \{-\ba, \ba \in \cA^+_k \}$. Now, for $N=k+1$, we append all vectors $\ba \in \cA^+_k$ by $1$, and put $[\ba^\top, 1]$ into $\cA^+_{k+1}$ and append all vectors $\ba \in \cA^-_k$ by $-1$, and put $[\ba^\top, -1]$ into $\cA^-_{k+1}$. It can be verify that, $|\cA^+_{k+1}| = |\cA^-_{k+1}|$ and  $\cA^-_{k+1} = \{-\ba, \ba \in \cA^+_{k+1} \}$.

§.§ Quadratic objective subject to infinite norm constraint

Let $\bw \in \real^p$, $a \in \real$ and $\epsilon \geq 0$.
Let us consider the problem

\begin{equation*}
\bdelta^* = \argmax_{\bdelta \in \real^p : \norm{\bdelta}_\infty\leq \epsilon} (\bw^{\top} \bdelta + a)^2 \enspace.
\end{equation*}

The solution is given by

\begin{equation}
\label{eq:local_delta_star_max}
\bdelta^* = \epsilon \sgn (a) \sgn (\bw) \in \real^p \enspace,
\end{equation}

where we overload the notation $\sgn$ denotes in the mean time a single element and a coordinate wise sign operator, i.e., $\sgn (a) \in \real$ but $\sgn (\bw) \in \real^p$.
Moreover, the maximum reached is

\begin{equation}
\label{eq:objective_at_delta_star}
(\bw^T \bdelta^* + a)^2 = ( \epsilon \sgn (a) \bw^T \sgn (\bw) + a)^2 = (\epsilon \norm{\bw}_1 + |a|)^2 \enspace.
\end{equation}

Let us give a first intuition and proof in dimension one and then extend this to larger dimensions.

* Case $p = 1$ ($\bw$ becomes $w$).
In this setting the problem intuition is clear: one should select $\bdelta$, with maximal amplitude, that makes $\bdelta w$ having the same sign as $a$.
If $a$ and $w$ have the same sign, then $\bdelta = \epsilon$.
Else, $\bdelta = -\epsilon$.

* Case $p \in \mathbb{N}^*$.

For all $\bw, \delta \in \real^p$, Hölder inequality gives that

\begin{equation*}
|\bw^\top \delta| \leq \norm{\delta}_{\infty} \norm{\bw}_1 \enspace.
\end{equation*}

Let $\bdelta \in \real^p$ such that $\norm{\bdelta}_{\infty} \leq \epsilon$.
Then, this implies that on the feasible set

\begin{equation}
\label{eq:dotprod_l1_upper_bound}
|\bw^\top \delta| \leq \epsilon \norm{\bw}_1 \enspace.
% \bw^\top \bdelta = \sum_{j=1}^p \bdelta_j \bw_j \leq \sum_{j=1}^p | \bdelta_j \bw_j | \leq \epsilon \norm{\bw}_1 \enspace.
\end{equation}

\begin{align*}
(\bw^T \bdelta + a)^2 &= (\bw^T \bdelta)^2 + 2 a \bw^T \bdelta + a^2 \\
&\overset{\eqref{eq:dotprod_l1_upper_bound}}{\leq} \epsilon^2 \norm{\bw}_1^2 + 2 a \bw^T \bdelta + a^2 \\
&\leq \epsilon^2 \norm{\bw}_1^2 + 2 |a| |\bw^T \bdelta | + a^2 \\
&\overset{\eqref{eq:dotprod_l1_upper_bound}}{\leq} \epsilon^2 \norm{\bw}_1^2 + 2 |a| \epsilon \norm{\bw}_1 + a^2 \\
&= (\epsilon \norm{\bw}_1 + |a|)^2 \enspace.
\end{align*}

Finally, one can check that upper bound of the objective is attained for $\bdelta^*$ given in (<ref>).

Let $\bw \in \real^p$, $a \in \real$ and $\epsilon \geq 0$.
Let us consider the problem

\begin{equation}
\label{eq:min_quadratic_obj_infinite_constraint}
\bdelta^* = \argmin_{\bdelta \in \real^p : \norm{\bdelta}_\infty\leq \epsilon} (\bw^T \bdelta + a)^2 \enspace.
\end{equation}

Let $I \eqdef \{i \in [p] : \bw_i \neq 0\}$.

* If $\epsilon \norm{\bw}_1 \geq |a|$, then a solution is given by

\begin{equation*}
\begin{cases}
\bdelta_i^* = - \frac{a}{\norm{\bw}_1} \frac{\bw_i}{|\bw_i|} &\quad \quad \forall i \in I \\
\bdelta_i^* = 0 &\quad \quad \forall i \in [p] \backslash I
\end{cases} \enspace .
\end{equation*}

* Else $\epsilon \norm{\bw}_1 < |a|$, and a the solution is given by

\begin{equation*}
\begin{cases}
\bdelta_i^* = - \epsilon \frac{a}{|a|} \frac{\bw_i}{|\bw_i|} &\quad \quad \forall i \in I \\
\bdelta_i^* = 0 &\quad \quad \forall i \in [p] \backslash I
\end{cases} \enspace .
\end{equation*}

This solution can be condensed in the following formulation:

\begin{equation}
\label{eq:condensed_sol_min_quadratic_obj_infinite_constraint}
\begin{cases}
\displaystyle
\bdelta_i^* = - a \frac{w_i}{|w_i|} \min \left\{ \frac{1}{\norm{\bw}_1}, \frac{\epsilon}{|a|}\right\} &\quad \quad \forall i \in I \\
\bdelta_i^* = 0 &\quad \quad \forall i \in [p] \backslash I
\end{cases} \enspace .
\end{equation}

The minimal value is given by:

\begin{align*}
\min_{\bdelta \in \real^p : \norm{\bdelta}_\infty\leq \epsilon} (\bw^T \bdelta + a)^2  = a^2\left(1- \min\left\{1, \frac{ \epsilon \|\bw\|_1}{|a|}\right\}   \right)^2.
\end{align*}

Note that in general there are an infinite number of solutions to (<ref>) as in (<ref>) one can choose arbitrarily the value of $\bdelta_i^*$ for all $i \in [p] \backslash I$ (as soon as it is kept smaller than $\epsilon$ in absolute value).

Let $[p] \eqdef \{1, \ldots, p\}$.
Let us try to build a solution which drives the dot product $\bw^\top \bdelta$ towards $-a$.
Let $I \eqdef \{i \in [p] : \bw_i \neq 0\}$.

Case 1: If $\boldsymbol{\epsilon \norm{\bw}_1 \geq |a|.}$
Let us $\bdelta^* \in \real^p$ such that

\begin{equation*}
\begin{cases}
\bdelta_i^* = - \frac{a}{\norm{\bw}_1} \frac{\bw_i}{|\bw_i|} &\quad \quad \forall i \in I \\
\bdelta_i^* = 0 &\quad \quad \forall i \in [p] \backslash I
\end{cases} \enspace .
\end{equation*}

This vector is in the feasible set as $\norm{\bdelta^*}_{\infty} = \max_{i \in I} \frac{|a|}{\norm{\bw}_1} \frac{|\bw_i|}{|\bw_i|} = \frac{|a|}{\norm{\bw}_1} \leq \epsilon$, as assumed.

\begin{equation*}
\bw^T \bdelta^* + a = - \frac{a}{\norm{\bw}_1} \sum_{i \in I} \frac{\bw_i^2}{|\bw_i|} + a = 0 \enspace.
\end{equation*}

This means that if the entries of vector $\bw$ are large enough (in absolute value), we can build a feasible vector $\bdelta^*$ such that the objective in (<ref>) is zero.

Case 2: If $\boldsymbol{\epsilon \norm{\bw}_1 < |a|.}$
Let us $\bdelta^* \in \real^p$ such that

\begin{equation*}
\begin{cases}
\bdelta_i^* = - \epsilon \frac{a}{|a|} \frac{\bw_i}{|\bw_i|} &\quad \quad \forall i \in I \\
\bdelta_i^* = 0 &\quad \quad \forall i \in [p] \backslash I
\end{cases} \enspace .
\end{equation*}

This vector is in the feasible set as $\norm{\bdelta^*}_{\infty} = \max_{i \in I} \epsilon \frac{|a|}{|a|} \frac{|\bw_i|}{|\bw_i|} = \epsilon$, as assumed.

\begin{equation*}
\bw^T \bdelta^* + a = - \epsilon \frac{a}{|a|} \sum_{i \in I} \frac{\bw_i^2}{|\bw_i|} + a = a \underbrace{\left( 1 - \epsilon \frac{\norm{\bw}_1}{|a|} \right)}_{\in [0, 1]} \enspace.
\end{equation*}

This means that if the entries of vector $\bw$ are too small (in absolute value), we can only build a feasible vector $\bdelta^*$ such that $\bw^\top \bdelta^*$ close too $-a$.
And the corresponding objective in (<ref>) becomes $a^2 \left( 1 - \epsilon \frac{\norm{\bw}_1}{|a|} \right)^2$.

Finally, one just can show with Hölder inequality that $(\bw^T \bdelta + a)^2 \geq a^2 \left( 1 - \epsilon \frac{\norm{\bw}_1}{|a|} \right)^2$ for all $\bdelta$ in the feasible set, which concludes the proof.
If $a \geq 0$, the computation follows easily, else we can just replace $\bdelta \leftarrow -\bdelta$ to get back to the former case.

§ CLASSIFICATION LOSS: OTHER ATTEMPTS

Ref: <cit.>.

*** begining ***

July 13th: I suggest that before relaxing the problem, you write it as a Quadratic Program:
Let $\mW \eqdef \bw \bw'^\top$,

\begin{eqnarray*}
&\min_{\mQ \in \R^{p \times p}, \ \bdelta \in \R^d} &\mathbf{Tr}(\mQ \mW) + \bx^\top (\mW^\top + \mW) \bdelta + \bx^T \mW \bx\\
&\text{subject to} \ & \mathbf{e}_i^T \bdelta -\epsilon \leq 0, \quad \forall i \in [p],\\
&& - \mathbf{e}_i^T \bdelta -\epsilon \leq 0, \quad \forall i \in [p],\\
&& \mQ = \bdelta \bdelta^T
\end{eqnarray*}

since easy computations give that $\mathbf{Tr}(\mQ \mW) = \mathbf{Tr}(\bdelta \bdelta^\top \bw \bw'^\top) = \bdelta^\top \bw \bw'^\top  \bdelta$.
*** end ***
For lower bound, we consider the following convex relaxation. Let $\mathbf{W} = \mathbf{w}\mathbf{w}'^T$, and then we have the following SDP relaxation:

\begin{eqnarray*}
&\min_{\mathbf{Q}, \boldsymbol{\delta}} &\mathbf{Tr}(\mathbf{Q}\mathbf{W}) + \boldsymbol{\delta}^T \mathbf{W} \mathbf{x}+ \mathbf{x} \mathbf{W} \boldsymbol{\delta} + \mathbf{x}^T \mathbf{W} \mathbf{x}\\
&\text{subject to} \ & \mathbf{e}_i^T \boldsymbol{\delta} -\epsilon \leq 0, \forall i \in [d],\\
&& \mathbf{Q} \succeq \boldsymbol{\delta}\boldsymbol{\delta}^T
\end{eqnarray*}

July 13th: I would rather use $\mD$ instead of $\mQ$ ($\mD$ or $\Delta$ like Delta $\bdelta$)

- Q1) isn't $\mA$ the same matrix as $\mW?

- Q2) Don't you miss the $p$ constraints $-δ_i ≤ϵ$ ?

Using Schur complement, we can rewrite the constraint and get:
\begin{eqnarray*}
&\min_{\mathbf{Q}\in \mathbb{R}^{d\times d}, \boldsymbol{\delta} \in \mathbb{R}^d} \ &\mathbf{Tr}(\mathbf{Q}\mathbf{W}) + \bx^\top (\mW^\top + \mW) \bdelta  + \mathbf{x}^T \mathbf{W} \mathbf{x}\\
&\text{Subject to:} \  &\mathbf{e}_i^T \boldsymbol{\delta} -\epsilon \leq 0, \forall i \in [d],\\
&&- \mathbf{e}_i^T \bdelta -\epsilon \leq 0, \quad \forall i \in [d],\\
\mathbf{Q} & \boldsymbol{\delta}\\
\boldsymbol{\delta}^T & 1
\end{bmatrix} \succeq  0
\end{eqnarray*}
\paragraph{Trial 1:}

Assuming $$ is positive semidefinite (PSD) (is it still a relaxation ?), we let $𝐳 = 𝐐^-1/2δ$, then we can rewrite the definiteness constraint as:
\begin{align*}
\begin{bmatrix}
\mathbf{Q} & \boldsymbol{\delta}\\
\boldsymbol{\delta}^T & 1
\end{bmatrix}  =  \begin{bmatrix}
\mathbf{Q}^{\frac{1}{2}} & \boldsymbol{0}\\
\boldsymbol{0}^T & 1
\end{bmatrix}  \begin{bmatrix}
\mathbf{I} & \mathbf{z}\\
\mathbf{z}^T & 1
\end{bmatrix}  \begin{bmatrix}
\mathbf{Q}^{\frac{1}{2}} & \boldsymbol{0}\\
\boldsymbol{0}^T & 1
\end{bmatrix} \succeq 0
\end{align*}
We can drop left and right matrices and the relation still holds:
\begin{align*}
\begin{bmatrix}
\mathbf{I} & \mathbf{z}\\
\mathbf{z}^T & 1
\end{bmatrix}  \succeq 0  \iff \|\mathbf{z}\| \leq 1.
\end{align*}
\nid{July 13th: to double check}
So the SDP can be rewritten as:
\begin{eqnarray*}
&\min_{\mathbf{Q} \in S_{+}^d, \mathbf{z}} \ &\mathbf{Tr}(\mathbf{Q}\mathbf{W}) + (\mathbf{Q}^{\frac{1}{2}}\mathbf{z})^T \mathbf{W} \mathbf{x}+ \mathbf{x} \mathbf{W} \mathbf{Q}^{\frac{1}{2}}\mathbf{z} + \mathbf{x}^T \mathbf{A} \mathbf{x}\\
&\text{Subject to:} \  &\mathbf{e}_i^T \mathbf{Q}^{\frac{1}{2}}\mathbf{z} -\epsilon \leq 0, \forall i \in [d],\\
&&\|\mathbf{z}\| \leq 1
\end{eqnarray*}

\paragraph{Trial 2:} Using KKT condition:
The Lagrangian:
\begin{align*}
\mathcal{L}(\mathbf{Q},\boldsymbol{\delta}, \boldsymbol{\mu},\boldsymbol{\nu},\mathbf{Z}) = \mathbf{Tr}(\mathbf{Q}\mathbf{W}) + \bx^\top (\mW^\top + \mW) \bdelta + \mathbf{x}^T \mathbf{W} \mathbf{x} +\sum_{i=1}^d {\mu}_i (\mathbf{e}_i^T \boldsymbol{\delta} - {\epsilon}) +\sum_{i=1}^d  {\nu}_i (-\mathbf{e}_i^T \boldsymbol{\delta} - {\epsilon}) - \left\langle \begin{bmatrix}
\mathbf{Q} & \boldsymbol{\delta}\\
\boldsymbol{\delta}^T & 1
\end{bmatrix}, \mathbf{Z} \right \rangle
\end{align*}
\begin{align*}
\mathbf{Z} = \begin{bmatrix}
\mathbf{S} & \mathbf{u}\\
\mathbf{u}^T & s
\end{bmatrix}
\end{align*}

Taking the derivative w.r.t. each of four variables:
\begin{align*}
&\frac{\partial \mathcal{L}}{\partial \mathbf{Q}} = \mathbf{W} - \frac{\partial tr(
\mathbf{Q} \mathbf{S}+\boldsymbol{\delta} \mathbf{u}^T) +\boldsymbol{\delta}^T\mathbf{u}+s}{\partial \mathbf{Q}} = \mathbf{W} - \mathbf{S} = 0\\
&\frac{\partial \mathcal{L}}{\partial \bdelta} = (\mW^\top + \mW)\bx + \sum_{i=1}^d {\mu}_i \mathbf{e}_i^T   -\sum_{i=1}^d  {\nu}_i \mathbf{e}_i^T  - \frac{\partial tr(
\mathbf{Q} \mathbf{S}+\boldsymbol{\delta} \mathbf{u}^T) +\boldsymbol{\delta}^T\mathbf{u}+s}{\partial \bdelta} =(\mW^\top + \mW)\bx + \sum_{i=1}^d {\mu}_i \mathbf{e}_i^T   -\sum_{i=1}^d  {\nu}_i \mathbf{e}_i^T - 2\mathbf{u} = 0
\end{align*}
primal feasibility:
\begin{align*}
\mathbf{e}_i^T \boldsymbol{\delta} - {\epsilon} \leq 0,\\
-\mathbf{e}_i^T \boldsymbol{\delta} - {\epsilon} \leq 0.
\end{align*}
dual feasibility:
\begin{align*}
\mu_i \geq 0, \nu_i \geq 0, \mathbf{Z} \succeq 0.
\end{align*}
complementary slackness:
\begin{align*}
\sum_{i=1}^d {\mu}_i (\mathbf{e}_i^T \boldsymbol{\delta} - {\epsilon}) = 0,\\
\sum_{i=1}^d  {\nu}_i (-\mathbf{e}_i^T \boldsymbol{\delta} - {\epsilon}) = 0,\\
-\left\langle \begin{bmatrix}
\mathbf{Q} & \boldsymbol{\delta}\\
\boldsymbol{\delta}^T & 1
\end{bmatrix}, \mathbf{Z} \right \rangle = 0.
\end{align*}

\subsection{Maybe junk: QP reformulation}

\nid{I think this* is not a Quadratically Constrained Quadratic Program (QCQP) but rather a simpler Quadratic Program (QP) as the constraints are linear.}
We consider the problem*
\begin{eqnarray}
\label{eq:quadratic_program}
\min_{\bdelta \in \R^p : \|\bdelta\|_\infty\leq \epsilon} (\bx_i+\bdelta)^\top \bw \bw'^\top (\bx_i+\bdelta)
= \underbrace{\bx_i^\top \mQ \bx_i}_{\text{kept as we are interested in the function value}} \ + &\min_{\bdelta \in \R^p} & \bdelta^T \mQ \bdelta + \bc^\top \bdelta\\
&\text{subject to: } &
\mA
\bdelta \preceq \bb \nonumber
\end{eqnarray}
where we defined $'^⊤∈^p ×p$, $(+ ^⊤) ∈^p$, $ _p
-_p  ∈^2p ×p$, $ϵ _p
-_p  ∈^p$ and $≼$ is an component-wise inequality sign.

\nid{Maybe we can separate the optimization over the orthogonal component of $\bw$ and $\bw'$ respectively, depending wheteher they are orthognal.}

This problem in~\eqref{eq:quadratic_program} is NOT exactly a Quadratic Program (QP), with ($2p$) linear constraints as described in
\url{https://en.wikipedia.org/wiki/Quadratic_programming#Problem_formulation}.

Concerning the almost QP in~\eqref{eq:quadratic_program}, we can find
\begin{itemize}
\item an \textbf{upper-bound} by taking a particular point
\item a \textbf{lower-bound} by taking looking at the dual and finding an upper-bound of it (might be hard to find a feasible point for the dual)
\end{itemize}

The dual of the QP is given by
\begin{eqnarray}
\label{eq:dual_quadratic_program}
&\max_{\bdelta \in \R^p} & -\frac{1}{2} \lambda^\top \mA \mQ^{-1} \mA^\top - \lambda^\top b \\
&\text{subject to: } & \lambda \geq 0 \nonumber
\end{eqnarray}
as written in \url{https://en.wikipedia.org/wiki/Quadratic_programming#Lagrangian_duality}.
\nid{Problem: $\mQ = \bw \bw'^\top$ is not invertible, not even symmetric...
Maybe we can symmetrize it by writing $\mQ = \underbrace{\mQ + \mQ^\top}_{\text{symmetric}} - \mQ^\top$

\end{document}