Learning Provably Robust Estimators for Inverse Problems via Jittering
Authors: Anselm Krainovic
Mahdi Soltanolkotabi
Reinhard Heckel
Venue: NeurIPS 2023 poster (2023)
Keywords: Adversarial Training
Jittering
Denoising
Deconvolution
Compressive Sensing
Inverse Problems
Robustness
TL;DR: Jittering, a training method that adds noise during training, enables to obtain provably optimal worst-case robust denoisers and is shown to be effective for training neural networks for denoising, deconvolution and compressive sensing.

Abstract: Deep neural networks provide excellent performance for inverse problems such as denoising. However, neural networks can be sensitive to adversarial or worst-case perturbations. This raises the question of whether such networks can be trained efficiently to be worst-case robust. In this paper, we investigate whether jittering, a simple regularization technique that adds isotropic Gaussian noise during training, is effective for learning worst-case robust estimators for inverse problems. While well studied for prediction in classification tasks, the effectiveness of jittering for inverse problems has not been systematically investigated. In this paper, we present a novel analytical characterization of the optimal $\ell_2$-worst-case robust estimator for linear denoising and show that jittering yields optimal robust denoisers. Furthermore, we examine jittering empirically via training deep neural networks (U-nets) for natural image denoising, deconvolution, and accelerated magnetic resonance imaging (MRI). The results show that jittering significantly enhances the worst-case robustness, but can be suboptimal for inverse problems beyond denoising. Moreover, our results imply that training on real data which often contains slight noise is somewhat robustness enhancing.

Learning Provably Robust Estimators for Inverse Problems via Jittering
Anselm Krainovic
Mahdi Soltanolkotabi University of Southern California soltanol@usc. edu
Technical University of Munich anselm. kwwinovic@tum.coommmm....
Reinhard Heckel
Technical University of Munich reinhard, heckel@tum de
Abstract
Deep neural networks provide excellent performance for inverse problems such denoising. However, neural networks be sensitive adversarial worst- case perturbations. This raises the question whether such networks can be trained efficiently be worst-case robust. In this paper, investigate whether jittering, a simple regularization technique that adds isotropic Gaussian noise during training, effective for learning worst-case robust estimators for inverse problems. While well studied for prediction in classification tasks, the effectiveness jittering for inverse problems has not been systematically investigated. In this paper, we present a novel analytical characterization of the optimal lg- co-rostt-case robust estimator for linear denoising and show that jittering yields optimal robust denoisers. Furthermore, we examine jittering empirically via training deep neural networks (U-nets) for natural image denoising, deconvolution, and accelerated magnetic resonance imaging (MRI). The results show that jittering significantly enhances the worst-case robustness, but can be suboptimal for inverse problems beyond denoising. Moreover, our results imply that training on real data which often contains slight noise somewhat robustness enhancing.
Introduction
Deep neural networks achieve state-of-the-art performance for image reconstruction tasks including compressive sensing, super-resolution, and denoising. Due to their excellent performance, deep networks are now used in a variety imaging technologies, for example MRI and CT. However, concerns have been voiced that neural networks can be sensitive to worst-case or adversarial perturba- tions. Those concerns are fuelled by neural networks being sensitive small, adversarially selected perturbations for prediction tasks such as image classification (Szegedy et al. 2014).
Recent empirical work for image reconstruction tasks (Huang al. 2018 Antun et al. 2020 Genzel
jet al.] 2022. Darestani et al. (222)) found that worst-case perturbations can have a signficantly larger effect on the image quality than random perturbations. This sensitivity worst-case perturbations is not unique to neural networks, classical imaging methods are similarly sensitive (Darestani et al. 202T)
This raises the question of whether networks can be designed or trained to be worst-case robust. A successful method proposed in the context of classification is adversarial training, which optimizes a robust or adversarial loss during training (Madry et al. 2018). However, the robust loss requires finding worst-case perturbations during training which difficult and computationally expensive.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Linear denoising
U-net denoising
U-net MRI reconstruction
U-net deconvolution
Robust risk R R./n
0.8
Standard
0.6
Jittering
1.5
10
Adversarial
0.4
1
1.0
0.2
0.5
0.1
0
0
0.1
0.2
0.30
0.1
0.2
0.3
0.00
0.01
0.02
0.03
0.0
0.1
0.2
0.3
è² f/B
|
e/BB
|
2
//E
|A
2
A 2
Figure 1: Jittering yields worst-case robust reconstruction methods. The plots show the pixel- wise empirical robust risks Re/1 of models trained to minimize the robust risk R. and jittering risk Jr., respectively, with suitable choices of jittering levels (e). The optimal robust risk approximated via adversarial training. The shaded areas are 66% confidence intervals. Left panel for subspace denoising where jittering and robust training are provably equivalent, the panels from second left to right are for image reconstruction problems with the U-net, where jittering is particularly effective for denoising.
In this work, we study jittering, a simple regularization technique that adds noise during training as bebustness-enhaneing technique for inverse problems. is long known that adding noise during training has regularizing effect and can be beneficial for generalization (Bishop) 1995 Holmstrom and Koistinen 1992. Reed and Marks II 1999). Prior work also studied adding noise for enhancing adversarial robustness for classification (Zantedeschi et al., 2017 Kannan et al., 2018 Gilmer et al., 2019). However, jittering has not been systematically studied robustness enhancing technique for training robust networks for inverse problems.
We consider the following signal reconstruction problem. Let J: Rm R" be estimator (a neural network in practice) for a signal (often an image) x E IR" based on the measurement y Ax E Rm where A is measurement matrix and is random noise. We want to learn estimator that has small robust risk defined as
R2 (J) = (x,))
max () + +e) - x [|
(1)
The robust risk is the expected worst-case error with respect to l2 fz-perturbation of norm at most of measured with the mean- -qua--quared error.
Thcoretical results. We start with Gaussian denoising of a signal lying subspace, and first characterize the optimal linear robust denoiser, i.e., the estimator that minimizes the robust risk (f)... While the resulting estimator is quite intuitive, proving optimality is fairly involved and relies on interesting applications of Jensen's inequality.
Second, we show that the optimal linear robust estimator minimizes the Jittering-risk
Ja (f) EE [xx,)) w [If(y w)
(2)
where w ~ _N( o² 1) is Gaussian jittering noise with noise variance o that depends on the desired robustness level This finding implies that instead of performing robust training via minimizing an empirical version of robust risk, we can train denoiser via jittering, i.e., injecting Gaussian noise during training, at least for denoising signal lying in subspace. Figure [ left panel, demonstrates the equivalence of training via minimizing a jittering risk and robust trainnn numerically for the subspace model. It evident that both methods of training yield equally robust estimator.
Moreover, we discuss extensions of our theory for linear inverse problems y Ax + z and find that jittering result in suboptimal worst-case robust estimators for some classes of forward operators.

---

Empirical results for real-world denoising, deconvolution and compressive sensing. Jittering is also effective for learning robust neural network estimators for solving inverse problems in practice. Figure 1 second from left to right, depicts the worst-case risk achieved by training U-net model for denoising, compressive sensing, and deconvolution, with standard training (blue), with jittering (purple), and with adversarial training (orange). For denoising, we see that jittering is as effective for obtaining a worst-case robust estimator as adversarial training, as suggested by theory. For compressive sensing and deconvolution, we find that jittering can be suboptimal beyond denoising, but is still effective for enhancing robustness.
Those findings make jittering a potentially attractive method for learning robust estimators in the context of inverse problems, since jittering can also be implemented easily and needs far less computational resources than adversarial training. Moreover, those findings imply that training on real data which often contains slight noise somewhat robustness enhancing.
2
Related work
Empirical investigation of worst-case robustness for imaging. Several works investigated the sensitivity of neural networks for image reconstruction tasks to adversarial perturbations, for limited angle tomography (Huang et al.) 2018), MRI and CT (Antun et al., 2020 [eezel et al. 2022] Darestani et al. (2021). and image-to-image tasks (colorization, deblurring, denoising, and super- resolution) (Choi et al. 2022: Yan al. 2022, Choi et al. 2019). Collectively, those works show that neural networks for imaging problems are significantly more sensitive to adversarial perturbations than to random perturbations, as expected. The effect of adversarial fg-perturbations measured in sucrr--suared-erroo is roughly proportional to the energy of the perturbations in most of those problems, demonstrating that up to a constant (that might be large) neural networks can be relatively stable for imaging tasks. Classical reconstruction methods, in particular f--regularized least-squares, are similarly sensitive to adversarial perturbations (Darestani et al. 2021).
Learning robust methods with robust optimization. To learn robust classifiers, Madry et al. (2018) proposed to minimize robust loss and to find worst-case perturbations during training with projected gradient descent. Adversarial training can be effective for learning robust methods, but is computationally expensive due the cost of finding adversarial perturbations. A variety of heuristics exist to lower the computational cost of robust training for neural networks. For example, Raj let al. (2020) consider compressive sensing and CT reconstruction problems and propose generate adversarial perturbations for training with an auxiliary network instead of solving a maximization problem. As another example, [Wong et al. (2020) considers adversarial training of classifiers and propose to calculate adversarial perturbations during training by first randomly perturbing the initial point and then applying single step of projected gradient descent.
Jittering for enhancing robustness in inverse problems. The literature is somewhat split on whether jittering is effective for enhancing worst-case robustness for imaging. Genzel et al. (2022) suggested that jittering can enhance worst-case robustness of networks trained on compressive sensing and CT tasks. Contrary. Gandikota et al. (2022) consider the robustness to fs--perturbation for neural-network based deblurring and observed that the DeepWiener architecture, trained via Jittering with noise levels sampled from a fixed interval, is sensitive to adversarial perturbations. In this work, we present the first systematic study on the effectiveness of jittering as robustness-enhancci technique for inverse problems.
Robustness for inverse problems versus robustness for classification problems. Robustness in general and adding noise during training in particular, has been intensively studied in the classifica- tion setting. However, inverse problems and classification/predice
problems are very different. Adversarial robustness for classifiers is defined as the (average) minimal distance to the decision boundary, and random noise robustness as the minimal noise strength (for example the radius of Gaussian noise sphere) such that one likely crosses the decision boundary (Fawzi et al. 2018). For inverse problems, there is no notion of a decision boundary. Therefore, results and intuitions from classification, which are often based on geometric insights on distances to surfaces (see for example Fawzi et al. (2016) and Shafahi et al. (2019) do not apply to inverse problems.
3

---

Jittering for enhancing robustness in classification. Prior work in classification considered Gaussian data augmentation adding Gaussian noise during training (which is conceptually very similar to jittering) as an mauustness-enhancinn technique and found that adding noise enhances adversarial robustness, but reported mixed results on its effectiveness. [Fawzi al. (2018) 8) proved for linear classifiers that adding Gaussian noise during training increases adversarial robustness, and Gilmer et al. (019) demonstrated that empirically adding Gaussian noise during training also increases adversarial robustness for neural networks in the context of classification, |Rusak et al. (2020) also found Gaussian noise addition beneficial for corruption robustness (including noise, compression and weather artifacts). Furthermore, Kannan et al. (2018) and Zantedeschi et al. (2017) considered adding Gaussian noise during training together with other regularization methods and report that adding noise at fixed noise level alone yields noticeable increase in robustness. Contrary, Carliii and Wagner (2017) reevaluated the methods proposed by Zantedeschi et al. (2017) and reported that the robustness gains are small compared adversarial training.
Randomized smoothing. Randomized smoothing is very successful technique for obtaining robust classifiers (Cohen et al. 2019; Carlini et al., 2023). and is based on constructing a smoothed classifier from base classifier by averaging the base classifier's outputs under Gaussian noise perturbation. The smoothed classifier is provably robust within a specified radii, without making any restrictions on the base classifier. Despite similarities first sight, randomized smoothing considers surrogate smoothed models, whereas jittering is a training technique (see the appendix on a detailed discussion).
3 Theory for robust reconstruction of a signal lying in a subspace
In this section, we characterize the optimal robust estimator for denoising a signal in subspace. While the resulting estimator is quite intuitive, proving optimality is fairly involved and relies on interesting applications of Jensen's 's inequality. We then show that the optimal robust estimator is also the unique minimizer of the jittering loss. Finally, we conjecture precise characterization of optimal estimators for linear inverse problems beyond denoising, and show that jittering can result in suboptimal estimators for linear inverse problems beyond denoising.
3.1 Problem setup
We consider a signal reconstruction problem, where the goal is to estimate a signal x based on a noisy measurement y = Ax + where (N(0, 1/mmml is Gaussian noise and A Rm*x measurement or forward operator. The random noise is scaled so that the expected noise energy is | of The random noise is denoted by z, distinguish it from the adversarial noise or worst-case error, denoted by We assume that the signal is (approximately) chosen uniformly from the intersection of sphere and subspace. Specifically, the signal is generated as x Uc, where ~ (O, 1/dI) is Gaussian and U E Raxd is an orthonormal basis for d-dimensional subspace
of Rd. The expected signal energy is E || 2
=²-
We consider a linear estimator of the form f(y) = Hy for estimating the signal from the measure- ment. For the standard reconstruction problem of estimating the signal x from the measurement y. performance is often measured terms of the expected least-squared error. We are interested in robust reconstruction and consider the expected worst-case reconstruction error with respect to an fz-perturbation, defined in equation (
and given by
R. (f) = Ex,y)
max [ell__S
[(y + e) -x11 x1[
For the robust risk reduces the standard expected mean-squared error.
3.2 Denoising
We start with denoising where the forward map the identity, i.e., I. The following theorem characterizes the optimal worst-case robust denoiser.

---

Optimal robust denoising
Robustness beyond denoising
Robust risk Re/n
2
No noise
Standard
Scaling factor
Medium noise
1.5
Adversarial
0.5
High noise
Jittering
1
0.5
0
0.5
1.5
0.0
0.05
0.1
0.15
2/02
Figure 2: Robust reconstruction of signals lying in subspace. The left panel shows the scaling factor of the optimal robust denoiser according Theorem 3.1 at noise levels 0₂ /d/n (0, 1.2) and signal energy of = 1. The right panel depicts the robust risks of standard training and jittering as well as the optimal robust risk for an inverse problem beyond denoising, with the details stated in subsection 3.3
Theorem 3.1. For d + oo, the optimal worst-cas case estimator, i.e., the estimator minimizing the worst-case risk (f) amongst all estimators of the form f(y) Hy, is aUU", where
if 6
8 2m
else.
The worst-case optimal estimator projects onto the signal subspace, and then shrinks towards zero, by factor determined by the noise variance o and the worst-case noise energy e². We consider the asymptotic setup where d - only for expositional convenience; our proof shows that the estimator the theorem is also near optimal for finite d.
To understand the implications of the theorem, let us first consider the case where the worst-case perturbation is zero. Then, the optimal estimator simply projects on the signal-subspace and shrinks
o² The larger the noise, the more shrinkage.
towards zero, by factor of obto?=
Next, consider the most interesting regime, where non-zero adversarial noise present. If the adversarial noise energy is larger than the signal energy, the estimator projects onto zero. However, this is an extreme regime since the adversarial noise can cancel the signal, and no good estimate of the signal can be achieved.
For the more practical regime where the adversarial noise energy is smaller than the signal energy, the theorem states that the optimal estimator projects onto the signal-subspace and shrinks towards zero- just like the optimal estimator for the noise-free case bus this time by factor a, that decreases in the adversarial noise energy e².
The proof of Theorem 3.1 is in the appendix. Note that for estimators H oUU worst-case perturbation can be computed in closed form for a fixed and x: a worst-case perturbation is the vector that points into the direction of the signal plus noise lying in the signal subspace, i.e., (1=a)ctaU** Uc [ However, for general estimator H, the perturbation can not be written in closed form, which makes proving optimality quite challenging. Our proof relies on characterization of the inner maximization problem as the solution to an optimization problem in one variable, and several unusual applications of Jensen's 's inequality.
3.2.1 Robust denoisers via jittering
An important consequence of the characterization of the worst-case optimal estimator in Theorem 3.1 that, at least for the linear setup considered in this section, worst-case optimal estimator can be obtained by regularization with jittering.
5

---

Recall from the introduction that regularization via jittering simply adds Gaussian noise w ~ (0 I the measurement during training. The jittering risk (2) of the estimator f(y) = Hy for
denoising is Jr, (/) (, [II(y + w) - x12 Choosing the variance of the jittering noise level accordingly as function of the desired robustness level yields an optimal worst-case robust estimator by minimizing the jittering loss, formalized by the following corollary of Theorem 3.1
Corollary 3.2. For e² oh the linear estimator f(y) Hy that minimizes the jitter- ing risk Jaw with noise level chosen as a function of the desired noise level as ow((t) -
Go2 to. Fo. 10 also minimizes the worst-case risk Re.
Hence, if we aim for robustness level e < de. we can simply apply training via Jittering instead of adversarial training by choosing the Jittering noise level using the explicit formula for the jittering noise level (c) in corollary 3.2
Figure 1 left panel, shows the results of numerical simulation for adversarial training and jittering. In the implementation we treat the linear reconstructions as neural networks with single layer without bias and perform adversarial training and jittering for each perturbation level. The simulations show that the robust risk performance of the models are identical, as predicted by the theory. Details on how adversarial training performed are Section 4
3.2.2 Robustness accuracy trade-off
Another consequence of Theorem 3.1 is an explicit robustness-accuraacy trade-off: increased worst- case robustness comes loss of accuracy. In the practically relevant regime of 0 6² of This expression yields the optimal standard error for 0 and is strictly monotonically increasing in e, hence showing the loss of accuracy when increasing robustness. Robustness aobusttess-accuracy tradeoffs can also be observed in other machine learning settings, for classification and regression settings, see for example (sipras al. 2019). For linear inverse problems with applications in control, robustness accuracy-traen trcuoocy-radeoot's were recently characterized by Lee et al. (202I) and LandJavann Javanmard et al. (2020).
o²
the standard risk of the optimal worst-case estimator fa(c) is Ro(fa(c)) = of a2+0?
3.3 General linear inverse problems
In the previous section, characterized the optimal worst-case robust estimator and found that jittering yields optimal robust denoisers. In this section, we derive a conjecture for the worst-case optimal robust estimator for more general linear inverse problems of reconstructing signal from measurement y = Ax + z, with a forward operator A (with A * I in general), and show that this estimator is in general not equal the estimator obtained with jittering, thus jittering is in general suboptimal.
Optimal robust estimator. Let AU WAVT be the singular value decomposition of the matrix AU with singular values X; As formalized by Lemma[A.IJof the appendix, the robust-risk (T) of the estimator f can be written as expectation involving minimization problem over single variable (instead of a maximization over an n-diimnnsioal variable, as in the original definition):
HHH Tv). v= (HA - Hz.
Re H E
min +v 2202
Here, mmx is the largest singular value of the matrix H. In order to find the optimal robust estimator we wish solve the optimization problem arg minH R. (H). The difficulty in solving this optimization problem is that we can't solve the minimization problem within the expectation (3) in closed form. In order to prove Theorem 3.1 for denoising (i.e., for A I) we derived an upper and matching lower bound of the risks using several unusual applications of Jensen's 's inequality. The proof does not generalize in a straightforward manner to the more general case where A A I. However, for large d, the random variable v (I HHH") > -''v concentrates around it's expectation, and thus we conjecture that for large d, we can exchange expectation and minimization, which yields:
expectation
R. (H) = min xe2 + Ev TT (I
HH --v
(4)
2

---

The expectation in the risk expression can be explicitly computed, which yields the following conjecture for the worst-case optimal estimator:
Conjecture 3.3. For d - oo the optimal worst-case estimator, i.e., the estimator minimizing the worst-case risk Re (f) amongst all estimators of the form f(y) = Hy, is H = UVdiag(o,) W with
1+ an 0,
d
A
1
M
d A o 2\,
2
- A,
2
m. 2X:
oz
2
m
0
if X; # 0 and 0; =0 otherwise. Here, the parameter À is a solution of:
d
-
XX
-
oo 2 m
1 1+
A
o oo + 2 m
oe Ad
argminx20 de²
+
d
The optimization problem involved is convex and box-constrained and can thus be solved numerically, Besides the argument above, we confirmed our conjecture with numerical simulations.
Optimal jittering estimator. Unlike for denoising, for general inverse problems, the jittering-ris risk minimizing estimator is in general not equal to the optimal worst-case estimator, but the two estimators often close. The optimal estimator minimizing the jittering risk is given (see Appendix C):
a o2 + 02 +
Hy(ow) UVdiag
WT.
o
where as before AU = WAVT is the singular value decomposition with singular values Aç While the estimator (5) has the same form the worst-case optimal estimator in Conjecture 3.3 the diagonal matrix in the two estimators is in general slightly different.
Numerical Simulation. The worst-case suboptimality of the jittering-risk optimal estimator (5) depends on the singular values of the matrix AU; if they are equal the jittering-ris estimator optimal, and if they are not equal there typically a small gap. To illustrate the gap, we consider forward operator A with linearly decaying singular values n for 1 <
with signal energy
of 1 and noise level σ₂ 0.2. We compare the (conjectured) optimal robust estimator specified by Conjecture 3.3 with the optimal Jittering estimator (5) at noise level Cw. where Tw is optimized such that one obtains minimal robust risk R, at given perturbation level The results in Figure 2 right panel, show small gap in robust risk, which implies that Jittering is suboptimal for this case. However, simulations with varying forward operators and noise levels indicate that the gap small relative to the robust risk of the standard estimator. Experiments on image deconvolution using U-Net show similar results.
presented in Section 4
Experiments
In this section, we train standard convolutional neural-networks with standard training, adversarial training, and jittering for three inverse problems: denoising images, image deconvolution, and compressive sensing, and study their robustness. We find that Jittering yields well-performing robust denoisers computational cost similar to standard training, which is significantly cheaper than adversarial training. We also find that jittering yields robust estimators for deconvolution and compressive sensing. This indicates that training real data which often contains slight measurement noise is robustness enhancing.
4.1 Problem setup
We start by describing the datasets, networks, and methodology.
Natural images. We consider denoising and deconvolution of natural images, where our goal is to reconstruct an image x E IR from noisy measurement y Ax + z, where z (1 1//n)) Gaussian noise and A measurement matrix, which is equal to identity for denoising, and implements
7

---

convolution for deconvolution. For deconvolution we use a 8 x 8-sized discretization of the 2- dimensional Gaussian normal distribution with standard deviation 2. The kemel visualized in Figure 3 in the appendix. We obtain train and validation datasets { ( yI)...... (XN, yN)] of sizes 34k and 4k, respectively, from colorized images of size n 128 128 3 generated by randomly cropping and flipping ImageNet images. The methods are tested on 2k original-sized images.
Medical data. We also perform experiments on accelerated singlecoil magnetic resonance imaging image E R from noisy and subsampled
(MRI) data, where the goal is to reconstruct measurement in the frequency domain y = MFx + z RR2m. dataset (Zhontar et al. 2018), which contains the images x and fully sampled measurements (M = I). We process it by random subsampling at acceleration factor and obtain train, validation and test datasets with approximately 31k, 3.5k and 7k slices, respectively. While perturbations are sought in frequency domain, the inverse Fourier transform is applied to the measurements before feeding the 320 x 320 cropped and normalized images into the network.
use the fastMRI singlecoil knee
Network architecture. We use the U-net architecture (Ronneberger et al. 2015) since it gives excellent performance for denoising (Brooks et al., 2019) and medical image reconstruction tasks, such as computed tomography (Jin et al. (017) and is used as a building block for state-of-the methods for magnetic resonance imaging (Zbontar et al. 2018) Sriram al. 2020). For natural images, we use a U-net with 3 x 3 padded convolutions with ReLU activation functions, 2 x 2 max-pooling layers for downscaling and transposed convolutions for upscaling. The network has 120k parameters. For MRI reconstruction we use a U-Net architecture similar to [Zbontar et al. (2018) with 3 padded convolutions, leaky ReLU activation function, 2 x 2 average pooling and transposed convolutions (480k learnable parameters). We denote the U-Net by the parameterized mapping fo: I R in the following.
Evaluation. We evaluate networks by measuring its robustness via the empirical robust risk defined as R. EE Il (yf + e;) x, l?. For evaluation, the robust empirical risk is computed over the test set. We assess the accuracy by computing the standard empirical risk (O). Computing the robust empirical risk is non-trivial since it requires finding adversarial perturbations for solving the inner maximization problem. This is explained next. We also study the computational cost of the different methods, which measure in terms of GPU cost and time.
Finding adversarial perturbations. To evaluate the empirical risk and for robust training, we need to compute adversarial perturbations e = arg maxi]ell,S (l + +) - x1| We find the perturbations by running Na projected gradient ascent steps, starting with initial perturbation e = 0 and iterate
ei+l = PB.O.e) ee'
+ 2.5 Ae ) where =e"= Ver y) - 100=x(;; x1
C Nu
Ae
Here, PR(O.e) is the projection into the la-ball B(0; c) of radius around the origin. The gradient is normalized facilitate step size optimization with multiplier 2.5 such that the iteration can reach and move along the boundary, as suggested by Madry et al. 2018).
Training methods. Standard training minimizes the standard empirical risk lg Adversarial training minimizes the empirical robust risk R. To minimize the empirical robust risk, we approxi- mate the inner maximization, ma [lfo + e) x; 1l with (f..) x, x1I where ý; is the adversarially perturbed measurement computed as described above. Training via jittering minimizes
(..(()) = Σ Eww.N00.0 [I + +w) x x1
where the jittering level ow is chosen depending on the desired robustness level. We treat the jittering noise level as a hyperparameter optimized using the validation dataset (shown in the appendix). Jittering is practically implemented via performing the SGD update rule 0:+1 MI
0: 7. E. Vollso(y: w,) - xil,?, with M samples per batch and learning rate n. For jit- tering, the network output is calculated on the noisy input y; w,, instead of y, (standard training)
8

---

Hyperparameter search
Jittering level (e)
Standard risk
Standard risk fto/n
0.08
Robust risk R /n
Jittering level d
0.6
0.4
0.06
0.4
0.04
0.2
0.2
0.02
0
0
0.2
0.4
0.6
0
0.1
0.2
0.3
0.1
0.2
0.3
Jittering level ow
e² P/E
X
e² /
|
Jittering Prediction
Adversarial
Jittering (optimal)
Standard
Estimating the optimal jittering noise levels for the denoising task. The left panel shows the results training networks via Jittering, at noise levels ows and calculating the empirical robust risk R. of each model. Each green line corresponds to robust risks at one perturbation level. The optimal jittering noise levels are shown in the middle panel and follow well the prediction from theory (Cor. 3.2 details in appendix). The jittering estimators are similarly robust as adversarial training (Figure I), but attain lower standard risks (right panel).
Figure 3:
y: ee (adversarial training). To approximate the expectation in the jittering risk draw independent jittering noise samples w; in each iteration of SGD.
Throughout, we use PyTorch's Adam optimizer with learning rate 10-3 and batch size 50 for natural images, and 10-2 and for MRI data. perturbation levels, we consider values within the practically interesting regime of e²
|
< 0.3 for natural images and 0.03 for MRI data. Note that for
2 > ||x Theorem 3.1 predicts for denoising (A I) that the optimal robust estimator is everywhere. Figure in the appendix shows that for large perturbations the trained U-net denoiser also maps to zero.
Results
We now discuss the results of the denoising, deconvolution, and compressive sensing experiments.
Robust and standard performance. Figure [ shows that the standard estimator is relatively robust for Gaussian denoising and increasingly sensitive for more ill-posed problems (deconvolution and compressive sensing). The experiments further show that jittering is effective for enhancing robustness, particular relative the sensitivity of the standard estimator. Nevertheless, as suggested by theory, we see gap between the robust risk of adversarial training and jittering for image deconvolution and compressive sensing. For Gaussian denoising, however, Jittering particularly effective and yields increasingly better performing networks in terms of standard risks for larger perturbations.
Choice of the jittering level. The results based on choosing the jittering noise levels via hyperparameter search for each task. Figure shows the results for Gaussian denoising: It can be seen that the choice of noise level is important for minimizing the robust risk. The estimated noise levels also aligns well the theoretical prediction. Details on this and the parameter choices for deconvolution and the compressive sensing experiments are in the appendix.
Computational complexity. We measured the GPU time until convergence and memory utilization of the methods and present the results the Table the appendix. Performing adversarial training is by a factor of the projected gradient ascent steps more expensive than standard training. Moreover, training via jittering has similar computational cost as standard training, since it solely consists of drawing and adding Gaussian noise the training data.

---

Standard estimator
Adversarial estimator
Jittering estimator
Target
Measurem.
clean
perturbed
clean
perturbed
clean
perturbed
Denoising
MRI-CS
Decony.
Figure 4: Example reconstructions using measurements (second column) and separately calculated perturbed measurements. The reconstructions are denoted as clean and perturbed, respectively. The perturbation levels are c² / Ax [g] 0.03 for denoising, 0.003 for compressive sensing and 0.001 for deconvolution. We can see that the standard estimator is visibly sensitive to perturbations. Jittering yields robust estimators, but the same time yields smoother reconstructions.
Visual reconstructions. For the linear subspace setting adversarial training and jittering are equiva- lent. For Gaussian denoising with neural network, however, they perform differently. For larger perturbations jittering tends to yield smoother images than networks trained adversarially, as can be in the example reconstructions shown in Figure This effect is particularly noticeable for the Gaussian deconvolution task. We quantified the effect using the total variation norm and present the results in the appendix. Moreover, we discuss an approximation jittering, Jacobian regularization, which similarly enhances robustness. It is computationally more expensive, but yields less smooth reconstructions.
Conclusion
In this paper, we characterized the optimal worst-case robust estimator for Gaussian subspace denoising and found that the optimal estimator can be provably learned with jittering. Our results for training neural networks for Gaussian denoising of images show that jittering enables the training of neural networks that are as robust as neural networks trained adversarially, but at fraction of the computational cost, and without the hassle of having find adversarial perturbations. While we demonstrated that jittering effective improving the robustness for compressive sensing and image deconvolution. Moreover, our results imply that training on real data that contains slight measurement noise is robustness enhancing.
yield suboptimal robust estimators in general, in practice, jittering is
Reproducability The repository at https://github com/MLI- botoonstucttrs_vaa_ttttte contains the code to reproduce all results in the main body of this paper.
Acknowledgments A.K. and R.H. are supported by the Institute of Advanced Studies at the Technical University of Munich, the Deutsche Forschungsgemeinscaatf (DFG, German Research Foundation) 456465471, 464123524, the DAAD, and the German Federal Ministry of Education and Research, and the Bavarian State Ministry for Science and the Arts. M.S. supported by Packard Fellowship in Science and Engineering, Sloan Research Fellowship in Mathematics, an NSF-CAREER under award #1 846369, DARPA FastNICS programs, and NSF-CIF awards #1813877 and #2008443.
10

---

References
V. Antun, F. Renna, C. Poon, B. Adcock, and A. C. Hansen. On instabilities of deep learning in image reconstruction and the potential costs of AL. In Proceedings of the National Academy of Sciences, 2020.
C. M. Bishop. Training with Noise is Equivalent to Tikhonov Regularization. Neural Computation, 7 (1):108-116, 1995.
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
T. Brooks, B. Mildenhall, T. Xue, J. Chen, D. Sharlet. and J. T. Barron. Unprocessing Images for Learned Raw Denoising. In IEEE Conference on Computer Vision and Pattern Recognition, 2019.
N. Carlini and D. Wagner. MagNet and "Efficient Defenses Against Adversarial Attacks" are Not Robust to Adversarial Examples. arXiv:171 1.80477, 2017.
N. Carlini, F. Tramer, K. D. Dvijotham, L. Rice, M. Sun, and J. Z. Kolter. (certified!)) adversarial robustness for free! In International Conference Learning Representations, 2023.
J. Choi, H. Zhang, J.-H. Kim, C.-J. Hsieh, and J.-S. Lee. Evaluating Robustness of Deep Image SesortResolution Against Adversarial Attacks. In IEEE International Conference Computer Vision, 2019.
J. Choi, H. Zhang, J. Kim, C.-J. Hsich, and J.-S. Lee. Deep Image Destruction: Vulnerability of Deep Image-to-Image Models against Adversarial Attacks, International Conference on Pattern Recognition, 2022.
J. Cohen, E. Rosenfeld, and Z. Kolter. Certified Adversarial Robustness via Randomized Smoothing. In International Conference on Machine Learning, 2019.
M. Z. Darestani, A. S. Chaudhari, and R. Heckel. Measuring robustness in deep learning based compressive sensing. In International Conference on Machine Learning, 2021.
A. Fawzi, S.-M. Moosavi-Dezfoolli, and Frossard. Robustness of Classifiers: From Adversarial to Random Noise. In Advances in Neural Information Processing Systems, 2016.
A. Fawzi, O. Fawzi, and P. Frossard. Analysis of classifiers' robustness to adversarial perturbations. Mach Learn, 107(3)488-508, 2018.
K. V. Gandikota, Chandramouli, and M. Moeller. On adversarial robustness deep image deblurring. In IEEE International Conference on Image Processing, 2022.
M. Genzel, J. Macdonald, and M. Marz. Solving Inverse Problems With Deep Neural Networks Robustness Included. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45: 1119-1134, 2022.
Gilmer, Ford, N. Carlini, and E. Cubuk. Adversarial Examples Are Natural Consequence of Test Error in Noise. In International Conference Muchine Learning, 2019.
L. Holmstrom and P. Koistinen. Using additive noise in back-propagation training. IEEE Transactions on Neural Networks, 3(1):24-38, 1992.
Y. Huang, T. Würfl, K. Breininger, L. Liu, G. Lauritsch, and A. Maier. Some Investigations Robustness of Deep Learning in Limited Angle Tomography. In Medical Image Computing and Computer Assisted Intervention, 2018.
A. Javanmard, M. Soltanolkotabi, and H. Hassani. Precise tradeoff' in adversarial training for linear regression. In Conference on Learning Theory, 2020.
K. H. Jin, M. T. McCann, E. Froustey, and M. Unser. Deep Convolutional Neural Network for Inverse Problems in Imaging, IEEE Transactions on Image Processing, 26(9):4509-4522, 2017.
H. Kannan, A. Kurakin, and I. Goodfellow. Adversarial Logit Pairing, arXiv: [cs), 2018.

---

B. D. Lee, T. C. K. Zhang. H. Hassani, and N. Matni. Adversarial Tradeoffs in Linear Inverse Problems and Robust State Estimation. arXiv:2111.08860 [cs, eess], 2021.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In International Conference on Learning Representations, 2018.
A. Raj. Y. Bresler, and B. Li. Improving Robustness of Deep-Learning- Saap-LLeernnn-aeeeee Image Reconstruction. In International Conference on Machine Learning, 2020.
R. Reed and R. J. Marks II. Neural Smithing: Supervised Learning in Feedforward Artificial Neural Networks. MIT Press, 1999.
R. Reed, Marks, and Oh. Similarities error regularization, sigmoid gain scaling, target smoothing, and training with jitter. IEEE Transactions on Neural Networks, 6(3):529- 538, 1995.
O. Ronneberger, P. Fischer, and T. Brox. U-Net: Convolutional Networks for Biomedical Image Segmentation. Medical Image Computing and Computer-Assisted Intervention, 2015.
E. Rusak, L. Schott, R. S. Zimmermann, J. Bitterwolf, O. Bringmann, M. Bethge, and W. Brendel. A Simple Way Make Neural Networks Robust Against Diverse Image Corruptions. In European Conference on Computer Vision, 2020.
H. Salman, G. Yang. J. Li, P. Zhang, H. Zhang, I. Razenshteyn, and S. Bubeck. Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers, In Advances in Neural Information Processing Systems, 2019.
H. Salman, M. Sun, G. Yang, A. Kapoor, and J. Z. Kolter. Denoised Smoothing: A Provable Defense for Pretrained Classifiers. In Advances Neural Information Processing Systems, 2020.
A. Shafahi, Huang, C. Studer, Feizi, and T. Goldstein. Are adversarial examples inevitable? In International Conference on Learning Representations, 2019.
A. Sriram, J. Zbontar, T. Murrell, A. Defazio, C. L. Zitnick, N. Yakubova, F. Knoll, and P. John- son. End-to-End Variational Networks for Accelerated MRI Reconstruction. In Medical Image Computing and Computer Assisted Intervention, 2020.
C. Szegedy, W. Zaremba, I. Sutskever, Bruna, D. Erhan, J. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representations, 2019.
E. Wong, L. Rice, and J. Z. Kolter. Fast better than free: Revisiting adversarial training. In International Conference Learning Representations, 2020.
H. Yan, Zhang, J. Feng, M. Sugiyama, and V. Y. Tan. Towards Adversarially Robust Deep Image Denoising. In International Joint Conference on Artificial Intelligence, 2022.
V. Zantedeschi, M.-I Nicolae, and A. Rawat. Efficient Defenses Against Adversarial Attacks. In ACM Workshop on Artificial Intelligence and Security, 2017.
Zhontar, F. Knoll, A. Sriram, M. Muckley, M. Bruno, A. Defazio, M. Parente, Geras, Kat- snelson, H. Chandarana, Z. Zhang, M. Drozdzal, A. Romero, M. Rabbat, P. Vincent, J. Pinkerton,
D. Wang, N. Yakubova, E. Owens, C. L. Zitnick, M. P. Recht, D. K. Sodickson, and Y. W. Lui, fastMRI: An Open Dataset and Benchmarks for Accelerated MRI. arXiv:1811.08838 CVJ, 2018.
12

---

A Proof of Theorem 3.1
In the main body we stated an analytical characterization of the optimal worst-case robust denoiser. We present the proof in the following and show that the risk
min (H) min Ex,z
max [|ellaSe
H xx12
(6)
minimized by OUUT with
c0.0:Vo
0
if > 2
0 + o
else.
The scaling factor a as a function of the noise level e of the optimal worst-case estimator is shown in Figure 2
We start by proving a lower bound of the risk, which relies on a characterization of the maximization and many unexpected applications of Jensens inequality.
We then compute the risk for oUU and show that it is equivalent the lower bound on the risk.
A.1 Lower hounding the risk
Towards lower bounding the risk we define for notational convenience
H
H.
U HU
U UHh
H
H
U
With
Ho
H=U
U1]
H
U
we get
max |c
H x
2) -x1
|e
max
H
H
(Uc 2)
-C
H
Ho
c C+U0 UTe
max lell,s
H
H1
U
c++ U+UUZ+U"e Ufz+Ufe
max
Hj
Ho]
|ell
H (c žn + - c Hoz 1
max
|| |eill,s. Se
Here, defined ei Uhe and z
U for notational convenience, and the last inequality follows by adding UT as a constraint the maximization, which gives lower bound.
Next, note that since
z z.
_o 0O(0,02/nI is Gaussian, the vector
Z|| is equally Gaussian
z
distributed (0, o2/1l) This implies that
E max
(c z + +ej) c
Hoz
=
E
max ||
H (c + z +ej) - -
| Se
Se
13

---

Then
E
max
H [c 2| +e1) c+ Hoz
||elll
1
E
max
H Hj(c + 2|| + +e) c Hoz 112
max l
H H 21 -e2)
Hoz 1
2
[llel Se
E
max
H [c + 2 + ) c Hoz
12
2
H (c + 1 +e))
2 2 Hoz
Se
| (c + 1|| e1) |
E
max ||oill2Se
where the last step follows from Jensens inequality. Thus, have shown that
min R max [ x1|
2 min E H
max [l
H (c -
For simplicity of exposition, we drop the |nnotation. Thus, with slight abuse of notation, the vectors on the left and right hand side have different dimensions. the left hand side, z, IR",, while on the right hand side 2, e E I and throughout has iid NO of/n) entries.
Next, we'll II apply the lemma below for characterizing the maximization inside of the expectation. The proof is in Section A.3 Similar computations as used to prove the lemma are on page 19-20 in the paper Lee et al. (2021) for deriving cobustnessacccuracy trade-off bounds.
Lemma A.1. For any z,
xe zJ 1 11-HHH
max zz SellaSt
Hell2
z.
(8)
A: A2
Amax HH"
Using Lemma A.1 the term within the expectation is
max Se
[|(
I)c + Hz + Hell
Xe² + ((H - I)c +H2) I +
min
((H IJc Hz)
A: A Amae (H" H)
X + T (H - 1)7 ( -1
min
(H-I)e I)c
A: A2 Amae (H"H)
(H I)c I -
2z 22TTH²
[
+ + H
Hz.
Now let's rewrite using the singular value decomposition H VEWT V and W. With this notation, the terms above can be rewritten as
with orthogonal matrices
a² d'E'' -1) ( 1
(VEW" I)c
=c lI1 1IV(1 (1- Vi(VEWT I)c
= =c' - ( (EWT - v-) (r.,,-v,)''
(I
where w; and are the i-th column vectors of the orthogonal matrices W and V, respectively. Using similar calculations for the other summands, the optimization problem on the right hand side of inequality ( is
14

---

minE
max 2S
(c + z e) - -c12
H
(o: -v) +2 22(w, (law,-vi)'s vi)'c) (o.w7'z) (o.w 2)²
= min
Bx V.W.o;
min de + Σ A
(o:w; c + v
= min V.W.o,
Be,z
min
de +
A: X20?
1-
o x
1=1
gr (0? +
20.v; 1 wi)
o
min Eg V.W.;;
min 2207
de +
d
+
1 1-
1=1
8
9i 2
(of + 1 - 20,)
0-
d
+
2
min E V.W.o;
min
Ac
A: X2o?
of
A
gi
d (0;
1)2
o o? n
min Eg 02
min A: A2o?
de²
where minimization above is over the orthonormal matrices V, W Rdxd and over the singular values og, Equality (i) follows by noting that (a,w?" - v,²')c je is Gaussian with variance (a +
20,(v; (v; T w):))= d and (a, )z is Gaussian with variance of and therefore we can replace the expectation with respect to (c. z) with the expectation with respect to g ~ N I) and suitable scaling. Moreover, inequality (ii) follows from the fact that 0; 2 and g. 0.
Continuing, first note that the function function is increasing in the first input and decreasing in the second input. Furthermore the mappings (z, 2) + and (ar, 2) + ~ー are convex and concave. Thus by the composition rule of convex functions we conclude that the functions
convex (z. y) when > 0. Also the extended value
and (x 1)2
[ar
1)
(a 1)a
are jointly convex in (z, 2).
Eg v(m)) Jensen's inequality states that for convex function v we have
Thus by Jensen's inequality the sum the expectation in the right-hand of the equation above can be lower-bounder as
1b
xx
Σ, 7
d
d [i:
1)2 gr 0
(o 1)2
o
a²
1
g
1
+ 7
1gl
g
Tell 01
(o(g) - 1) + (o (g)))
(a(g) 2
where (gg) Ei= o
[|
0,
15

---

Now consider the event & = {g: llg 2 (1 5)d} which holds with probability at least 4d On this event, we have
(0. 1)2
9i de² +
0. (ō(g) 1)2 + + (o)
Ae
(Ø)))
Using the same argument as before the right hand side of the above inequality is jointly convex in (A, (c)). Since partial minimization of jointly convex function preserves convexity we conclude that the function
min 1g + 1 6) -. (ō - 1) + >: X2o?
(o(g)) (
(6)
1 (a(g))²
is convex in ã. Thus by using convexity in terms of o, applying Jensen's 's inequality (i.e., IE [v)(o] 2 (E (āl)) we have
min dc² + ||g| 1 (ā(g) 1)² 2 (g))
min g
A: 220?
d
(a(g))²
min 1xd + 1s(11 0) 0 (o - 1)2 + o (o()))
min Eg
A: A2m?
1 (
0. (o(g) - 1)² + o2 2d
(o(g)
min E g
min
Xe² + (1 -
zn
A: A2o?
1 (a()))²
0.2 EE (g)) - 1)² + o
2d (E 0 (g)))
min min
de² + (1 - 8)
En
d: X: 7
(g
0e (ā 1)2 + 2d (0)
min min
de² + (1 8)
A: 22o?
1 (0)*
where we defined ō = Di= E gi
Putting things together, we have shown that
|
min Ri (H)
2 min E
max Se
(c + 2 e - -cl
Hi
Jt (a, 1)2 o
min Eg d,
min
2c²
+
A: X2
- ot
i=1
0 (ō - 1)² + + (0)
min min de² + (1 8)
A: A2o?
1- (m)
0. (ō - 1) + 02 2d (6) min min de² + (1 8)
A: A2
1 (2)
where the last inequality follows from max 2 G. For + xc, we can choose 8 arbitrarily small, which yields
min R. (H) min min Xe 02 (a - 1)2 1 222002 A: X
(9)
Solving the optimization problem 9 i.c.,
Consider the inner minimization problem in equation
with f(A) X62 + c(o)
min f()) A: 2
1 -
16

---

where c(o) = o (o - 1)² + o2 o² for notational convenience. Since f is differentiable on (a oo) we can calculate its critical point X by setting the derivative with respect to À to zero, which yields
vd +
X
From this expression, we see that the constraint X > o² is satisfied and by convexity of f we know that X is the unique minimizer. Hence, we have:
min f(A) f(X²) (co + ve(a)) x2
(10)
It follows that
min (H) 2 min g()) g + + 0 1)2 +
(II)
Calculating the derivative of g(o) and setting zero, get:
2 2(a (co+ co
20 1) + 22 20
1)2 002(0-1)3+ 11f0--13-00 03 0² )00) (
0
2 oo 1)2 02
The left factor is non-negative, and the right factor is zero if o.. > e² and if
10.0.V
Vo 2-
(12)
0
If of <², then the function ((r) is monotonically increasing on [0, oo) and hence 0 is the
minimizer.
A.2 Upper bound for the risk of the estimator = -UU
We upper bound the risk of the estimator H = OUUT For H = oUU the risk (6) becomes
Re(oUUT) = Ex,x
+e+z) -x1
max ||ell
Σx.2
max |eell
|ooUU (Uc++z))) Ucl(
max ||(o 1)c σe oz 112
Ee,
||9||l_5
With Lemma A.I
min Xe2 ((a 1)c + o2)) (1-
-1
(lo 1)c )0))) oz))
(.(OUU)) min Ee
A: X202
(a l)c + oz,
min Ba, H
min
2
+
A: 22
1 - 0²
i=1
1)2 d
0²
min Eg
min X203
xc +
17

---

Using the optimal X², by equation 10
we get
1
(((UU*)= = E
+ ||Bll2
V
(o
1)R0? + + -²2
Vdl
1
181 21
()-
E
(cor) + 200 gl
2 Vd V lo 1) + 0² o2-07 +
d
oz
(0- 10- + o2
- (eo)² + 200 (a- 1)30 + 0² o
n
2
d
co 1 1)20? 0² -0? n
where equation (i) follows by using Jensen's inequality once again (specifically, using (E (Ellg)))) < [| d). Noting that (ii) is equal to the lower bound of the risk for any symmetric H in shows that H = UUUT with the optimal parameter o derived above is optimal.
E
equation
A.3 Proof of Lemma A.1
The optimization problem
max || Sell.Se
Hell |
(13)
can be written as
min -| He subject to 6² -ee00
The corresponding Lagrangian is, for X 2 0
L(e, = -z - -e) T (z He) - X(2² - eee)
= 22 He e'HH He Xe2 Xe
H" He 2TTHo Te dc² n, 2
The Lagrange Dual Function
(()) = inf L(c, A).
Using that min, 2c e + Be = - 'ccc c, we get, provided that À > Amax HH"
Be
<(A) = -22"'H (AT H'H
HT 2 Xo² - zTz z
=-2" (I H(I H 'H) Xa²
=- --
- X6
where the last equality follows from the Woodburry Identity. Thus, the dual problem is
max g(A) = min - ((A) A
X
-1 2e TT I H H
min
z.
22 (H7 H)
Even though the primal problem (33 is non-convex, strong duality holds, since the primal program
a quadratic program that is strictly feasible, see Boyd and Vandenberghe (2004) Appendix B. The
primal problem strictly feasible if there exists a vector e such that e" e² > satisfied as long > 0.
This trivially
18

---

B Additional proofs for denoising
We state two more proofs on optimal worst-case denoisers and jittering.
B.1 Proof of Corollary 3.2
In the main text was stated that linear estimators f(y) Hy that minimize the jittering risk Ja with noise level chosen function of the desired noise level
2o22 d + 2 c d2 - e 2
(e)
d(o? 22)
also minimizes the worst-case risk R.-
The result follows from Theorem 3.1 For that let fr and fj be linear estimators minimizing the robust risk R. and the jittering risk Ja.. respectively, By Theorem 3.1 the two estimators are scaled
projections onto the subspace, i.e., (y) a, UU and fʃ(y) a, UU with
GO..VE
0 2
o² and 0g - o
Or
2 + o
Setting ar = aj and solving for the standard deviation ow yields the result.
B.2 Form of perturbations for estimators H = aUUT
We noted in the main body that for estimators in closed form for fixed and x. We calculate:
aUUT worst-case perturbations can be computed
è arg max | [ + 2 c) -x1
|ell|SS
arg max
| - IJUc + Hz + Hel
|ell,
||(AUL" - aUU aUU'=
arg max |ell,
arg max
||l|sSe
U arg max - + 2 aell
||
Uc (1 - a)c + QU
[[ a)c aUT 2|12
Thus the perturbation points into the direction of the signal plus noise lying the signal subspace.
C Theory for general linear inverse problems
In the following, we consider linear inverse problems y Ax + 2, with linear forward operator E Rmxx and noise z ~ oN, /m/mI.. For denoising (A = I) we stated an explicit analytical characterization of the optimal worst-case estimator and presented proof in the appendix. The proof, however, does not generalize in a straightforward manner to more general inverse problems. We conjecture the worst-case optimal linear estimator for large dimensions d and present numerical simulation results. Moreover, we state the proof for the optimal jittering estimator, and demonstrate that it can yield suboptimal worst-case robust estimators in general.
C.1 Optimal worst-case robust estimator
As formalized by Lemma A. the robust-risk (T) of the estimator / can be written as an expectation involving minimization problem over single variable (instead of maximization over an
19

---

dimensional variable, as in the original definition):
(.(H) Ey
min A2max, of
A v
HH
(HA I)x Hz.
(14)
À
Here, o, are the singular values of the matrix H. In order to find the optimal robust estimator we wish solve the optimization problem arg mins R. (H). The difficulty solving this optimization problem is that we can't t solve the minimization problem within the expectation (14) in closed form. In order to prove Theorem 3.1 for denoising (i.e., for A I) we derived an upper and matching lower bound of the risks using several unusual applications of Jensen's 's inequality. The proof does generalize in straightforward manner to the more general case where + However, for
large d, the random variable v (I H -''vv concentrates around it's expectation, and thus we conjecture that for large d, we can exchange expectation and minimization, which yields:
(H)
min de + Ev v A2max, o?
HH -'v
(15)
Based on equation 15 we derive characterization the optimal worst-case estimator. We proceed similar to the denoising case and start with rearranging the terms in expectation:
HH 1 ((HA I)x
Hz)²(1
Hz) T
HH (HHA I)x + Hz)
X
c² ((HA T)U) (I
( -]UCc
2z H HH*) IJUc z² H HH Hz.
X HHz
Now, let AU = WAVT be the singular value decomposition of the matrix AU and H UVEWT the singular value decomposition of H. We then have:
HHT (UVEW)) = -
HAU = UVEW" = UVEAV".
For the individual parts in the summation it follows:
cH(HAU T) - - "HAH")-(HAU---
(UVVAVT (I - (1-LUVV'VUT)--UVVAAN - U)c
-UUVVVV - -U)"UV(L { -V-" U)c
=(V (EA I)(I - 1 - Σ
- (ai) - 1)
1=1
where we define v. c using the i-th column vector v; of the matrix V. Similarly, we set 2; wi Tz. 2, with w; the i-th column vector of W, and get for the other parts:
20,(o,7, - 1)c
22 H (I HH
HAU UJC
1 o7
i=1
2002
z T HH
-H
Hz
X
Hence, for the term in expectation in Eq. we get:
15
(ci(or); 1)+ 220,)²
Ey T
HH
lv
E
1- o²
3
(aid: - 1)2 + o² a?
9
d
Eg
o²
1=1
20

---

where we note that - are iid zero-mean gaussian with variance and 9: (0, 1). From this it follows, assuming the robust risk conjecture robust estimator minimizes:
m o
that the optimal
min R. (H) = min oL.2o77
f(A, 01 (I,,,,,.., on):
(16)
H
o + d (0i); - 1)2
01, de
(17)
1-
We first calculate the unconstrained minimizer of the function f and get:
0f
2A \1o0 o²
Ao(A + o o.( o + m
0o:
(A 07)
For A; = O we obtain
8f 80,
= + 0; = 0 and for A + 0:
0f 0o; 0 =0 0
1+
d
o
1+
d
の 2 2\ o
V
-
2\,
m 2Λ, o²
2x
m
The solutions T. obtained are for suitable a()) of the form:
o = a -a(A)=-X.
On further examining the constraint of S the problem (16 note that for real numbers a > b holds va² - 82 2 a b. Hence, follows:
oi.= V a(A) V - O.
Therefore, we can rule out og and set of = o. Finally, inserting of for S Sisc into the robust risk (7) yields:
min (H) min XE
+
Σ i=1
1-
AX
A o 2
+ XX 2 d
a²
Ao
02 AAp
(18)
2
2
de
The optimization problem involved convex and hox-constrained and can thus be solved numerically. Besides the argument above, we confirmed our conjecture with numerical simulations.
C.2 Optimal jittering estimator
We derive the optimal jittering estimator, i.e., the estimator f(y) HH that minimizes the jittering risk
Jo.. (f) E (x,a.w
H[Ax w + +z) - x
where as before the signal is assumed lie within a subspace, i.e., x Uc. We first calculate the expectation by using that ~ AN(0, oz/dl), NNO, o of/mm)/ and w NO of are Gaussian distributed. The jittering risk
Jo.. (f) = B(x,a.)
H + z + w) x
=Ex [I(HA - 1) 2 By |2
((HA-I)Ucl11
1/
+ E
Hw
0h =t -*((HA-IUU" (HA -1))
o²
IJUU
(HH")
(HH")
o
d
m
Hence, the optimal jittering estimator minimizes
Jo (f) tr(HXH trr(H o2
2 where X = - AU(AU) + (o + +=//m) I and Y AUUT. Using matrix calculus we oxt
calculate the optimal estimator as
VHJaa (f) | - 2Y =0,
21

---

which yields H' = = Then:
Now, let AU WAVT be the singular value decomposition of AU.
X WA + -
d
Y U
We get the optimal jittering estimator as:
argmini Ja (f) -00=Y"x-- = UVAW (#WA t tz//m)]
(19)
-
UVA
A² + (ou + +oz/m)1
WT
(20)
d
d
UVdiag
WT
(21)
d?
do
C.3 Numerical simulations supporting Conjecture
3.3
In the following we present numerical simulations for general linear inverse problems in the subspace model support the Conjecture 3.3 further. The results show that the (empirical) optimal robust risk, obtained via adversarial training, is the same as the robust risk of the conjectured optimal estimator. Moreover, the results show that jittering can yield suboptimal robust estimators some cases.
We consider linear inverse problems y = Ax + z with the signal x lying in subspace x = Uc with c c~~N o /dI and Gaussian noise z ~ (0, o2/ /l). For the simulations, we choose a a = 100. Moreover, consider diagonal
and /2/ / 0.1 with dimensions d 50 and forward operators A diag(A:): operator with linear decaying singular values (A; and one with geometrically decaying singular values X; 0.7*.
Optimal worst-case estimator. We first estimate the optimal robust risks by performing adversarial training and compare it with the robust risk of the conjectured optimal estimator. Adversarial training is performed as described in Section 4 where we generate data {(y;, x:) using the respective forward model in the subspace. The estimator with one layer and without bias. Figure that the robust risk of the conjectured estimator is essentially the same as the (empirical) optimal robust risk.
f'y)) Hy can be viewed as neural network
Linear decay (A; = i/n)
Geometric decay (A; = 0.7*)
Robust risk R./n
0.5
0.5
0.4
0.48
0.3
0.46
Conjectured Adv. training
0.2
0.44
0.1
0.0
0.05
0.1
0.0
0.01
0.02
2
2/0²
Figure 5: Robust risks of adversarial training (dots) and the conjectured optimal estimator (lines) for two forward operators within the subspace model. can be seen that the conjectured estimators yield essentially the same robust risks as those of adversarial training.
22

---

Suboptimality of jittering. We further investigate whether optimal robust estimators can be obtained via jittering, To that end, we calculate the minimal robust risk attainable via jittering
min R. (argmin, Je.. (f)),
where fy) = Hy is a linear reconstruction operator as before. We make use of the analytic expression of the jittering estimator in Eq. (2l) and calculate the attainable robust risk by minimizing the robust risk of jittering with respect to the jittering noise level. The results are compared to the (conjectured) optimal robust risks via Eq. (8) and the robust risk of the standard estimator. Figure shows the results of the calculations for the forward operator with linear and geometrically decaying singular values described above. can be seen that the standard estimator noticeable less robust
compared to denoising setups. Moreover, gap can be observed between the robust risk obtained via jittering and the optimal robust risks.
Linear decay
Geometric decay
Standard
Robust risk Re
Adversarial Jittering
1.0
0.1
0.0
0.03
0.06
0.09
0.0
0.06 0.12 0.18
2//02
e² 2
Figure 6: Pixel-wise robust risk of the optimal worst-case estimator, the jittering estimator with optimal jittering noise level, and the standard estimators. A small gap can be observed, showing that (isotrope) jittering does not yield the optimal linear worst-case estimator in general. Moreover, the standard estimator is more sensitive adversarial perturbations in the denoising setup.
D Details on the experimental results and further experimental results
In this section, present details the experimental results in Section 4 and present further experimental results on U-nets trained with robustness-enhancing methods for image denoising. deconvolution, and compressive sensing. The setup and methods considered described in the main body.
D.1 Optimal robust denoiser for large perturbation levels
In the main body, we presented empirical results for perturbation levels in the range e² /E
||x ||x
[0, 0.3), since this is the practically most relevant regime. Figure 7 shows the risk of linear estimators and U-nets trained adversarially for perturbation levels the range e² <²/EE ||x E [0, 1.5). From
those plots, we see that the transition at //E [|] predicted by Theorem 3.1 for the estimator
map zero occurs for the subspace model (as predicted by the theory) well for the U-net for image denoising.
D.2 Convolution kernel for deconvolution experiments
In addition to experiments on denoising image data, we consider a deconvolution setup k*x + in this work. The kernel k is Gaussian, applied channel- and visualized in Figure g
D.3 Quantifying the smoothing effeet of Jittering
In the main text we presented visual example reconstructions and observed that neural networks trained via Jittering yield smoother reconstructions compared to adversarial and standard training.
23

---

Linear subspace denoising
U-Net image denoising
Robust risk R. n
1.5
No noise
Medium noise
1
High noise
0.5
0
0.5
1.5
0.5
Perturbation level e? /]E[[|x[[]] Perturbation level e² [1[[[
Figure 7: The empirical robust risk for models trained with adversarial training for noise levels 0₂ 0 (no noise), 02 0z/yn 0.5 (medium noise) and o./v/n 1.5 (high noise). The transition
predicted by Theorem 3.1 at e² x E and image denoising settings.
| for the estimator to map to zero occurs for the subspace
0.04
0.03
0.02
0.01
Figure 8: Gaussian kernel for the deconvolution experiment. The 8 x 8-pixel kernel is calculated as discretization the 2d Gaussian density with standard deviation 2.
We further quantify this observation by calculating the total variation norm of reconstructed images for the deconvolution task. The results are shown Figure Higure/land confirm the observation that networks trained via Jittering yield smoother images.
D.4 Hyperparameter selection
In the experiments we treat the Jittering noise level aw as a hyperparameter, which we optimize over validation dataset obtain robust estimators the desired perturbation levels. The hyperparameter search is performed by choosing a grid of jittering noise levels for each task. For each noise level neural networks (U-Nets) are trained via Jittering, and subsequently evaluated on the considered perturbation levels. Figures I0 I1 and 12 show the robust risks of jittering for the considered tasks, well the derived jittering choice rule. The smooth curves on the left panels represent the robust risk at a particular robustness level and are obtained by applying uniform filters on the evaluation results, can be seen that for image denoising the empirical jittering choice close to the prediction from theory.
24

---

Smoothness of reconstructions
Total variation TV(F)/10*
1.0
Standard
0.8
Adversarial
Jittering
0.6
0.4
0.1
0.2
0.3
Perturbation level e² P/B[||Ax||]
Figure 9: Jittering yields smoother reconstructions for deconvolution. The plot shows the total variation norm of images, which are reconstructions using U-nets trained via jittering, adversarially and via standard training. The TV-noom is calculated per reconstructed image fe (y;) and averaged over the dataset, i.e. TV Σ (y:) with n 2000 measurements y,.
Robust risks of jittering (Denoising)
Jittering level choice (Denoising)
Robust risk R. /n
Jittering level dw
0.6
0.4
0.4
0.2
0.2
0
0.2
0.4
0.6
0.1
0.2
0.3
Jittering level ow
Perturbation level e² [
Figure 10: Jittering hy hyperparameter results for image denoising. Neural networks (U-nets) are trained via jittering on a grid of jittering noise levels ow (with fixed noise level oz/vn = 0.25). The models are subsequently evaluated on the robust risk R. which is calculated for each of the perturbation levels e. Each line in the left panel corresponds to the robust risk at one perturbation level. The derived choice rule displayed in the right panel. empirical jittering choice matches the prediction (dashed line) from theory well (Corollary 3.2 with 128 128 49152 and subspace dimension d 32000).
be seen that for denoising the
D.5 Computational complexity
We measured the GPU time until convergence and memory utilization the schemes on the task of Gaussian denoising of colorized images. Figure [3 shows the training error of adversarial training, training via jittering and standard training function of the number of epochs. It shows networks trained at two perturbation levels for adversarial training and jittering (parameter choice taken from Figure TO). We find that all methods require similar number of epochs for convergence (roughly 600 epochs). Table [ the measured GPU time until convergence and average memory consumption. It can seen that adversarial training is by factor of the projected gradient ascent steps (3 in this plot) more expensive than jittering. Moreover, training via jittering has similar computational cost as standard training terms of GPU time. All three methods require similar amount of GPU memory to train.
25

---

Robust risks of jittering (MRI)
Jittering level choice (MRI)
Jittering level a '10 10-s
2
Robust Risk Re
1.5
1.5
1
0.5
0.5
0
0
0.5
1.5
0.00
0.01
0.02
0.03
Jittering level 0w/10-5
Perturbation level e²
||Ax|]
Figure 11: Jittering hyperparameter search for compressive sensing. Neural networks (U-nets) trained via jittering on grid of noise levels ow. The models are subsequently evaluated on the robust risk R., which is calculated for each of the perturbation levels Each line in the left panel corresponds the robust risk at one perturbation level. The derived choice rule is displayed in the right panel.
Robust risks of jittering (Deconvolution)
Jittering level choice (Deconvolution)
Robust risk R./n
Jittering level dw
1,5
0.5
4
0.1
0.2
0.3
Jittering level ow
Perturbation level 2²
|
Figure 12: Jittering hyperparameter results for image deconvolution. Neural networks (U-nets) are trained via jittering on grid jittering noise levels aw (with fixed noise level /./ 0.25). The models are subsequently evaluated on the robust risk Re, which is calculated for each of the perturbation levels e. Each line the left panel corresponds the robust risk one perturbation level. The derived choice rule is displayed in the right panel.
D.6 Required compute
The experimental results presented in this paper computed using on-premise infrastructure equipped with Nvidía RTX A6000 GPUs. In total, 18 GPU days were spent for the presented colorized image denoising, 20 GPU days for colorized image deconvolution and 15 GPU days for the compressive sensing experiments.
E
Discussion of the related work on randomized smoothing
Randomized smoothing is a very successful technique for obtaining robust classifiers (Cohen et al.) 2019; Carlini et al.) (023). Randomized smoothing constructs smoothed classifier based on a base classifier by averaging the base classifier's outputs under Gaussian noise perturbation. The smoothed classifier allows for certified radii in which it is provably robust, without making any restrictions on the base classifier. However, (Salman al. (2020) demonstrated that it can give loose bounds, since the base classifier is not trained to be robust to Gaussian noise. For that reason Salman et al.)
26

---

Adversarial Training
Jittering
Training error R. /n
Training error J nn
2² //|||>|] - 0.06
10 10-0.8
²² /B[[|]]]]] = 0.08
10 10-1.5
Standard training
10-1
10 10-1.2
1.2
10
11
11
100
10
10
103
100
10
10
10a
Epochs trained
Epochs trained
Figure 13: Training metrics of U-nets for adversarial training, jittering and standard training. The plot shows that the convergence rates are very similar for the considered setup. The curves show the training of networks for perturbation levels e² /|[[||||]]] 0.03 (red) and 0.06 (green). Training the methods takes roughly 600 epochs for convergence.
Method
Total GPU hours
Memory
Adversarial training
12.2
9971 MiB
Training via jittering
3.0 h
9523 MiB
Standard training
3.0
9523 MiB
Table I: GPU time until convergence and memory utilization of adversarial training, jittering and standard training for the task of denoising colorized images. The required number of epochs is estimated from the data visualized in Figure 13 GPU time and memory consumption are measured on Nvidia RTX A6000 GPU.
(020)) propose denoised smoothing, which considers a composition of the base classifier with a denoising method. At first sight, randomized smoothing might sound similar to the Jittering approach investigated here. However, as we argue below, randomized smoothing is conceptually very different from Jittering.
Given a classifier f: IRd + [I,...,K] K} randomized smoothing constructs a smoothed classifier from the classifier as:
(xx) arg
min kE(I...,KK
Ei- [f #k]) k)).
where the parameter o² controls the robustness-accuracc tradeoff.
For an inverse problem, where we aim to reconstruct a signal x RR" from a measurement, R. using given reconstruction method f, replacing the 0/1 by the lz loss yields:
g(y) = arg min 11
[[ + e) - x|
oe [f + +))
For linear estimator f(y) Hy we see that g f(y), so for the linear setting considered in the theory part of this paper randomized smoothing would not change the original estimator. If one considers f: Ih - [0. 11" the smoothed estimator g(y) differs from f'y) and robustness gains can be expected, which follows from Salman et al. (2019), Lemma 1. In summary, randomized smoothing very different to jittering that constructs a surrogate smoothed model gyy) based on given fixed estimator f(y), whereas jittering is training technique.
F Regularizing beyond jittering for enhancing robustness
Training neural networks via jittering, with noise levels chosen for larger perturbations, yields smoother reconstructions compared adversarial training (see results in Section 4.. In this section,
27

---

we investigate two related regularization methods, ez-regularization and Jacobian regularization. discuss the connection to regularization with jittering, and present experimental results for denoising grayscale images.
E1
E-- and Jacobian regularization in the subspace model
In the subspace model we established that the optimal jittering estimator is also worst-case optimal, when using a suitable choice of noise level (e). It turns out, that jittering can further be approxi- mated with an explicit regularizer, Jacobian regularization. For the linear setup considered here, this approximation becomes exact and therefore Jacobian regularization also enables training worst-case robust estimator. Specifically, using the linear approximation of the function f around the point y. we get
Baw [I + w) x[2]
Ea [I|((>) + Jyw w x Il(l)) x12 1
(22)
Here, Jy is the Jacobian of the function f at y. The approximation is good for small values of the noise variance ai and is exact for the linear estimator f(y)= Hy consider in this section. The approximate relation (22) motivates the Jacobian regularized risk, defined as
Jacx(S) = B(xxy) [IIsty) x|| X||Jy|1
(23)
The connection between jittering and Jacobian regularization well known the literature and discussed by Reed ct al. (1995). Recall that for the linear estimator considered in this section the approximation in equation (22) p exact, and therefore Jacobian regularization equivalent to jittering. Thus, Jacobian regularization yields a provably robust estimator, if the regularization parameter is chosen o (c) according to corollary 3.2
For the linear case, Jacobian regularization is even equivalent to fz-regularization, since the Jacobian of the function f(y) Hy is Jy H, and thus even fz-regularization yields a robust estimator.
F.2 Experimental results on grayscale image denoising
In the following we present results on Gaussian denoising of grayscale images. While f2 regularization is equivalent to jittering in the subspace model, we find that the parameter choice À = (c) does not yield robust neural networks using le regularization. In contrast, Jacobian regularization turns out to be quite effective for learning neural network denoisers, but is computationally demanding compared to jittering.
F.2.1 Problem setup
We consider once again the dataset of natural image and convert the images to grayscale. We perform Gaussian denoising, i.e. the problem is to reconstruct the image x from measurement y = + z, with z oo, nnI) and o./vá 0.2.
The estimators are chosen as neural networks (U-nets) with the same architecture as for colorized images. We consider adversarial training, jittering and standard training as bascline and compare against E2 and Jacobian regularization:
l2 regularization. Implemented as weight-decay in PyTorch's SGD optimizer to minimize
N
(
Σ llfo(y)) x112 x||0
Jacobian regularization. We train networks with the Jacobian regularized empirical risk
Jacx(0) Σ Ilfeo(y.) xx11 AlIJy.
where Jy, the Jacobian of the network fo with respect it's input (not it's parameters) at y:- This regularization be viewed as an approximation of the jittering risk, described in
28

---

Robust risk Rt/n
0.6
Standard Risk Ru/n
Jacobian
0.05
Jittering
0.4
fz-reg.
0.2
0.03
0.01
0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
Perturbation level e//E ||x|2
Perturbation level e²/EB
||x
Pixel-wise robust (left) and standard risk (right) of U-nets trained via jitteringg & and Jacobian regularization on the task of denoising grayscale images (at noise level /z/Vn = 0.2). The plot shows that & regularization yields less robust and accurate estimators compared jittering. In contrast, Jacobian regularization obtains similarly robust estimators, but with slightly weaker performance in standard risk.
Figure 14:
subsection F.1 Calculating the full Jacobian Jy, with PyTorch requires n-many calls of the backward function, which is very expensive, since n is large. To mitigate this cost, we approximate the where w
norm of the Jacobian, I|TT,. 1l with Jyy "yy""w/ |
(N, I). This approximation of the norm concentrates around the actual squared norm the Jacobian, and only costs one call of the Py PyTorch-acckyy function.
2
For the experiments we use stochastic gradient descent (SGD) with learning rate 10-2, momentum 0.9 and batch size 100. We evaluate using the empirical pixel-wise robust risk Re/n.
F222 Results
The experimental results, plotted in Figure 14, show that the networks trained with jittering and Jaco- bian regularization have similar robust risks compared to the adversarial trained one. Weight-decay or l2 regularization yields worse performing estimators than jittering and Jacobian regularization. While for the linear subspace setting, adversarial training, Jacobian and & regularization are equivalent, for Gaussian denoising they perform differently. Figure [5 shows that Jacobian regularization, unlike jittering, does not yield smoothed images for larger perturbations. However, Jacobian regularization requires approximately 1.4 much GPU memory and times more time per epoch.
29

---

(a) Original
(b) Noisy Image
(c) Standard
Robust (medium
(e) Jittering (medium c)
Jacobian (medium
(g) Robust Tr. (large c)
(h) Jittering (large
(i) Jacobian (large c)
Example reconstructions using U-Nets, trained with different robustness-enhancing schemes noise level o./ 0.2. The second depicts the results of using neural networks trained with methods tuned on a medium perturbation level of 2//0² = 0.03, whereas the third row shows results for large perturbation level e² e²/o² 0.3. The plot shows that jittering yields smooth reconstructions, whereas adversarial training and Jacobian regularization yield less smooth reconstructions.
Figure 15:
30


Reviews:
[{"review_id": "X0d54vDNcQ", "reviewer": "Reviewer_koTN", "summary": "The authors study the effectiveness of jittering in the setting of inverse problems, specifically considering denoising, compressive sensing, and deconvolution problems. Jittering is a well-known regularization technique for classification problems. The authors prove in the linear setting that the robust risk estimator can be probed to be the optimal estimator when learned with jittering for Gaussian subspace denoising. In addition, the authors demonstrate experimentally jittering is effective at improving the robustness of compressive sensing and image deconvolution, even though it yields suboptimal estimates.", "questions": "1). Could you provide metrics for a test set confirming jittering yields smoother reconstructions? \n\n2). Could the authors justify why they studied a linear model instead a non-linear model, a model more similar to a U-net? \n\n3). Could the authors explain the connection of section 3.3 to experiments in Section 4? Does the linear model exhibit enough similar behavior as the non-linear model to justify it as an appropriate model for general linear inverse problems? If so, could you please provide some numerical evidence? \n\n", "limitations": "I do not see any negative societal impacts of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1). The theoretical contribution is straightforward but has a strong contribution in the denoising setting. Even though the authors studied a linear model they were able to provide insights in the non-linear model (U-net) that was studied empirically. Refer to Figure 3 (Middle Plot), Cor.3.2 can accurately predict the optimal jittering level.\n\n2). The authors extend theoretical contribution for general inverse problems, section 3.3. \n\n3). The authors do a thorough investigation on the effectiveness of jittering empirically and theoretically for denoising inverse problems. ", "weaknesses": "1). The motivation of the paper seems a bit unclear, it appears to be motivated by results from classification problems rather than image reconstruction results in inverse problems. This approach seems slightly ad-hoc because the authors choose a popular regularization technique for classification problems and tested if it was effective for inverse problems without stating their intuition for it being effective or being of interest to the community. \n\n2). Section 4.2 lacks some metrics, specifically, Section 4.2 Figure 4 states \"Jittering yields robust estimators, but at the same time yields smoother reconstructions.\". This claim seems pretty strong considering it is not reported over a large test set with appropriate metrics for image reconstruction. \n\n3).  The section for 3.3 appears disconnected from section 4, it's unclear whether the linear model studied in this section (3.3) is representative of the behavior of the non-linear model utilized in section 4. \n\n\n\n\n\nMinor Weakness-\nTypo Figure 3- \"The jittering estimators estimators are similarly robust as adversarial\ntraining (Figure 1), but attain lower standard risks (right panel)\" Repeated word estimators estimators", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback and for noting that we make a strong contribution for denoising, and that even though 'they study a linear model they were able to provide insights in the non-linear model (U-net) that was studied empirically'. \n\nComments on the weaknesses and answers to the questions:\n\n**Weakness (1), clarifying the motivation of the paper.** The main motivation for the paper is to understand whether neural networks for signal/image reconstruction can be trained efficiently to be worst-case robust. To address this question, we first characterize the worst-case optimal estimator for a linear setup. This is the main technical contribution. While the worst-case optimal estimator is intuitive, showing optimality is non-trivial.\n\nWe then investigate whether jittering, a simple regularization technique that adds isotropic Gaussian noise during training, is effective for learning worst-case robust estimators for inverse problems, motivated by an ongoing discussion in the community on whether jittering is effective or not specifically for signal/image reconstruction problems. Specifically, Genzel et al. (2022) finds that jittering is effective for MRI and CT, whereas Gandikota et al. (2022) report suboptimality for deconvolution. \n\nOur work shows that jittering is provably effective for inverse problems, which we consider to be of great interest for the community given that it is computationally so much cheaper than adversarial training.\n\nWe'll clarify this motivation in the paper.\n\n**Weakness (2) and Question (1), on metrics capturing the smoothing effect:** During the rebuttal, we measured the smoothness using the total variation (TV) norm of reconstructed images for the deconvolution problem (same networks as in Figure 1; 2k test images). The results are in the attached pdf and confirm our observation that jittering yields to smoother reconstructions: The TV-norm of reconstructions using networks trained via jittering is generally smaller than those of standard or adversarial training.\n\n**Question (2), why doing theory for a linear model and not for a U-net**: We certainly would like to extend our theory to deep neural networks in particular a U-net or the like, but right now the theoretical tools for characterizing optimal network estimators of the complexity of U-nets do not exist to the best of our knowledge. The vast majority of results for neural networks is actually for linear networks, and for networks in the neural-tangent-regime that behave like an associated linear model. Our setup is already very difficult to treat analytically, since we have a minimization followed by an expectation followed by a maximization. That said, as we demonstrate empirically the insights carry over to neural networks and serve as an important first step towards analyzing nonlinear networks. Indeed, many theoretical results that are emerging (NTK, power method analysis in first few iterations) rely on understanding of appropriate linear networks for their nonlinear analysis. We hope to build upon this first step in future work.\n\n**Weakness (3) and Question (3), on the connection of 3.3 (theory for a linear model) to section 4 (experimental results):** \nWhile our theory is for a linear model, our experiments are for real-world imaging problems. We find a strong agreement of the theoretical results for the linear model and the real-world simulations for the U-net:\n- Jittering empirically yields optimal worst-case robust U-Net denoisers, as proven for the linear estimator (Fig. 1).\n- Jittering can be suboptimal for inverse problems beyond denoising, which is explained by our theory for general linear inverse problems in section 3.3 (Fig. 2 and Fig. 1).\n- The optimal jittering noise levels for U-net-denoisers are accurately predicted by theory (Fig. 3).\n- Adversarial training of U-nets even reproduces the theoretically predicted extreme behavior for large perturbations (obtaining U-nets mapping everything to zero, Fig. 8).\n\nPlease let us know if that addressed your concerns, if the clarifications change your final score, and if you have any further questions or comments."}, {"review_id": "4NB98KV0C1", "reviewer": "Reviewer_yCWN", "summary": "This work studies the design of estimators for the solutions of inverse problems that are adversarially robust, in the sense that they minimize the maximum MSE after being contaminated with an additive and L2 bounded perturbation. The authors show that, for linear estimators and for signals lying on linear subspaces, the optimal solution (i.e. optimally robust) is attained by training the estimator with “Jiterring”, i.e. by minimizing a loss over the randomly perturbed inputs. For more general inverse problems (when the forward operator is not an identity), the authors show that the resulting estimator from Jittering is not optimally robust in general, but their difference can be small. Moreover, they show numerically that this gap is small in practice, thus leading to similar performance (as that obtained by adversarial training) alas with significant increase in computational efficiency.", "questions": "1. As the authors mention, estimating the robust risk is non-trivial, since this involves the optimization of a non-convex/non-concave problem for non-convex functions $f(\\cdot)$ (as in the case of U-net). In light of this, the plots in Fig. 1 are not “exactly” the robust risk, but rather numerical approximations to it (except for the linear case). The authors might wish to clarify this in the caption and/or the description of Fig. 1 in the text.\n2. The role of the symmetry of H is not completely clear to me. When describing their results colloquially, the authors mention that, broadly speaking, training linear estimators with Jittering provides an estimator with minimal robust risk if the signal lies on a subspace. However, as written, the formal statement of Theorem 3.1 requires the estimator not only to be linear but also symmetric. So is, is symmetry required for Thm 3.1 to hold, or does symmetry arise as a property of the optimal estimator? I have a related question for Conjecture 3.3 - is symmetry here required, and in particular, $H = UV\\Sigma W^T$ need not be symmetric, as written.\n3. Their results are stated for $d\\to \\infty$. It is unclear why this is needed, or how the other dimensions and parameters scale with d. \n4. In Eq (3), do the authors mean to require $\\lambda \\geq max_i \\sigma_i^2$?\n5. Can the authors comment some more on the choice of norms? More precisely, the authors have focused on the MSE as loss (L2) as well as L2 bounded perturbations. I wonder to what extent their conclusions might extend to other norms. Moreover, it is possible that for different choices, some of the limitations in the analysis (e.g. in proving their conjecture) might be resolved. On the same vein, and because of their signal model, I wonder if there are any connections to the work of [Awasthi, Pranjal, et al. \"Adversarially robust low dimensional representations.\" COLT 2021], that the authors could leverage. ", "limitations": "Some limitations are commented on throughout the text. Might be nice to stress or clarify them further.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Neat and elegant idea.\n- Very clear presentation - this was a pleasure to read.\n- The results are novel and interesting.", "weaknesses": "- The results are somewhat limited, and hold for linear estimators with potentially overly simple signal models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback and are very pleased to hear the reviewer enjoyed reading our paper, that the results are novel and interesting, and that the idea is neat and elegant. \n- **Question 1, concerning robust risk vs an approximation of the robust risk**: Thanks for the suggestion, we added \"empirical robust risk\" to the labels of the plots and included “To approximate the optimal worst-case robust risk, i.e., the minimizer of $R_{\\epsilon}$, adversarial training is performed.” in the caption to clarify that we empirically approximate the robust risk, since we can't compute it exactly.\n- **Question 2, the role of symmetry of  $H$**: That is a very good point, it turns out symmetry of $H$ is not required for the main theorem, nor should it be part of the conjecture for general linear inverse problems (section 3.3). \nIn the submitted version, we assumed symmetry of $H$. During the rebuttal, we revisited the proof of our main theorem and were able to waive the symmetry assumption completely. This only required minor changes in the proof. Specifically, in the proof of the lower bound in section A.1, we now employ an SVD $H=V \\Sigma W^T$, and show that cross-terms between $V$ and $W$ in the robust risk can be lower-bounded suitably such that one can proceed as before.\n- **Question 3, assuming $d \\to \\infty$**: Our results exactly characterize the optimal estimator for the asymptotic case, and in the asymptotic case there is for example a sharp transition where the estimator maps to zero when the noise energy is equal to the signal energy. For very small d, there is no such sharp transition since the associated random variables do not concentrate well. That said, for moderately large values of d (larger than a constant) our results hold approximately with high probability by utilizing results from high-dimensional probability. We decided to state asymptotic results to provide cleaner expressions. Indeed, our simulations for the linear model show that the analytical formula is already accurate for moderate dimensions (d > 25).\n_Regarding the other variables_: In the limit subspace dimension $d \\to \\infty$, the embedding space $n > d$ is similarly treated in this limit. The energies $\\sigma_c^2$ and $\\sigma_z^2$, however, do no not depend on the dimensions.\n- **Question 4, question on Eq (3)**: $\\lambda \\geq \\sigma_i^2$ is used as an abbreviation of $\\lambda \\geq \\max_i \\sigma_i^2$. We included the maximum in the revision for clarification.\n- **Question 5, considering other norms:** We consider the $\\ell_2$-norm for the loss function and perturbations, since they are most relevant for inverse problems ($\\ell_2$-norm measures signal energy). \nWe would certainly be interested in extending our theory to other norms. However our results do not generalize in a straightforward manner to other norms. Specifically, it is unclear how to generalize Lemma 1 of the appendix, which reformulates the robust risk optimization problem to a tractable one with respect to a single variable. \nHowever, while it's unclear how to obtain a precise characterization, some more general predictions can be made. As an example, the transition predicted to the zero-estimator, predicted by Theorem 1, also exists $\\ell_p$-type perturbations ($p \\geq 2$). From our understanding, the work on robust PCA the reviewer pointed us to studies efficient approximation algorithms for finding $\\ell_p$-adversarially robust subspaces (but not actually characterizing the optimal ones). Moreover, finding these subspaces consists of finding optimal projection matrices onto subspaces, whereas we consider general reconstruction matrices for solving linear inverse problems. The paper is very interesting and we’ll investigate further connections. We appreciate the reference and add a discussion of this work to the related work section of our paper.\n\nWe really appreciate your feedback, which has improved the paper, in particular it led us to generalize our results to non-symmetric H. We hope this addresses your concerns. If so, we would appreciate it if you can consider increasing your score. Of course we are happy to address any further questions or comments you may have. \n"}, {"review_id": "PvNvFpj9X6", "reviewer": "Reviewer_uuzi", "summary": "This work considers introducing Jittering to the inverse problems for the benefits of robustness to the l2-worst-case. In this work, some analytical results are provided in proving the robust estimation with some assumptions, which I think are reasonable. Then, empirical experiments verify the effectiveness on the robustness improvement at a relatively lower computational cost compared to adversarial training.", "questions": "1. Some statements lack clarity, e.g., ‘we study jittering, a simple regularization technique that adds noise during training as a robustness-enhancing technique for inverse problems’……as a regularization technique, I would expect a concrete implementation or algorithmic description to make the paper more readable to general readers. (Similar as the bullet 3 in *Weakness); \n\n2. Line 90-94, page 3, [1][2] are mentioned. I quickly checked [1], and it seems like it already implemented the Jittering to the task of inverse problem. It would be nice to provide more details on the difference and relation to [1]. Though [1] has been cited, no further explanations or comparisons are provided later on in this work. As far as I have understood, this work is posed as a step forward upon [1] with some analytical results? This I believe should be clarified. \n\n3. It mentioned the random smoothing method in Section 2 and also the appendix. I understand that RS is significantly different this work. In RS, lots of samplings are required in evaluations. I’m wondering as an expectation over ‘w’ as in (2), there should also be some procedures requiring samplings either for training or evaluations or for sufficing assumptions. Could you please elaborate this part? (Similar as the bullet 3 in *Weakness) \n\n4. In the analytical results of this work, $\\sigma_c$, $\\sigma_z$ are the essentials. Could you summarize or provide  a general procedure of the relevant implementation procedures or simulation verifications on these variables when they are unknown in the practical settings.  (Similar as the bullet 3 in *Weakness), and the same applies to Section 3.3. \n\n5.  In section 4, besides the bullet 2 in *Weakness, the authors can provide some synthetic experiments to show and explain more detailed results or analysis, as these mentioned variables in the assumptions can be known explicitly and also at least can help the readability. \n\n6. It seems that the hyper-parameter tuning can be time consuming, if too many searches are needed to bring good results.\n\n7. One major claimed benefit is the efficiency, however, only Table 1 is provided roughly, where the complexity analysis is lacking. It should also be nice to mention the computational part involved in finding the hyper parameters. I roughly checked the codes of defining “param” argument and it seems that it just pre-gave a  energy value and heuristically proceeds the setup of other relevant params to run the training. (Similar as the bullet 3 in *Weakness) . For instance, though the compared the adversarial training is more expensive, it doesn't need too many pre-requisite or tuning and can be flexibly applied in various practical tasks.\n\nIf this paper can be put in a clearer way connecting the theoretical results and the implementation, and also the empirical experiments can be more practically feasible and convincing in the results, this work would deserve an improved score and I would like to increase my evaluation.\n\n[1] M. Genzel, J. Macdonald, and M. Marz. Solving Inverse Problems With Deep Neural Networks- Robustness Included. IEEE TPAMI 2022\n[2] K. V. Gandikota, P. Chandramouli, and M. Moeller. On adversarial robustness of deep image deblurring. In IEEE International Conference on Image Processing, 2022.", "limitations": "The authors should verify how convenient and efficient the proposed method can be applied in practical settings and explain some pipelines, in line with the claimed provability of the robust estimator. It seems unclear to me that how promising it could be in generally practical applications, especially considering the claimed analytical aspects.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The motivation of this work is quite nice, towards a provable robust estimator.\n2. The assumptions are reasonable.\n3. Existing results show somewhat promising performance.", "weaknesses": "1. Though some analytical results are presented, the actual realization and numerical implementation of the algorithm  are not articulated well I think, e.g., the assumed energy level of signals and noises are normally unknown, so that more details and algorithmic implementation discussions can be presented in a more systematic way, rather than just being mentioned in fractures in Section 4.\n2. Several experiments are conduced, but the presented results are limited in each experiment, e.g., cherry pick can be done if only a few images are presented.\n3. Some parts of the paper I read a few times, but I still found a bit difficult back and forth to relate all analytical results to the experiments in practical applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback and noting that the motivation is quite nice, the assumptions are reasonable, and the results show promising performance. \n\nComments on the weaknesses:\n- **Relation of theory and experiment:** The theory gives insights into worst-case robustness and justifies using jittering for obtaining optimal robust estimators. Our theory even predicts the optimal choice of jittering noise level for Gaussian denoising well. In addition, in practice, the optimal jittering level can be determined via a single-parameter hyperparameter search.\n- **Experimental results:** We perform experiments for several inverse problems (denoising, deconvolution and compressive sensing) and evaluate the methods on large datasets. Therefore the results are not cherry picked, as we evaluate on thousands of examples (see 4.1. Problem setup). Perhaps this impression can arise since we show a few example images only. Those images are chosen randomly to visualize reconstructions and to illustrate that jittering yields smoother reconstructions. During the rebuttal, we also quantified the smoothness using the TV norm (see the attached pdf) to be more precise.\n\nRegarding the questions:\n- **Question 1, implementation details on jittering:** Thanks for your feedback on this. It is indeed important to be specific on the implementation details of training with jittering. To fix this, we added the following lines in the paragraph *Training methods* in section 4.1: “Jittering is practically implemented via performing the SGD update rule $\\theta \\leftarrow \\theta - \\frac{\\eta}{n} \\sum_{i=1}^n \\nabla_{\\theta} \\| f_{\\theta} (y_i + w_i) - x_i \\|^2$. For jittering, the network output is calculated on the noisy input $y_i + w_i$, instead of $y_i$ (standard training) or $y_i + e_i$ (adversarial training). To approximate the expectation we draw independent jittering noise samples $w_i$ in each iteration of SGD.\n- **Question 2, related work on jittering for inverse problems [1,2]:**\nThe focus of the paper [1] is to obtain high-quality CT reconstruction. While the paper [1] mentions that it trains with jittering and this improves robustness, there is no systematic study on the effectiveness of jittering, no comparison to robust training, and no theory. In order to clarify the relation to [1,2], we revised the paragraph on jittering for enhancing robustness in inverse problems in our related work section accordingly. \n- **Question 3, regarding sampling and RS**: Randomized smoothing (RS) and jittering both approximate expectations w.r.t. Gaussian random variables. However, since RS is performed during evaluation (fixed network) lots of samples are required to approximate this expectation. Contrary, jittering is performed during training. While every sample is revisited multiple times during multiple epochs of training, it is sufficient to sample new noise at each iteration of SGD. We will further discuss this in the paper.\n- **Question 4 and 5, estimating signal energies in the experiments**: In practical experiments $\\sigma_c$ and $\\sigma_z$ are not actually required, since the optimal jittering level for robustness can simply be found via hyperparameter search (see also above). If needed (e.g. for testing the theory), they can be calculated as follows:   \n*Signal energy*: Given a dataset of $n$ images $x_i$, the signal energy $\\sigma_c^2 = \\mathbb{E}[\\|x\\|^2]$ can be estimated via $\\frac{1}{n} \\sum_{i=1}^n \\| x_i \\|^2$.   \n*Noise level*: If the forward operator $A$ for the inverse problem $y = A x + z$ is known, the noise level can be estimated via $\\sigma_z^2 = \\mathbb{E}[\\|y - A x \\|^2]$. If not, a linear reconstruction operator can be trained, and $\\sigma_z^2 d/m$ be obtained from its standard risk (see e.g. the formula in 3.2.2. Robustness accuracy trade-off).\n- **Question 6 and 7, cost of hyperparameter search:** The hyperparameter search is computationally inexpensive, since it is only a search over a single scalar variable. Moreover, our experiments show that only relatively few epochs are needed to find the optimal jittering noise levels (e.g. 30 epochs for denoising natural images). The actual training of the networks, however, needs a lot more epochs for convergence (600 for denoising). Thus, the cost for the hyperparameter search is a fraction of the training cost and thus relatively inexpensive.   \nMoreover, adversarial training requires $N$ times more GPU hours compared to standard training, where $N$ is the number of iterations for seeking the worst-case examples during training. For the networks depicted in the complexity analysis $N=3$, so adversarial training is three times more expensive (section D.4).   \nDue to this scaling, hyperparameter search for jittering is significantly more efficient. Finally, the pre-given energy level can be easily computed from the dataset, as described above. It is used in the code to scale the relative perturbation levels ($\\epsilon^2 / \\mathbb{E}[\\|x\\|^2]$ in paper).\n\nWe hope that those clarifications and changes connect the theoretical results and the implementation better, and we hope that we clarified that the experiments are practically feasible. Thanks for being open to increasing your score. Please let us know if you have any additional comments and questions. \n"}]

Author rebuttal:
We thank the reviewers for their helpful feedback. In this post, we address one of reviewer *koTN*'s questions.

**Metrics quantifying the smoothing effect**: During the rebuttal, we measured the total variation (TV) norm of reconstructed images for the deconvolution task over a large test dataset. The results are presented in the attached pdf and confirm our observation that jittering yields smoother reconstructions compared to adversarial and standard training.

Meta-review: This paper studies adversarially robust estimators to inverse problems by Jittering ie minimizing the loss after the input has been perturbed. 
The idea is novel, the method is reasonable and seems to work well. The reviewers liked the paper and asked reasonable questions that were addressed in the rebuttal. So this is a clear accept.
Decision: Accept (poster)