Learning Bregman Divergences with Application to Robustness
Authors: Mohamed-Hicham LEGHETTAS
Markus Püschel
Venue: NeurIPS 2024 poster (2024)
Keywords: Bregman divergence
similarity and distance learning
mirror descent
corruption robustness.
Primary area: machine_vision
TL;DR: Just as the KL divergence is derived from the Shannon entropy, we generate Bregman divergences from learned base functions and apply them to obtain similarity measures for real-world image corruptions, which we then use for robustness training.

Abstract: We propose a novel and general method to learn Bregman divergences from raw high-dimensional data that measure similarity between images in pixel space. As a prototypical application, we learn divergences that consider real-world corruptions of images (e.g., blur) as close to the original and noisy perturbations as far, even if in $L^p$-distance the opposite holds. We also show that the learned Bregman divergence excels on datasets of human perceptual similarity judgment, suggesting its utility in a range of applications. We then define adversarial attacks by replacing the projected gradient descent (PGD) with the mirror descent associated with the learned Bregman divergence, and use them to improve the state-of-the-art in robustness through adversarial training for common image corruptions. In particular, for the contrast corruption that was found problematic in prior work we achieve an accuracy that exceeds the $L^p$- and the LPIPS-based adversarially trained neural networks by a margin of 27.16\% on the CIFAR-10-C corruption data set.

Learning Bregman Divergences with Application to Robustness
Mohamed-Hichhnn Leghettas Department of Computer Science ETH Zurich, Switzerland mleghettas@inf ethz. ch
Markus Püschel Department of Computer Science
ETH Zurich, Switzerland pueschel@inf. wwt.iitt............mmmme .ethz. ch
Abstract
We propose a novel and general method to learn Bregman divergences from raw -igh-dimensional data that measure similarity between images in pixel space. As a prototypical application, we learn divergences that consider real-world corruptions images (e.g., blur) as close to the original and noisy perturbations if in I,P 1.--distance the opposite holds. We also show that the learned Bregman divergence excels on datasets of human perceptual similarity judgment, suggesting its utility in range of applications. We then define adversarial attacks by replacing the projected gradient descent (PGD) with the mirror descent associated with the learned Bregman divergence, and them to improve the satte-of-the-ee in robustness through adversarial training for common image corruptions. particular, for the contrast corruption that was found problematic in prior work achieve an accuracy that exceeds the L and the APIPS-basce adversarially trained neural networks by margin of 27. 27.16% the CIFAR-10-C corruption data set.
far, even
Introduction
The need to measure the semantic distance between images is a recurring requirement various computer vision tasks, including image retrieval 55 53
near-duplicate detection [82]. face
recognition [64), and zero-shot learning [60]. This has led to a significant body of research in the field of metric learning (75 which focuses developing automated methods for learning such distances. The most successful approaches to assessing similarity between images involve encoding them into a compact latent space and computing the (.--distance between the resulting latent features. Image encoders are typically residual neural networks or vision transformers that are pre-trained in supervised 778), weeakl--uupervsee
(36), or self-supervised [3]] fashion. The latent space is usually assumed Euclidean and hence the - is the common choice, although some non- non-Euclidean geometries have been considered [23]
Image similarity measures are also crucial in the field robust machine learning. Since models are known to be sensitive to small input perturbations 9 68 [56], robustness study requires measure for the difference between clean and perturbed inputs. A common choice is the L"-norm computed in the pixel space. lacks semantic meaning but adversarial training (AT) for robustness using these
norms (via adversarial training [52] and its many follow-up variants, e.g., (69 80 72 [4] 61
has been found also improve the robustness distribution shifts associated with common, realistic image corruptions like blur or contrast changes 33). Conversely, corruption robustness evaluation shown more reliable than ad adversarial robustness evaluations when distinguishing successful adversarial defense methods from ones that merely cause vanishing gradients (55
Both metric learning and corruption robustness approaches obtain similarity measures by calculating standard norms latent spaces. In this work, we take different route by learning Bregman divergences directly the pixel space. This way, benefit from strong mathematical underpinning
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

including the associated mirror descent, an optimization framework to natively solve constrained problems that we then put to use for AT.
Bregman divergence and mirror descent. The Bregman divergence 10] (referred to as BD in the remaining paper) is generalization of the Kullback-Leebler (KL.) divergence [45] and is widely used in statistics and information theory to define distances in spaces where the Euclidean geometry is not appropriate such as probability distributions, covariance descriptors, random processes and others
[6 18 6 67 27 29]. It is defined via an underlying base function (e.g., the Shannon entropy for the KL divergence) that has to be strongly convex and with invertible gradient. Nemirovski and Yudin introduced the mirror descent framework [54] as a method for minimizing a function by utilizing a Bregman divergence to incorporate the geometric structure of the underlying space.
Contributions. In this paper we offer progress in the quest for similarity measures through a theoretically principled approach learn BDs for images in pixel space and exploit the associated mirror descent for achieving robustness through AT. Our main contributions are as follows:
We provide novel self-supervised algorithm to derive BDs for images in pixel space. The key idea is to learn eligible base functions using a suitable network architecture. These divergences are semantic in the sense that they assess similar images close and randomly perturbed ones as far from the clean image, even if in Euclidean distance the converse holds.
We then learn first BDs that are coruption-speccfic. where similar images are derived by applying image corruptions from CIFAR- 10-C dataset [33] Then we learn BDs that are corruption-oliiioous where similar images are obtained from Berkeley-Adobe Perceptual Patch Similarity (BAPPS) dataset [8])
We show that the learned BDs are consistent and successfully distinguish between corrupted and noisy images. We also show that BD learned mimic human judgment on the BAPPS dataset performs well on the two alternative forced choice (2AFC) test.
We then propose a mirror-descent-ingg cer---eeeeen--ippreeddddd algorithm to perform semantic adversarial attacks using the learned BDs instead of the L and adopt this attack for AT. Doing so we improve the state-of-the-ar in AT-based corruption robustness on CIFAR-10-C In particular for the contrast and fog corruptions that known to be problematic (e.g.. 25 and [41), the improvements are a substantial 27% and 13% increase in accuracy.
2 Background
We first recall standard adversarial training (AT) with projected gradient descent (PGD). Then provide background on the BD [10 and the associated mirror descent framework, which generalizes PGD [54)
Adversarial training. Let ((ar, y: 0) be loss of classifier parameterized by 0 where the input image E [0, 1j" and the label are sampled from the data distribution 2. As formalized by (52), training an adversarially robust model amounts to solving the following min-max optimization problem:
min E (
1a', y; O) (')((m))
max
where S(x) is the set of images that are considered similar to æ. Under the common L threat model, S(x) is defined as an LP ball centered on of chosen radius c: S(x) B(x, c). In this case, the inner maximization problem is solved by PGD, which consists of iterating over two steps: a gradient-based update followed by projection into B(x,,).
Bregman divergence (BD). For a strongly convex : X R (called base function) on a given space X' (called the primal space) with thus strictly monotonous gradient Vh X Z (Z is called the dual space), the associated BD [T0 Dr : X X + [0, oo) from æ to x' is defined as
(x x:) = h(x') - h(x:) (Vh(x), x' xz)
(2)
The BD similar metric or distance (non-negative, zero iff x x'), except that in general is not symmetric in its arguments and only satisfies a weaker version of the triangle inequality (whose
All threat models add another condition to ensure that the adversarial example x' does not exceed its natural range of pixels.

---

Table I: Notation and context of our approach. First column: generic concepts associated with the BD and mirror descent. Second and third column: known instantiations. Last column: our learned BDs with novel approach to robustmess application.
Generic
Euclidean norm
KL divergence
Ours
Some space X'
Euclidean space
Discrete distributions
Images
Base function h + (strongly convex)
k(p) Σ, , pt log(p:)
learned ø (an input conver NN)
h(x)= ||00||
(Shannon entropy)
Mirror map Vh: : -
Vh (approximate gradient)
Vh(x)
Vh(p). = =l.g(p.)
(strictly monotone)
Inverse map (Vh) : - X
(Vh) (z)
(Vh) 1(z); c
Fenchel conjugate y
Bregman Divergence
|| - =112
Σ; log Ps
Dg
(w || x))
(learned divergence)
Mirror descent
PGD
Hedge algorithm
Ours
z' Vh(w')
x² (x="
x ++1
VV((''
x² x= = x²' -NV((E) x++1= = -lle(x')
p = p/c o4, p² lla(p")
*+1 x² + +1((((x')) x² (xx
(vh)
x :- 11g (xx)
x++ lls(x²)
exact form is not relevant here). D₁ is convex in its first argument but not necessarily in the second [1]] The projection of an æ E X' on a closed and convex set K S X w.r.t. to Dj, exists and unique:
[x(x)) = arg min (ax'' ar).
æ'ek
The generic concepts are shown in the first column Tab. T the other columns are examples. The squared Euclidean distance is a BD for h chosen as the squared norm. More interestingly, if h is the negative Shannon entropy, the associated BD the Kullback-Leiller (KL) divergence. Various other divergences have been defined [6] 67 29).
The Bregman ball centered on æ with radius is then given by
By (x, (a' E X (a S].
(4)
The ball B, is bounded, compact if X' is closed, and convex (21).
Mirror descent. Mirror descent [54] framework for optimizing functions f X' R possibly constrained to a feasible convex set K: minæek (ar), given a suitable base function h that defines BD. Mirror descent requires the gradient Vh (called the mirror map) and the existence of (Vh) (called the the inverse map). The algorithm is iterative as shown in the first column in Tab. I After initializing x any point K, each iteration consists of four steps: (i) mapping the current point x to point in the dual space x' = Vh(x*) through the mirror map, (ii) taking gradient step of size ry: z1+1 zt (xx', (iii) mapping z++1 back to the primal space using the inverse map: x = (Vh) (2(+1), (iv) projecting x² into the feasible set IK w.r.t. D₁: a--1 Ilx(x*) with (
As shown in Tab. [ for the Euclidean divergence, mirror descent is exactly PGD. For the KL divergence it becomes the so-called hedge algorithm (26). In this paper, sketched in the fourth column, we will learn base functions that we call @ and associated divergences Dy for common image corruptions and use them for AT.
3 Learning BD
As first main contribution we exploit the theory BD to derive new similarity measures for images. Namely, we learn a base function h & that satisfies the properties to make D3 a divergence. Mathematically, this e will play the same role as the Shannon entropy for KI. divergence. Formally, the challenge is to learn ó with the following properties:
3

---

4.0
3.5
10
25
2.0
-1
-1
(a) Training samples of'
(b) Heat map of ||n
mn (c) Heat map of leareed (
(0, 0), the noisy perturbations are in blue, the corrupted points T(x) (in red) have angles between 8 ग and æ. (b) Heat map of the d to the origin, which is unable to distinguish corrupted from noisy points. (c) Heat map of our learned BD trained the samples in (a), which considers corrupted points very close compared to noisy points.
Figure 1: Learning BD in two dimensions. (a) The original point is
é is strongly convex and differentiable, and thus D& a divergence; 2. Vo(œ)) and (<)) are (approximately) computable to execute mirror descent.
3.1 Strongly convex architecture
We propose to model á as deep neural network with a particular architecture: the imput convex neural network (ICNN) [ 42 for which we propose self-supervised learning algorithm. The architecture is an L-layered deep neural network with activations z' defined as:
u' = 90 W x
z = gd
U + V + bo
(5)
u' q'11 w
x' ----1 Ul'u' +
6'-1] 1-11 for 2 2515L.
And finally the output is defined as x(x) = x + ج with a > 0. The weights W U² and V with the biases b' are learnable parameters while of and g' are non-linear activation functions.
The function é is convex provided that all V V²,.., VL-1 and U U UL-1 non-negative and all the activation functions q' and g are convex and non-decreasing II Proposition 1]. Furthermore, adding the term / [ to the final layer ensures that á a-strongly convex.
We can choose the activations q' to be the Hadamard square and the weights U ..., UL-1 be the identity matrix. As we intend to compute the derivative of this network with respect to the input (to obtain V/), the derivative of the Hadamard square will be linear feedthroughs. This activation function has proven to be the effective in practical settings. Further, we set all the activation functions g' be the continuously differentiable exponential linear unit (CELU) (5] and the linear layers as convolutions. Once we have ø. we numerically approximate the evaluation of the mirror map V (xx Vo(œ) using automatic differentiation [58] obtain the associated divergence as
Dø(æ' ó((') <(x) (x)) x' -x)- -
(6)
3.2 Training divergences for corruptions
real-world corruption an image r(x)) (like blurred or with changed contrast) typically lies at a large L distance e (say 10) of the clean image and thus L--based attack with this would find it but instead an extremely noisy one क at similar distance which would likely not be recognizable by human. As an additional problem, the L.-based AT also does not converge for large and
typically very small around 0.1 are used [33 25 74
39 411.
Our second main contribution is to train ø such that the induced D& considers corrupted image T2x) close to the clean while considering noisy images {Ø pm far away even when the Euclidean

---

distance suggests the opposite. This means each of the divergences ( x)), i I,... m, should
be larger than (T(T(z) æ) or equivalently -Do(r(x) || a) > D ( x). We propose the following Bregman loss (x o, v to jointly enforce these inequalities:
La a Φ, v) = - log e (2(T(m)) -=(r(()))
Σ, (o(**l(m)
The loss (1(aaaa o. V can be interpreted as cross entropy where the logits vector is the negative of the BDs (T || m), San-Day (a("" .),,.., (# a)] and the ground truth class always corresponds
the first entry. Then, we learn o by minimizing:
min BanD [=( 0, W)].
(7)
After successful training the Bregman ball (x (T(T(2) æ)) contains the transformed image rax) by definition but does contain any of the noisy images (#') We execute this approach on an example in two dimensions as illustrated in Fig.
Sampling noisy images. To train for 7 we need way to sample random images { 1m at distance proportional to that the corrupted image [[+()) - x x||2. This distance is controlled by the proportion coefficient d E (0, 1]. In other words, sample {क Ji=1 from some distribution X such
that:
m Σ 1|at
1
20122 d [|r())) 0/12-
We chose this distribution to be the isotropic Gaussian:
ï = x + (1/vn - [17(2) ml120, (O,
(8)
This way the expectation Appendix A).
[|| a:| [|]] asymptotically equivalent dll[(a:) æl12 (proof in
4 Mirror descent adversarial training
As the third main contribution, we use our learned BDs D3 to achieve corruption robustness through AT. First, part of the threat model we define the neighborhood of clean image as Bregman ball:
S(x) (z,
Then, we perform the attack by instantiating mirror descent (Tab. to solve the inner maximization problem 1.. As explained in Sec. 2] doing so requires the inverse map (VØ)-* and projection
w.r.t. D& that we discuss next.
Inverse map. Since obtain an approximation, we leverage the Fenchel conjugate [24 convex Φ is again convex, and defined as:
gradient of neural network, its inverse Wr 1 is not readily available. To
Z - R of ó, which exists for
((z) max (x, 2) ((x).
(10)
If Φ is of so-called Legendre type (i.e., proper closed, essentially smooth and essentially strictly convex (63), then [2]] states that (VØ) -1 V general, checking that a function is Legendre type is difficult (6]. in particular in this case where the function is neural network. So instead
of deriving a closed-form solution using this result, we use to motivate an approximation: first defining the conjugate Φ again as an ICNN with the exact same architecture as & in ( then training by minimizing:
2
min EgED (V))) ar112] J.W
(11)
Now (xx RJ V VΦ( is again computed using automatic differentiation and approximates (V desired.
In this expression, V is not an explicit neural network but rather gradient of the neural network computed w.r.t the input.
5

---

Projection. The projection w.r.t. BD into general convex set is difficult to compute [9.. Numerical solutions only exist for special sets such as hyperplanes or affine spaces that are not applicable to our set of interest S(x)). So to approximate the projection of x:" into S(x) (see last row last column of Tab. D. we perform a binary search over the segment having a and x:" as endpoint until we find a point a' + E S(x:). This heuristic is not guaranteed to produce optimal results, as there may exist points x' E S(x)) closer to x" than w'+1, that are out of the considered line segment. However, as we will show, it is fast enough to be incorporated in training and it yields good results (see Sec. 6
5 Related work
Corruption robustness via data augmentation. Much of the prior literature on corruption robustness aims to improve citto--distribution generalization by using simulated and augmented images for training. Many such data augmentation techniques are based on creating synthetic training examples through mixing pairs of training images and their labels. This is achieved for example by linear weighted blending of images [79] or by cutting and pasting parts of an image onto another [77]. Researchers also fused images based on masks computed through frequency spectrum analysis [30, based on adaptive masks 488 or based on moodll-generatee features [70]. Other works considered a hybrid version of these mixing methods [57]] stochastic version of them 57 an ensemble of them 776 or a concurrent combination of them
Adversarial attacks without LP-norms. Another line of work focuses on adversarial image pertur- bations not constrained by Ld-norms. (35) introduces semantic adversarial attacks that target image transformation parameters instead of image pixels. Similarly, (22) targets spatial transformations. 34 manipulates the hue and saturation components in the hue saturation value (HSV) color space to create adversarial examples. In addition to colorization, [8] also tweaked the texture of objects within images. [65] modified colors within the invisible range. Some works altered the semantic features of images through conditional generative models (38 or conditional image editing [59].
Robustness via learned similarity metric.
The closest related work adopts the so-called learned
perceptual image patch similarity (LPIPS) to study robustness. LPIPS is a weighted sum of the T.2 of the feature maps taken from the activation layers of a trained convolutional network:
LPIPS( x') = Σ wi will - w/ (2x")) (22)
(12)
where wi is the feature map up to the (-layer and wi weighs the contribution of the layer I. 71 and [51] propose an attack similar to [II] by adding the LPIPS along with the Lo-norm. Differently, 44 and [46] used LPIPS as a function to define the set of similar images (refer to Sec. 2 for notation context): S(x) = fa' E R"I LPIPS(x: x²) S c). Since the projection into this LPIPS-based set does not admit a closed from expression, solving the inner maximization problem of (T) (i.e., performing the adversarial attack) requires approximation [46] or relaxation [41]. The resulting attacks and their associated AT have been proven effective to train robust models against common image corruptions.
We compare against LPIPS in our experiments.
Learning BDs BDs have been widely used in machine learning but are typically hand-engineered
and not learned 4 73 44). [66] 17 62) learn BDs relying on piccewise linear functions and linear
lower bound approximation to ensure the convexity of the learned base functions. These methods are limited to low-dimensional inputs, either tabular data or extracted features. (66] uses Gorubi solvers (2 for lower bounds approximation as part of clustering/ranking algorithms. Similarly, [17] use functional BD and apply it clustering while [62] learn the architecture proposed by [66] through a contrast learning algorithm. Recently, [50) proposed to learn a BD for clustering where its input are features extracted from a CNN. In contrast, are the first to learn an end-to-end BD on images from
raw data where the inputs to the divergence are pixels in a way that yields a convex base functions by construction without bound approximation. This allows us instantiate the Bregman ball (to define robustness) and to run the mirror descent framework (to train for robustness), which is not possible with prior methods.
6 Corruption-specifie Bregman divergences
We first show that we can successfully learn a BD that assesses corrupted images (for a given type of corruption) as close and randomly perturbed ones as far from the clean image, even if in Euclidean

---

density
density
density
0.08
0.050
0y0050 [x]
0.35
Inte) xila
0.025
0.06
0.000
0:25
0.04
density
0.20
0.15
0.02
0.10
0.00
10
0000
0.0
0.2
0.4
0.6
0.8 1.0
0.00
1
(a) Euclidean distance: equal
104
distributions
(b) Trained BD
Figure 3: Distribution trained
Figure 2: (a) Noisy (blue) and contrast-corrupted (red) images chosen to have equal distribution Euclidean distance to the clean image, and (b) the associated distributions of the learned BDs. Done over 10,000 CIFAR-10 10 test set images.
BDs for contrast-corrupte im- ages Dx(T(w) II x) with multiple severities over 10,000 CIFAR-10 test set images.
distance the converse holds (see Sec. 3 We perform experiments on CIFAR-10 43 and consider the 14 noise-free corruptions from CIFAR-I0-C 333 that can be applied with severities from to 5. One focus are the corruptions of contrast and fog, which have been found the most challenging in We first analyze the learned BDs and then show robustness results when used with AT.
AT 25 41
6.1 Learning the BD
Learning BD amounts to learning the base function. For both the base function & and its conjugate we use the same architecture: an ICNN with 12 convolutional layers followed by 4 fully connected layers. The strong-convents parameter is chosen as a = 10 -3 The mirror map and the inverse map numerically approximated using autograd. grad from Py Torch's automatic differentiation engine (58). As initialization phase, we first train and ø such that v and V approximate the identity function (so initially T = - holds) on uniformly drawn samples from the usual range of pixels [0, 1|":
min E (0 [Il (a+) -x112)-
(13)
6
This identity training is performed for 7,000 steps using the Adam optimizer 40 with a batch size of 64, a learning rate of 3 10 and no weight decay. For a given corruption т, we then train ø with 77) while randomly sampling its severity (1 to 5) for each image at each epoch. The hyperparameter for sampling noisy images in (8) is uniformly sampled from [1999. The training batch contains 32 clean images, one corrupted image for each clean image, and m 63 samples of noisy images per clean image (2,080 images in total). The training is performed for 10 epochs using the AdamW optimizer [49 with an initial learning rate of 10-4 and weight decay 10-9, After each update of & according to (7). we also update क according to (11). Finally, we freeze the parameters of and continue training for an additional 10 epochs. The training converged for 10 of the 14 considered corruptions.
It is conceivable train BD be symmetric, however, it is not good idea since perfectly symmetric BD is just a quadratic function. However, we found that our learned divergence is qualitatively symmetric in the sense that it performs equally well with flipped arguments (see App. D for details).
Performance on corruption vs. noise. We first show in Fig. 2 that the learned divergence D3 on
images (dimension n = 3072) agrees with the 2D example in Fig. I To do so we consider, for the test set of 10,000 clean images œ, contrast-corrupedd images 7 7(x) with severity
5 (red, one per clean image) and a set of noisy images (blue, one per clean image). The noisy images are sampled from with df = 1.0. With this choice, the distribution of the = to the clean image is equal for the noisy and the corrupted images (Fig. 2 a). Fig. 2 shows the distribution very close (mean 3.8, std 6.0) but the
learned
divergences to the clean image. Here, all corrupted images noisy ones far (mean 8385, std 4939), which shows that the learned BD works as intended. Visual results images from ImageNet are provided in App. D
Next, we generate multiple corrupted images with different severities from to s = 5 and report their divergences from the clean images in Fig. R The divergence considers more severely corrupted
7

---

images further from the clean images expected. All these results are qualitatively the same for all 10 corruptions with learned BDs.
Comparison against other similarity measures. We evaluate how well different similarity measures distinguish between noisy and corrupted images. For each clean image and the corresponding corrupted version 7 r()) with severity 5, we sample 9 noisy images ă. We repeat the sampling for
different noise coefficients
shown in Fig. 4 We consider 5 similarity measures å to distinguish
between noisy and corrupted images: ô = L over the pixels. our trained BD 8 De, and the three
state-of-the-as the-tt---trrtttt metric learning methods Dino 13 Unicom
21. and Moco (v2) 15
x). An accurate similarity measure yields 8 (z)) x) smaller than the rest. We test this accuracy over the test set for multiple values
First we measure the similarities: (( 2)) (())))((()............."........
of noise coefficients d in Fig. 4a Our learned divergence performs best by far, and considers noisy images further compared corrupted images for all d, whereas other state-of-the-an metric learning measures only do so for high noise d.
Next, we inspect the ratio ō(σē /))((((())) æ) and report the aggregated results over the test set in Fig. 4b For L this ratio is by construction. We observe that learned ó offer better ratios (distinguish corrupted from noisy images better) than L and that this distinction improves with d as expected. Consistent with the accuracy results, our trained BD outperforms the other measures by 1 for all noise levels d.
yielding ratios
accuracy
100
similarity
d
80
0.025
0.05
0.1
0.2
0.4
60
Unicom
Dino
7,2
0.025
0.05
0.1
0.2
0.4
40
Mocolv2)
Dino
0.09
0.21
0.41
0.67
0,98
Bregman
Unicom
0.62
0.72
0.88
20
Moco (v2)
0.71
0.76
0.83
0.93
1.02
Bregman (ours)
4.15
14.79
52.6
192.7
726.5
coefficient
(a) Accuracy
(b) Ratio r = 8(3; x))6(((()),))))))
Figure 4: Comparing the similarity of corrupted images ((T(a)), .:) against the similarity of noisy images 8(@, æ) considering different similarity measures 8, different noise levels d, averaged over the test set. We test whether (x)) x) < 8(ă, x) and report it as an accuracy in (a). (b), we further inspect the ratio 8(ă, 0) (z)) a)) that should be I for successful noise-corruption distinction.
6.2 AT with mirror descent
As an application of our learned BD, we perform AT by instantiating the associated mirror descent (see Sec. 4 and compare against the relaxed LPIPS AT (RLAT) [4]. We show that the proposed method improves the state of the art adversarial training- based robustness on several common image corruptions. For the classification model which was also used by 41). J. For fair comparison, we set the number of iterations for our attack to T 1 to match the one-step attack used in RLAT. We also compare against the L PGD AT. AT details are reported in App E The mirror descent is executed following Alg. Samples from the generated adversarial images provided in App.
use the PreAct ResNet-18 architecture (32),
AT for contrast corruption. Both PGD and RLAT fail to improve robustness against contrast as found by (25) and [1 and replicated in Tab. 2 Our mirror descent AT using the learned BD for contrast improve this robustness considerably across all severities (on average from 63.92% to 87.4%). Surprisingly, mirror descent AT for the zoom blur corruption yields further improvement to 90.03% on average. We discuss the reason the next expanded experiment.
Comparing AT for different corruptions. We expand the previous experiment by mirror descent AT for fog, and brightness corruptions and report the average accuracy across severities in Tab. 5 for different corruptions. In all considered cases, our mirror descent AT maintains high accuracy on clean images. We notice that with the zoom blur divergence performs best for contrast, brightness, and very well for fog, but, surprisingly, not for zoom blur, for which LPIPS AT is best.

---

Table Comparison of corruption robustness of models trained under different regimes.
Standard accuracy
Contrast
Average
1
8 2
3
4
5
Standard training
95.12
94.52
91.32
87.50
86.40
38.68
78.13
IAdversarial
PGD
93.52
91.68
82.96
72.31
51.43
21.26
63.92
training
RLAT
93.27
91.47
82.32
70.65
48.35
21.58
62.87
Mirror Descent with D
94.04
93.99
92.77
91.20
88.33
70.72
87.40
Mirror Descent with D Damomsblrr
95.16
95.00
93.94
92.75
90.41
78.05
90.03
Table 3: Corruption robustness of the standard-trainee model against adversarially trained models under L RLAT, and our mirror descent (MD) AT for different corruptions.
Standard
Contrast
Fog
Zoom blur
Brightness
Standard training
95.12
78.13
88.72
78.86
93.46
PGD
93.52
63.92
77.47
85.87
91.88
Adversorial training
RLAT
93.27
62.87
77.00
85.88
91.72
MD Dromma
94.04
87.40
90.34
80.81
92.51
94.62
83.77
90.87
81.84
93.03
MD Droom bier
95.16
90.03
90.50
79.59
93.47
MD D higghnness
94.71
88.61
90.16
79.16
93.31
We notice a high degree cross-corruption robustness generalization for the shown models. E.g., model trained for brightness also performs well contrast. The reason is that the underlying BDs exhibit the same kind of generalization, i.e., the BD trained for brightness also considers contrast corrupted images close to the original. We provide detailed analysis in Appendix [ For the 6 corruptions with learned BDs not shown, our AT did not improve over prior work which we attribute the small scale of our ICNN; see limitations below.
Corruption-oblivous Bregman divergence
Next train a BD on distinct dataset of varying corruptions, thereby rendering it oblivious CIFAR- 10-C. Specifically, we use the Berkeley-Ados Perceptual Patch Similarity (BAPPS) data 81 which is a collection of image triplets (reference, distortion distortion 2) and a human judgment stating which of distortions is similar to the reference (so no classification labels). The data set features diverse range of images and distortions, spanning categories, including traditional and CNN-based distortions. The former modify images through a combination of low-level edits such as saturation adjustments and spatial warping, while generative model to produce distorted images. We show results on BD learning and for robustness with AT on this data set.
distortions alter the parameters of
7.1 Learning the BD
Somewhat different from the BD learning before, train here the BD mimic the human judgment in BAPPS, evaluated on the 2AFC test, which provides 6 categories test data. To do so we consider images human-judged to be more similar close, and the other we are not using additional pre-training data, we compare against the VGG version of LPIPS that does not use ImageNet pre-training. The training pipeline (loss, optimizers, batch size, etc.) is similar to that in [8T]. We report the accuracy results on the test categories of 2AFC in Tab. Our method outperformed LPIPS in all categories except for Frame Interpolation.
far from the original. Since
AT with mirror descent
We perform again AT by training BD on the entire BAPPS, different from Sec. 7.1
described
in Sec. 3.2 except that the corrupted image not generated by a corruption T but rather one of the distortions from BAPPS. This BD is thus oblivious to any particular corruption and those in

---

Table 4: Accuracy of the trained Bregman divergence compared to LPIPS evaluated on different categories of the 2AFC task from the BAPPS dataset.
Traditional
CNN-based
Super Resolution
Video deblur
Colorization
Frame Interpolation
LPIPS Bregman (ours)
51.41
72.10
60.46
54.25 56.95
55.18
55,55
63.65
79.57
61.04
61.63
$3.73
Table 5:
Corruption robustness of the learned corruption-oblivious Bregman divergence compared to PGD and RLAT.
Clean
Contrast
Fog
Zoom blur
PGD
93.65
63.19
77.18
86.08
RI.AT
93.28
62.87
77.01
85.89
Bregman (ours)
93.61
77.70
88.00
87.12
CIFAR-IO-C. We then re-execute adversarial training CIFAR-10 with this divergence. The results on CIFAR-1O-C in Tab show again that our method outperforms RLAT and PGD especially for the fog and the contrast corruptions where PGD and RLAT are known fail [25] and [4]] Zoom blur improves over all prior results in Tab. 6
Again our AT does not improve the other categories.
8 Discussion
When used with AT, our method introduces an overhead first training for valid divergence and then in performing the mirror descent with the heuristic projection (see App. for detailed cost analysis). Our method does provide adversarial examples within the trained Bregman ball using the suggested line search projection, however a better heuristic for projection is one important avenue for improvements.
Limitations.
The training of BDs did not succeed for some CIFAR-IO-C corruptions nor for all its corruptions simultaneously, but worked on BAPPS. Further, AT with our mirror iesppret AT is unable to improve robustness prior work for several corruptions. We attribute these issues to the small scale of the used convex architecture Φ. Scaling up and training on larger data sets with larger image sizes should be easily straightforward with more GPUs, instead of the one V100 GPU we had access to. However, despite the relatively small scale, the results in Sec. demonstrate that our method can successfully learn corruption-oblivinn BD that exhibits robust generalization across various types of corruptions, when given a suitable training set.
Broader impact. One of the contributions of this paper is to increase the corruption robustness of machine vision models specifically by using the AT machinery. Corruption robustness enhances the reliability and safety of models deployed in various applications such as autonomous driving.
9 Conclusion
We see our main contribution in showing how to learn BD from raw high-dimensional data with an approach that should generalize to settings other than the image corruptions considered here. The benefit importing the associated theoretical underpinning of the BD such as the compactness of Bregman balls and the well-established mirror descent. The latter motivated for corruption robustness as prototypical application. We considered the two very different data sets CIFAR- and BAPPS to obtain both corruption-specificc and coruption-oblivious BDs, and demonstrated that they are consistent in various ways: the former approximately symmetric and monotonous in the corruption severity, the latter outperforming LPIPS in mimicking human judgment. The associated ATs were particularly successful on contrast and fog that troubled prior work.
consider AT
Our contribution is only first step and opens various avenues for further improvements including the use of more complex architectures for learning the base functions and thus the BDs, better heuristics for the mirror descent projections, and applications and data sets beyond images.
10

---

References
[1] B. Amos, L.. Xu, and J. Z. Kolter. Input convex neural networks. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 146-155. PMLR, 06-11 Aug 2017.
[2] X. An, J. Deng, K. Yang, J. Li, Z. Feng, Guo, J. Yang, and T. Liu. Unicom: Universal and compact representation learning for image retrieval. arXiv preprint arXiv:2304.05884 2023.
[3] D. Aurizio. How show F((n-1)22) Tln22)
v vn-Z
Mathematics Stack Exchange.
URL.lttpss/mmathssaekkeehnngg http://ngnecom//////om///m1 (version: 2018-11-21).
[4] A. Banerjee, S. Merugu, S. Dhillon, J. Ghosh, and J. Lafferty. Clustering with bregman divergences. Journa of machine learning research, 6(10), 2005.
[5] J. T. Barron. Continuously differentiable exponential linear units. CoRR, abs/ less///04.7483,, 2017.
[6] H. H. Bauschke, J. M. Borwein, et al. Legendre functions and the method random bregman projections, Journal of convex analysis, 4(1):27-67, 1997.
[7] A. Bellet, A. Habrard, and M. Scbban. Metric learning. Springer Nature, 2022.
[8] A. Bhattad, M. J. Chong, K. Liang, B. Li, and D. A. Forsyth. Unrestricted adversarial examples via semantic manipulation. International Conference on Learning Representations, 2019.
[9] B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šmndić, Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In Joint European conference machine learning and knowledge discovery in databuses, pages 387-402. Springer, 2013.
[10] L. Bregman. The relaxation method of finding the common point of convex sets and its applica- tion to the solution of problems convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200 217, 1967.
[11] N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pages 39-57, 2017.
[12] Y. Carmon, A. Raghunathan, L. Schmidt, P. Liang, and J. C. Duchi. Unlabeled Data Improves Adversarial Robustness. Curran Associates Inc., Red Hook, NY, USA, 2019.
[13] M. Caron, H. Touvron, I. Misra, H. Jégou, J. Mairal, P. Bojanowski, and A. Joulin. Emerging properties in self-supervised vision transformers. P Proceedings of the IEEE/CVF international conference on computer vision, pages 9650-9660, 2021.
[14] Chen, Y. Cheng, Z. Gan, Q Gu, and J. Liu. Efficient robust training via backward smoothing. 2021.
[15] X. Chen, H. Fan, R. Girshick, and K. He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.04297, 2020.
[16] S. R. Chowdhury, P. Saux, O. Maillard, and A. Gopalan. Bregman deviations of generic exponential families. In G. Neu and L. Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 394 449. PMLR, 12-15 Jul 2023.
[17] H. K. Cilingir, Manzelli, and B. Kulis. Deep divergence learning. International Conference on Machine Learning, pages 2027-2037. PMLR, 2020.
[18] Csiszar and F. Matus. On minimization of entropy functionals under moment constraints. In 2008 IEFE International Symposium on Information Theory, pages 2101-2105, 2008
[19] I. Dhillon and A. Tropp. Matrix nearness problems with bregman divergences. SIAM Journal on Matrix Analysis and Applications, 29(4):1120-1146 2008.

---

[20] S. Dodge and L. Karam. A study and comparison of human and deep learning recognition performance under visual distortions. In 2017 26th International Conference on Computer Communication and Networks (ICCCN), pages 1-7, 2017.
[21] H. Edelsbrunner and H. Wagner. Topological Data Analysis with Bregman Divergences. In B. Aronov and M. J. Katz, editors, 33rd International Symposium Computational Geometry (SoCG 2017), volume 77 of Leibniz International Proceedings in Informatics (LJPlcs), pages 39:1-39:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibnizz Zentrru fuer Informatik.
[22] I.. Engstrom, Tran, D. Tsipras, Schmidt, and A. Madry. Exploring the landscape of spatial robustness. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1802-1811. PMLR, 09-15 Jun 2019.
[23] A. Ermolov, L. Mirvakhabova, V. Khrulkov, N. Sebe, and I. Oseledets. Hyperbolic vision transformers: Combining improvements in metrie learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages
2022.
[24] W. Fenchel. On conjugate convex functions. Canadian Journal of Mathematics, 1(1):33-77, 1949.
[25] N. Ford, J. Gilmer, and E. D. Cubuk. Adversarial examples are natural consequence of test error in noise, 2019.
[26] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119 199-199, 1997.
[27] B. A. Frigyik, S. Srivastava, and M. R. Gupta. Functional bregman divergence and bayesian estimation of distributions. JEEE Transactions on Information Theory, 54(11):5130-513) 2008.
[28] L. Gurobi Optimization. Gurobi optimizer reference manual, 2023.
[29] M. Harandi, M. Salzmann, and F. Porikli. Bregman divergences for infinite dimensional covariance matrices. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1003-1010, 2014.
[30] E. Harris, A. Marcu, M. Painter, M. Niranjan, A. Prugel-Bennett, and J. Hare. [FM]iix: Enhancing mixed sample data augmentation, 2021.
[31] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9729 9939997781211 2020.
[32] K. He, X. Zhang. S. Ren, and J. Sun. Identity mappings deep residual networks. In Computer Vision-ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part IV 14, pages 630 645. Springer, 2016.
[33] D. Hendryeks and T. Dietterich. Benchmarking neural network robustness to common corrup- tions and perturbations. In International Conference on Learning Representations, 2019.
[34] H. Hosseini and R. Poovendran. Semantic adversarial examples. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 1614-1619, 2018.
[35] L. Hsiung, Y.-Y. Tsai, P.-Y. Chen, and T.-Y. Ho. Towards compositional adversarial robustness: Generalizing adversarial training to composite semantic perturbations. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 24658- 24667, June 2023.
[36] C. Jia, Y. Yang, Y. Xia, Y.T. Chen, Z. Parekh, H. Pham, Q Le, Y.H.. Sung, Z. Li, and T. Duerig. Scaling up visual and vision-language representation learning with noisy text supervision. In International conference machine learning, pages 1914-4916. PMLR, 2021.
12

---

[37] Y. Jiang, C. Liu, Z. Huang, M. Salzmann, and S. Susstrunk. Towards stable and efficient adversarial training against I bounded adversarial attacks. In Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Confer- ence on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pages 15089-15104, PMLR, 23-29 Jul 2023.
[38] A. Joshi, A. Mukherjee, S. Sarkar, and C. Hegde. Semantic adversarial attacks: Parametric transformations that fool deep classifiers. In Proceedings of the IEEE/CVF international conference on computer vision, pages 4773 2019.
[39] D. Kang, Y. Sun, T. Brown, D. Hendrycks, and J. Steinhardt. Transfer of adversarial robustness between perturbation types. arXiv preprint
2019.
[40] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[41] K. Kireev, M. Andriushchenko, and N. Flammarion. On the effectiveness of adversarial training against common corruptions. In The 38th Conference on Uncertainty Artificial Intelligence, 2022.
[42] A. Korotin, V. Egiazarian, A. Asadulaev, A. Safin, and E. Burnaev. Wasserstein-2 generative networks. International Conference on Learning Representations, 2021.
[43] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[44] B. Kulis, M. A. Sustik, and I. S. Dhillon. Low-rank kernel learning with bregman matrix divergences. Journal of Machine Learning Research, 10(13):3413376, 2009.
[45] Kullback and R. A. Leibler. On information and sufficiency. Ann. Math. Statist., 22(1):79-86, 1951.
[46] C. Laidlaw, S. Singla, and S. Feizi. Perceptual adversarial robustness: Defense against unseen threat models. In ICLR, 2021.
[47] W. Liang, Y. Liang, and J. Jia. Miamix: Enhancing image classification through a multi-stage augmented mixed sample data augmentation method, 2023.
[48] Z. Liu, S. Li, D. Wu, Z. Chen, L. Wu, J. Guo, and S. Z. Li. Automix: Unveiling the power of mixup for stronger classifiers. In European Conference on Computer Vision, pages 441-458, 2022.
[49] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint 1rX1v:1711.05101. 2017.
[50] Lu, E. Raff, and F. Ferraro. Neural bregman divergences for distance learning. In The Eleventh International Conference on Learning Representations, 2023.
[51] C. Luo, Q Lin, W. Xie, B. Wu, J. Xie, and L. Shen. Frequency- imperceptible adversarial attack on semantic similarity. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
[52] A. Madry, A. Makelov, Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
[53] Y. Movshovitz-Attia,, A. Toshev, T. K. Leung, loffe, and S. Singh. No fuss distance metric learning using proxies. Proceedings of the IEEE international conference on computer vision, pages 360-368, 2017.
[54] A. Nemirovskij and D. B. Yudin. Problem complexity and method efficiency in optimization. 1983.
[55] H. Oh Song, Y. Xiang, S. Jegelka, and S. Savarese. Deep metric learning via lifted structured feature embedding. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4004-4012, 2016.
13

---

[56] N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami. The limitations of deep learning in adversarial settings. In 2016 IEEE European symposium on security and privacy (EuroS&P) P), pages 372-387. IEFE, 2016.
[57] C. Park, S. Yun, and S. Chun. A unified analysis of mixed sample data augmentation: A loss function perspective. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
[58] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation in pytorch. 2017.
[59] H. Qiu, C. Xiao, L. Yang, X. Yan, H. Lee, and B. Li. Semanticadv: Generating adversarial examples via attributeconndttione image editing. In 20CV.
[60] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748-88 9748.8763. PMLR, 2021.
[61] S.-A. Rebuffi, S. Gowal, D. A. Calian, F. Stimberg, O. Wiles, and T. Mann. Data augmentation can improve robustness. In A. Beygelzimer, Y. Dauphin, Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[62] M. Rezaei, F. Soleymani, B. Bischl, and S. Azizi. Deep bregman divergence for sulf-super representations learning. Computer Vision and Image Understanding, 235:103801, 2023.
[63] R. T. Rockafellar. Convex analysis. Princeton Mathematical Series. Princeton University Press, Princeton, N. J., 1970.
[64] F. Schroff, D. Kalenichenko, and J. Philbin. Facenet: A unified embedding for face recogni- tion and clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815-823, 2015.
[65] A. S. Shamsabadi, R. Sanchez-Matilla and A. Cavallaro. Colorfool: Semantic adversarial colorization. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Seattle, Washington, USA, June 2020.
[66] A. Siahkamari, X. Xia, Saligrama, D. Castañón, and Kulis. Learning to approximate a bregman divergence. Advances in Neural Information Processing Systems, 33:3603-3612, 2020.
[67] W. Stummer and I. Vajda. On bregman distances and divergences of probability measures. IEEE Transactions on Information Theory, 58:1277-1288, 2009.
[68] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. Jan. 2014. 2nd International Conference Learning Representations, ICLR 2014 Conference date: 14-04-2014 Through 16-04-2014.
[69] J. Uesato, J.-B. Alayrac, P.-S. Huang, R. Stanforth, A. Fawzi, and P. Kohli. Are Labels Required for Improving Adversarial Robustness? Curran Associates Inc., Red Hook, NY, USA, 2019.
[70] D. Walawalkar, 7. Shen, Z. Liu, and M. Savvides. Attentive cutmix: An enhanced data augmentation approach for deep learning based image classification. CoRR, htt//2003.13444 2020.
[71] Y. Wang, S. Wu, W. Jiang. S. Hao, Y. Tan, and Q Zhang. Demiguise attack: Crafting invisible semantic adversarial perturbations with perceptual similarity. CoRR, abs/2107.013%6 2021.
[72] D. Wu, S.-T. Xia, and Y. Wang. Adversarial weight perturbation helps robust generalization. In Proceedings of the 34th International Conference on Neural Information Processing Systems, N 20, Red Hook, NY, USA, 2020. Curran Associates Inc.
[73] I. Wu, R. Jin, S. Hoi, J. Zhu, and N. Yu. Learning bregman distance functions and its application for semi-supervised clustering. Advances in neural information processing systems, 22, 2009.
14

---

[74] C. Xie, M. Tan, B. Gong. J. Wang, A. L. Yuille, and Q. V. Le. Adversarial examples improve image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), June 2020.
[75] E. Xing, M. Jordan, S. J. Russell, and A. Ng. Distance metric learning with application to clustering with side- -ndeiifformatin. Advances neural information processing systems, 15, 2002.
[76] H. Yin, D. Cao, and Y. Zhou. Randommix: An effective framework to protect user privacy information ethereum. In 2022 IEEE 22nd International Conference on Software Quality, Reliability, and Security Companion (QRS-C), pages 764-765, 2022.
[77] S. Yun, D. Han, S. J. Oh, S. Chun, J. Choe, and Y. Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In International Conference on Computer Vision (ICCV), 2019.
[78) x. Zhai, A. Kolesnikov, N. Houlsby, and L.. Beyer. Scaling vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12104-12113, 2022.
[79] H. Zhang, M. Cisse, Y. Dauphin, and D. Lopez-Paz. mixup: Beyond empirical risk mini- mization. In International Conference on Learning Representations, 2018.
[80] H. Zhang, Y. Yu, J. Jiao, E. Xing, L. El Ghaoui, and M. Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference machine learning, pages 7472-7482. PMLR, 2019.
[81] R. Zhang, P. Isola, A. A. Efros, E. Shechtman, and O. Wang. The unreasonable effectiveness of deep features as perceptual metrie. In 2018 IEEE/CVF Conference on Computer Vision and Pultern Recognition, pages 586-595, 2018.
[82] S. Zheng. Y. Song, T. Leung, and I. Goodfellow. Improving the robustness of deep neural networks via stability training. Proceedings of the ieee conference on computer vision and pattem recognition, pages 4480-448. 2016.
15

---

A Asymptotic equivalence of noisy image sampling expectation
This section presents the proof mentioned in Sec. equivalent to d ||<(x)- ø||2- We first show that:
3.2 the expectation EE [|| æ|[2] is asymptotically
( a 2 d
||||
2=12]
[1(())
vn (T(2)
Then we simplify this expression. Deriving the expectation. Let a E IR" a fixed image and x random variable defined as follows with μ >
= nd 8 N In),
(14)
The random variable is a gaussian because is a linear combination of gaussians (æ is fixed).
æ112
Σ [23 xz,)
(15)
Σ 8?
11
uVz
z is Chi-square distribution of degree n with density:
2n/2-1e-212
(2(2)= 22/2T((1)
(16)
We defined the variable f(z) v2, u 2 0. The density of can be computed by the change or variable formula:
d.
Pu(u) pzlf (u))
du
(17)
w en-1e-u2/1
2m12-211(H)
Next, we compute the expectation of
E(u) = -0 (u)(u)
- " a² 12
2n/2-Ir(z)
(18)
V2
((n-1)/2 -dtt
(by substituting v2t)
r(a)
V2
T 71 + 1
(by definition of r)
2
So we have:
V2I n+1
B||l [||1]
E(pu) /1
(19)
In Equ. 14
set:
16

---

d [T(x)) 2
(20)
vn
to conclude that for the Gaussian defined in
2T m+ vn (T )
|||| x
d [[(x)) -
(21)
Asymptotic equivalence. To prove that E||ii x [|2] is asymptotically equivalent to d [|T(x) 2 122 suffices to prove that ( ! is is asymptotically equivalent v2/ I. The later can be obtained using Laplace/Hayman's method following the steps explained by 3
r( r( [("
2 VT
00 (cos 0)" d0
02
2
exp
-(n
1)
d0
(22)
VT
n
Pseudo-code of the mirror descent-based AT
In this section, we provide the pseudo-code of two majors phases of our method. First, Alg. T for the training of BD that was discussed in Sec. 3.2 and its inverse map presented in Sec. Our instantiation of the mirror descent procedure used for adversarial training (see Sec. 4 is detailed in See In practice, all these training procedures are performed on batches of images but here we present them for one image. We also omit the validation loops and early stopping conditions to improve readability.
Algorithm 1 Self-supervised BD training
Input: unlabeled training set 2, meaningful image corruption (such blur). Output: trained base function ø and its approximated Fenchel conjugate ø. Pre-train ø such as its mirror map Y fits the identity function following Equ. 13
Copy the parameters
Φ.
for e = 1 to F: do
for each image æ in the training set do Compute the corrupted image 7 7xx) and the distance ||T(x) x112.
Sample ã. ,², ,,.,..,,?" T.m.
Perform forward pass á to obtain ((x), ((r()((()))))))))))))))))))))))) ((ā)), )())) .... d(T)))
Perform a backward pass on & to obtain 2 = (zx).
(-())))))
Compute the Bregman loss
log -Pylr(elle) +E. Potef(=)
Perform an AdamW optimization step on the parameters of & and Yi to minimize l. Freeze the parameters of and V Perform backward pass Ø obtain x' (z).
Compute the MSE loss = ||æ: - x l2.
Perform an AdamW on the parameters of / and to minimize l'.
Unfreeze the parameters of & and v. end for end for return & Φ
C Cost analysis of the Mirror descent adversarial training
Compared to the standard AT, the (multiplicative) overhead is bounded by O(K) where K is the depth of the convex NNs used. In our case K 14. In practice, our method requires about twice the runtime the standard AT when implemented in PyTorch and run single V V100 GPU.
17

---

Algorithm 2 Our instantiation of the mirror descent
Input: clean image æ, its ground truth label y, trained base function d, mirror map vp and inverse
map V
Output: potentially misclassified image inside in the Bregman ball x' e (x,
Initialize x' æ. for i 1 to T do
? = c10
z' ((x')
z' - z' + v ,y;
x' = vT(2')
O
while (2 x) do
m (a + /2
m(x' 2)
if ( a m else
x) > then
b = m end if end while x' = clippw',00 0,
end for return x''
This overhead is due to replacing the computation of the L norm by the costly BD and the application of the mirror map and its inverse. Computing one BD amounts to two forward passes on the NN ó and one backward pass ø while computing mirror (or inverse) map is one backward pass ø (or Φ), respectively. The cost of each forward backward pass is linear in K 14, the depth of the neural network ø (or Φ)
D Further results about the learned divergence
Trained based function. In Sec. 6 we have shown that trained BD is semantically meaningful as it considers noisy image far off clean images and the corrupted images closer even when the L says otherwise. Here, we inspect the learned base functions d, i.e., our trained "entropy" for images. The distribution of its outputs on the test set is shown in Fig. 5 We notice that the trained based function have modality with amplitude different than that of the T.2-norm, the base function in the based threat models (see Tab.
density
density
0.0012
10111
0.0010
0.0008
0.0006
0.010
0.0004
0.005
0.0002
50
100
150
160000 162000 164000
Euclidean Space
Trained base function
Figure 5: Distribution of BD's base functions over 10,000 CIFAR-10 test set images. Our trained base function á (b) is compared against (a) its counterpart in the PGD setting, the half of norm I squared (see Tab. 1b.
18

---

Evaluation on higher dimensions. The performance of Bregman divergence on higher dimensions matches that presented for lower resolution (32x32) as shown by Figure The Bregman divergence successfully distinguishes corrupted from noisy 256x256 ImageNet images despite being trained on 32x32 CIFAR-10 images.
CON SATOON
THAL
CHLL
Figure 6: Evaluation of the Bregman divergence of 256x256 images from ImageNet. The clean images plotted in the first column, corrupted versions in the second column, and noisy versions (with different noise thresholds) thereafter
Symmetricity. It is conceivable to train the divergence to be symmetric Ds(æ' || x)) 2 (a || x') by minimizing the following loss in conjunction with the Bregman loss in (7): Elii x Do x') ll)] However, this is not good idea because enforcing the sym- metry limits the expressive power the learned divergence, since perfectly symmetric D3 is just
quadratic function. And indeed, our trained BD is not symmetric as shown in Fig, However,
19

---

density
3.0
-
1o |x| Pat 1008
2.5
1.5
0.5
0.0
Figure 7: Symmetricity test of the trained BD over the 10,000 images of the test set.
Table 6: Corruption robustness of the standard- trained model against adversarially trained mod- els under T.?, RLAT,, and our mirror descent (MD) AT for different corruptions.
Table 7: Evaluating a BD learned for a corruption (D in rows) on different corruptions 7' (in columns) by computing the ratio (T'((()) x) (T a) averaged over the test set.
Staddrrd
Contrast
Zoom Blur Brighness
Standard
95.12
78.13
93.46
PGD
Fog
Brightess
Advenatal uriiiing
93.27
77.00
91.72
1.0
2.32
4.23
10.97
94.04
87.40
90.34
80.81
92.51
Dfa
94.62
83.77
1,64
1.0
4.84
10.46
MD Dpere-ter
95.16
90.03
90.50
79.59
93.47
1.17
0.89
1.0
5.34
D3
Ripaans
94.71
88.6 61
16
93.31
1.11
0.68
1.03
1.0
notice that (s (>) and (s x²) have similar magnitudes, which property.
consistency
Cross Cross-corruption generalization. We consider trained divergences D for multiple corruptions As explained in Sec. 6 DJ considers image and its corrupted version r(x) close, i.c., Dī(((z) x) is small. Now, we pick another corruption r' and investigate whether D also considers 7' ((xx) close æ, by computing the ratio (z) || ())
x)) as shown Tab, 7 These ratios stay within reasonable values, in other words, and interestingly, divergence trained for a corruption t may also perform well w.rt. a different corruption r'_ This shows that a trained BD generalize across corruptions, and consequently, the associated mirror descent AT also inherits this generalization.
E Further results about mirror descent adversarial training
AT is performed using the SGD optimizer for 150 epochs with learning rate of 0.1 that decays by factor of 10 each 50 epochs, a batch size of 128, and a weight decay of 5 10-4, 4 These are the same hyperparameters for which RLAT performs the best. The RLAT radius is taken be 0.08. We also compare against the T PGD AT with radius 0.1, which 41 found the most effective for corruption robustness. Fig. 8 shows sample of the adversarial images found for the contrast and zoom blur corruptions. Fig. 9 shows more adversarial examples for all of 10 BDs (as an extension of Fig. g
20

---

Figure 8: Samples from training images (first row), adversarial examples found by our mirror descent
attack using the BD trained for Zoom Blur (second row) and Contrast (third row) corruptions.
Figure 9: The first row are clean images then each row are adversarial examples found using BD trained for different corruption in this order: contrast, zoom blur, fog, brightness, elastic, spatter, ipeg, snow, motion blur, and saturate.
21

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims are fully supported by the results in Sec. 0 and Sec. 7
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations discussed in Sec. g under the paragraph "Limitations".
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
The detailed proof of the asymptotic equivalence in provided in App. A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All training and evaluation details are reported in Sec. 6 Sec and App. (for the Mirror descent, adversarial training and robustness evaluation).
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general, releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer:
[No]
Justification: The source code is not part of the supplemental material because it is released upon publication under non-anonymized GPLv2 license.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
public/guides httpleeseeeoeeeeeeesssssoooooooe
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https
wttgg/udd/o/oouuubbeeeee ssinoolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All training and evaluation details are reported in Sec. 6.1 and Sec. 7. (for BD training/evaluuaion)) Sec. 66.2 Sec. 7.2 and App. E (for the Mirror descent, adversarial training and robustness evaluation).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Running the coreudy-cmmptaaiionnl expensive adversarial training multiple times to produce error bars beyond the compute power we have access to.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The details are reported in App
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The goal and the results of this work aim to further improve safety machine learning.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The last paragraph of Sec. g is dedicated to broader impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This work poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All the used datasets and libraries are properly cited and their licenses (Apache License 2.0 for CIFAR-IO-C, MIT License for CIFAR-10 and BSD-3 for PyTorch) are respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
27

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "BgS0iO1Afm", "reviewer": "Reviewer_DULG", "summary": "The authors propose a new method to learn Bregman divergences from raw, high-dimensional data. This method measures similarity between images in pixel space, and considers two images as similar even if one image is corrupted by real-world corruptions, such as blur, changes in contrast, or weather conditions such as fog. The method does this in-part by simultaneously considering real-world corruptions as close to the original image, while noisy perturbations as far from the original image, even when the $L^p$ distance considers noisy perturbations as close. The authors then define adversarial attacks by replacing the projected gradient descent with mirror descent using the learned Bregman divergence. Through adversarial training on this new learned Bregman divergence, they improve the state-of-the-art in robustness.", "questions": "- Can we see some examples of noisy images that are considered not semantically the same as the original? Under some noise threshold, it seems reasonable for a human to classify a noisy image as the original label, right?\n\n- In Table 3, when using the proposed method, training for one corruption doesn't necessarily perform the best for that corruption (as acknowledged by the authors in the paper). For example, $\\text{MD} \\thinspace D_{\\phi}^{\\text{contrast}}$ does not perform the best on contrast corruptions, but rather $\\text{MD} \\thinspace D_{\\phi}^{\\text{zoom-blur}}$ does the best. Do you have an explanation for that? I would have liked to see this explored and explained, as it goes against intuition.\n\n- There are a lot of approximations, like computing the inverse map. How do you expect your algorithm to perform with higher resolution images?", "limitations": "The authors appropriately acknowledge limitations where appropriate.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The authors clearly explain the pipeline of the algorithm and give great explanations for the choices they made (e.g. using equation (7) to approximate $\\nabla \\bar{\\phi}$.)\n\n- The authors make a good case for using Bregman divergences and learning the metric, and it seems like an interesting direction.\n\n- The algorithm seems well-motivated at each step of the pipeline, and it looks like the authors took care to make sure each step follows theory. Figures 1, 2, and 3 are helpful in explaining the motivation.", "weaknesses": "- A big weakness is using only one dataset for comparison. Perhaps the authors could show more experiments on ImageNet-C, and/or the Berkeley-Adobe Perceptual Patch Similarity (BAPPS) that was introduced with one of the methods the authors compared against, LPIPS.\n  - On the above note, there are a lot of parts to the algorithm, and it's unclear how hard one has to tune the algorithm to make sure each approximation lines up to get an overall, well-performing model. I would have wanted to see a stress test on the pipeline with larger images.\n  - If the authors had comparisons on more datasets and of more difficulty than CIFAR10-C, then I would be inclined to raise the score to an accept.\n\n- The proposed method takes longer to train than other standard adversarial training methods, as mentioned in the appendix.\n\nEDIT: After considering the author responses and reading all the reviewers, I have raised my score from a 4 to a 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the \"great explanations\" of the choices we made (especially the approximation of the conjugate $\\nabla \\overline \\phi$), for finding the use of the Bregman divergences for metric learning \"interesting direction\", and for acknowledging that each step of the pipeline is \"well-motivated\". We have performed the suggested experiments, and we answer the other concerns below:\n\n> A big weakness is using only one dataset for comparison. Perhaps the authors could show more experiments on ImageNet-C, and/or the Berkeley-Adobe Perceptual Patch Similarity (BAPPS) that was introduced with one of the methods the authors compared against, LPIPS.\n\nDone, we have done two new experiments on BAPPS and evaluation on 256x256 ImageNet images. Please refer to the global rebuttal.\n\n> How do you expect your algorithm to perform with higher resolution images?\n\nThe performance on higher resolution (up to 256x256) matches that presented for lower resolution (32x32) as shown by the new experiments on BAPPS and ImageNet. The Bregman divergence successfully distinguishes corrupted from noisy 256x256 ImageNet images despite being trained on 32x32 CIFAR-10 images. The inference is possible because the convolutional layers are followed by an average pooling to size 1x1 before the final feedforward layers.\n\n\n> there are a lot of parts to the algorithm, and it's unclear how hard one has to tune the algorithm to make sure each approximation lines up to get an overall, well-performing model. \n\nThe part that needs a tuning effort is the architecture of the base function $\\phi$ which is typical for deep learning pipelines. The other parts are fairly standard such as the widely used Adam optimizer.\n\n\n\n> The proposed method takes longer to train than other standard adversarial training methods, as mentioned in the appendix.\n\nYes, it requires roughly twice the runtime as the standard AT when implemented in PyTorch and run on a single V100 GPU.\n\n\n\n> Can we see some examples of noisy images that are considered not semantically the same as the original? Under some noise threshold, it seems reasonable for a human to classify a noisy image as the original label, right?\n\nPlease refer to the rebuttal PDF. Those are 256x256 ImageNet clean samples in the first column, corrupted versions in the second column, and noisy versions (with different noise thresholds) thereafter. Unlike the $L^2$, the trained Bregman divergence considers the corrupted version closer than the noisy versions (as extensively evaluated in the plot and table in Figure 4 of the paper).\n\n\n\n> In Table 3, when using the proposed method, training for one corruption doesn't necessarily perform the best for that corruption (as acknowledged by the authors in the paper). [...] Do you have an explanation for that? I would have liked to see this explored and explained, as it goes against intuition.\n\nThis behavior is investigated and to some degree explained in the paragraph \"Cross-corruption generalization\" of Sec.7 with further experiments reported in Tab.4. For example, the fact that classification models trained with mirror descent under the divergence $D_\\phi^{zoom-blur}$ are performing well on contrast can be traced back to the fact that the divergence $D_\\phi^{zoom-blur}$ does consider Contrast corruptions close the original images. Why this is the case is not clear but one reason may be that fog/blur/zoom-blur are somewhat similar corruptions.\n\n\n> There are a lot of approximations, like computing the inverse map\n\nOur approach includes two heuristics:\n\n**Approximate inverse map.** This one we consider strong. The approximation is not only theoretically principled but also empirically precise. It is based on the Fenchel conjugate (Fenchel, 1949) as detailed in Section 4. The resulting approximation has satisfactory empirical precision: the mean square error between an image $\\boldsymbol{x}$ and its reconstruction $\\overline\\Psi(\\Psi(\\boldsymbol{x}))$ (after undergoing the map $\\Psi$ and the inverse map $\\overline\\Psi$) is less than 0.001 on the test set.\n\n\n**Approximate projection**. Indeed, the exact projection to the closest point with respect to Bregman divergence is known to be an open problem (Dhillon & Tropp, 2008) and our approach would immediately benefit from any progress, exact or heuristic. However, our proposed heuristic is successful:\n* it yields valid results (inside the Bregman ball),\n* it results in images with high semantic similarity (as illustrated in Figures 7 and 8),\n* it is fast enough to be incorporated in training, \n* it provides good results in the down-stream task (an accuracy improvement up to 27.16%),\n* mathematically, it is still a projection (idempotent mapping from a set to a subset).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cVi9TBpwmZ", "reviewer": "Reviewer_AVtS", "summary": "The authors present an approach to learn Bregman divergences that capture perceptual image similarities according to a given dataset.\nRelying on two input-convex neural networks, they present a procedure that mimics mirror descent over the learned Bregman divergence.\nThe procedure is used to learn networks that are robust to image corruptions. Results on CIFAR-10-C subsets are presented.", "questions": "1) How is the dataset for the training of the Bergman divergence obtained? Is this a holdout from the original CIFAR-10-C?\n2) Could the authors add the performance against noise-like perturbations in the comparison against PGD and RLAT? \n3) Would the proposed approach scale to ImageNet-C? I do not think scaling to ImageNet-C is necessary, but I think such discussions should be included.\n4) The employed ICNN is different from the original work [1] as it displays quadratic terms. I understand that the squared term on x added on top of $z^l$ is useful for strong convexity. What about the quadratic terms in equation (5)?", "limitations": "The limitations paragraph is satisfactory.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "The idea to (attempt to) do mirror descent over learned Bregman divergences in order to train networks robust to corruptions is novel and interesting.", "weaknesses": "While the idea in itself is interesting, I do not find neither the technical presentation, nor the provided results convincing.\n\nMost of the motivation of the work derives from the use of Bergman divergences, which come with an associated mirror descent. However, in practice, I do not think the authors can be claiming to do mirror descent, because of the approximation of the inverse map, and because of the lack of a projection operator. Given the two above limitations, I do not think what the authors do would have convergence guarantees even in the convex case. Taking this into account, the stress on the mathematical motivation of the approach seems to be a bit fragile. Sometimes mathematical concepts are introduced without a clear purpose (for instance, the Legendre type, which is then not really necessary to justify their approximation of the inverse map). I would urge the authors to tone down these claims and refrain from saying they are doing mirror descent: I'd rather call it an approach \"inspired by mirror descent\".\n\nFurthermore, the work assumes that a dataset describing the corruptions is available to learn the divergence: is this a reasonable assumption for datasets such as CIFAR-10-C, which are designed as benchmarks for OOD generalization?\n\nConcerning the results: I do not think the proposed comparisons are fair. Both l2 PGD and RLAT use a threat model which is general and not targeted at specific perturbations. As such, they attain good performance over the entirety of the CIFAR-10-C corruptions. The authors, instead, focus on a small set of perturbations and show results for an algorithm that is explicitly aware of the perturbations the network need to be robust against.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The goal is to generate Bregman divergences from learned base functions $\\phi$, that are parametrized neural networks. As a result, the gradients of the base functions $\\Psi$ and their inverses $\\Psi^{-1}$ are also learned and thus approximated by definition. We see your point on calling it mirror descent and will adapt the wording, but, after doing so, we think it is fair to use the name as it closely follows the general structure and despite the absence of convergence guarantees that, to the best of our knowledge, have never been established even for PGD when adopted for adversarial training by the seminal work of [52]. Nevertheless, we believe that the (meanwhile more, see global comment) extensive experimental results show the effectiveness of our method. Finally, we note that our heuristic is mathematically still a projection (idempotent mapping from a set to a subset).\n\n\n> Furthermore, the work assumes that a dataset describing the corruptions is available to learn the divergence: is this a reasonable assumption for datasets such as CIFAR-10-C, which are designed as benchmarks for OOD generalization?\n\n> I do not think the proposed comparisons are fair. Both l2 PGD and RLAT use a threat model which is general and not targeted at specific perturbations ... be robust against.\n\nTo address these two OOD-related concerns, we trained a corruption oblivious Bregman divergence on a different dataset (Berkeley-Adobe Perceptual Patch Similarity) and performed the associated adversarial training on CIFAR-10. The results on CIFAR-10-C outperforms RLAT and PGD especially for the Fog and the Contrast corruptions where PGD and RLAT are known to fail. Please refer to the global rebuttal for details.\n\n\n\n> How is the dataset for the training of the Bergman divergence obtained? Is this a holdout from the original CIFAR-10-C?\n\nThe Bregman divergence training algorithm (Sec. 3.2 and Algorithm 1) takes a corruption $\\tau$ as an input ($\\tau$ is a function that corrupts a given input image). Training is then done on the CIFAR-10 test set, creating pairs, clean and corrupted by $ \\tau$. CIFAR-10-C corresponds to the CIFAR-10 test set.\n\nAlternatively, it is possible to dircetly train with (clean, corrupted) pairs as we have done in the new experiments on the Berkeley-Adobe Perceptual Patch Similarity dataset (see global rebuttal for details).\n\n\n\n> Could the authors add the performance against noise-like perturbations in the comparison against PGD and RLAT?\n\nThe accuracy for noise categories such as Gaussian is low (52.41\\%) which a direct consequence of training algorithm: The core idea is to train the Bregman divergence to consider those noisy images far and thus excluded from the Bregman ball and finally not covered during adversarial training.\n\n\n\n> Would the proposed approach scale to ImageNet-C? I do not think scaling to ImageNet-C is necessary, but I think such discussions should be included.\n\nThe Bregman divergence (despite being trained on CIFAR-10 32x32 images) performs well for 256x256 ImageNet images as shown in the rebuttal PDF. Unfortunately, the adversarial training on ImageNet to evaluate on ImageNet-C is beyond the computational resources we have access to (one V100 GPU).\n\n\n\n> The employed ICNN is different from the original work [1] as it displays quadratic terms. I understand that the squared term on x added on top of is useful for strong convexity. What about the quadratic terms in equation (5)?\n\nThe equation (5) may look a bit different the equations in [1] but it is a special case that conforms to the conditions of the Proposition 1 in [1]. The equation (5) can be expanded to:\n\n$u^1 = q^0\\left[W^0x + 0 \\right]$\n\n$z^1 =  g^0\\left[U^1u^1 + V^0x +  b^0 \\right]$\n\n$u^l = q^{l-1}\\left[W^{l-1}x + 0 \\right]$\n\n$z^{l} = g^{l-1} \\left[U^lu^{l} + V^{l-1}z^{l-1} + b^{l-1} \\right]$\n\nhere [1, Proposition 1] imposes that the activation $q^l$ and $g^l$  are convex and non-decreasing and the weights $V^1, .., V^{L−1}$ and $U^1, .., U^{L−1}$ are non-negative. In particular, we can choose the activations $q^l$ to be the Hadamard power $()^{\\circ 2}$ and the weights $U^1, .., U^{L−1}$ to be the identity matrix to obtain exactly the equation (5).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7O30XMWUpk", "reviewer": "Reviewer_zPfU", "summary": "This paper proposes to use input-convex neural networks to learn Bregman divergences as a means to distinguish semantically meaningful image corruptions from random noise perturbations. The approach is linked to classifier robustness by showing how the associated mirror descent algorithm can be used to perform adversarial training against image corruptions coming from a Bregman ball. Experiments on benchmark corruption datasets show that the proposed method outperforms prior learned similarity metrics in distinguishing corruption from noise and in adversarial training. The proposed method is also shown to generalize quite well to corruptions that it is not trained on.", "questions": "1. Line 42: \"...that has to be convex and with invertible gradient.\" Do you mean strictly convex?\n2. Line 37: The title of this paragraph is \"Bregman divergence and mirror descent,\" yet mirror descent is not discussed at all. Please give a brief description of mirror descent here.\n3. Line 64: Please put the footnote number \"1\" after the punctuation (period). With the footnote number before the punctuation, it makes it look like an exponent. Please also do the same for all other footnotes.\n4. Line 73: In (3), do you mean \"argmin\" instead of \"min\"?\n5. Table 1: Please write out \"ICNN\" completely as \"input convex neural network\" here, or define the acronym somewhere in the text before Table 1 for readers unfamiliar with ICNNs.\n6. Line 79: This sentence looks strange starting with $\\mathbb{B}_h$; I suggest adding \"The ball\" to the beginning of the sentence.\n7. Table 1: Do you mean \"strictly convex\" instead of \"strongly convex\" in the text underneath the base function?\n8. Line 79: \"...but not necessarily convex.\" This is not true; Bregman balls, as you've defined them, are indeed always convex. Since $h$ is convex, its domain $\\mathcal{X}$ is convex, and therefore convexity of the Bregman ball (4) follows from convexity of $\\mathcal{X}$ together with convexity of $D_h$ in its first argument. On the other hand, if you were to have defined the ball with respect to a fixed point in the first argument of $D_h$ and varying second arguments, then the set is not necessarily convex.\n9. Line 102: I don't recall ever seeing an ICNN defined in terms of Hadamard squares of the input feedthroughs. Can you explain why you are choosing to define your ICNN model using these Hadamard squares, and how the properties of this model might differ from just using the standard linear feedthroughs with arbitrary (not necessarily nonnegative) weights? Your model seems somewhat restrictive in how much influence the feedthrough may have, as its contributions to each preactivation vector are always nonnegative.\n10. Line 123: Again, starting a sentence with math looks strange.\n11. Figure 4: How come Moco appears to perform on par with or better than the other two prior learning-based methods in Figure 4b, but it's accuracy is shown as 0 across all noise levels in Figure 4a?", "limitations": "N/A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very well-written, easy to follow, and has great visualizations. The proposed method appears novel and performative, and is certainly of interest to the ML and robustness communities.", "weaknesses": "See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thorough review and for finding our work \"novel and performative\" and \"of interest to the ML and robustness communities\". The questions **Q2**, **Q3**, **Q4**, **Q5**, **Q6** and **Q10** are directly incorporated for the next revision. We answer the rest of the questions below:\n\n**Q1 and Q7:** In both cases, we mean strongly convex. This will corrected in the next revision.\n\n**Q8:** Bregman balls are not necessary convex [21]. For example, the Itakura-Saito ball (a Bregman ball for $h(x)= − \\log x$) is not convex (Nock et al. 2005).\n\n**Q9**: The definition in line 102 is indeed a special case of an ICNN. This can be seen by expanding equation (5) to:\n\n$u^1 = q^0\\left[W^0x + 0 \\right]$\n\n$z^1 =  g^0\\left[U^1u^1 + V^0x +  b^0 \\right]$\n\n$u^l = q^{l-1}\\left[W^{l-1}x + 0 \\right]$\n\n$z^{l} = g^{l-1} \\left[U^lu^{l} + V^{l-1}z^{l-1} + b^{l-1} \\right]$\n\nhere [1, Proposition 1] imposes that the activation $q^l$ and $g^l$ are convex and non-decreasing and the weights $V^1, .., V^{L−1}$ and $U^1, .., U^{L−1}$ are non-negative. In particular, we can choose the activations $q^l$ to be the Hadamard power $()^{\\circ 2}$ and the weights $U^1, .., U^{L−1}$ to be the identity matrix to obtain exactly the equation (5).\n\nSo the non-negativity of the weights is a requirement for convexity that we can not avoid here. The Hadamard square is a choice for an activation function that has practical benefits. As we intend to compute the derivative of this network with respect to the input (to obtain $\\Psi$), the derivative of the Hadamard square will be linear feedthroughs. We have tried to define the architecture without these Hadamard squares and the results were not satisfactory. This can be appended as an ablation study for the next revision.\n\n**Q11**: The (positive) ratios of Figure. 4b are an average across all 10000 points. This ratio can be very large (>> 1) for few outliers and just below 1 for the other points. This makes the average of the ratios just above 1 (1.05 for d=1 in Figure 4b) but when we measure the accuracy (number of ratios strictly above 1) we get a negligible number of outliers and thus the accuracy will be close to 0.\n\nReferences:\n\n(Nock et al. 2005) Fitting the smallest enclosing Bregman ball. European Conference on Machine Learning, 2005.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their comments. We responded to each concern in detail in our individual responses. These discussions and also corrections will be incorporated in the next revision. We have strengthened the results of our work by performing an evaluation on the BAPPS dataset (suggested by **Reviewer DULG**) and further trained a corruption-oblivious Bregman divergence to address the Out-Of-Distribution concerns raised by **Reviewer AVtS**. These experiments are detailed below:


**A. Performance on BAPPS.** We applied Bregman learning to the Berkeley-Adobe Perceptual Patch Similarity (BAPPS) dataset (Zhang et al. 2018). Particularly, we considered the two alternative forced choice (2AFC) test. The dataset is a collection of image triplets (reference, distortion 1, distortion 2) and a human judgment stating which of distortions is similar to the reference (so no classification labels). The images and the distortions are diverse from 6 categories. We train our Bregman divergence to mimic the human judgement, more similar distortion closer to the reference. Since we are not using additional data, we compare against the VGG version of LPIPS that does not use ImageNet pre-training. The training pipeline (loss, optimizers, batch size, ... etc.) is similar to that in (Zhang et al. 2018). We report the accuracy results on the 6 test categories of 2AFC below. Our method outperformed LPIPS in all categories except for Frame Interp:

|     | Traditional | CNN-based   |  Superres | Video Deblur | Colorization | Frame Interp |
| :---        |    :----:   |  :----:   | :----:   |:----:   |:----:   |:----:   |
| LPIPS     | 51.41       | 72.10    | 60.46 | 54.25 | 55.18 | 55.55 |
| Bregman (ours)   | 63.65 | 79.57 | 61.04  | 56.95  | 61.63 | 53.73 |

**B. The corruption-oblivious Bregman divergence.** Inspired by the BAPPS experiments, we extended our robustness pipeline and experiment to be oblivious to the corruptions in CIFAR-10-C. Namely, we trained a Bregman divergence on the entire BAPPS that considers distorted versions close to the original and noisy far, exactly following our scheme described in Sec. 3.2 and Algorithm 1 except that the corrupted image is not generated by a corruption $\tau$ but rather it is one of the distortions from BAPPS. BAPPS considers a few dozens of distortions and the divergence is thus not corruption specific, and oblivious to the corruptions in CIFAR-10-C. 

We then re-executed adversarial training on CIFAR-10 with this divergence. The results on CIFAR-10-C show again that our method outperforms RLAT and PGD especially for the Fog and the Contrast corruptions where PGD and RLAT are known to fail (e.g., [25] and [41]):

|     | Clean | Fog |  Contrast | Zoom Blur | 
| :---        |    :----:   |  :----:   | :----:   |:----:   |
| PGD [41]          | 93.65 | 77.18 | 63.19 | 86.08 | 
| RLAT  [41]        | 93.28 | 77.01 | 62.87 | 85.89 | 
| Bregman (ours) | 93.61 | 88.00 | 77.70 | 87.12 | 


References:

(Zhang et al. 2018) The unreasonable effectiveness of deep features as a perceptual metric. In Proc. CVPR 2018.

Meta-review: This paper proposes an approach for increasing adversarial robustness against some semantic corruptions, such as contrast, blur and fog, which have remained as difficult problems through adversarial training. To do this, this paper proposes to formulate a learned Bregman Divergence, defined by a (strongly) convex (parametric) function. The approach then relies on learning a divergence that measures semantic perturbations (like the ones above) as close and noisy/Gaussian perturbations as far - even if their Lp norms of these are comparable. With such a divergence, the authors propose to learn a robust model by means adversarial training with mirror descent* for the obtained divergence for specific corruptions models. Their numerical experiments demonstrate that models learned under this framework have state-of-the-art robustness against these semantic perturbations.

This paper received mixed opinions and reviews, stimulating feedback from the authors who also provided significantly extended numerical experiments. The discussions among reviewers continued beyond the author-discussion period. In summary: 

**Strengths:** 

* The novel formulation of learning robust models for semantic perturbations under a learned Bregman divergence, 
* The improved robustness obtained for some corruptions. 

**Weaknesses:**

* The algorithm implemented in practice is not mirror descent exactly (which would be an important analytical benefit of employing Bregman divergences), given that two of the necessary steps (invertibility of the mirror map and projection onto a Bregman divergence ball) are hard and are therefore solved approximately.
* The initial numerical experiments were carried out on relatively small dimensions, and there are concerns on whether the obtained models are robust more generally rather than with respect to the chosen semantic corruption models.

**Conclusion:**

Upon reading all discussions and opinions, and reading the paper, I recommend this paper be accepted due to the following reasons:

1) The formulation is innovative and seems to lead to significantly better results, but some of the steps are approximations. Adversarial robustness to semantic perturbations is a hard problem, and the presented approach might provide a general framework to make progress on this front. While there were some issues about the way the claims were phrased by the authors, I trust they will incorporate this feedback into the final revision.

2) The authors have significantly expanded their numerical results, showing that the method can be scaled up to higher dimensional data during the rebuttal phase. Most of the reviewers agreed that the revised experiments are convincing and sufficient to justify acceptance.
Decision: Accept (poster)