text:
\section{Related Methods and Discussion}
\emph{MaxUp} is closely related
to both data augmentation and adversarial training.
It can be viewed as an \emph{adversarial variant of data augmentation}, in that it minimizes the worse case loss on the perturbed data, instead of an average loss like typical data augmentation methods.
\emph{MaxUp} can also be viewed as a \emph{``lightweight'' variant of adversarial training}, in that
the maximum loss is calculated by simple random sampling, instead of more accurate gradient-based optimizers for finding the adversarial loss,
such as projected gradient descent (PGD);
\emph{MaxUp} is much simpler and faster than the PGD-based adversarial training, and is more suitable for our purpose of alleviating over-fitting on clean data (instead of adversarial defense).
We now elaborate on these connections in depth.

\iffalse
\emph{MaxUp} itself is a kind of data augmentation method, as it minimizes the risk on the augmented data other than the original data. However, instead of minimizing the empirical risk on the augmented data, \emph{MaxUp} only minimizes the risk on the augmented data with the worst performance, which means that \emph{MaxUp} cares more about the worst case performance rather than the average case performance.

Moreover, \emph{MaxUp} can be viewed as a kind of \emph{weak} adversarial training. Adversarial training~\citep{madry2017towards} works by first generating adversarial examples with different attack methods, and then minimize the objective on these virtual samples. Most of the attack methods include solving a constrained optimization problem with gradient-based optimization. \emph{MaxUp} instead, generates some \emph{weak} adversarial examples, by finding samples that have the maximum risk over a set of augmented data. Thus, we term it as \emph{weak} adversarial training. Notice that, the original adversarial training is introduced to improve the robustness. However, \emph{MaxUp} aims at improving the generalization. There are some discussions on the trade-off between the robustness and accuracy~\citep[e.g.][]{zhang2019trades, tsipras2018robustness}, and it can be an interesting topic on how to view this kind of \emph{weak} adversarial training can improve the generalization.

In the section,
we discuss the connections and differences between our method and existing training methods like data augmentation and adversarial training.

\fi
\subsection{Data Augmentation}
Data augmentation has been widely used in machine learning, especially on image data which admits a rich set of invariance transforms (e.g. translation, rotation, random cropping).
Recent augmentation techniques, such as  MixUp~\citep{zhang2018mixup},
CutMix~\citep{yun2019cutmix} and manifold MixUp~\citep{verma2018manifold}
have been found highly useful in training deep neural networks,
especially in achieving state-of-the-art results on important image classification benchmarks such as SVHN, CIFAR and ImageNet.
More recently,
more advanced methods have been developed to
find the optimal data augmentation policies
using reinforcement learning or adversarial generative network~\citep[e.g.][]{cubuk2018autoaugment, cubuk2019randaugment, zhang2019adversarial}.

\emph{MaxUp} can easily leverage these advanced
 data augmentation techniques to achieve good performance.
 The key difference, however, is that \emph{MaxUp} in \eqref{equ:maxup1} minimizes the \emph{maximum loss} on the augmented data, while typical data augmentation methods minimize the \emph{average loss}, that is,

\begin{align}\label{equ:SumUp}

    \min_{\th}\mathbb{E}_{ \x \sim \Dn}
    \left [ \frac{1}{m}\sum_{i=1}^m L(\x_i^\prime,\vv\theta) \right],
\end{align}
which we refer to as \emph{standard data augmentation} throughout the paper.
It turns out \eqref{equ:maxup1} and \eqref{equ:SumUp}
behave very different as regularization mechanisms, in that \eqref{equ:SumUp} does not introduce the gradient-norm regularization as \eqref{equ:maxup1},
and hence does not have the benefit of having gradient-norm regularization.
This is because the first-order term in the Taylor expansion is canceled out due to the averaging in \eqref{equ:SumUp}.

Specifically,
let $\mathbb{P}(\cdot|\x)$ be any distribution whose expectation is $\x$ and $L(\x,\vv\theta)$ is second-order differentiable w.r.t $\x$.
Define the expected loss related to \eqref{equ:SumUp} on data point $\x$:

\begin{align}
    \hat L_{\P, m}(\x, \vv\theta) := \E_{\{\x_i'\}_{i=1}^m\sim \P(\cdot|\x)^m} \left [ \frac{1}{m} \sum_{i=1}^m L(\x_i^\prime,\vv\theta) \right].
\end{align}
Then with a simple Taylor expansion, we have
\begin{align}
    \hat L_{\P, m}(\x, \vv\theta) = \nonumber L(\x,\vv\theta) + \mathbf O(\sigma^2),
\end{align}
which misses the gradient-norm regularization term when compared with \emph{MaxUp} decomposition in Theorem~\ref{thm:smooth_regularization}.

Note that the \emph{MaxUp} update is computationally \emph{ faster} than the
solving \eqref{equ:SumUp} with the same $m$,
because we only need to backpropagate on the worst augmented copy for each data point (see Equation~\ref{equ:grad}),
while solving \eqref{equ:SumUp} requires to backpropagate
on all the $m$ copies at each iteration.
\iffalse
\begin{proof}
This is a simple folklore result.
By Taylor expansion,
\begin{align*}
 & \hat L_{\P, m}(\x, \vv\theta) -  \nonumber L(\x,\vv\theta) \\
    & ~~~~~ =\mathbb{E}_{\{\x_i^\prime\}_{i=1}^m \sim \mathbb{P}(\cdot|\x)^m}\left[ \frac{1}{m} \sum_{i=1}^m (L(\x_i^\prime,\vv\theta)  - L(\x,\vv\theta) )\right]\\

     &~~~~~ = \sigma \mathbb{E}_{z\sim \mathcal{N}(0, I)} \left [\langle \nabla_x L(\x,\vv\theta), z\rangle \right] \\
    &~~~~~~~~~~~~~ + \sigma^2 \mathbb{E}_{z\sim\mathcal{N}(0, I)}\left[ z^\top \nabla_{\x \x} L(\x,\vv\theta)) z\right]+ \mathbf O(\sigma^3)\\
    &~~~~~= \sigma^2 \text{trace}(\nabla_{\x \x} L(\x,\vv\theta)) + \mathbf O(\sigma^3).
\end{align*}
\end{proof}
\fi

\subsection{Adversarial Training}
Adversarial training has been developed to
defense various adversarial attacks on the data inputs \citep{madry2017towards}.
It estimates $\th$ by solving the following problem:
\begin{align}\label{equ:adv}
    \min_\th \mathbb{E}_{\vv{x}\sim \mathcal{D}_n}
    \left [ \max_{\vv x^\prime \in \mathcal{B}(\vv x, r)} L(\x^\prime, \th) \right] ,
\end{align}
where $\mathcal{B}(\x, r)$ represents a ball centered at $\x$ with radius $r$ under some metrics (e.g. $\ell_0$, $\ell_1$, $\ell_2$, or $\ell_{\infty}$ distances). The inner maximization is often solved by running projected gradient descent (PGD) for a number of iterations.

\emph{MaxUp} in \eqref{equ:maxup1}  can be roughly viewed as
solving the inner adversarial maximization problem in \eqref{equ:adv}
using a ``{mild}'', or {``lightweight''}  optimizer by randomly drawing $m$ points from $\P(\cdot | \x)$ and finding the best.
Such mild adversarial optimization increases the robustness against the random perturbation it introduces,
and hence enhance the generalization performance.
Adversarial ideas have also been used to improvement generalization  in a series of recent works \citep[e.g.,][]{xie2019adversarial, zhu2019freelb}.

Different from our method,
typical adversarial training methods, especially these based PGD~\citep{madry2017towards},
tend to
solve the adversarial  optimization much more \emph{aggressively} to achieve higher robustness, but at the cost of scarifying the accuracy on clean data.
There has been shown a clear trade-off between the
accuracy of a classifier on clean data and
its robustness against adversarial attacks \citep[see e.g.,][]{tsipras2018robustness, pmlr-v97-zhang19p, yin2019rademacher, schmidt2018adversarially}.
By using a mild adversarial optimizer, \emph{MaxUp} strikes a better balance between the
accuracy on clean data and adversarial robustness.

Besides,
\emph{MaxUp} is much more computationally efficient than PGD-based adversarial training, because it
does not introduce additional back-propagation steps as PGD.
In practice, \emph{MaxUp} can be equipped with various complex data augmentation methods (in which case $\mathbb{P}(\cdot|\x)$ can be discrete distributions), while PGD-based adversarial training mostly focuses on perturbations in $\ell_p$ balls.

\subsection{Online Hard Example Mining}
Online hard example mining  (OHEM) \citep{shrivastava2016hardmining}
is a training method originally developed for region-based objective detection,
which improves the performance of neural networks by
picking the hardest examples within mini batches of stochastic gradient descent (SGD). It can be viewed as
running SGD for minimizing the following expected loss
$$
\min_{\th}
\E_{\mathcal M}
\left [
\max_{\x\in \mathcal M} L(\x, \th)
\right ],
$$
which amounts to randomly picking a mini-batch $\mathcal M$ at each iteration and minimizing the loss of the hardest example within
$\mathcal M$.
By doing so, OHEM
can focus more on the hard examples and hence improves the  performance on borderline cases. This makes OHEM particularly useful for
class-imbalance tasks, e.g. object detection~\citep{shrivastava2016hardmining}, person re-identification~\citep{luo2019bag}.

Different with \emph{MaxUp},
the hardest examples in OHEM are selected in mini-batches consisting of independently selected examples, with no special correlation or similarity.
Mathematically, it can be viewed as reweighing the data distribution to emphasize harder instances. This is substantially different from \emph{MaxUp}, which is designed to enforce the robustness against existing random data augmentation/perturbation schemes.

\section{Conclusion}
In this paper,
we propose \emph{MaxUp}, a simple and efficient training algorithms for improving generalization,
especially for deep neural networks.
\emph{MaxUp} can be viewed as a introducing a gradient-norm smoothness regularization for Gaussian perturbation, but does not require to evaluate the gradient norm explicitly,  and
can be easily combined with any existing data augmentation methods.
We empirically show that
\emph{MaxUp} can improve the performance of data augmentation methods in image classification, language modeling, and certified defense.
Especially, we achieve SOTA performance on ImageNet.

For future works, we will apply \emph{MaxUp} to more applications and models, such as  BERT~\citep{devlin2018bert}.
Furthermore,
we will generalize \emph{MaxUp} to apply mild adversarial optimization on  feature and label spaces  for other challenging tasks in machine learning, including transfer learning, semi-supervised learning.

\subsection{Maxup as a Smoothness Regularization}
We provide a theoretical interpretation of
Maxup
as introducing a  smoothness regularization.
We consider the special case of
Gaussian data augmentation, that is,
$\mathbb{P}(\cdot|\x) = \normal(\x, \sigma^2 \boldsymbol I)$, where $\sigma^2$ denotes a small variance parameter, and $\boldsymbol I$ the identity matrix.

\red{[Write in a more formal way?]}

For notation, denote by $L(\x, \theta) = \ell(f_\theta(\x), y)$ the loss at point $\x$,
and
\begin{align} \label{equ:Lpm}
\tilde L^{[m]}_\P(\x, \th) := \E_{\{\x_i' \}\sim \P(\cdot ~|~\x)^m} \left [ \max_{i\in [m]}
\ell(f_\th(\x_i'), y)
\right].
\end{align}
the expected Maxup loss at $\x$, with $m$ augmentation.

\begin{theorem}
Let $\mathbb{P}(\cdot|\x) = \normal(\x, \sigma^2 \boldsymbol I)$ and $\tilde L^{[m]}_\P(\x, \theta)$ be defined in \eqref{equ:Lpm}.
Assume $L(\x, \theta)$ is continuously differentiable w.r.t. $\x$.
There exists a constant $c\in (0, \sqrt{2}]$ such that
$$
\tilde L^{[m]}_\P(\x, \th) = L(\x, \th) +
c\sigma\sqrt{\log m} ~ \left \| \nabla_{\x} L(\x,  \th) \right\|_2 + O(\sigma^2).
$$
\end{theorem}

This shows that the Maxup loss can be viewed as introducing a local Lipschitz regularization $\| \nabla_{\x} L(\x,  \th) \|_2$, which encourages the smoothness of $L(\x, \th)$ w.r.t. the input $\x$.

\paragraph{Remark}
Some work are based on direct gradient
norm based regularization (\url{https://openreview.net/forum?id=BkeoqIywz}) Our advantage is lower computational cost, requiring no additional backpropagation.

Theoretical issues of gradient regularizations are discussed in \url{https://arxiv.org/pdf/1808.09540.pdf}, and connection to adversarial robustness are drawn.

\begin{proof}
Using Taylor expansion, we have  (need clean up, write the technical condition for bounding the residual (bounded hessian))
\begin{align*}
    & \mathbb{E}_{\x_i^\prime \sim \mathbb{P}(\cdot|\x)} \max_{i\in [q]} \ell (f_{\th}(\x_i^\prime), y)\\
    = &  \ell(f_{\th}(\x), y) + \mathbb{E}_{\x_i^\prime \sim \mathbb{P}(\cdot|\x)} \max_{i\in [q]} \left[\ell (f_{\th}(\x_i^\prime), y) - \ell(f_{\th}(\x), y)\right]\\
    = & \ell(f_{\th}(\x), y) + \sigma_{\xi} \mathbb{E}_{z_i\sim \mathcal{N}(0, I)} \max_{i\in[q]}\langle \nabla_x \ell(f_{\th}(\x), y), z\rangle \\
    & + \mathcal{O}(\sigma_{\xi}^2),
\end{align*}
where the first term $\ell(f_{\th}(x), y)$ is the empirical risk on clean data, the second term can be viewed as the smooth regularization, due to the  Lemma~\ref{lem:maxGauss} (move the Lemma to appendix?).
\end{proof}

\begin{lemma}\label{lem:maxGauss}
Let $\boldsymbol g$  be a fixed vector in $\R^d$,
and $\{\vv z_i\}$ are i.i.d. random variables from $\normal(0, \sigma^2 \vv I)$. We have
\begin{align*}
    \mathbb{E} \left [ \max_{i\in[q]}\langle \vv g, \vv z_i\rangle \right ]
    = c_{m, \sigma} \| \vv g \|_2,
\end{align*}
where $c_{m, \sigma}= \int XXXX$ (write the explicit formula).
\end{lemma}
\begin{proof}
As $z_i\sim \mathcal{N}(0, I)$, the term $\langle \nabla_x \ell(f_{\th}(\x), y), z_i\rangle$ is a 1-dimensional Gaussian random variable with variance $\|\nabla_x \ell(f_{\th}(x), y)\|^2$. With the expectation of the maximum of Gaussian samples {\color{red} TODO: cite}, we have the desired result.
\end{proof}

\section{Introduction}

A central theme of machine learning
is to alleviate the issue of overfitting,
improving the generalization performance on testing data.
This is often achieved by leveraging important prior knowledge of the models and data of interest.
For example, the
regularization-based methods introduce penalty on the complexity of the model,
which often amount to enforcing certain smoothness properties.
Data augmentation techniques, on the other hand,
leverage important invariance properties of the data
(such as the shift and rotation invariance of images)
to improve performance.
Novel approaches that exploit important knowledge of the models and data hold the potential of substantially improving the performance of machine learning systems.

We propose \emph{MaxUp}, a simple yet powerful training method
to improve the generalization performance
and alleviate the over-fitting issue. Different from standard methods that minimize the average risk on the observed data, \emph{MaxUp} generates a set of random perturbations or transforms of each observed data point, and minimizes the average risk of  the \emph{worst} augmented data of each data point.
This allows us to enforce robustness against the random perturbations and transforms,
and hence improve the generalization performance. \emph{MaxUp} can easily leverage arbitrary  state-of-the-art data augmentation schemes \citep[e.g.][]{zhang2018mixup, devries2017cutout, cubuk2018autoaugment}, and substantially improves  over them
by minimizing the worst (instead of average) risks on the augmented data, without adding significant computational ahead.

Theoretically,
in the case of Gaussian perturbation,
we show that
\emph{MaxUp} effectively introduces
a \emph{gradient-norm regularization term} that serves to encourage smoothness of the loss function,
which does not appear in  standard data augmentation methods that minimize the average risk.

\emph{MaxUp} can be viewed as a ``lightweight'' variant of adversarial training against adversarial input pertubrations \citep[e.g.][]{tramer2017ensemble, madry2017towards},
but is mainly designed to improve the generalization on the clean data, instead of robustness on perturbed data (although \emph{MaxUp} does also increase the adversarial robustness in Gaussian adversarial certification as we shown in our experiments (Section~\ref{sec:adversarial})).
In addition,
compared with standard adversarial training methods such as projected gradient descent (PGD) \citep{madry2017towards},
\emph{MaxUp} is
much simpler and computationally much faster, and can be easily adapted to increase various  robustness defined by the corresponding data augmentation schemes.

We test \emph{MaxUp} on three challenging tasks: image classification, language modeling, and certified defense  against adversarial examples~\citep{cohen2019certified}.
We find that \emph{MaxUp} can leverage the
different state-of-the-art
 data augmentation methods and boost their performance to achieve new state-of-the-art on a range of tasks, datasets, and neural architectures.
In particular,
we set up a new state-of-the-art result on ImageNet classification without extra data,
which improves the best $85.5\%$ top1 accuracy
 by \citet{xie2019adversarial} to $85.8\%$.
For the adversarial certification task, we find \emph{Maxup} allows us to train more verifiably robust classifiers than
prior arts such as the PGD-based adversarial training proposed by \citet{salman2019provably}.

\section{Main Method}
\label{sec:method}
We start with introducing the main idea of \emph{MaxUp}, and then discuss its effect of introducing smoothness regularization in Section~\ref{sec:smooth}.

\paragraph{ERM}
Giving a dataset $\Dn =\{\x_i\}_{i=1}^n$,
learning often reduces to a form of
empirical risk minimization (ERM):
\begin{align}
\min_{\th} \E_{\x\sim\Dn} \left [L(\x, \vv\theta) \right],
\end{align}
where $\th$ is a parameter of interest (e.g., the weights of a neural network), and $L(\x, \vv\theta)$ denotes the loss associated with data point $\x$.
A key issue of ERM is the risk of overfitting,
especially when the data information is insufficient.

\paragraph{\emph{MaxUp}}
We propose \emph{MaxUp} to alleviate overfitting.
The idea is to generate a set of random augmented data and minimize the maximum loss over the augmented data.

Formally, for each data point $\x$ in $\Dn$,
we generate a set of perturbed data points $\{\x_i'\}_{i=1}^m$ that are similar to $\x$, and estimate $\th$
by minimizing the maximum loss over $\{\x_i'\}$:
\begin{align}\label{equ:maxup1}
\text{\emph{MaxUp:}} &&   \min_{\th}
\mathbb{E}_{\x\sim \Dn}
    \left [ \max_{i\in [m]} L(\x_i^\prime, \th)

    \right].
\end{align}
This loss can be easily minimized with stochastic gradient descent (SGD). Note that the gradient of the maximum loss is simply the gradient of the worst copy, that is,
\begin{align} \label{equ:grad}
\nabla_{\vv\th} \left(\max_{i\in [m]} L(\x_i^\prime, \th)\right)
= \nabla_{\vv\th} L(\x_{i^*}^\prime, \th),
\end{align}
where $i^* =\argmax_{i\in [m]} L(\x_i^\prime, \th)$.
This yields a simple and practical algorithm shown in Algorithm~\ref{alg:main}.

In our work, we assume the augmented data $\{\x_i'\}_{i=1}^m$ is \emph{i.i.d.} generated from a  distribution $\P(\cdot|\x)$.
The $\P(\cdot|\x)$ can be based on small perturbations around $\x$, e.g., $\P(\cdot|\x) = \normal(\x, \sigma^2 \vv I)$, the Gaussian distribution with mean $\x$ and isotropic variance $\sigma^2$.
The $\P(\cdot |\x)$ can also be
constructed based on invariant data transformations that are widely used in the data  augmentation literature,
such as random crops, equalizing, rotations, and clips for images
\citep[see e.g][]{cubuk2018autoaugment, devries2017cutout, cubuk2019randaugment}.

\subsection{\emph{MaxUp} as a Smoothness Regularization}\label{sec:smooth}
We provide a theoretical interpretation of \emph{Maxup}
as introducing a \emph{gradient-norm regularization} to the original ERM objective to encourage smoothness.
Here we consider the simple case of isotropic Gaussian perturbation, when
$\mathbb{P}(\cdot|\x) = \normal(\x, \sigma^2 \vv I)$.
For simplifying notation, we define
\begin{align} \label{equ:maxup_risk}
\tilde L_{\P, m}(\x, \vv\theta) := \E_{\{\x_i'\}_{i=1}^m\sim \P(\cdot|\x)^m} \left [ \max_{i\in [m]}
L(\x_i^\prime, \vv\theta)
\right],
\end{align}
which represents the expected \emph{MaxUp} risk of data point $\x$ with $m$ augmented copies.

\begin{theorem}[MaxUp as Gradient-Norm Regularization]
Consider $\tilde{L}_{\P, m}(\x, \vv\theta)$ defined in \eqref{equ:maxup_risk} with $\mathbb{P}(\cdot|\x) = \normal(\x, \sigma^2\vv  I)$.
Assume $L(\x, \vv\theta)$ is second-order differentiable w.r.t. $\x$.
Then \begin{align}
\tilde{L}_{\P, m} &(\x, \vv\theta)  = \nonumber L(\x, \vv\theta) + c_{m, \sigma} \left \| \nabla_{\x} L(\x, \vv\theta) \right\|_2 + \mathbf O(\sigma^2),
\end{align}
\label{thm:smooth_regularization}
where $c_{m,\sigma}$ is a constant and
$c_{m, \sigma} =\mathbf \Theta( \sigma \sqrt{\log m})$, where $\mathbf \Theta(\cdot)$ denotes the big-Theta notation.

\end{theorem}

Theorem \ref{thm:smooth_regularization} shows that, the expected \emph{MaxUp} risk can be viewed as introducing a
Lipschitz-like regularization with the gradient norm $\|\nabla_x L(\x,\vv\theta)\|_2$, which encourages the smoothness of $L(\x,\vv\theta)$ w.r.t. the input $\x$.
The strength of the regularization is controlled by $c_{m,\sigma}$, which depends on the number of samples $m$ and perturbation magnitude  $\sigma$.
\begin{proof}
Using Taylor expansion, we have
\begin{align*}
    & \tilde L_{\mathbb{P},m}(\x, \th)  \\
    &=
    \
    \left [\max_{i\in [m]} L (\x_i^\prime, \vv\theta) \right ]\\
    & = L (\x, \vv\theta) + \mathbb{E
    \left [ \max_{i\in [m]} \left(L (\x_i^\prime, \vv\theta) - L (\x, \vv\theta)\right) \right ]\\
     &= L(\x,\vv\theta) +  \mathbb{E
     \left[ \max_{i\in[q]}\langle \nabla_{\x} L(\x,\vv\theta), \vv z_i\rangle \right]+ \mathbf O(\sigma^2),
\end{align*}
where we assume $\vv z_i = \x_i' - \x$, which follows $\normal(0, \sigma^2 \vv I)$.
The rest of the proof is
due to the Lemma~\ref{lem:maxGauss} below.
\end{proof}

\begin{lemma}\label{lem:maxGauss}
Let $\vv g$  be a fixed vector in $\R^d$,
and $\{\vv z_i\}_{i=1}^m$ are $m$ i.i.d. random variables from $\normal(0, \sigma^2 \vv I)$.
We have
\begin{align*}
    \mathbb{E} \left [ \max_{i\in[m]}\langle \vv g, \vv z_i\rangle \right ]
    = c_{m, \sigma} \|\vv g\|_2,
\end{align*}
where $c_{m, \sigma}
= \mathbf \Theta\left (\sigma \sqrt{\log m}\right).$

\end{lemma}
\begin{proof}
Define $y_i = \langle \vv g, \vv z_i\rangle/\norm{\vv g}_2$.
Then $\{y_i\}_{i=1}^m$ is \emph{i.i.d.} from $\normal(0, \sigma^2)$.
Therefore, $c_{m,\sigma}=\E[\max_{i\in [m]} y_i]$,
which is well known to be $\mathbf \Theta(\sigma\sqrt{\log m})$.
See e.g., \citet{orabona2015optimal, kamath2015bounds} for bounds related to $\E[\max_{i\in [m]} y_i]$.
More specifically,
we have
$0.23\sigma \sqrt{\log m} \leq  c_{m,\sigma} \leq \sqrt{2}\sigma \sqrt{\log m}$ following \citet{kamath2015bounds}.
\end{proof}

\section{Experiments}

We  test our method using both image classification and language modeling
for which
a variety of strong regularization techniques and data augmentation methods have been proposed.
We show that
\emph{MaxUp} can outperform all of these methods on the most
challenging datasets (e.g. ImageNet, Penn Treebank, and Wikitext-2) and  state-of-the-art models (e.g. ResNet, EfficientNet, AWD-LSTM).
In addition, we apply our method to adversarial certification
 via Gaussian smoothing \citep{cohen2019certified},  for which we find that \emph{MaxUp} can outperform both the augmented data baseline and PGD-based adversarial training baseline.

For all the tasks, if training from scratch, we first train the model with standard data augmentation with 5 epochs and then switch to \emph{MaxUp}.

\paragraph{Time and Memory Cost}
\emph{MaxUp} only slightly increase the time and memory cost compared with standard training.
During \emph{MaxUp},
we only need to find the worst instance out of the $m$ augmented copies through forward-propagation, and
then
only back-propagate on the worst instance.
Therefore, the additional cost of \emph{MaxUp} over standard training is $m$ forward-propagation,
which
introduces no significant overhead on both memory and time cost.

\subsection{ImageNet}
We evaluate \emph{MaxUp} on  ILSVRC2012, a subset of ImageNet classification dataset~\citep{deng2009imagenet}.
This dataset contains around 1.3 million training images and 50,000 validation images.
We follow the standard data processing pipeline including scale and aspect ratio distortions, random crops, and horizontal flips in training. During the evaluation, we  only use the single-crop setting.

\begin{table}[t]
    \centering
    \begin{tabular}{l|cc}
        \hline
        Method & Top-1 error & Top-5 error \\
        \hline
        Vanilla\tiny{~\citep{he2016resnet}} & 76.3 & - \\
        \hline
        Dropout\tiny{~\citep{srivastava2014dropout}} & 76.8 & 93.4 \\
        DropPath\tiny{~\citep{larsson2016fractalnet}} & 77.1 & 93.5 \\
        Manifold Mixup\tiny{~\citep{verma2018manifold}} & 77.5 & 93.8 \\
        AutoAugment\tiny{~\citep{cubuk2018autoaugment}} & 77.6 & 93.8 \\
        Mixup\tiny{~\citep{zhang2018mixup}} & 77.9 & 93.9 \\
        DropBlock\tiny{~\citep{ghiasi2018dropblock}} & 78.3 & 94.1 \\
        CutMix\tiny{~\citep{yun2019cutmix}} & 78.6 & 94.0 \\
        \hline
        \emph{MaxUp}+CutMix & \bf{78.9} & \bf{94.2} \\
        \hline
    \end{tabular}
    \caption{Summary of top1 and top5 accuracies on the validation set of ImageNet for ResNet-50.}
    \label{tab:resnet50}
\end{table}

\begin{table*}[h]
    \centering
    \begin{tabular}{l|c|c|cc}
        \hline
        Model & Model Size & FLOPs & +CutMix  (\%) & +\emph{MaxUp}+CutMix (\%)\\
        \hline

        ResNet-101 & 44.55M & 7.85G & 79.83 & \bf{80.26} \\
        \hline
        ProxylessNet-CPU & 7.12M & 481M & 75.32 & \bf{75.65} \\
        ProxylessNet-GPU & 4.36M & 470M & 75.08 & \bf{75.42} \\
        ProxylessNet-Mobile $\times 1.4$ & 6.86M & 603M & 76.71 & \bf{77.17} \\
        \hline
        EfficientNet-B7 & 66.35M & 38.20G & ~85.22$^*$ & ~\bf{85.45}$^*$ \\
        Fix-EfficientNet-B8 & 87.42M & 101.79G & ~85.57$^*$ & ~\bf{85.80}$^*$ \\
        \hline
    \end{tabular}
    \caption{Top1 accuracies of different models on the validation set of ImageNet 2012.
    The ``$*$'' indicates that \emph{MaxUp} is applied to the pre-trained model and trained for $5$ epochs.}

    \label{tab:imagenet}
\end{table*}

\paragraph{Implementation Details}

We test \emph{MaxUp}
with $\P(\cdot|\x)$  defined by
the CutMix  data augmentation technique~\citep{yun2019cutmix} (referred to as \emph{MaxUp}+CutMix).
CutMix randomly cuts and pasts patches among training images, while the ground truth labels are also mixed proportionally to the area of the patches.
\emph{MaxUp}+CutMix applies CutMix on one image for $m$ times (cutting different randomly sampled patches),
and select the worst case to do backpropagation.

We test our method on  ResNet-50, ResNet-101~\citep{he2016resnet}, as well as recent energy-efficient  architectures, including ProxylessNet \citep{cai2018proxylessnas} and EfficientNet~\citep{tan2019efficientnet}.
We resize the images to $600 \times 600$ and $845 \times 845$ for EfficientNet-B7 and EfficientNet-B8, respectively~\citep{tan2019efficientnet},
for which we process the images with the data processing pipelines proposed by \citet{touvron2019fixing}.
For the other models,
the input image size is $224 \times 224$.
To save computation resources,
we only fine-tune the pre-trained models with \emph{MaxUp} for a few epochs.
We set $m = 4$ for \emph{MaxUp} in the ImageNet-2012 experiments unless indicated otherwise. This means that we optimize the worst case in $4$ augmented samples for each image.

For ResNet-50, ResNet-101 and ProxylessNets, we train the models for 20 epochs with learning rate $10^{-5}$ and batch size $256$ on 4 GPUs for 20 epochs.
For EfficientNet, we fix the parameters in the batch normalization layers and train the other parameters with learning rate $10^{-4}$ and batch size 1000 for 5 epochs.

As shown in Table~\ref{tab:imagenet},
for ResNet-50 and ResNet-101, we achieve the best results among all the data augmentation method.
For EfficientNet-B8, we further improve the state-of-the-art result on ImageNet with no extra data.

\paragraph{ResNet-50 on ImageNet}

Table~\ref{tab:resnet50} compares
a number of state-of-the-art
 regularization techniques with
\emph{MaxUp}+CutMix on ImageNet with
 ResNet-50.\footnote{All the FLOPS and model size reported in this paper is calculated by \url{https://pypi.org/project/ptflops}.}
We can see that \emph{MaxUp}+CutMix achieves better performance compared to all the strong data augmentation and regularization baselines.
From Table~\ref{tab:resnet50},
we see that CutMix gives the best top1 error ($78.6\%$) among all the augmentation tasks, but our method further improves  it to $78.9\%$.
DropBlock outperforms all the other methods in terms of the top5 error, but by augmenting CutMix with \emph{MaxUp}, we improve the $94.1\%$ top5 error rate obtained by DropbBlock to $94.2\%$.

\paragraph{More Results on Different Architectures}
 Table~\ref{tab:imagenet} shows the result of ImageNet on
ResNet-101,  ProxylessNet-CPU/GPU/Mobile~\citep{cai2018proxylessnas} and EfficientNet.
We can see that
\emph{MaxUp} consistently improves the results in all these cases.
On ResNet-101, it improves the $79.83\%$ baseline to $80.26\%$.
On ProxylessNet-CPU and ProxylessNet-GPU,
\emph{MaxUp} enhances the $75.32\%$ and $75.08\%$ top1 accuracy to $75.65\%$ and $75.42\%$, respectively.
On ProxylessNet-Mobile, we improve the $76.71\%$ top1 accuracy to $77.17\%$.

For EfficientNet-B7, CutMix enhances the original top1 accuracy $85.0\%$~\citep[by][]{tan2019efficientnet} to $85.22\%$.
\emph{MaxUp} further improves the top1 accuracy to $88.45\%$.
On Fix-EfficientNet-B8, \emph{MaxUp} obtains the state-of-the-art $85.80\%$ top1 accuracy.
The previous state-of-the-art top1 accuracy, $85.50\%$, is achieved by EfficientNet-L2.

\subsection{CIFAR-10 and CIFAR-100}
We test \emph{MaxUp} equipped with Cutout \citep{devries2017cutout} on CIFAR-10 and CIFAR-100,
and denote it by  \emph{MaxUp}+Cutout.
We conduct our method on several  neural architectures, including  ResNet-110~\cite{he2016resnet}, PreAct-ResNet-110~\citep{he2016identity} and WideResNet-28-10~\citep{BMVC2016_87}.
We set $m=10$ for WideResNet and $m=4$ for the other models.
We use the public code\footnote{The code is downloaded from \url{https://github.com/junyuseu/pytorch-cifar-models}}
and keep their hyper-parameters.

\paragraph{Implementation  Details}
For CIFAR-10 and CIFAR-100,
we use the standard data processing pipeline (mirror+ crop) and train the model with 200 epochs.
All the results reported in this section are averaged over five runs.

We train the models for 200 epochs on the training set with 256 examples per mini-batch,
and evaluate the trained models on the test set.
The learning rate starts at 0.1 and is divided by 10 after 100 and 150 epochs for ResNet-110 and PreAct-ResNet-110.
For WideResNet-28-10, we follow the settings in the original paper~\citep{BMVC2016_87}, where the learning rate is divided by 10 after 60, 120 and 180 epochs.
Weight decay is set to $2.5^{-4}$ for all the models, and we do not use dropout.

\begin{table}[t]
    \centering
    \begin{tabular}{c|cc}
        \hline
        Model & + Cutout & + \emph{MaxUp}+Cutout \\
        \hline
        ResNet-110 & 94.84 $\pm$ 0.11 & \bf{95.41 $\pm$ 0.08}\\
        PreAct-ResNet-110 & 95.02 $\pm$ 0.15 & \bf{95.52 $\pm$ 0.06}\\
        WideResNet-28-10 & 96.92 $\pm$ 0.16 & \bf{97.18 $\pm$ 0.06}\\
        \hline
    \end{tabular}
    \caption{Test accuracy on CIFAR10 for different  architectures.}
    \label{tab:cifar10}
\end{table}

\begin{table}[t]
    \centering
    \begin{tabular}{c|cc}
        \hline
        Model & + Cutout & + \emph{MaxUp}+Cutout \\
        \hline
        ResNet-110 & 73.64 $\pm$ 0.15 & \bf{75.26 $\pm$ 0.21}\\
        PreAct-ResNet-110 & 74.37 $\pm$ 0.13 & \bf{75.63 $\pm$ 0.26}\\
        WideResNet-28-10 & 81.59 $\pm$ 0.27 & \bf{82.48 $\pm$ 0.23}\\
        \hline
    \end{tabular}
    \caption{Test accuracy on CIFAR100 for different  architectures.}
    \label{tab:cifar100}
\end{table}

\paragraph{Results}
The results on CIFAR-10 and CIFAR-100 are summarized in Table~\ref{tab:cifar10} and Table~\ref{tab:cifar100}.
We can see that the models trained using \emph{MaxUp}+Cutout significantly outperform the standard Cutout for all the cases.

On CIAFR-10,
\emph{MaxUp} improves the standard Cutout baseline from $94.84\%\pm0.11\%$ to $95.41\%\pm0.08\%$ on ResNet-110.
It also improves the accuracy from $95.02\%\pm0.15\%$ to $95.52\%\pm0.06\%$ on  PreAct-ResNet-110.

On CIFAR-100, \emph{MaxUp} obtains improvements by a large margin.
On ResNet-110 and PreAct-ResNet-110,
\emph{MaxUp} improves the performance of Cutout from $73.64\%\pm0.15\%$ and $74.37\%\pm0.13\%$ to $75.26\%\pm0.21\%$ and $75.63\%\pm0.26\%$, respectively.
\emph{MaxUp}+Cutout also improves the standard Cutout from $81.59\% \pm 0.27\%$ to $82.48\% \pm 0.23\%$ on  WideResNet-28-10  on CIFAR-100.

\paragraph{Ablation Study}
We test \emph{MaxUp} with different sample size $m$ and investigate its impact on the performance on
ResNet-100 (a relatively small model) and WideResNet-28-10 (a larger model).

Table~\ref{tab:abaltion} shows the result when we vary the sample size in $m \in \{1, 4, 10, 20\}$.
Note that \emph{MaxUp} reduces to the na\"ive data augmentation method when $m = 1$.
As shown in Table~\ref{tab:abaltion},
\emph{MaxUp} with all $m>1$ can improve the result of standard augmentation ($m=1$).
Setting $m=4$ or $m=10$ achieves best performance on ResNet-110
, and $m=10$ obtains best performance on WideResNet-28-10.
We can see that the results are not sensitive once $m$ is in a proper range (e.g., $m\in [4:10]$), and it is easy to outperform the standard data augmentation $(m=1)$ without much tuning of $m$.
Furthermore,
we suggest to use a large $m$ for large models, and a small $m$  for  relatively small models.

\begin{table}[t]
    \centering
    \begin{tabular}{c|c|c}
        \hline
        $m$ & ResNet-110 & WideResNet-28-10 \\
        \hline
        1 & 73.64 $\pm$ 0.15 & 81.59 $\pm$ 0.27\\
        4 & 75.26 $\pm$ 0.21 & 81.82 $\pm$ 0.22\\
        10 & 75.19 $\pm$ 0.13 & \bf{82.48 $\pm$ 0.23}\\
        20 & 74.37 $\pm$ 0.18 & 82.43 $\pm$ 0.24\\
        \hline
    \end{tabular}
    \caption{Test accuracy on CIFAR100 with ResNet-110 and
    WideResNet-28-10, when the sample size $m$ varies.}

    \label{tab:abaltion}
    \vspace{-5pt}
\end{table}

\begin{table*}[tbp]
    \begin{center}
    \setlength{\tabcolsep}{1.2em}
        \begin{tabular}{l|c||cc}
            \hline
            Method & \tt Params & Valid & Test \\
            \hline
            NAS-RNN~\citep{zoph2016neural} & 54M & - & 62.40 \\
            AWD-LSTM~\citep{merity2017awd} & 24M & 58.50 & 56.50 \\
            AWD-LSTM + FRAGE~\citep{gong2018frage} & 24M & 58.10 & 56.10 \\
            AWD-LSTM + MoS~\citep{yang2018breaking} & 22M & 56.54 & 54.44\\
            \hline
            \multicolumn{4}{l}{w/o dynamic evaluation} \\
            \hline
            ADV-AWD-LSTM~\citep{wang2019improving} & 24M & 57.15 & 55.01\\
            \bf{ADV-AWD-LSTM + \emph{MaxUp}} & 24M & \bf{56.25} & \bf{54.27}\\
            \hline
            \multicolumn{4}{l}{+~~dynamic evaluation \citep{krause2017dynamic}} \\
            \hline
            ADV-AWD-LSTM~\citep{wang2019improving} & 24M & 51.60 & 51.10\\
            \bf{ADV-AWD-LSTM + \emph{MaxUp}}  & 24M & \bf{50.83} & \bf{50.29}\\
            \hline
        \end{tabular}
    \end{center}
\caption{\label{tab:ptb}
Perplexities on the validation and test sets on the Penn Treebank dataset.  Smaller perplexities refer to better language modeling performance. {\tt Params} denotes the number of model parameters.
}
\end{table*}

\begin{table*}[h]
    \begin{center}
    \setlength{\tabcolsep}{1.2em}
        \begin{tabular}{l|c||cc}
            \hline
            Method & \tt Params & Valid & Test \\
            \hline
            AWD-LSTM~\citep{merity2017awd} & 33M & 68.60 & 65.80 \\
            AWD-LSTM + FRAGE~\citep{gong2018frage} & 33M & 66.50 & 63.40 \\
            AWD-LSTM + MoS~\citep{yang2018breaking} & 35M & 63.88 & 61.45\\
            \hline
            \multicolumn{4}{l}{w/o dynamic evaluation} \\
            \hline
            ADV-AWD-LSTM~\citep{wang2019improving} & 33M & 63.68 & 61.34 \\
            \bf{ADV-AWD-LSTM + \emph{MaxUp}} & 33M & \bf{62.48} & \bf{60.19}\\
            \hline
            \multicolumn{4}{l}{+~~dynamic evaluation \citep{krause2017dynamic}} \\
            \hline
            ADV-AWD-LSTM~\citep{wang2019improving} & 33M & 42.36 & 40.53\\
            \bf{ADV-AWD-LSTM + \emph{MaxUp}}  & 33M & \bf{41.29} & \bf{39.61}\\
            \hline
        \end{tabular}
    \end{center}
\caption{\label{tab:WT2}
Perplexities on the validation and test sets on the WikiText-2 dataset.  Smaller perplexities refer to better language modeling performance. {\tt Params} denotes the number of model parameters. }
\end{table*}

\subsection{Language Modeling}
For language modeling, we test \emph{MaxUp} on two benchmark datasets: Penn Treebank (PTB) and Wikitext-2 (WT2).
We use the code provided by \citet{wang2019improving} as our baseline\footnote{\url{https://github.com/ChengyueGongR/advsoft}}, which stacks a three-layer LSTM
and implements a bag of regularization and optimization tricks
for neural language modeling proposed by \citet{merity2017awd}, such as weight tying, word embedding drop and Averaged SGD.

For this task, we apply \emph{MaxUp} using  word embedding dropout~\citep{merity2017awd} as the random data augmentation method.
Word embedding dropout implements dropout on the embedding matrix at the word level,
where the dropout is broadcasted across all the embeddings of all the word vectors.
For the selected words,
their embedding vectors are set to be zero vectors.
The other word embeddings in the vocabulary are scaled by $\frac{1}{1 - p}$, where $p$ is the probability of embedding dropout.

As the word embedding layer serves as the first layer in a neural language model,
we apply \emph{MaxUp} in this layer.
We do feed-forward for $m$ times and select the worst case to do backpropagation for each given sentence.
In this section, we set a small $m=2$ since the models are already well-regularized by other regularization techniques.

\paragraph{Implement Details}
The PTB corpus~\citep{marcus1993ptb} is a standard dataset  for benchmarking language models. It consists of 923k training, 73k  validation and 82k test words.
We use the processed version provided by \citet{mikolov2010recurrent} that is widely used for PTB.

The WT2 dataset is introduced in  ~\citet{merity2017awd} as an alternative to PTB. It contains pre-processed Wikipedia articles, and the training set contains 2 million words.

The  training  procedure can be decoupled into two stages: 1) optimizing the model with SGD and averaged SGD (ASGD);
2) restarting ASGD for fine-tuning twice.
We apply \emph{MaxUp} in both stages, and report the perplexity scores at the end of the second stage.
We also report the perplexity scores with a recently-proposed post-process method, dynamical evaluation ~\citep{krause2017dynamic} after the training process.

\paragraph{Results on PTB and WT2}
The results on PTB and WT2 corpus are illustrated in Table~\ref{tab:ptb} and Table~\ref{tab:WT2}, respectively.
We calculate the perplexity on the validation and test set for each method to evaluate its performance.
We can see
that \emph{MaxUp}  outperforms the state-of-the-art results achieved by
Frage~\citep{gong2018frage} and Mixture of SoftMax~\citep{yang2018breaking}.
We further compare \emph{MaxUp} to the result of ~\citet{wang2019improving} based on AWD-LSTM~\citep{merity2017awd} at two checkpoints, with or without dynamic evaluation~\citep{krause2017dynamic}.
On PTB, we enhance the baseline from $55.01/51.10$ to $54.27/50.29$ at these two checkpoints on the test set.
On WT2, we enhance the baseline from $61.34/40.53$ to $60.19/39.61$ at these two checkpoints on the test set.
Results on validation set are reported in both Table~\ref{tab:ptb} and \ref{tab:WT2}
to show that the improvement can not achieved by simple hyper-parameter tuning on the test set.

\subsection{Adversarial Certification}
\label{sec:adversarial}
\begin{table*}[htbp]
	\begin{center}
		\begin{tabular}{l|ccccccccccc}
			\hline
            $\ell_2$ RADIUS (CIFAR-10) & $0.25$ & $0.5$ & $0.75$ & $1.0$ & $1.25$ & $1.5$ & $1.75$ & $2.0$ & $2.25$ & $2.5$ & $2.75$ \\
            \hline
            \citet{cohen2019certified} (\%) & 60 & 43 & 34 & 23 & 17 & 14 & 12 & 10 & 8 & 6 & 4\\
            \citet{salman2019provably} (\%) & \bf{74} & \bf{57} & 48 & 38 & 33 & 29 & 25 & 19 & 17 & 14 & 12\\
            \hline
            Ours (\%) & \bf{74} & \bf{57} & \bf{49} & \bf{40} & \bf{35} & \bf{31} & \bf{27} & \bf{22} & \bf{19} & \bf{17} & \bf{15}\\
            \hline
		\end{tabular}
	\end{center}
	\caption{\label{tab:l2-cifar10} \small Certified accuracy on CIFAR-10 of the best classifiers by different methods, evaluated against $\ell_2$ attacks of
	 different radiuses.}
	\label{tab:certified}
\end{table*}

Modern image classifiers are known to be sensitive to small, adversarially-chosen perturbations on inputs~\citep{goodfellow2014explaining}.
Therefore, for making high-stakes decisions,
it is of critical importance to develop methods with \emph{certified robustness}, which
provide (high probability) provable guarantees
on the correctness of the prediction subject to arbitrary attacks within certain perturbation ball.

Recently, \citet{cohen2019certified} proposed
 to construct certifiably robust classifiers against $\ell_2$ attacks
 by introducing Gaussian smoothing on the inputs,

which is shown to outperform all the previous $\ell_2$-robust classifiers in CIFAR-10.
There has been two major methods for training such smoothed classifiers:
\citet{cohen2019certified} trains the classifier with  a Gaussian data augmentation technique, while
\citet{salman2019provably} improves the original Gaussian data augmentation by using PGD (projected gradient descent) adversarial training,
in which PGD is used to find a local maximal within a given $\ell_2$ perturbation ball.

In our experiment,
we use \emph{MaxUp} with Gaussian perturbation (referred to as \emph{MaxUp}+Gauss) to train better smoothed classifiers
than the methods by \citet{cohen2019certified} and \citet{salman2019provably}.
Like how \emph{MaxUp} improves upon standard data augmentation,
it is natural to expect that our \emph{MaxUp}+Gauss can learn more robust classifiers than the standard Gaussian data augmentation method in \citet{cohen2019certified}.

\paragraph{Training Details}
We applied ~\emph{MaxUp} to
Gaussian augmented data on CIFAR-10 with ResNet-110~\citep{he2016resnet}.
We follow the training pipelines described in ~\citet{salman2019provably}.
We set a batch size of 256, an initial learning rate of 0.1 which drops by a factor of 10 every 50 epochs, and train the models for 150 epochs.

\paragraph{Evaluation}
After training the smoothed classifiers,
we evaluation the certified accuracy of different models under different $\ell_2$ perturbation sets.
Given an input image $\boldsymbol{x}$ and a perturbation region $\mathcal{B}$,
the smoothed classifier is called
certifiably correct if its prediction is correct and has a guaranteed lower bound larger than $0.5$ in $\mathcal{B}$.
The certified accuracy is the percentage of images
that are certifiably correct.
Following \citet{salman2019provably},
we calculate the certified accuracy of all the classifiers for various radius and report the best results overall of the classifiers.
We use the codes provided by ~\citet{cohen2019certified} to calculate certified accuracy.\footnote{\url{https://github.com/locuslab/smoothing}}

Following \citet{salman2019provably},
we select the best hyperparameters with grid search.
The only two hyperparameters of our \emph{MaxUp}+Gauss are the sample size $m$ and the variance $\sigma^2$ of the Gaussian perturbation, which we search in
$ m \in \{5, 25, 50, 100, 150\}$ and $\sigma \in \{0.12, 0.25, 0.5, 1.0\}$.
In comparison,
\citet{salman2019provably} requiers to search a larger number of hyper-parameters, including
the number of steps of the PGD,
the number of noise samples,
the maximum $\ell_2$ perturbation,
and the variance of Gaussian data augmentation during training and testing.
Overall, \citet{salman2019provably} requires to train and evaluate  over 150 models for hyperparmeter tuning,
while \emph{MaxUp}+Gauss  requires only 20 models.

\paragraph{Results}
We show the certified accuraries on CIFAR-10 in Table~\ref{tab:certified} under  $\ell_2$ attacks for each $\ell_2$ radius.
We find that \emph{MaxUp} outperforms  \citet{cohen2019certified} for all the $\ell_2$ radiuses by a large margin.
For example, \emph{MaxUp} can improve the certified accuracy at radius $0.25$ from 60\% to 74\% and improve the 4\% accuracy on  radius $2.75$ to 15\%.
\emph{MaxUp}  also outperforms the PGD-based adversarial training of \citet{salman2019provably} for all the radiuses, boosting the accuracy from 14\% to 17\% at radius $2.5$, and from 12\% to 15\% at radius $2.75$.

In summary,
\emph{MaxUp} clearly outperforms both \citet{cohen2019certified}
and
\citet{salman2019provably}.
\emph{MaxUp} is also much faster and requires less hyperparameter tuning than \citet{salman2019provably}.
Although the PGD-based method of \citet{salman2019provably} was designed to outperform the original method by  \citet{cohen2019certified},
\emph{MaxUp}+Gauss further  improves upon \citet{salman2019provably}, likely because \emph{MaxUp} with Gaussian perturbation is more compatible with the Gaussian smoothing based certification of \citet{cohen2019certified} than PGD adversarial optimization.

\subsection{Adversarial Training as Smooth Regularization}

It is worth noticed that, adversarial training can be viewed as a training methods with special data augmentation: the adversarial examples. However, this kind of data augmentation does not aimed at improving the generalization, but for the adversarial robustness. Here, we use the similar idea to show that, when performing adversarial training in $\ell_p$-ball, $p\geq 1$ with small radius $r$, we can view it as introducing an $\ell_q$ regularization of gradient to the original objective, where $\frac{1}{p} + \frac{1}{q} = 1$.

\begin{proposition}[Adversarial Training as Gradient-norm Regularization]
Assume $\ell(f_{\th}(\x), y)$ is second-order differentiable w.r.t $\x$. Define
\begin{align}
    \bar{L}(\x, \vv\theta):=\max_{\|\x^\prime - \x\|_p \leq r} L(\x_i^\prime,\vv\theta).
\end{align}
Then we have that:
\begin{align}
    \bar{L}(\x, \vv\theta) = L(\x,\vv\theta) + r\|\nabla_\x L(\x,\vv\theta)\|_q + \mathcal{O}(r^2).
\end{align}
\end{proposition}

\begin{proof}
With Taylor expansion, we have that:
\begin{align}
    & \bar{L}(\x, \vv\theta) \nonumber\\
    = & L(\x,\vv\theta) + \max_{\|\x^\prime - \x\|_p\leq r}\langle \nabla_{\x} L(\x,\vv\theta), \x^\prime - \x\rangle + \mathcal{O}(\sigma^2)
\end{align}
With Lemma \ref{lem:dual_norm}, we know that the second term is equal to $r\|\nabla_\x L(\x,\vv\theta) \|_q$, that finishes the proof.
\end{proof}
\begin{lemma}
\label{lem:dual_norm}
Assume $g$ is a fixed vector in $\mathbb{R}^d$, then
\begin{align}
    \max_{\|z\|_p\leq 1} \langle g, z\rangle = \|g\|_q.
\end{align}
\end{lemma}
\begin{proof}
This result can be simply derived via the duality of $\ell_p$ norm. We can also use the Lagrangian multiplier, i.e. solve the following optimization problem:
\begin{align}
    \max_{z} \min_{\lambda \geq 0}\langle g, z \rangle - \lambda(\|z\|_p^p - r^p).
\end{align}
Let $g = (g_1, g_2, \cdots, g_d)^\top$ and $z= (z_1, z_2, \cdots, z_d)^\top$. One of the optimal condition for min-max problem is $g - \lambda (z_1^{p-1}, z_2^{p-1}, \cdots, z_d^{p-1}) = 0$. Thus, we can know that when $z = (\frac{1}{\|g\|_q})^{\frac{q-1}{q}}(g_1^{q-1}, g_2^{q-1}, \cdots, g_d^{q-1})^\top$, the original problem $\max_{\|z\|_p\leq 1} \langle g, z\rangle$ get the maximum, which is $\|g\|_q$.
\end{proof}

\subsection{Average Data Augmentation}

\begin{proposition}[AvgUp as Hessian-trace Regularization]
Assume $\mathbb{P}(\cdot|\x) = \mathcal{N}(\x, \sigma^2 I)$ and $L(\x,\vv\theta)$ is third-order differentiable w.r.t $\x$. Define
\begin{align}
    \hat L_{\P, m}(\x, \vv\theta) := \E_{\{\x_i'\}_{i=1}^m\sim \P(\cdot|\x)^m} \left [ \frac{1}{m} \sum_{i=1}^m L(\x_i^\prime,\vv\theta) \right].
\end{align}
\end{proposition}
Then we have
\begin{align}
    \hat L_{\P, m}(\x, \vv\theta) = \nonumber L(\x,\vv\theta) + \sigma^2 \text{trace}(\nabla_{\x \x} L(\x,\vv\theta)) + \mathcal{O}(\sigma^3).
\end{align}
\begin{proof}
This is a simple folklore result.
By Taylor expansion,
\begin{align*}
 & \hat L_{\P, m}(\x, \vv\theta) -  \nonumber L(\x,\vv\theta) \\
    & ~~~~~ =\mathbb{E}_{\{\x_i^\prime\}_{i=1}^m \sim \mathbb{P}(\cdot|\x)^m}\left[ \frac{1}{m} \sum_{i=1}^m (L(\x_i^\prime,\vv\theta)  - L(\x,\vv\theta) )\right]\\

     &~~~~~ = \sigma \mathbb{E}_{z\sim \mathcal{N}(0, I)} \left [\langle \nabla_x L(\x,\vv\theta), z\rangle \right] \\
    &~~~~~~~~~~~~~ + \sigma^2 \mathbb{E}_{z\sim\mathcal{N}(0, I)}\left[ z^\top \nabla_{\x \x} L(\x,\vv\theta)) z\right]+ \mathcal{O}(\sigma^3)\\
    &~~~~~= \sigma^2 \text{trace}(\nabla_{\x \x} L(\x,\vv\theta)) + \mathcal{O}(\sigma^3).
\end{align*}
\end{proof}
This shows that the average loss in \eqref{equ:avgup} tends to penalize the the second order gradient of the loss function, instead of the first order gradient like MaxUp.
Therefore, AvgUp encourages the loss function $L(\x, \th)$ to behave linearly w.r.t. $\x$,
and may not be as effective as the smooth regularization of MaxUp in terms of preventing overfitting.

\section{Related Works}
We review related literatures, including
online hard example mining (OHEM),
data augmentation,
adversarial training.

\textbf{Data Augmentation}\space\space
Recently,
a range of regularization methods have been proposed to enhance the generalization of large deep neural networks.
Among them, MixUp~\citep[e.g.,][]{zhang2018mixup} and its variants are widely used~\citep{he2019bag}.
\red{Many of these?}
These methods force the neural networks to have local linear behaviour.
Some people have tried to ensemble different kinds of data augmentations
and \red{make the networks have better performance}.
\red{~\citet{cubuk2018autoaugment} defines a search space of data augmentation and search the best policy to combine them.
~\citet{cubuk2019randaugment} makes random policy to combine different augmentation. }
~\citet{zhang2019adversarial} proposes adversarial AutoAugment, which finds a policy to maximize the training loss.
This method shares a similar intuition as \emph{MaxUp}.
However, it needs hundreds of GPU hours to search for the policy.

\red{Except for successes in practical algorithms,
some researchers focus on understanding why and how data augmentation can help the generalization.}
\blue{As providing non-i.i.d data,
data augmentation is different from giving more data to the classifier and is hard to analyze.}
\citet{hernandez2018data} views data augmentation as an implicit regularization.
They further show that
data augmentation alone can achieve the same performance or higher as regularized models.
\citet{chen2019invariance} gives a theoretical analysis of data augmentation based on the invariant transformations.
\citet{li2019enhanced} shows CNN Gaussian Process kernels and convolutional neural tangent kernels are equivalent to full \red{translation data augmentation for deep learning.?}
Although some successes have been made, it is still hard to fully understand data augmentation.
Since \emph{MaxUp} has similar attributes as PGD adversarial augmented data,
we may start from analyzing \emph{MaxUp} and then extend it to general data augmentation.\red{what is the point?}

\textbf{Adversarial Training}\space\space
The original idea of adversarial training is to enhance the generalization of augmented adversarial data.

In practice, many works have shown that,
under some conditions,
adversarial training can improve the generalization of clean data, such as \citep{xie2019adversarial}

\citet{xie2019adversarial} uses different batch normalization layers for adversarial and clean data.

By using extra data,
they achieve current state-of-the-art results on ImageNet.

Virtual adversarial training~\citep{miyato2015distributional} generates adversarial augmented data for unlabelled data,
and improve the performance on semi-supervised learning tasks.
\red{repetitive with earlier}
Some researchers build an analysis of the trade-off between the robustness and the generalization of clean data, e.g. \citet{zhang2019trades}.
Some~\citep{raghunathan2019hurt} find out that it can hurt the generalization of clean data but not always.
It is not clear that under which condition,
PGD adversarial training can improve the generalization of clean data. \red{what is the points?}

\section{Error analysis}
We want to discuss the impact of the perturbation measure and the number of sample, by decomposing the gap between training error (with surrogate loss) and testing error (of the original loss).
\subsection{Notation}
Assume $f\in\mathcal{F}$, where $\mathcal{F}$ is the model class. $\ell$ denotes the loss function and the goal of the natural training algorithm is minimizing the empirical risk:
\begin{align*}
    \hat{R} = \mathbb{E}_{(x_i, y_i)\sim \mathcal{D}_n} \ell(f(x_i), y_i)
\end{align*}
where $\mathcal{D}_n$ is the empirical measure of data we use.

In our algorithm, we want to minimize the following surrogate loss based on $\ell$ ({\color{red} maybe called as empirical max risk}):
\begin{align*}
    \hat{R}^\prime = \mathbb{E}_{(x_i, y_i)\sim \mathcal{D}_n} \max_{k\in [q]} \ell(f(\xi_k), y_i)
\end{align*}
where $\xi_k \sim \mathbb{P}(\cdot |x_i)$, and $\mathbb{P}(\cdot |x_i)$ is some probability mass we used to sample data based on $x_i$.

So we want to measure the gap between
\begin{align*}
    R = \mathbb{E}_{(x, y)\sim \mathcal{D}} \ell(f(x_i), y_i)
\end{align*}
and $\hat{R}^\prime$. To do this, we introduce an additional term
\begin{align*}
    R^\prime = \mathbb{E}_{(x, y)\sim \mathcal{D}} \max_{k\in [q]} \ell(f(\xi_k), y_i)
\end{align*}
And bound the two following two terms
\begin{align*}
    G_1 = & R^\prime - \hat{R}^\prime, \\
    G_2 = & R^\prime - R,
\end{align*}
separately. The first term can be viewed as a generalization error, and the second term is a fixed error term that does not depend on the data we use.

We assume the loss is bounded, e.g. in the interval $[0, B]$. Notice that, $\ell (f(\xi_k), y_i)$ is a random variable depends on $f$ and $\mathbb{P}(\cdot|x_i)$, we need to assume some basic property of this random variable (e.g. expectation, concentration).

\begin{assumption}
Given some function class $\mathcal{F}$ and $\mathbb{P}(\cdot |x)$, for all $(x_i, y_i)\sim \mathcal{D}$ and $f\in\mathcal{F}$, we have an uniform upper bound of the tail probability of loss, i.e. $\mathbb{P}(\ell(f(\xi_k), y_i) \geq t)\leq \sigma(t)$, where $\xi_k\sim \mathbb{P}(\cdot|x_i)$.
\end{assumption}

Obviously, we can have a trivial upper bound $\sigma(t) = 1$. However, to make our analysis more meaningful, we assume $\sigma(t)$ is monotonically decreasing with $t$, with $\sigma(0)=1$, $\sigma(B)=0$. [{\color{red}, Notice that as the support of loss is bounded, it's always sub-Gaussian. However, currently it's not clear how to use this property and if it is necessary.}]
\section{Conceptual Examples}
In this section, we want to show how MaxUp can benefit the generalization, with some simple conceptual examples.

\subsection{Linear Binary Classification}

We denote $\mathcal{Y}=\{-1,+1\}$ and let the hypothesis set $\F\in\R^{\mathcal{X}}$
be a set of linear functions for $\x\in\mathcal{X}$. To be specific,
we define $f_{\th}(\x)=\th^{\top}\x$ and set $\F=\{f_{\th}:\left\Vert \th\right\Vert \le R\}$.
The label is predicted by the sign of $f_{\th}(\x)$. We assume the
loss function is
\[
\ell(f_{\th}(\x),y)=\varphi(y\th^{\top}\x),
\]
where $\varphi:\mathbb{R}\to[0,B]$ is monotonically non-increasing
and $L_{\varphi}$-Lipschitz, e.g. the Hinge Loss.

We consider the Gaussian data augmentation, i.e. $\mathbb{P}(\cdot|\x) = \x + \xxi$ where $\xxi\sim\mathcal{N}(0, \sigma_{\xxi}^2 \boldsymbol{I})$.
The function class of MaxUp for this case is:
\begin{align*}

    \tF= & \left\{ f_{\th}(\x):=\E_{\xxi_{[q]}}\min_{\xxi_{i},i\in[q]}\th^{\top}\left(\x+\xxi_{i}\right)y:\left\Vert \th\right\Vert \le R\right\}.
\end{align*}

Here we show that, {\color{red} under some mild assumption}, our method can improve the generalization on the clean data.

\begin{theorem}[Gaussian Adversarial Rademacher Complexity]
\label{thm:weak}
We have that
\begin{align*}
    \Rn[\tF]\le\Rn[\F]+\frac{G_{q,R}}{2\sqrt{n}},
\end{align*}

where
\begin{align*}
    G_{q,R}=\int_{-\infty}^{\infty}s d \Phi^{q}(\frac{s}{R\sigma_{\xxi}}),
\end{align*}
and $\Phi(\cdot)$ is the cumulative density function of a standard Gaussian distribution.
\end{theorem}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.4\textwidth]{figs/integral.pdf}
    \caption{$G_{q, R}$ with different $q$, when $R\sigma_{\xxi} = 1$}
    \label{fig:integral}
\end{figure}

\paragraph{Remark}

Notice that, as Figure \ref{fig:integral} shows, $G_{q, R}$ is (near) constant that only slowly increase with $q$. In comparison, under the same setting, as shown in \citep{yin2019rademacher}, the $\epsilon-\ell_{\infty}$ adversarial training
can hurt the generalization with $\Rn[\tF]=\Theta\left(\Rn[\F]+\epsilon R\sqrt{\frac{d}{n}}\right)$, that is scale with $d$.

With the Ledoux-Talagrand Lemma and the standard generalization result with Rademachar complexity, we simply have the following corollary.

\begin{corollary}[Gap between Losses]
\label{cor:gap}
Let $\mathcal{D}$ denote the population data distribution, and define
\begin{align*}
    \Delta_{q}(\th):= \E_{\mathcal{D}}\E_{\xxi_{[q]}}\max_{\xxi_{i},i\in[q]}\ell(f_{\th}(\x+\xxi_{i}),y)-\E_{\mathcal{D}}\ell(f_{\th}(\x),y).
\end{align*}
Then for any $\delta>0$, with probability $1-\delta$, we have
\begin{align*}
    \E_{\mathcal{D}}\ell(f_{\hat{\th}}(\x),y)& \le\E_{\mathcal{D}_{n}}\E_{\xxi_{[q]}}\max_{\xxi_{i},i\in[q]}\ell(f_{\hat{\th}}(\x+\xxi_{i}),y) - \Delta_{q}(\hat{\th})\\
    & +2L_{\varphi}\Rn[\F]+\frac{L_{\phi}G_{q,R}}{\sqrt{n}}+\sqrt{\frac{\ln(1/\delta)}{n}}.
\end{align*}

\end{corollary}

\paragraph{Remark}
Notice that, ERM has the following generalization bound:
\begin{align*}
    \E_{\mathcal{D}}\ell(f_{\hat{\th}}(\x),y)\le\E_{\mathcal{D}_{n}}\ell(f_{\hat{\th}}(\x),y)+2L_{\varphi}\Rn[\F]+\sqrt{\frac{\ln(1/\delta)}{n}}.
\end{align*}
Thus, if $\hat{\th}$ satisfies the following inequality:
\begin{align*}
    \E_{\mathcal{D}_{n}}\E_{\xxi_{[q]}}\max_{\xxi_{i},i\in[q]}\ell(f_{\hat{\th}}(\x+\xxi_{i}),y)&-\E_{\mathcal{D}_{n}}\ell(f_{\hat{\th}}(\x),y)\\
&\le\Delta_{q}(\hat{\th})-\frac{L_{\varphi}G_{q,R}}{\sqrt{n}},
\end{align*}
which is related to the sample of $\mathcal{D}_n$, then we have a sharper generalization bound than ERM, which means we improve the generalization with the weak adversarial training.

Define
\begin{align*}
    \Delta_{q, n}(\th):=\E_{\mathcal{D_n}}\E_{\xxi_{[q]}}\max_{\xxi_{i},i\in[q]}\ell(f_{\th}(\x+\xxi_{i}),y)-\E_{\mathcal{D}}\ell(f_{\th}(\x),y),
\end{align*}
we can see that:
\begin{align*}
    \mathbb{E}_{\mathcal{D}_n\sim \mathcal{D}} \Delta_{q, n} = \Delta_{q}.
\end{align*}
{\color{red} This is not true since parameter depends on data}

And obviously, $\Delta_{q,n}$ is sub-Gaussian distributed as the loss is bounded. With the standard concentration inequality, we have constant (though small) probability that the $\x$ satisfies the desired property.

\paragraph{Remark}
Another methods is that, we can show the two estimator have different behavior in practice. For example, on the linear separable data, probably with this kinds of method we can have larger margin than ERM, but other data augmentation can also work. {\color{red} TODO}

Intuitively, the inequality means that $\hat{\th}$ is hard to attack with this kinds of weak adversarial perturbation on training set compared with the test set.
Here we introduce a more concrete example to show the condition can be satisfied in practice. Suppose that $\x| y\sim\mathcal{N}(\th^{*}y,\sigma^{2} I)$ and $y\sim\text{Unif}\{-1,1\}$. {\color{red} This is a special case of the halfspace learning, where the data are generated from the Gaussian mixture.} We use $\varphi(s)=\max(-s, 0)$.

\begin{theorem}
\label{thm:cdf}
\begin{align*}
 & \frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\xxi_{[q]}}\min_{\xxi_{j},j\in[q]}\mathbb{I}\left\{ \th^{\top}(\x_{i}+\xxi_{j})y_{i}\le0\right\} \\
= & 1-\frac{1}{n}\sum_{i=1}^{n}\Phi^{q}\left(\frac{-\th^{\top}\x_{i}y_{i}}{\left\Vert \th\right\Vert \sigma_{\xxi}}\right),
\end{align*}
where $\Phi$ is the cdf of standard gaussian distribution.
\end{theorem}

\subsection{Linear Multi-Class Classification}

We continue to study the multi-class linear classifier. In $K$-class
classification problems, we choose $\mathcal{Y}=\{0,1\}^{\otimes K}$.
The prediction function $f_{\th}(\x):\mathbb{R}^{d}\to\mathbb{R}^{K}$,
in which, the $k$-th coordinate of $f_{\th}(\x)$ is the score that
$f_{\th}$ gives to the $k$-th class. We make prediction by choosing
the class with the highest score. Given the label $\y=[y_{1},...,y_{K}]\in\R^{K}$,
in which $y_{k}=1$ and $y_{i}=0$ for all $i\ne k$, if $\y$ belongs
to the $k$-th class. Suppose our linear classifier is defined by
\[
f_{\th}(\x)=\th^{\top}\x,\ \th=[\th_{1},...,\th_{k}]\in\R^{d\times K}.
\]
And we define
\[
\F=\F=\{f_{\th}:\left\Vert \th\right\Vert _{2,\infty}\le R\}.
\]
And the loss is defined as $\ell(f_{\th}(\x),\y)=\varphi(\y^{\top}f_{\th}(\x))$
for some $\varphi:\mathbb{R}\to[0,B]$ that is monotonically nonincreasing
and $L_{\varphi}$-Lipschitz.

\paragraph{Theorem 4 (Extension to multi-class case)}

\[
\Rn[\ell_{\tF}]\le L_{\phi}\Rn[\ell_{\F}]+\frac{L_{\phi}G_{q,R}}{2\sqrt{n}}.
\]

\subsection{Toy Examples verifies the Theory}

Denote
\begin{align*}
\text{Train\_Gap}_{q} & =\E_{\mathcal{D}_{n}}\E_{\xxi_{[q]}}\max_{\xxi_{i},i\in[q]}\ell(\x+\xxi_{i},y;f_{\hat{\th}})-\E_{\mathcal{D}_{n}}\ell(\x+\xxi_{i},y;f_{\hat{\th}})+\frac{L_{\phi}G_{q,R}}{\sqrt{n}},\\
\text{Test\_Gap}_{q} & =\E_{\mathcal{D}}\E_{\xxi_{[q]}}\max_{\xxi_{i},i\in[q]}\ell(\x+\xxi_{i},y;f_{\th})-\E_{\mathcal{D}}\ell(\x+\xxi_{i},y;f_{\th}).
\end{align*}
By our theory, if we have $\text{Train\_Gap}_{q}<\text{Test\_Gap}_{q}$,
then the proposed surrogate loss improves the generalization. To show
this, we conduct a simpler linear classifier toy example using Hingeloss.
Figure (\ref{fig:Train_Gap-vs-Test_Gap.}) gives the quantity of $\text{Train\_Gap}_{q}$
and $\text{Test\_Gap}_{q}$ for $q=[1,2,3,4,5]$. As shown by the
result, we indeed have $\text{Train\_Gap}_{q}<\text{Test\_Gap}_{q}$
which verifies our theory.

\begin{figure}
\begin{centering}
\includegraphics[scale=0.6]{figs/gap.pdf}
\par\end{centering}
\caption{Train\_Gap vs Test\_Gap. \label{fig:Train_Gap-vs-Test_Gap.}}
\end{figure}

\section{The proof}
\subsection{Proof of Theorem \ref{thm:weak}}
\label{sec:proof_weak_rademacher}

Define
\[
\tf_{\th}(\x,y)=\E_{\xxi_{[q]}}\min_{\xxi_{i},i\in[q]}\left[\th^{\top}\left(\x+\xxi_{i}\right)y\right].
\]
Thus when $y=1$, we have
\begin{align*}
 & \tf_{\th}(\x,y)\\
= & \th^{\top}\x y+\E_{\xxi_{[q]}}\min_{\xxi_{i},i\in[q]}\th^{\top}\xxi_{i}\\
= & \th^{\top}\x y-\E_{\xxi_{[q]}}\max_{\xxi_{i},i\in[q]}\th^{\top}\xxi_{i}.
\end{align*}
Notice that $\th^{\top}\xxi_{i}\sim\mathcal{N}(\boldsymbol{0},\sigma_{\xxi}^{2}\left\Vert \th\right\Vert ^{2})$,
which gives that
\[
\E_{\xxi_{[q]}}\max_{\xxi_{i},i\in[q]}\th^{\top}\xxi_{i}=G_{q,\left\Vert \th\right\Vert },
\]
where
\[
G_{q,r}=q\int_{-\infty}^{\infty}s\Phi^{q-1}(\frac{s}{r\sigma_{\xxi}})\phi(\frac{s}{r\sigma_{\xxi}})ds,
\]
and $\Phi(\cdot)$ and $\phi(\cdot)$ is the cumulative/probability
density function of a standard gaussian distribution. Similarly, we
have
\begin{align*}
\tf_{\th}(\x,y) & =\th^{\top}\x y+\E_{\xxi_{[q]}}\min_{\xxi_{i},i\in[q]}-\th^{\top}\xxi_{i}\\
 & =\th^{\top}\x y-\E_{\xxi_{[q]}}\max_{\xxi_{i},i\in[q]}\th^{\top}\xxi_{i},
\end{align*}
when $y=-1$. Thus we conclude that
\[
\tf_{\th}(\x,y)=\th^{\top}\x y-G_{q,\left\Vert \th\right\Vert }.
\]
We then bound the Rademacher complexity of function class $\tF$.
\begin{align*}
\Rn[\tF] & =\frac{1}{n}\E_{\h}\left[\sup_{\left\Vert \th\right\Vert \le R}\sum_{i=1}^{n}h_{i}\left(y_{i}\th^{\top}\x_{i}-G_{q,\left\Vert \th\right\Vert }\right)\right]\\
 & \le\frac{1}{n}\E_{\h}\left[\sup_{\left\Vert \th\right\Vert \le R}\sum_{i=1}^{n}h_{i}y_{i}\th^{\top}\x_{i}\right]+\frac{1}{n}\E_{\h}\left[\sup_{\left\Vert \th\right\Vert \le R}\sum_{i=1}^{n}h_{i}G_{q,\left\Vert \th\right\Vert }\right]\\
 & =\Rn[\F]+\frac{1}{n}\E_{\h}\left[\sup_{\left\Vert \th\right\Vert \le R}\sum_{i=1}^{n}h_{i}G_{q,\left\Vert \th\right\Vert }\right]\\
 & =\Rn[\F]+\frac{1}{n}\E_{\h}\left[\sum_{i=1}^{n}h_{i}\mathbb{I}\left\{ \sum_{i=1}^{n}h_{i}>0\right\} G_{q,R}\right]\\
 & =\Rn[\F]+\frac{G_{q,R}}{2n}\E_{\h}\left[\left|\sum_{i=1}^{n}h_{i}\right|\right]\\
 & \le\Rn[\F]+\frac{G_{q,R}}{2\sqrt{n}},
\end{align*}
where the last inequality is by Khintchine's inequality.

\subsection{Proof of Theorem \ref{thm:cdf}}

Given training set $\{\x_{i},y_{i}\}_{i=1}^{n}$ and choose the $0$-1
loss, $\varphi(s)=\mathbb{I}\{s\le0\}$. We learn $\th$ by minimizing
\[
\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\xxi_{[q]}}\min_{\xxi_{j},j\in[q]}\mathbb{I}\left\{ \th^{\top}(\x_{i}+\xxi_{j})y_{i}\le0\right\} .
\]
Notice that if $y_{i}=1$, we have
\[
\mathbb{I}\left\{ \th^{\top}\xxi_{j}\le-\th^{\top}\x_{i}\right\} \sim\text{Bernoulli}\left(\Phi\left(\frac{-\th^{\top}\x_{i}}{\left\Vert \th\right\Vert \sigma_{\xxi}}\right)\right).
\]
And thus
\[
\mathbb{E}_{\xxi_{[q]}}\min_{\xxi_{j},j\in[q]}\mathbb{I}\left\{ \th^{\top}(\x_{i}+\xxi_{j})y_{i}\le0\right\} =1-\left[1-\Phi\left(\frac{-\th^{\top}\x_{i}}{\left\Vert \th\right\Vert \sigma_{\xxi}}\right)\right]^{q}.
\]
If $y_{i}=-1$, we have
\begin{align*}
\mathbb{I}\left\{ \th^{\top}(\x_{i}+\xxi_{j})y_{i}\le0\right\}  & =\mathbb{I}\left\{ \th^{\top}\xxi_{i}\ge-\th^{\top}\x_{i}\right\} \\
 & =\mathbb{I}\left\{ -\th^{\top}\xxi_{i}\le\th^{\top}\x_{i}\right\} \\
 & \sim\text{Bernoulli}\left(\Phi\left(\frac{\th^{\top}\x_{i}}{\left\Vert \th\right\Vert \sigma_{\xxi}}\right)\right),
\end{align*}
which gives that
\[
\mathbb{E}_{\xxi_{[q]}}\min_{\xxi_{j},j\in[q]}\mathbb{I}\left\{ \th^{\top}(\x_{i}+\xxi_{j})y_{i}\le0\right\} =1-\left[1-\Phi^{q}\left(\frac{\th^{\top}\x_{i}}{\left\Vert \th\right\Vert \sigma_{\xxi}}\right)\right]^{q}.
\]
And thus we have
\begin{align*}
 & \frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\xxi_{[q]}}\min_{\xxi_{j},j\in[q]}\mathbb{I}\left\{ \th^{\top}(\x_{i}+\xxi_{j})y_{i}\le0\right\} \\
= & 1-\frac{1}{n}\sum_{i=1}^{n}\left[1-\Phi\left(\frac{-\th^{\top}\x_{i}y_{i}}{\left\Vert \th\right\Vert \sigma_{\xxi}}\right)\right]^{q}.
\end{align*}

redpajama_set_name: RedPajamaArXiv


Tuesday and Wednesday were very exciting days for the Poland team. On Tuesday we had our second day of teaching and practicing English with students in a Polish high-school. To help the students with their English we simply had conversations with them.
We spoke to the students about their lives in Poland, and answered many questions about life in the U.S. The students seemed really excited and engaged, and it was encouraging to see them so happy to be in school!
On Tuesday we also had the second day of our evening English program in the church in Sandomierz. It had a great outcome! 9 students came, and we had lessons with them in 2 groups, intermediate and advanced. We had a really fun time with them, and they seemed really excited to be at the church, and hopefully they will come to our last class on Thursday!
On Wednesday we took an excursion to Lublin. We went to the Majdaneck Concentration Camp to begin our day. We saw the place were many horrible events took place during the Holocaust, and it was a very humbling experience for everyone. It was also very educational as we were led through the camp by a tour guide.
We also were able to explore the city of Lublin; we ate lunch there and did some sight-seeing and shopping. Everyone in the group enjoyed seeing the city!
These past two days were so amazing, as we got to see God at work here in Sandomierz in so many ways.
Please continue to pray for the people here, as well as for our team.


text:
A US trade policy for development: Helping the poorest in a time of crisis
Kimberly Elliott 27 May 2009
The economic crisis is hitting the world's poorest countries through falling trade and commodity prices. This column argues that the US should respond by further opening its market to exports from small, poor economies. That would not only provide an additional stimulus to those economies but also strengthen US global leadership, give a boost to the Doha Round, and serve broader US national interests by helping to promote political stability in some very shaky parts of the world.
"The World's poorest developing nations have a special place in the Obama trade agenda."
US Trade Representative Ron Kirk, Georgetown University, 29 April 2009
While welcome, it is not yet clear how Ambassador Kirk's words, and the President's commitment, will be turned into action – and the need for action is urgent.
The latest projections say global trade will fall by roughly 10% this year and stagnate next year, growing by less than 1%, according to the IMF. In a recent paper, Gary Hufbauer and Sherry Stephenson (2009) analyse the impact of the crisis on developing-country trade and find that it is more severe for smaller, poorer countries than for the top 20 developing-country exporters. The world's poorest countries are generally not well-integrated in global financial markets and mostly avoided the direct effects of the financial crisis, but the associated fall in trade and global commodity prices is hammering them. The World Bank recently estimated that more than 50 million people will remain trapped in extreme poverty as a result of a financial crisis that they had no role in creating.
Most of the drop in trade and commodity prices is due to sharply falling demand in rich countries, and, to a far smaller degree, reduced access to trade finance. Trade policies in the US and other rich countries are not, so far, playing a significant role, but there are worrying trends. Chad Bown (2009) is tracking anti-dumping and other ad hoc trade "remedy" measures for the World Bank's trade monitoring initiative and has found sharp increases in both the initiation of investigations and imposition of measures in the second half of 2008 and first quarter of 2009. In the US, only three new anti-dumping investigations were launched in the last half of 2008 and, again, in the first quarter of 2009, but the number of new anti-dumping measures imposed jumped from just two in the first half of last year to 21 in the second half, the largest increase anywhere, though India continued to lead in number of measures imposed for the year as a whole (Bown 2009). Hufbauer and Stephenson document a wider range of trade measures adopted in the face of the crisis, with subsidies to the auto and financial sectors dominating in the rich countries and traditional border measures being a more important tool in budget-constrained developing countries.
What the US could do
Many of the trade policy steps that countries should take, or avoid, in coping with the crisis are well covered on this site.1 Avoiding additional protectionist measures is at the top of the list. Completing the Doha Round of multilateral trade negotiations is also more important than ever, as it would help to constrain the use of at least some protectionist measures.
But the Doha Round, under the best of circumstances, will take some time to conclude, and the US and other rich countries should move as quickly as possible to further open their markets to the world's poorest countries. The eighth of the Millennium Development Goals adopted at a UN summit in 2000 calls on the rich countries to provide duty-free-quota-free market access for the least-developed countries (LDCs). This goal was reiterated at the WTO's 2005 Hong Kong ministerial meeting, but US negotiators would only commit to provide access for 97% of products and only in conjunction with the conclusion of the Doha Round.
Importantly, the pledge to provide duty-free-quota-free access is not part of the round's "single undertaking," and the LDCs are not being asked to undertake liberalisation commitments. So President Obama would lose nothing and could gain a great deal of good will, as well as providing an economic boost to struggling developing countries, by asking Congress to act now and provide access on 100% of products, as the European Union already does, rather than just 97% as promised in Hong Kong. Three percent may not sound like much, but such liberalisation would unblock a number of items that that are of the most interest to poor countries.
Providing full market access will not reverse the decline in trade flows, but it would open opportunities for some of the poorest countries in the world. It would also address a fundamental unfairness created by the fact that US trade policy, like that of other rich countries, discriminates against poor countries and poor people. The highest US tariffs fall on agricultural products and labour-intensive light manufactures, where many developing countries have a comparative advantage.
Figure 1. Average US tariff by sector
Figure 1 masks the impact on agricultural exports from poor countries because the average across all goods obscures the prohibitively high tariffs on a few products, notably sugar, peanuts, tobacco, and dairy products (see Elliott 2008).
The US offsets the impact of trade barriers on developing countries to some degree through programs that provide preferential access. But the same "sensitive" sectors are typically excluded from the Generalised System of Preferences available to most countries. Regional programs provide better access for countries in the Caribbean, Andean, and sub-Saharan Africa, but they still restrict agricultural and a few other products and include strict rules of origin for gaining access that make the programs difficult to fully exploit.
Moreover, there are more than a dozen least-developed countries that do not benefit from these regional programs and a handful that, because of the concentration of their exports in high-tariff sectors, are especially hard-hit. Figure 2 shows average tariffs for various countries and groups of countries. Bangladesh and Cambodia, for example, are LDCs with average annual per capita incomes of around $500, yet the dollar value of duties paid on their exports, almost $1 billion in 2006 for the two combined, is as much as that paid on much larger exports from the much richer countries of France and the UK. The duties collected were also six times higher than the value of the aid that Bangladesh and Cambodia received from the US in that year.
Figure 2. Average tariff rates by source country
In addition to the gaps in US treatment of UN-designated "least-developed countries," there are a number of small and poor countries that are not quite vulnerable enough to meet the UN definition for LDCs. Several current legislative proposals would use trade to promote US interests in political stability and security in some of these countries, including Pakistan, Afghanistan (an LDC), and Georgia. Rather than adding further complexity to US trade programs by creating new ones, however, Congress should expand eligibility for duty-free-quota-free access to countries that (1) have incomes below the World Bank's low middle-income threshold and (2) have total national incomes of less than $50 billion, a category that includes Pakistan and Georgia. In 2007, LDCs accounted for 0.5% of total non-oil US imports; adding the roughly two dozen countries that fall into the expanded small and poor category doubles the share to 1% – hardly a major threat to American producers.2
The economic crisis is hitting the world's poorest countries through falling trade and commodity prices; trade policy needs to be part of the US response. These countries had nothing to do with causing the crisis, and they are the least able to cope with its impact, especially on their most vulnerable citizens. Macroeconomic stimulus to restore demand and rigorous monitoring to stem the spread of trade protectionism are vital to recovery. But furthering opening the US market to the most vulnerable and poorest countries would not only provide an additional stimulus to those economies, it would also strengthen US global leadership, give a boost to the Doha Round, and serve broader US national interests by helping to promote political stability in some very shaky parts of the world.
Bown, Chad P. 2009, Protectionism is on the rise: antidumping import investigations up to 31% in 2008, in The collapse of global trade, murky protectionism, and the crisis: Recommendations for the G20, edited by Richard Baldwin and Simon J. Evenett, a VoxEU.org publication; update available here.
Elliott, Kimberly Ann, 2008, US Trade Policy and Global Development, in The White House and the World: A Global Development Agenda for the Next U.S. President, edited by Nancy Birdsall, Center for Global Development.
Hufbauer, Gary Clyde and Sherry Stephenson, 2009, Trade Policy in a Time of Crisis: Suggestions for Developing Countries, CEPR Policy Insight No. 33, Centre for Economic Policy Research.
1 See the contributions by Richard Baldwin, Simon Evenett, Jeffrey Schott, and others gathered under the Open Markets theme of the Global Crisis Debate section.
2 This proposal will be fleshed out in detail in a forthcoming Center for Global Development working paper. A similar proposal with the list of countries potentially eligible may be found on the Center's website here.
Topics: Development International trade
Tags: trade liberalisation, crisis, US trade policy, LDCs
Kimberly Elliott
Fellow with the Center for Global Development
Women shaping global economic governance: A new eBook
Gonzalez, Jansen
Risk sharing plus market discipline: A new paradigm for euro area reform? A Debate
Pisani-Ferry, Zettelmeyer
Sound at last? Assessing a decade of financial regulation: A new eBook
Bolton, Cecchetti, Danthine, Vives
China Economics Summer Institute (CESI)
17 - 18 August 2019 / Peking University, Beijing / Chinese University of Hong Kong – Tsinghua University Joint Research Center for Chinese Economy, the Institute for Emerging Market Studies at Hong Kong University of Science and Technology, the Guanghua School of Management at Peking University, the Stanford Center on Global Poverty and Development at Stanford University, the School of Economics and Management at Tsinghua University, BREAD, NBER and CEPR
CALL FOR PAPER - Vienna Symposium on Foreign Exchange Markets
19 - 20 August 2019 / Vienna, Palais Coburg / WU Research Institute for Capital Markets (ISK)
SALENTO MACRO MEETINGS 2019
29 - 30 August 2019 / Galatina, Italy /
Sustainable Development Conference 2019
4 - 5 September 2019 / Roma Eventi, Congress Center, Pontificia Università Gregoriana Piazza della Pilotta, 4, Rome, Italy / European Center of Sustainable Development , CIT University
CIMS Summer School and Conference 2019
9 - 14 September 2019 / Guildford, Surrey, UK / The University of Surrey
CEPR Policy Research
Homeownership of immigrants in France: selection effects related to international migration flows
Gobillon, Solignac
Climate Change and Long-Run Discount Rates: Evidence from Real Estate
Giglio, Maggiori, Stroebel, Weber
The Permanent Effects of Fiscal Consolidations
Summers, Fatás
Demographics and the Secular Stagnation Hypothesis in Europe
Favero, Galasso
QE and the Bank Lending Channel in the United Kingdom
Butt, Churm, McMahon, Morotz, Schanz
Independent report on the Greek official debt
Eichengreen, Avgouleas, Poiares Maduro, Panizza, Portes, Weder di Mauro, Wyplosz, Zettelmeyer
Rebooting the Eurozone: Step 1 – Agreeing a Crisis narrative
Baldwin, Beck, Bénassy-Quéré, Blanchard, Corsetti, De Grauwe, den Haan, Giavazzi, Gros, Kalemli-Ozcan, Micossi, Papaioannou, Pesenti, Pissarides , Tabellini, Weder di Mauro
A world without the WTO: what's at stake?
Baldwin, Nakatomi
The economics of insurance and its borders with general finance
Thimann
Maturity mismatch stretching: Banking has taken a wrong turn
Goodhart, Perotti
@VoxEU

redpajama_set_name: RedPajamaCommonCrawl


Xiaomi Redmi 4a was released dated – 2016, November. Lets take a look at Xiaomi Redmi 4a Price in Pakistan with detailed review and specification.
Xiaomi Redmi 4a has been officially released on 2016, November.
Xiaomi Redmi 4a is 4G LTE based Android smartphone providing LTE band 1(2100), 3(1800), 7(2600), 38(2600), 39(1900), 40(2300), 41(2500) bands.
Xiaomi Redmi 4a supports EDGE data modes -> Yes.
Xiaomi Redmi 4a supports GPRS data modes like Yes.
In terms of Dimension it has 139.5 x 70.4 x 8.5 mm (5.49 x 2.77 x 0.33 in) size.
Total weight is 131.5 g (4.66 oz).
Xiaomi Redmi 4a comes with 5.0 inches (~70.2% screen-to-body ratio) providing a total of 720 x 1280 pixels (~294 ppi pixel density).
Xiaomi Redmi 4a MultiTouch support : Yes.
Xiaomi Redmi 4a runs Android OS, v6.0.1 (Marshmallow) on the top of Qualcomm MSM8917 Snapdragon 425 chipset and powerful Quad-core 1.4 GHz Cortex-A53 CPU.
For fluid visual experience it has a powerful Adreno 308 GPU.
Primary Camera or Rare/Back Camera is at 13 MP, f/2.2, autofocus, LED flash with Geo-tagging, touch focus, face/smile detection, HDR, panorama and video recording capability of 1080p@30fps.
Xiaomi Redmi 4a WLAN is based on Wi-Fi 802.11 b/g/n, Wi-Fi Direct, hotspot.


Login and click on "New Discovery"
- Title - Mr. Ms. Dr. Prof.
You will receive account activation email on this address. This email will be also used as your login on ImmuniWeb® Platform.
Our support may call you in urgent cases. Therefore, please make sure that your direct phone number is valid and that we can reach you on it.
If you don't have a legal entity please indicate your website name here and put your private address below.
If you don't have a company please indicate your private address.
Please chose a complex password consisting of different types of characters.
Please enter the same password as above to confirm it.


text:
Home » Januvia, Byetta Linked to Adverse Health Events
Januvia, Byetta Linked to Adverse Health Events
Januvia (sitagliptin) and Byetta (exenatide), prescribed for the treatment of Type 2 diabetes, have been associated with reports of increased risks for pancreatic and thyroid cancers.
Researchers at the University of California, Los Angeles looked at the both Januvia and Byetta in comparison to other therapies and all of the drugs' risks for pancreatic and thyroid cancers and pancreatitis.
The study, published in the journal, Gastroenterology and conducted by researchers at the University of California, revealed that Januvia and Byetta patients experienced a nearly three-fold risk of developing pancreatic cancer. Evidence also suggests an increased incidence of thyroid cancer among patients taking Byetta.
Specifically, the research indicates that Januvia users are 2.7 times and Byetta users are 2.9 times likelier to develop pancreatic cancer and patients taking either Byetta or Januvia were six times likelier to develop pancreatitis and that patients taking Byetta are at increased risks for developing thyroid cancer.
Januvia is manufactured by Merck and Amylin Pharmaceuticals makes Byetta.
Both drugs are glucagon-like peptide-1 based therapies that are in the class dipeptidyl peptidase-4 (DPP-4) inhibitors. The drugs increase certain natural substances that lower raised blood sugar levels. Diabetics typically have abnormally low amount insulin levels or their bodies have difficulties utilizing insulin efficiently.
Other serious side effects have been linked to these Type 2 diabetes drugs and, according to Foodconsumer.org, some of these serious side effects include low blood sugar; anaphylaxis and other allergic reactions including hives, rash, swelling of face, lips, tongue, and/or throat; acute pancreatitis, and death.
Approved in 2006 by the U.S. Food & Drug Administration (FDA), Januvia continues to be associated with risks for pancreatic side effects, pancreatitis, and pancreatic cancer. In 2009, the agency required a label update warning of the risk of acute pancreatitis based on 88 reports of acute pancreatitis in patients who took Januvia between October 2006 and February 2009. Chronic pancreatitis is painful, potentially fatal, and a known risk factor for pancreatic cancer.
Testing for the safety of Januvia has not looked at other effects drugs in the DPP-4 inhibitors class, specifically, the drugs' role in inhibiting one of the body's natural cancer-suppressing mechanisms. For example, Foodconsumer.org pointed out that diabetes patients could be at risk for years before the full effects and risks of taking Januvia and other DPP-4 drugs are known.
Meanwhile, Amylin Pharmaceuticals came under fire for allegedly hiding a study that revealed serious heart risks associated with Byetta. FDA claimed Amylin concealed the Byetta heart study from the agency, and then tried to keep the FDA from getting its hands on the key data when the agency learned of its existence.
Byetta, administered via a twice-daily injection, was first approved in 2005 to be used in conjunction with other diabetes treatments and was later approved as a stand-alone therapy for type 2 diabetes.


text:
Bryan Ferry House Disco 2010 US
album Bryan Ferry - You Can Dance mp3 download
Performer: Bryan Ferry
Album: You Can Dance
Style: House, Disco
Other Formats: APE VOC MP1 MMF MPC DTS MIDI
Olympia is the thirteenth studio album by the British singer Bryan Ferry, released by Virgin Records on 25 October 2010. Co-produced by Ferry and Rhett Davies, Olympia is Ferry's first album of predominantly original material since 2002's Frantic.
All those rappers, they're the only glamorous people working in music now. The rock bands are rather drab, even the good ones. You definitely don't want to look at them. But some of those R&B people are very good. Now playing: The police - Every Breath you take. You can leave your e-mail and we will let you know when the broadcast of the station will be online again: Or listen to the other country dec name stations.
No, there's nothing wrong with your ears. We just stopped the music because you haven't touched the player in a while. Hey, you haven't touched the player in a while.
Album: Olympia (2010). Get the Sheet Music License This Song. The hitchhike into Paris And zigzag by the Seine The Hollywood moment I'll never be the same. There's a world awaiting Way beyond the sea How I love to travel Baby will you come with me? You can dance. Jump on the table Slide down the pole You can wear your sable You can bare your soul. Through Reno down to Vegas The casinos never close To the movers and the shakers The Tango never knows. You can dance You can dance You can dance You can dance dance dance dance You can dance dance dance dance. I need some inspiration. I've got a lot of time to lose.
We reported last week on news of Bryan Ferry's star-studded new solo album 'Olympia' as well as upcoming Roxy Music reunion dates - and now comes the video for that disc's first single, 'You Can Dance,' which premiered at RollingStone. Glad to see Bryan Ferry back on the scene. Love the homage to Avalon album's True to Life in You Can Dance. Not enough footage of Ferry and the 'artists' and too much of the club girls and their less than rhythmic hips. on Jul 19, 2010 at 9:49 pm. Hate to say it, especially as a Bryan Ferry fan, but this is pretty sterile and stale sounding compared to, say, anyhting off of BETE NOIR or even FRANTIC. Maybe I'm just getting old and expect too much.
1 You Can Dance (Padded Cell Remix)
Remix – Padded Cell
Copyright (c) – Dene Jesmond Enterprises Ltd.
Licensed To – Virgin Records Ltd.
Copyright (c) – EMI Records Ltd.
(C) 2010 Dene Jesmond Enterprises Ltd licensed to Virgin Records Ltd
(C) 2010 EMI Records Ltd.
ASIN: B003XC31H6
none Bryan Ferry You Can Dance (Remixes) (CDr, Single, Promo) Astralwerks none US 2010
Bryan1 Bryan Ferry You Can Dance (Remixes) (12", S/Sided, Unofficial, W/Lbl) Not On Label (Bryan Ferry) Bryan1 UK 2011
none Bryan Ferry You Can Dance (CDr, Single, Promo) Virgin none UK 2010
none Bryan Ferry You Can Dance (Remixes) (CDr, Maxi, Promo) Astralwerks none US 2010
VF019 Bryan Ferry You Can Dance (Remixes) (12", Ltd) The Vinyl factory VF019 UK 2010
Bryan Ferry - He'll Have To Go album mp3
Title: He'll Have To Go
Bryan Ferry - ...Is Your Love Strong Enough album mp3
Title: ...Is Your Love Strong Enough
Bryan Ferry - A Fool For Love / One Way Love album mp3
Title: A Fool For Love / One Way Love
Bryan Ferry And Roxy Music - Bryan Ferry - The Ultimate Collection With Roxy Music album mp3
Title: Bryan Ferry - The Ultimate Collection With Roxy Music
Bryan Ferry - Don't Stop The Dance album mp3
Title: Don't Stop The Dance
Bryan Ferry - The Times They Are A-Changin' album mp3
Pop Rock, Classic Rock
Title: The Times They Are A-Changin'
Bryan Ferry - Kiss And Tell album mp3
Title: Kiss And Tell
Bryan Ferry - Windswept album mp3
Pop Rock, Synth-pop
Title: Windswept
Bryan Ferry And Roxy Music - More Than This - The Best Of Bryan Ferry And Roxy Music album mp3
Title: More Than This - The Best Of Bryan Ferry And Roxy Music
Bryan Ferry - Mamouna album mp3
Soft Rock, Pop Rock, Avantgarde
Title: Mamouna
Bryan Ferry - Radio Sampler album mp3
Lounge, Easy Listening
Genre: Jazz / Pop
Title: Radio Sampler
Bryan Ferry - Live In Paris album mp3
Title: Live In Paris


If you're going to pay someone to smash avocado on bread for you, you might as well go to a place that does it right.
We're still obsessed with avocado toast—and if the menus of many of the best resturants in Los Angeles are any indication, so is everybody else. The trendy toast is more than an Instagram-worthy treat, it's a kind of testament to what makes SoCal cooking so great: simple preparation of fresh produce, presented with finesse, adding up to a casual yet oh-so-stylish dish. Avocado toast is also versatile, showing up everywhere from elaborate offerings at the best hotel brunch services in the city, to more grab-and-go versions at some of L.A.'s best coffee shops. Make your way to these spots and you'll see why we think they're the toast of the town.
Where to find the best avocado toast in L.A.
Stop by this sidewalk cafe for a take that is heavy on the chunks of avocado, topped with a generous toss of dried pepper and large flakes of salt. Place an order at the walk-up window, take a seat at one of the open-air tables and watch the world of Echo Park go by.
Situated right on the main drag of Abbot Kinney, the white-washed, sun filled space is the perfect place to grab a morning Vittoria coffee and smashed avocado toast, topped with a farm-fresh egg.
Alexander Phaneuf and Or Amsalan bring their incredible baking skills to everything they serve at Lodge Bread, so you know the toast is going to be the star of this one. An imposingly-thick slice is topped with avocado and a beautiful array of thinly-sliced radishes.
California cuisine and a love of local produce infuses the fare at Goldie's so it's no surprise they sling a mean avocado toast. A hearty wedge of grilled bread is topped with lemon, chive and smoked chili flakes.
Not every avocado toast has to be a fancy production. This diner-style version is simplified, but no less satisfying. Here, a smooth spread of avocado is slapped across bread and dusted with pepper flakes, and, best of all, you can sate your cravings at almost any hour of day or night.
Only available on the breakfast menu, the avocado toast here is a classic. Start your day with slim slices of toasted seven-grain bread, decked out with mashed avocado, aleppo pepper and a light scattering of radish.
Is there any spot in L.A. more associated with fancy toast than Sqirl? Obviously, Sqirl wouldn't stop at simply avocado on bread—here a slice of bread is piled high with avocados from JJ's Farm, hot pickled carrots, green garlic creme fraiche, wood sorrel and za'atar.
This elegantly-sliced avocado toast is a distinctly West Coast addition to the generally Southern-inspired menu at this charming resturant in the courtyard of the Palihotel in West Hollywood. Toppings can include slivered red onion and smoked black olives.
The name may sound cute-sy (it's also a Fleetwood Mac song), but Honey Hi is serious about making flavorful, healthy dishes for the Echo Park crowd; the most popular of which is their bright, colorful avocado toast (even the L.A.-lovers over at the New York Times think so). Creamy avocado tops a buckwheat sourdough, and is then piled high with sweet potato, pickled onions, scallions, parsely and lemon, and lightly dusted with sumac and smoked paprika. It's almost too pretty to eat.
Want to chase your avocado toast with some green juice?
Slurp up at the best juice bars in L.A.
Juice bars are sprouting up faster than you can turn that kale into liquid green. From seaside smoothies in Malibu to raw juices in Hollywood, check out the best juice bars in L.A.


About Us - R.E. Becker Builders, Inc.
The Becker's come from several generations of builders. Ron Becker grew up learning the building trades by working for his father's construction company in various "on site" capacities of residential and commercial construction work. Today many family members and longtime employees assist Ron with the daily business activities. Kamille Becker, his wife and business partner for over 30 years, manages the office staff.
For over 30 years, R.E. Becker has specialized almost exclusively in single family residences. He is the approved regional builder of Unibilt Homes for Unibilt Industries of Dayton (Vandalia) Ohio.
R.E. Becker primarily builds to the Homebuyer's selections and on their land. The locations cover an 8-10 county area, including Allen, Auglaize, Hardin, Mercer, Logan, Putnam, Shelby, Van Wert, and other counties in Ohio. The average construction schedule from "dig" to completion or "move-in" ranges 60-90 days.
Prices range from the basic of $65,000 to just over $300,000. When needed, financing is simplified through the experience of the "Becker Team" in handling conventional loans from lending institutions as well as government programs such as FHA, VA, and Rural Development loans.
Every Becker home offers a large variety of customization with quality construction backed by a full home warranty. All the employees at R.E. Becker Builders are dedicated to providing the "Best Home Value" to each and every Homeowner. They care about their buyers before and after the sale.
R.E. Becker Builders is a member of the West Central Home Builders Association, National Association of Home Builders, The Better Business Bureau, Wapakoneta Area Chamber of Commerce and other local business organizations.


text:
Q: Can I use python static variables to communicate between two modules? I have two files, one that performs a step in an automated test and a second that stores and emails the test results. Both files are kicked off using a Hudson server and I need the first module to share information with the second, but when I access the static variables in the Reporter module, they have the initial values of 'None'. I've cut the files down to the bare minimum in order to focus on getting the data sharing to work. File one is:
    #!/usr/bin/python

    from reports import Reporter
    import time

    class Flash_Device():
        def Begin_Flashing( self ):
            Reporter.flash_start_time = time.time()

    if ( __name__ == "__main__" ):
        flasher = Flash_Device()
        flasher.Begin_Flashing()

The second file is the reporting file defined something like the code below:
    #!/usr/bin/python

    class Reporter():
        flash_start_time = None

        def Report_Results( self ):
            print "Flash start time:", Reporter.flash_start_time

    if ( __name__ == "__main__" ):
        reporter = Reporter()
        reporter.Report_Results()

What I was hoping for is that I execute flasher.py, which updates the static variable flash_start_time, and then can access the updated value when executing reporter.py.
Will that work if I make the method Begin_Flashing() static?

A: No. The problem is that only one module can be "__main__", therefore only one main stanza will be run.
There's nothing wrong with your code though, except that you import Monkey_Reporter when you probably mean to import Reporter. And no, accessing it via reports wouldn't change anything; they're still the same class.

redpajama_set_name: RedPajamaStackExchange