Learning Bregman Divergences with Application to Robustness

Authors: mohamed-hicham  leghettas
markus  püschel
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 10:39:58

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.

Main paper: 
 introduction: 
 The need to measure the semantic distance between images is a recurring requirement in various computer vision tasks, including image retrieval [55, 53, 2] , 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, 7] , which focuses on 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 L p -distance between the resulting latent features. Image encoders are typically residual neural networks or vision transformers that are pre-trained in a supervised [78] , weakly-supervised [36] , or self-supervised [31] fashion. The latent space is usually assumed Euclidean and hence the L 2 -norm is the common choice, although some non-Euclidean geometries have been considered [23] .Image similarity measures are also crucial in the field of robust machine learning. Since models are known to be sensitive to small input perturbations [9, 68, 56] , a robustness study requires a measure for the difference between clean and perturbed inputs. A common choice is the L p -norm computed in the pixel space. It 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, 12, 72, 14, 61, 37] ) has been found to also improve the robustness to distribution shifts associated with common, realistic image corruptions like blur or contrast changes [20, 33] . Conversely, corruption robustness evaluation is shown more reliable than adversarial robustness evaluations when distinguishing successful adversarial defense methods from ones that merely cause vanishing gradients [25] .Both metric learning and corruption robustness approaches obtain similarity measures by calculating standard norms in latent spaces. In this work, we take a different route by learning Bregman divergences directly in the pixel space. This way, we benefit from a strong mathematical underpinning 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 a generalization of the Kullback-Leibler (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 [16, 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 to 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 a 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 as 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 corruption-specific, where similar images are derived by applying image corruptions from CIFAR-10-C dataset [33] . Then we learn BDs that are corruption-oblivious where similar images are obtained from Berkeley-Adobe Perceptual Patch Similarity (BAPPS) dataset [81] . • We show that the learned BDs are consistent and successfully distinguish between corrupted and noisy images. We also show that a BD learned to mimic human judgment on the BAPPS dataset performs well on the two alternative forced choice (2AFC) test. • We then propose a mirror-descent-inspired algorithm to perform semantic adversarial attacks using the learned BDs instead of the L p -norm and adopt this attack for AT. Doing so we improve the state-of-the-art in AT-based corruption robustness on CIFAR-10-C. In particular for the contrast and fog corruptions that are known to be problematic (e.g., [25] and [41] ), the improvements are a substantial 27% and 13% increase in accuracy. 
background: 
 We first recall standard adversarial training (AT) with projected gradient descent (PGD). Then we provide background on the BD [10] and the associated mirror descent framework, which generalizes PGD [54] .Adversarial training. Let l(x, y; θ) be a loss of a classifier parameterized by θ where the input image x ∈ [0, 1] n and the label y are sampled from the data distribution D. As formalized by [52] , training an adversarially robust model amounts to solving the following min-max optimization problem:EQUATIONwhere S(x) is the set of images that are considered similar to x. Under the common L p threat model, S(x) is defined as an L p ball centered on x of chosen radius ϵ: S(x) = B(x, ϵ). 1 In this case, the inner maximization problem is solved by PGD, which consists of iterating over two steps: a gradient-based update followed by a projection into B(x, ϵ).Bregman divergence (BD). For a strongly convex h : X → R (called base function) on a given space X (called the primal space) with thus strictly monotonous gradient ∇h : X → Z (Z is called the dual space), the associated BD [10] EQUATION)The BD is similar to a metric or distance (non-negative, zero iff x = x ′ ), except that in general it is not symmetric in its arguments and only satisfies a weaker version of the triangle inequality (whose : X → R (strongly convex) h(x) = 1 2 ||x|| 2 2 h(p) = i pi log(pi) (Shannon entropy) h = learned ϕ (an input convex NN) Mirror map ∇h : X → Z (strictly monotone) ∇h(x) = x ∇h(p)i = log(pi) Ψ ≈ ∇h (approximate gradient) Inverse map (∇h) -1 : Z → X (∇h) -1 (z) = z (∇h) -1 (z)i = e z i Fenchel conjugate Ψ Bregman Divergence D h (x ′ ∥ x) 1 2 ||x ′ -x|| 2 2 i qi log q i p i D ϕ (learned divergence)Mirror descent PGD Hedge algorithm Oursz t = ∇h(x t ) z t+1 = z t -η∇f (x t ) x * = (∇h) -1 z t+1 x t+1 = Π K (x * ) x * = x t -η∇f (x t ) x t+1 = Π B (x * ) p * i = p t i e -ηl i p t+1 = Π∆(p * ) z t = Ψ(x t ) z t+1 = z t + η∇l(x t ) x * = Ψ z t+1 x t+1 = Π S (x * )exact form is not relevant here). D h is convex in its first argument but not necessarily in the second [21] . The projection of an x ∈ X on a closed and convex set K ⊆ X w.r.t. to D h exists and is unique:EQUATIONThe generic concepts are shown in the first column in Tab. 1; the other columns are examples. The squared Euclidean distance is a BD for h chosen as the squared L 2 -norm. More interestingly, if h is the negative Shannon entropy, the associated BD is the Kullback-Leibler (KL) divergence. Various other divergences have been defined [6, 67, 29] .The Bregman ball centered on x with radius ϵ is then given byEQUATIONThe ball B h is bounded, compact if X is closed, and convex [21] .Mirror descent. Mirror descent [54] is a framework for optimizing functions f : X → R possibly constrained to a feasible convex set K: min x∈K f (x), given a suitable base function h that defines a BD. Mirror descent requires the gradient ∇h (called the mirror map) and the existence of (∇h) -1 (called the the inverse map). The algorithm is iterative as shown in the first column in Tab. 1. After initializing x 0 at any point in K, each iteration t consists of four steps: (i) mapping the current point x t to a point in the dual space z t = ∇h(x t ) through the mirror map, (ii) taking a gradient step of size η: z t+1 = z t -η∇f (x t ), (iii) mapping z t+1 back to the primal space using the inverse map:x * = (∇h) -1 z t+1 , (iv) projecting x * into the feasible set K w.r.t. D h : x t+1 = Π K (x * ) with (3).As shown in Tab. 1, for the Euclidean divergence, mirror descent is exactly PGD. For the KL divergence it becomes the so-called hedge algorithm [26] . In this paper, as sketched in the fourth column, we will learn base functions h that we call ϕ and associated divergences D ϕ for common image corruptions and use them for AT.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: The limitations are discussed in Sec. 8 under the paragraph "Limitations".Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 fairness. • 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
learning a bd: 
 As first main contribution we exploit the theory of BD to derive new similarity measures for images. Namely, we learn a base function h = ϕ that satisfies the properties to make D ϕ a divergence. Mathematically, this ϕ will play the same role as the Shannon entropy for KL divergence. Formally, the challenge is to learn a ϕ with the following properties: 1. ϕ is strongly convex and differentiable, and thus D ϕ a divergence; 2. ∇ϕ(x) and (∇ϕ) -1 (x) are (approximately) computable to execute mirror descent.We propose to model ϕ as a deep neural network with a particular architecture: the input convex neural network (ICNN) [1, 42] for which we propose a self-supervised learning algorithm. The architecture is an L-layered deep neural network with activations z l defined as:       u 1 = q 0 W 0 x z 1 = g 0 U 1 u 1 + V 0 x + b 0 u l = q l-1 W l-1 x z l = g l-1 U l u l + V l-1 z l-1 + b l-1 for 2 ≤ l ≤ L. (5)And finally the output is defined as ϕ(x) = z L + α 2 ||x|| 2 2 with α > 0. The weights W l , U l , and V l with the biases b l are learnable parameters while q l and g l are non-linear activation functions.The function ϕ is convex provided that all V 1 , .., V L-1 and U 1 , .., U L-1 are non-negative and all the activation functions q l and g l are convex and non-decreasing [1, Proposition 1] . Furthermore, adding the term α 2 ||x|| 2 2 to the final layer ensures that ϕ is α-strongly convex. We can choose the activations q l to be the Hadamard square and the weights U 1 , .., U L-1 to be the identity matrix. As we intend to compute the derivative of this network with respect to the input (to obtain Ψ), 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 l to 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 Ψ(x) ≈ ∇ϕ(x) using automatic differentiation [58] to obtain the associated divergence asEQUATIONA real-world corruption of an image τ (x) (like blurred or with changed contrast) typically lies at a large L 2 distance ϵ (say 10) of the clean image x and thus an L 2 -based attack with this ϵ would not find it but instead an extremely noisy one x at similar distance which would likely not be recognizable by a human. As an additional problem, the L p -based AT also does not converge for large ϵ and typically very small ϵ around 0.1 are used [33, 25, 74, 39, 41] .Our second main contribution is to train ϕ such that the induced D ϕ considers a corrupted image τ (x) close to the clean x while considering noisy images { xi } m i=1 far away even when the Euclidean distance suggests the opposite. This means each of the divergences D ϕ ( xi ∥ x), i = 1, ..., m, should be larger than D ϕ (τ (x) ∥ x) or equivalently -D ϕ (τ (x) ∥ x) > -D ϕ ( xi ∥ x). We propose the following Bregman loss l B (x; ϕ, Ψ) to jointly enforce these m inequalities:l B (x; ϕ, Ψ) = -log e -D ϕ (τ (x)∥x) e -D ϕ (τ (x)∥x) + i e -D ϕ ( xi ∥x) .The loss l B (x; ϕ, Ψ) can be interpreted as a cross entropy where the logits vector is the negative of the BDs -D ϕ (τ (x) ∥ x), -D ϕ ( x1 ∥ x), ..., -D ϕ ( xm ∥ x) and the ground truth class always corresponds the first entry. Then, we learn ϕ by minimizing:EQUATIONAfter successful training the Bregman ball B ϕ (x, D ϕ (τ (x) ∥ x)) contains the transformed image τ (x) by definition but does not contain any of the noisy images { xi } m i=1 . We execute this approach on an example in two dimensions as illustrated in Fig. 1 .Sampling noisy images. To train for (7) we need a way to sample random images { xi } m i=1 at a distance proportional to that of the corrupted image ||τ (x) -x|| 2 . This distance is controlled by the proportion coefficient d ∈ (0, 1]. In other words, we sample { xi } m i=1 from some distribution x such that:1 m i || xi -x|| 2 = d ||τ (x) -x|| 2 .We chose this distribution to be the isotropic Gaussian:EQUATIONThis way the expectationE [||x -x|| 2 ] is asymptotically equivalent to d||τ (x) -x|| 2 (proof in Appendix A).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Answer: [No] Justification: The source code is not part of the supplemental material because it is released upon publication under a non-anonymized GPLv2 license.Guidelines:• The answer NA means that paper does not include experiments requiring code. 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 a 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, or as supplemental material. 
mirror descent adversarial training: 
 As the third main contribution, we use our learned BDs D ϕ to achieve corruption robustness through AT. First, as part of the threat model we define the neighborhood of a clean image x as a Bregman ball:EQUATIONThen, we perform the attack by instantiating mirror descent (Tab. 1) to solve the inner maximization problem in (1) . As explained in Sec. 2, doing so requires the inverse map (∇ϕ) -1 and a projection w.r.t. D ϕ that we discuss next.Inverse map. Since Ψ is a gradient of a neural network, its inverse Ψ -1 is not readily available. To obtain an approximation, we leverage the Fenchel conjugate [24] ϕ : Z → R of ϕ, which exists for convex ϕ, is again convex, and defined as:EQUATION)If ϕ is of so-called Legendre type (i.e., proper closed, essentially smooth and essentially strictly convex [63] ), then [24] states that (∇ϕ) -1 = ∇ϕ. In general, checking that a function is Legendre type is difficult [6] , in particular in this case where the function is a neural network. So instead of deriving a closed-form solution using this result, we use it to motivate an approximation: first defining the conjugate ϕ again as an ICNN with the exact same architecture as ϕ in (5); then training by minimizing:2 min ϕ,ΨEQUATION)Now Ψ(x) ≈ ∇ϕ(x) is again computed using automatic differentiation and approximates (∇ϕ) -1 (x) as desired.Projection. The projection w.r.t. a BD into a general convex set is difficult to compute [19] . 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. 1), we perform a binary search over the segment having x and x * as endpoint until we find a point x t+1 ∈ S(x). This heuristic is not guaranteed to produce optimal results, as there may exist points x ′ ∈ S(x), closer to x * than x t+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). 
related work: 
 Corruption robustness via data augmentation. Much of the prior literature on corruption robustness aims to improve out-of-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 [48] or based on model-generated features [70] . Other works considered a hybrid version of these mixing methods [57] , a stochastic version of them [57] , an ensemble of them [76] or a concurrent combination of them [47] .Adversarial attacks without L p -norms. Another line of work focuses on adversarial image perturbations not constrained by L p -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 L 2 of the feature maps taken from the activation layers of a trained convolutional network:EQUATIONwhere ω l is the feature map up to the l-layer and w l weighs the contribution of the layer l. [71] and [51] propose an attack similar to [11] by adding the LPIPS along with the L p -norm. Differently, [41] and [46] used LPIPS as a function to define the set of similar images (refer to Sec. 2 for notation context):S(x) = {x ′ ∈ R n | LPIPS(x, x ′ ) ≤ ϵ}.Since the projection into this LPIPS-based set does not admit a closed-from expression, solving the inner maximization problem of (1) (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 piecewise 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 [28] for lower bounds approximation as part of clustering/ranking algorithms. Similarly, [17] use functional BD and apply it to 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, we 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 to 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. 
corruption-specific 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 distance the converse holds (see Sec. 3). We perform experiments on CIFAR-10 [43] and consider the 14 noise-free corruptions from CIFAR-10-C [33] that can be applied with severities from 1 to 5. One focus are the corruptions of contrast and fog, which have been found the most challenging in AT [25, 41] . We first analyze the learned BDs and then show robustness results when used with AT.Learning a 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-convexity parameter is chosen as α = 10 -3 . The mirror map and the inverse map are numerically approximated using autograd.grad from PyTorch's automatic differentiation engine [58] . As an initialization phase, we first train ϕ and ϕ such that Ψ and Ψ approximate the identity function (so initially Ψ = Ψ -1 holds) on uniformly drawn samples from the usual range of pixels [0, 1] n : minEQUATIONThis 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 -4 and no weight decay. For a given corruption τ , we then train ϕ with (7) while randomly sampling its severity (1 to 5) for each image at each epoch. [49] with an initial learning rate of 10 -4 and a weight decay of 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 out of the 14 considered corruptions.It is conceivable to train a BD to be symmetric, however, it is not a good idea since a 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 D ϕ on images (dimension n = 3072) agrees with the 2D example in Fig. 1 . To do so we consider, for the test set of 10,000 clean images x, contrast-corrupted images τ (x) with severity s = 5 (red, one per clean image) and a set of noisy images x (blue, one per clean image). The noisy images are sampled from (8) with d = 1.0. With this choice, the distribution of the L 2 -distances to the clean image is equal for the noisy and the corrupted images (Fig. 2 .a). Fig. 2 .b shows the distribution of learned divergences to the clean image. Here, all corrupted images are very close (mean 3.8, std 6.0) but the noisy ones far (mean 8385, std 4939), which shows that the learned BD works as intended. Visual results on images from ImageNet are provided in App. D.Next, we generate multiple corrupted images with different severities from s = 1 to s = 5 and report their divergences from the clean images in Fig. 3 . The divergence considers more severely corrupted images further from the clean images as 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 τ (x) with severity 5, we sample 9 noisy images x. We repeat the sampling for different noise coefficients d as shown in Fig. 4 . We consider 5 similarity measures δ to distinguish between noisy and corrupted images: δ = L 2 over the pixels, our trained BD δ = D ϕ , and the three state-of-the-art metric learning methods Dino [13] , Unicom [2] , and Moco (v2) [15] .First we measure the similarities: δ(τ (x), x), δ( x1 , x), . . . , δ( x9 , x). An accurate similarity measure yields δ(τ (x), x) smaller than the rest. We test this accuracy over the test set for multiple values of noise coefficients d in Fig. 4a . Our learned divergence performs best by far, and considers noisy images further compared to corrupted images for all d, whereas other state-of-the-art metric learning measures only do so for high noise d.Next, we inspect the ratio r = δ( x, x)/δ(τ (x), x) and report the aggregated results over the test set in Fig. 4b . For δ = L 2 this ratio is d by construction. We observe that all learned δ offer better ratios (distinguish corrupted from noisy images better) than L 2 and that this distinction improves with d as expected. Consistent with the accuracy results, our trained BD outperforms the other measures by yielding ratios r > 1 for all noise levels d, (b) Ratio r = δ( x, x)/δ(τ (x), x)Figure 4 : Comparing the similarity of corrupted images δ(τ (x), x) against the similarity of noisy images δ( x, x) considering different similarity measures δ, different noise levels d, averaged over the test set. We test whether δ(τ (x), x) < δ( x, x) and report it as an accuracy in (a). In (b), we further inspect the ratio δ( x, x)/δ(τ (x), x) that should be > 1 for a successful noise-corruption distinction.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) [41] . We show that the proposed method improves the state of the art in adversarial training-based robustness on several common image corruptions. For the classification model f , we use the PreAct ResNet-18 architecture [32] , which was also used by [41] . For a 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 2 PGD AT. AT details are reported in App E. The mirror descent is executed following Alg. 2. Samples from the generated adversarial images are provided in App. E.AT for contrast corruption. Both PGD and RLAT fail to improve robustness against contrast as found by [25] and [41] 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 in 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. 6 for different corruptions. In all considered cases, our mirror descent AT maintains high accuracy on clean images. We notice that AT 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. We notice a high degree of cross-corruption robustness generalization for the shown models. E.g., a model trained for brightness also performs well on 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 as close to the original. We provide a detailed analysis in Appendix D. For the 6 corruptions with learned BDs not shown, our AT did not improve over prior work which we attribute to the small scale of our ICNN; see limitations below. 
corruption-oblivious bregman divergence: 
 Next we train a BD on a distinct dataset of varying corruptions, thereby rendering it oblivious to CIFAR-10-C. Specifically, we use the Berkeley-Adobe Perceptual Patch Similarity (BAPPS) data set [81] , which 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 data set features a diverse range of images and distortions, spanning 6 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 CNN-based distortions alter the parameters of a generative model to produce distorted images. We show results on BD learning and for robustness with AT on this data set.Somewhat different from the BD learning before, we train here the BD to mimic the human judgment in BAPPS, evaluated on the 2AFC test, which provides 6 categories of test data. To do so we consider images human-judged to be more similar as close, and the other one as far from the original. Since 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 [81] . We report the accuracy results on the 6 test categories of 2AFC in Tab. 4. Our method outperformed LPIPS in all categories except for Frame Interpolation.We perform again AT by training a BD on the entire BAPPS, different from Sec. 7.1, as described in Sec. 3.2 except that the corrupted image is not generated by a corruption τ but rather it is one of the distortions from BAPPS. This BD is thus oblivious to any particular corruption and those in CIFAR-10-C. We then re-execute adversarial training on CIFAR-10 with this divergence. The results on CIFAR-10-C in Tab. 5 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 [25] and [41] . Zoom blur improves over all prior results in Tab. 6. Again our AT does not improve the other categories.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 already-computational expensive adversarial training multiple times to produce error bars is 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, confidence intervals, or statistical significance tests, at 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 run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to 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 or the standard error of the mean. Justification: The goal and the results of this work aim to further improve safety in machine learning.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
discussion: 
 Limitations. When used with AT, our method introduces an overhead in first training for a valid divergence and then in performing the mirror descent with the heuristic projection (see App. C for a 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.The training of BDs did not succeed for some CIFAR-10-C corruptions nor for all its corruptions simultaneously, but worked on BAPPS. Further, AT with our mirror descent-inspired AT is unable to improve robustness on 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. 7 demonstrate that our method can successfully learn a corruption-oblivious 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. 
conclusion: 
 We see our main contribution in showing how to learn a BD from raw high-dimensional data with an approach that should generalize to settings other than the image corruptions considered here. The benefit is in importing the associated theoretical underpinning of the BD such as the compactness of Bregman balls and the well-established mirror descent. The latter motivated us to consider AT for corruption robustness as prototypical application. We considered the two very different data sets CIFAR-10-C and BAPPS to obtain both corruption-specific and corruption-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.Our contribution is only a 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. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: The last paragraph of Sec. 8 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a 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 no such risks.• Released models that have a 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 a 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-10-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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • 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 is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?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. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: This section presents the proof mentioned in Sec. 3.2: the expectation E [||x -x|| 2 ] is asymptotically equivalent to d ||τ (x) -x|| 2 . We first show that:E[||x -x|| 2 ] = √ 2Γ( n+1 2 ) √ n -1Γ( n 2 ) d ||τ (x) -x|| 2Then we simplify this expression.Deriving the expectation. Let x ∈ R n a fixed image and x a random variable defined as follows with µ > 0:EQUATIONThe random variable x is a gaussian because it is a linear combination of gaussians (x is fixed).EQUATIONz is a Chi-square distribution of degree n with density:EQUATIONWe defined the variable u = f (z) = √ z, u ≥ 0. The density of u can be computed by the change or variable formula:EQUATIONNext, we compute the expectation of u:EQUATIONSo we have:EQUATIONIn Equ. 14, we set:EQUATIONto conclude that for the Gaussian defined in ( 8):EQUATIONAsymptotic equivalence.To prove that E[||x -x|| 2 ] is asymptotically equivalent to d ||τ (x) -x|| 2 , it suffices to prove that Γ( n 2 )/Γ( n+1 2 ) is is asymptotically equivalent to √ 2/ √ n -1.The later can be obtained using Laplace/Hayman's method following the steps explained by [3] :EQUATION)B Pseudo-code of the mirror descent-based ATIn this section, we provide the pseudo-code of two majors phases of our method. First, Alg. 1 is for the training of BD that was discussed in Sec. 3.2 and its inverse map presented in Sec. 4. Our instantiation of the mirror descent procedure used for adversarial training (see Sec. 4) is detailed in Sec.2. 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. e -D ϕ (τ (x)∥x) + i e -D ϕ ( xi ∥x) . Perform an AdamW optimization step [49] on the parameters of ϕ and Ψ to minimize l. Freeze the parameters of ϕ and Ψ. Perform a backward pass on ϕ to obtain x ′ = Ψ(z).′ = ||x ′ -x|| 22 . Perform an AdamW on the parameters of ϕ and Ψ to minimize l ′ . Unfreeze the parameters of ϕ and Ψ. end for end for return ϕ, ϕ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 as the standard AT when implemented in PyTorch and run on a single V100 GPU.Input: clean image x, its ground truth label y, trained base function ϕ, mirror map Ψ and inverse map Ψ Output: potentially misclassified image inside in the Bregman ball x ′ ∈ B ϕ (x, ϵ).Initialize x ′ = x. for t = 1 to T do η = ϵ10 -4t T z ′ = Ψ(x ′ ) z ′ = z ′ + η∇ x l(x ′ , y; θ) x ′ = Ψ(z ′ ) a = 0 b = 1 while D ϕ (x ′ ∥ x) > ϵ do m = (a + b)/2 x ′ = x + m(x ′ -x) if D ϕ (x ′ ∥ x) > ϵ then a = m else b = m end if end while x ′ = clip(x ′ , 0, 1) end for return x ′This overhead is due to replacing the computation of the L 2 norm by the more 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 on ϕ while computing a mirror (or inverse) map is one backward pass on ϕ (or ϕ), respectively. The cost of each forward or backward pass is linear in K = 14, the depth of the neural network ϕ (or ϕ).Trained based function. In Sec. 6, we have shown that our trained BD is semantically meaningful as it considers noisy image far off clean images and the corrupted images closer even when the L 2 says otherwise. Here, we inspect the learned base functions ϕ, 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 a modality with an amplitude different than that of the L 2 -norm, the base function in the L 2 -based threat models (see Tab. 1). Evaluation on higher dimensions. The performance of Bregman divergence on higher dimensions matches that presented for lower resolution (32x32) as shown by Figure 6 . The Bregman divergence successfully distinguishes corrupted from noisy 256x256 ImageNet images despite being trained on 32x32 CIFAR-10 images. Symmetricity. It is conceivable to train the divergence to be symmetric D ϕ (x ′ ∥ x) ≈ D ϕ (x ∥ x ′ ) by minimizing the following loss in conjunction with the Bregman loss in (7) :E [||D ϕ (x ′ ∥ x) -D ϕ (x ∥ x ′ )|| 2 ]. However, this is not a good idea because enforcing the symmetry limits the expressive power of the learned divergence, since a perfectly symmetric D ϕ is just a quadratic function. And indeed, our trained BD is not symmetric as shown in Fig. 7 . However, we notice that D ϕ (x ′ ∥ x) and D ϕ (x ∥ x ′ ) have similar magnitudes, which one can see as a consistency property.Cross-corruption generalization. We consider trained divergences D τ ϕ for multiple corruptions τ . As explained in Sec. 6, D τ ϕ considers an image and its corrupted version τ (x) as close, i.e., D τ ϕ (τ (x) ∥ x) is small. Now, we pick another corruption τ ′ and investigate whether D τ ϕ also considers τ ′ (x) close to x, by computing the ratio D τ ϕ (τ ′ (x) ∥ x)/D τ ϕ (τ (x) ∥ x) as shown in Tab. 7. These ratios stay within reasonable values, in other words, and interestingly, a divergence trained for a corruption τ may also perform well w.r.t. a different corruption τ ′ . This shows that a trained BD can generalize across corruptions, and consequently, the associated mirror descent AT also inherits this generalization.AT is performed using the SGD optimizer for 150 epochs with a learning rate of 0.1 that decays by a factor of 10 each 50 epochs, a batch size of 128, and a weight decay of 5 • 10 -4 . These are the same hyperparameters for which RLAT performs the best. The RLAT radius is taken to be 0.08. We also compare against the L 2 PGD AT with radius 0.1, which [41] found the most effective for corruption robustness. Fig. 8 shows a 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. 8 ). • 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 as long as it is clear that these goals are not attained by the paper.38th Conference on Neural Information Processing Systems (NeurIPS 2024).All threat models add another condition to ensure that the adversarial example x ′ does not exceed its natural range of pixels.In this expression, Ψ is not an explicit neural network but rather a gradient of the neural network ϕ computed w.r.t. the input. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
  - 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.
  - 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.

- The proposed method takes longer to train than other standard adversarial training methods, as mentioned in the appendix.

EDIT: After considering the author responses and reading all the reviewers, I have raised my score from a 4 to a 5.
questions: 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?

- 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.

- There are a lot of approximations, like computing the inverse map. How do you expect your algorithm to perform with higher resolution images?
limitations: limitations: The authors appropriately acknowledge limitations where appropriate.
paper_summary: paper_summary: The authors present an approach to learn Bregman divergences that capture perceptual image similarities according to a given dataset.
Relying on two input-convex neural networks, they present a procedure that mimics mirror descent over the learned Bregman divergence.
The procedure is used to learn networks that are robust to image corruptions. Results on CIFAR-10-C subsets are presented.
strength_weakness: strength_weakness: While the idea in itself is interesting, I do not find neither the technical presentation, nor the provided results convincing.

Most 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".

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?

Concerning 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.
questions: questions: 1) How is the dataset for the training of the Bergman divergence obtained? Is this a holdout from the original CIFAR-10-C?
2) Could the authors add the performance against noise-like perturbations in the comparison against PGD and RLAT? 
3) 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.
4) 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: limitations: The limitations paragraph is satisfactory.
paper_summary: paper_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.
strength_weakness: strength_weakness: See questions below.
questions: questions: 1. Line 42: "...that has to be convex and with invertible gradient." Do you mean strictly convex?
2. 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.
3. 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.
4. Line 73: In (3), do you mean "argmin" instead of "min"?
5. 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.
6. Line 79: This sentence looks strange starting with $\mathbb{B}_h$; I suggest adding "The ball" to the beginning of the sentence.
7. Table 1: Do you mean "strictly convex" instead of "strongly convex" in the text underneath the base function?
8. 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.
9. 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.
10. Line 123: Again, starting a sentence with math looks strange.
11. 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: limitations: N/A.

Comments: comment: We thank the reviewer for engaging in the rebuttal and for the corrections.

**Q1 and Q7:** Indeed, strict convexity alone is enough to define the divergence but since our ICNNs is $\alpha$-strongly convex (needed later for the conjugate), one can assume strongly convexity from the beginning.


**Q8:** We agree. The Bregman ball as we defined in Eq.4 is what is called the dual Bregman ball which is convex. This convexity explains the success of our projection procedure.


> ... since $q^l(\cdot) = (\cdot)^{\circ 2}$ is not nondecreasing (it is decreasing in a given element when that element ranges over negative values). However, it is pretty obvious that your proposed architecture is input-output convex.

Indeed, it is always the case that the input range is non-negative due to the CELU activations.

 >  My original comment was moreso on your choice of using Hadamard square activation functions for the feedthrough terms. In particular, I suggest clearly asserting in your manuscript that your (5) is a particular example of an ICNN where you choose to impose Hadamard square activations on every feedthrough term, in order to clarify to the reader that not all ICNNs can be written in your form. Also, it would be good to discuss why you chose such a parameterization, over the more general ICNNs used in other works.

We will feature this architectural choice more prominently in the next revision along with an ablation study in the appendix.
Thank you for your responses and revisions. I maintain my original score. See more discussion below that I hope will help further improve your manuscript.

**Q1 and Q7**: Do you need to assume strong convexity? It is more standard to define Bregman divergences with respect to strictly convex functions, not strongly convex functions (see even your listed reference, Nock et al. 2005).

**Q8**: The Bregman ball, as you defined it in (4), is always convex. As you stated on line 72 of your manuscript, the Bregman divergence $D_h$ is convex in its first argument. Therefore, the set $\mathbb{B}_h(\mathbf{x},\epsilon)$ defined in (4) is a convex set, since it is the $\epsilon$-sublevel set of the convex function $\mathbf{x}' \mapsto D_h(\mathbf{x}',\mathbf{x})$. In your reference Nock et al. 2005, they mention that there are two ways of defining balls from Bregman divergences (equations (3) and (4) in their paper), and they mention that the second way in their equation (4), which coincides with your definition of Bregman ball, leads to a convex set, whereas the first way in their equation (3), does not necessarily lead to convexity. Their example of the nonconvex Itakura-Saito ball is an instantiation of their equation (3), which is different from your definition of Bregman ball (and, correspondingly, their equation (4)).

**Q9**: "here [1, Proposition 1] imposes that the activation and are convex and non-decreasing" ... "we can choose the activations $q^l$ to be the Hadamard power". Technically, [1,Proposition 1] doesn't apply to the expansion of your proposed architecture, since $q^l(\cdot) = (\cdot)^{\circ 2}$ is not nondecreasing (it is decreasing in a given element when that element ranges over negative values). However, it is pretty obvious that your proposed architecture is input-output convex. My original comment was moreso on your choice of using Hadamard square activation functions for the feedthrough terms. In particular, I suggest clearly asserting in your manuscript that your (5) is a particular example of an ICNN where you choose to impose Hadamard square activations on every feedthrough term, in order to clarify to the reader that not all ICNNs can be written in your form. Also, it would be good to discuss why you chose such a parameterization, over the more general ICNNs used in other works.

**Q11**: I see, thanks for the clarification.
We are happy that the new experiments (corruption-oblivious Bregman divergence and the associated Mirror Descent adversarial training) addressed the OOD concerns raised earlier and here we answer the new concerns.

Before, we want to emphasize that we consider the learning of a meaningful, consistent, applicable Bregman divergence (as confirmed by the experiments and the prototypical and successful application to robustness) a main contribution of this paper and we would imagine that the community could use our pipeline in various settings where non-Euclidean similarity is useful. The new results suggested by you and another reviewer further strengthen our work. 

> Given that the baselines (PGD and RLAT) typically improve OOD generalisation over a wide range of corruptions ...

We are particularly focusing here to present the results on fog and contrast corruptions only because these corruptions are problematic for both PGD and RLAT:

From (Kireev et al., 2022):
> Interestingly, for the fog and contrast corruptions, the performance degrades for all methods (see Table 10 in App. H), consistently with the observation made in Ford et al. (2019).

From (Ford et al., 2019):
> Interestingly, both methods performed much worse than the clean model on the fog and contrast corruptions. For example, the adversarially trained model was 55% accurate on the most severe contrast corruption compared to 85% for the clean model.

We have shown that our method (trained on a different dataset and oblivious to the corruptions) excels particularly for these problematic corruptions, the improvement in accuracy is about 27%. Also, our method achieves comparable performance on other non-problematic corruptions such zoom blur. This is a notable strength of our method.

> In this sense, the marked decrease in the accuracy to noise-based corruptions should be concerning for an approach presented as a tool to increase general robustness. 

We respectfully disagree. Robustness against noise is, in this case, neither very important $i)$ nor expected $ii)$:

* $i)$ Robustness against real-world corruptions such as contrast is more important than robustness against Gaussian noise (that is equivalent to robustness on $L^2$ balls), e.g.:

> Goodfellow, Shlens, and Szegedy intended $l_p$ adversarial examples to be a toy problem where evaluation would be easy, with the hope that the solution to this toy problem would generalize to other problems. (Gilmer et al., 2018)

* $ii)$ We train the Bregman divergence by forcing it to consider noisy images far from the original (divergence values for noisy images are in 10000 order of magnitude while divergence to corrupted images are typically below 100). So when we pick a Bregman ball radius (of 100) for adversarial training, the noisy images (gaussian noise) will be automatically excluded. Thus, model trained to be robust in these Bregman balls are not even expected to be robust on noisy images.

> Finally, the authors state that their addition of the quadratic terms to ICNNs was empirically useful. This detail, along with a comprehensive explanation, should have been prominently featured in the submission.

These quadratic terms are not a result of random tuning. They are a choice of activation functions obeying the conditions of the ICNN. In fact, the quadratic function is the simplest choice that obeys them (apart from the identity). We will make this clearer in the next revision and add an ablation study in the appendix.
I thank the authors for their response. I am happy to see the new experiments showing results on CIFAR-10-C with the divergence learned from BAPPS. However, the corruptions in the comparison table (fog, contrast, zoom blur) appear to be even more cherry-picked in this context where the divergence is learned from another dataset. Given that the baselines (PGD and RLAT) typically improve OOD generalisation over a wide range of corruptions, the comparison still feels quite unfair, casting doubts over the overall empirical effectiveness of the proposed approach. In this sense, the marked decrease in the accuracy to noise-based corruptions should be concerning for an approach presented as a tool to increase general robustness.
Finally, the authors state that their addition of the quadratic terms to ICNNs was empirically useful. This detail, along with a comprehensive explanation, should have been prominently featured in the submission.
We thank the reviewer for engaging in the rebuttal. We are happy to answer the new questions:

> Can you provide more context on the rebuttal PDF, such as procedures used to generate those images, where the images came from, etc.? I'm assuming they came from BAPPS?
 
Those are 256x256 images from the ImageNet validation set. The first column is for clean samples. The second column are corrupted versions of clean images. The chosen corruption here is Gray color conversion. Thereafter, we generate noisy images (based on the clean image) according to Equ.8 of the paper. For each image (corrupted or noisy) we report the $L^2$ distance to its clean image along with the Bregman divergence $D_\phi$. This Bregman divergence is trained on 32x32 CIFAR-10 training set for the corruption $\tau$ as Gray color conversion following the scheme detailed in Sec. 3.2 and Algorithm 1.

> In the rebuttal pdf, I see that in the 4th row (image of a parrot's right face), under the proposed metric $D_\phi$ the black-and-white image is much closer to the original image than the image in the 3rd column (slight noise). But, in my opinion, most humans would make the the opposite judgement. How would you address such concerns, as I imagine the metric $D_\phi$ is meant to be more "semantic" than the simple L2 distance?

We train the Bregman divergence by forcing it to consider corrupted images (gray images in the second column) close to the clean images, and the noisy images as far. The threshold to generate noisy images is the adjustable hyperparameter, $d>0$ in Equ.6. For this particular experiment the noise threshold $d$ is chosen to be relatively low: randomly sampled from $[10^{-7}, 0.99 ]$ (see paragraph "Training details" of Sec. 6 for more details). 

The noise parameter $d$ corresponding to the image in the fourth row, third column is $d\approx0.4$ (which is the $L^2$ of this noisy image divided by the $L^2$ of the corrupted image in the second column). This value of $d$ falls into what we forced the divergence to consider far from the image ($10^{-7}<d<0.99$) so the divergence is behaving as intended. We have chosen these low values of $d$ because they gave the best result once the divergence is used for Mirror Descent adversarial training. 

Nevertheless, in another use-case, the threshold noise $d$ can be increased (for example above 1), so the divergence will consider even images in the seventh column close to the original image if that is what the user wants.
I thank the authors very much for their hard work in addressing my concerns and in the additional experiments. I just have a couple more questions.

- Can you provide more context on the rebuttal PDF, such as procedures used to generate those images, where the images came from, etc.? I'm assuming they came from BAPPS?

- In the rebuttal pdf, I see that in the 4th row (image of a parrot's right face), under the proposed metric $D_\phi$ the black-and-white image is much closer to the original image than the image in the 3rd column (slight noise). But, in my opinion, most humans would make the the opposite judgement. How would you address such concerns, as I imagine the metric $D_\phi$ is meant to be more "semantic" than the simple L2 distance? 

Thank you again in working to address my concerns.