Nuclear Norm Regularization for Deep Learning
Authors: Christopher Scarvelis
Justin Solomon
Venue: NeurIPS 2024 poster (2024)
Keywords: nuclear norm
low-rank
optimization
regularization
denoising
representation learning
Primary area: optimization_for_deep_networks

Abstract: Penalizing the nuclear norm of a function's Jacobian encourages it to locally behave like a low-rank linear map. Such functions vary locally along only a handful of directions, making the Jacobian nuclear norm a natural regularizer for machine learning problems. However, this regularizer is intractable for high-dimensional problems, as it requires computing a large Jacobian matrix and taking its SVD. We show how to efficiently penalize the Jacobian nuclear norm using techniques tailor-made for deep learning. We prove that for functions parametrized as compositions $f = g \circ h$, one may equivalently penalize the average squared Frobenius norm of $Jg$ and $Jh$. We then propose a denoising-style approximation that avoids the Jacobian computations altogether. Our method is simple, efficient, and accurate, enabling Jacobian nuclear norm regularization to scale to high-dimensional deep learning problems. We complement our theory with an empirical study of our regularizer's performance and investigate applications to denoising and representation learning.

Nuclear Norm Regularization for Deep Learning
Christopher Scarvelis MIT CSAIL scarvêmit.. edu
Justin Solomon MIT CSAIL ceolommnt....... edu
Abstract
Penalizing the nuclear norm of a function's 's Jacobian encourages it to locally behave like low-rank linear map. Such functions vary locally along only handful of directions, making the Jacobian nuclear norm a natural regularizer for machine learning problems. However, this regularizer is intractable for high-dimensional problems, as it requires computing a large Jacobian matrix and taking its SVD. We show how to efficiently penalize the Jacobian nuclear norm using techniques tailor- made for deep learning. We prove that for functions parametrized as compositions -g o h, one may equivalently penalize the average squared Frobenius norms of Jg and Jh. We then propose denoising-style approximation that avoids Jacobian computations altogether. Our method is simple, efficient, and accurate, enabling Jacobian nuclear norm regularization to scale to nigh-dimensional deep learning problems. We complement our theory with an empirical study of our regularizer's performance and investigate applications to denoising and representation learning.
f f=g
Introduction
Building models that adapt to the structure of their data is a key challenge in machine learning. As real-world data typically concentrates on low-dimensional manifolds, good model should only be sensitive to changes to its inputs along the data manifold. One may encourage this behavior by regularizing that its Jacobian J ff [a]] has low rank. This causes f to locally behave like low-rank linear map and therefore be locally constant in directions that are in the kernel of J f
How should we regularize f so that its Jacobians have low rank? Directly penalizing rank(J [z)) during training challenging, the rank function not differentiable. In light of this, the nuclear norm [ [x]]l is appealing alternative: Being the I.1 norm of matrix's 's singular values, it is the tightest convex relaxation of the rank function, and as it is differentiable almost everywhere, can be included in standard deep learning pipelines.
One critical flaw in this strategy is its computational cost. The nuclear norm matrix is the sum of its singular values, so to penalize [|J [ in training, one must (1) compute the Jacobian of typically -igh-dimensional map f II" R. (2) take the singular value decomposition (SVD) of this m x matrix, (3) sum its singular values, and (4) differentiate through each of these operations. The combined cost of these operations is prohibitive for high-dimensional data. Consequently, nuclear norm regularization has yet to be widely adopted by the deep learning community.
This work shows how to efficiently penalize the Jacobian nuclear norm | using techniques maieor-made for deep learning. We first show that parametrizing f as a composition f = feature common to all deep learning pipelines allows one to replace the expensive nuclear norm [x][l with two squared Frobenius norms || Jh [x] I and []]]h(z))]| which admit an elementwise computation that avoids costly SVD. We prove that the resulting problem is exactly equivalent to the original problem with the nuclear norm penalty. We in turn approximate this by denoising-style objective that avoids the Jacobian computation altogether. Our method is
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

simple, efficient, and accurate both in theory and in practice and enables Jacobian nuclear norm regularization to scale to high-dimensional deep learning problems.
We complement our theoretical results with an empirical study of our regularizer's performance on synthetic data. As the Jacobian nuclear norm has seldom been used regularizer in deep learning, we propose applications of our method to unsupervised denoising, where one trains a denoiser given dataset of noisy images without access to their clean counterparts, and to representation learning. Our work makes the Jacobian nuclear norm a feasible component of deep learning pipelines, enabling users to learn locally low-rank functions unencumbered by the heavy cost of naive Jacobian nuclear norm regularization.
2 Related work
Nuclear norm regularization. As penalizing the nuclear norm in matrix learning problems en- courages low-rank solutions, nuclear norm regularization (NNR) has been widely used throughout machine learning. Rennie and Srebro [2005] propose NNR for collaborative filtering, where one attempts to predict user interests by aggregating incomplete information from large pool of users. Candès et al. [2011] introduce robust PCA, which decomposes noisy matrix into low-rank and sparse parts and uses nuclear norm regularization to learn the low-rank part. Cabral et al. [2013], Dai et al. [2014] use NNR to regularize the ill ill-posed structureffomm-moon problem, which recovers a 3D scene from a set of 2D images.
line of work beginning with Candès and Recht [2012] takes inspiration from compressed sensing and studies the conditions under which a low-rank matrix can be perfectly recovered from a small sample of its entries via nuclear norm minimization. This work was followed by Candès and Tao [2010], Keshavan et al. [2009], Recht [2011]. which progressively sharpen the bounds on the number of samples required for exact recovery. parallel, Cai et al. [2010] propose singular value thresholding (SVT), a simple algorithm for approximate nuclear norm minimization that avoids solving a costly semidefinite program as with earlier algorithms. However, SVT still requires computing singular value decomposition in each iteration, which is an onerous requirement for large matrices, Motivated by this challenge, Rennie and Srebro [2005] show how to convert nuclear norm-regularized matrix learning problem into an equivalent non-convex problem involving only squared Frobenius norms. Our work generalizes their method to non-linear learning problems.
Jacobian regularization in deep learning. Sokolić et al. [2017], Varga et al. [2017], Hoffman et al. [2020] penalize the spectral and Frobenius norms of neural net's Jacobian with respect to its inputs to improve classifier generalization, particularly in the low-data regime. Similarly, Jakubovitz and Giryes [2018] fine-tune neural classifiers with Jacobian Frobenius norm regularization improve adversarial robustness. Unlike our work, these papers do not consider nuclear norm regularization.
Neural ODEs [Chen et al., 2018 8] parametrize functions as solutions to initial value problems with neural velocity fields. Ensuring that the learned dynamics are well-conditionel minimizes the number of steps required to accurately solve these ODEs. To this end, Finlay et al. [2020] penalize the squared Frobenius norm of the velocity field's Jacobian and observe a tight relationship between the value of this norm and the step size of an adaptive ODE solver. Kelly et al. [2020] extend this approach by regularizing higher-order derivatives as well.
Finally, it has been observed as early as Webb [1994], Bishop [1995] that training a neural net on noisy data approximately penalizes the squared Frobenius norm of the network Jacobian training data. Inspired by this observation, Vincent et al. [2008, 2010] propose denoising autoencoders for representation learning, and Rifai al. [201 1] propose directly penalizing the squared Frobenius norm of the encoder Jacobian to encourage robust latent representations. Alain and Bengio [2014] show that an autoencoder trained with a penalty on the squared Frobenius norm of its Jacobian learns the score of the data distribution for small regularization values. Recently, Kadkhodaie et al. [2024] employ a similar analysis of the denoising objective to study the generalization of diffusion models.
Denoising via singular value shrinkage. While a full survey of the denoising literature is out of scope (see e.g. Elad et al. [2023]), we highlight a handful of works that employ singudar value shrinkage (SVS) to denoise low-rank data corrupted by isotropic noise given noisy data matrix. SVS denoises noisy data matrix Y by applying shrinkage function o to its singular values da-
2

---

This function shrinks small singular values of Y while leaving larger singular values untouched. Shabalin and Nobel [2010] study the conditions under which it suffices to rescale the noisy data's singular values while preserving its singular vectors. Gavish and Donoho [2014] study the optimal hard thresholding policy, which sets all singular values below a threshold
while preserving the rest. Nadakuditi [2014] considers general shrinkage policies whose error is measured by the squared Frobenius distance between the true and denoised data matrix. Gavish and Donoho [2017] then study optimal shrinkage policies under larger class of error measures. All of these methods assume that the clean data matrix is low-rank and hence that the data globally lies a low-dimensional subspace. Under the manifold hypothesis, real-world data such images typically lie on Now-dimensiona manifolds and hence locally lie in -iw-dimensional subspaces. Inspired by this observation, we use method in Section 5 to learn image denoiser given dataset of exclusively noisy images.
Method
In this section, we introduce our method for Jacobian nuclear norm regularization. We first prove that for functions parametrized as compositions f h (which include all non-trivial neural networks), one may replace the expensive nuclear norm penalty [[] - in a learning problem with the average of two squared Frobenius norms 2 [I]] 3 + [| [(]))) and obtain an equivalent learning problem. These squared Frobenius norms admit an elementwise computation that avoids a costly SVD in computing [-]][>)] As the Jacobian computation itself costly for large neural nets, use first-order Taylor expansion and Hutchinson's 's trace estimator [Hutchinson, 1989] to estimate the Frobenius norm terms. Computing a loss with our regularizer costs as few as two additional evaluations of g and h per sample, allowing our method to scale to large neural networks with high-dimensional inputs and outputs.
3.1 Preliminaries
Any matrix A E Rm*x admits a singular value decomposition (SVD) A UEVT, where U e Rm and V E R= are orthogonal matrices, and Σ E m is diagonal matrix storing the singular values o, 2 0 of A. The rank of is equal to its number of non-zero singular values.
The nuclear norm |||| of matrix A E IR=x" is the sum of its singular values: ||A||- - E, og As 2 0 by definition, ||A||| is also the L norm of its vector of singular values. Just as L regularization steers learning problems towards solutions with many zero entries, nuclear norm regularization steers matrix learning problems towards low-rank solutions with many zero singular values. For this reason, nuclear norm regularization has seen widespread use in problems ranging from collaborative filtering [Rennie and Srebro, 2005, Candès and Recht, 2012] to robust PCA [Candès et al., 2011] to concuurr-frommmttieee [Cabral al., 2013, Dai et al., 2014].
However, | A|l is costly to compute because it requires a cubic-time SVD. Furthermore, even efficient algorithms for nuclear norm minimization such as Cai et al. [2010]'s singular value thresholding require one SVD per iteration, which is prohibitive for very large matrices A. Motivated by this computational challenge. Rennie and Srebro [2005, Lemma 1] state that one can compute ||. by solving non-convex optimization problem:
||||
U.V.VV A (IU I[V])))
min
For completeness, we prove this identity in Appendix A.1. Using this result, Rennie and Srebro [2005) show that the following problems equivalent:
((A) + M|| = min ((UVT) 7 ( [V] AERmxn
min
(2)
"eR
VeR"x
where r = min (m, n) and f is a generic differentiable loss function. As | and its derivative V U can be computed elementwise without a costly SVD, the RHS objective (2) is amenable to gradient-based optimization.
3

---

3.2
Our key result
Equation (2) enables the use of simple and efficient gradient- based methods for learning low-rank linear map by parametrizing the matrix A as composition A = UVT of linear maps U and V In deep learning, one is interested in learning non- non-linear functions that are parametrized by compositions of simpler functions. Such functions I are differentiable almost everywhere so they are locally well-apppoxi by linear maps specified by their Jacobians J [x]]
Encouraging the learned function to have a low-rank Jacobian is natural prior: It corresponds to learning function that locally behaves like a low-rank linear map. Such functions vary locally along only a handful of directions and are constant in the remaining directions. When the training data is supported on a low-dimensional manifold, these directions correspond the tangents and normals, respectively, to the data manifold. One may implement this low-rank prior on Jf by solving the following optimization problem:
inf E [(((()) J[([]l] f:3" D(O))
where is generic differentiable loss function and (S2) is a data distribution supported on Q S R". If is parametrized neural network and n, m large, this problem is costly to optimize via stochastic gradient descent, as [xx E Im and computing the subgradient of [=][[=]]l- requires a cubic-time SVD. In fact, simply storing Jf [a:] in memory is often intractable for large n, m, which is typical when f is an image-to-image map. For example, if f is a denoiser operating on 1024 x 1024
RGB images, its inputs are 3 1024 x 1024 3,145, 728-dimensional, and J ʃ occupies nearly 40 TB of memory.
To address these challenges, we first prove theorem generalizing (2) to non-linear functions. We then show how to avoid computing J [x] altogether using a first-order Taylor expansion and Hutchinson's 's estimator. Our primary contribution is the following result:
Theorem 3.1 Let D(2) be a data distribution supported on a compact set S2 C R" with measure μ that is absolutely contimuous with respect to the Lebesgue measure Q. Let & C' (TR. x RT) be a continuously differentiable loss function. Then,
inf E (EC D(1)
[e(f(z). x) + f[[]f[=]]++]]
x)) " (I +1 (4)
inf hEC (9) SEC (M(R)
E D~D(
On the left-hand side, we learn function f RR Rm given fixed input and output dimensions n, m. On the right-hand side, we learn functions h : R" - I and g Rd + IR" with n, m fixed but optimize over the inner dimension d. We prove this theorem in Appendix A.2 and sketch the proof below. Theorem 3.1 shows that by parametrizing f as a composition of and h - feature common all deep learning pipelines - one may learn locally low-rank function without computing expensive SVDs during training.
Proof sketch. We denote the left-hand side objective by Ey(f) and its inf by (L); we denote the right-hand side objective by ER(g, h) and its inf by (It). We prove that (L) < (Rt and (R) S (L).
(L) < (R) is the easy direction. The basic observation is that if f g h. then J[[w] Jy(h(a)) Jh(z) by the chain rule. Equation (1) then implies that
1 (IU + I1 S [[Ig)( 1
1
||
min U.V.V = 2
(R) < (I. is the hard direction. The proof strategy is as follows:
1. We begin with a function fm E (12) such that Er.(Jn) arbitrarily close to its inf over C ( We use fm to construct parametric families of affine functions y hi whose composition a good local approximation to fun in neighborhood of E St both pointwise and in terms of the contributions to ER(g hmm) and (f(fm). resp., due to E Ω near

---

2. We then stitch together these local approximations to form a sequence of global approxima- tions g h to fm. These functions are piecewise affine and hence not regular enough to lie in C (22) required by the right-hand side of Equation (4).
3. Finally, mollifying the piecewise affine functions g h yields minimizing sequence of C (S2) functions gmm.. h such that En(gm,er h m,,) approaches the inf of EL.
While Theorem 3.1 shows how to regularize a learning problem with the Jacobian nuclear norm without cubic-time SVD, the Jacobian computation incurs quadratic time and memory cost, which remains heavy for high- nigh-dimensional learning problems. To mitigate this issue, the following section shows how approximate the []g[h(w))] and [Jh[a]]l terms in (4).
3.3 Estimating the Jacobian Frobenius norm
When f -"" 1Rm is a function between high-dimensional spaces, f is an m x n matrix that costly to compute and to store in memory. Previous works employing Jacobian regularization for neural networks have noted this issue and proposed stochastic approximations based on Jacobian- vector products (JVP) against random vectors [Varga et al., 2017, Hoffman et al., 2020]. As JVPs may be costly to compute for large neural nets, we propose an alternative stochastic estimator that requires only evaluations of f and analyze its enror:
Theorem 3.2 Let f R + mm be continuously differentiable. Then,
|| c-1100,211 +
-(x)] - + 0
(5)
Similar results appear in the ML literature as early as Webb [1994]. Our proof in Appendix A.3 relies on first-order Taylor expansion and Hutchinson's 's trace estimator; similar proof is given by Alain and Bengio [2014]. practice, we obtain accurate approximations to [>]][> by using a small noise variance o² and rescaling the expectation in (5) by 1 to compensate. In Section 4, we also show that single noise sample (O 1²1) suffices in practice.
Using this efficient approximation, we obtain the following regularizer:
E R(x; f) 20 c00 - s(h(2))) [| + 1())
+
(6)
where / = g h. In practice, one may use a single draw of e ~ N(00021) per training iteration while maintaining good performance downstream tasks; e.g. the results in Section 5. In this case, our regularizer R(:; f') costs merely two additional function evaluations, enabling it to scale to large neural networks acting on high high-dimensional data. In Section 4, we show that parametrizing fe as neural net and solving
E fo fa D(I)
inf
[((fo())
+ (2; fo)]
yields good approximations to the solution to (3) for problems where exact solutions are known. We then propose two applications of Jacobian nuclear norm regularization in Section 5.
Validation
In this section, empirically validate method special case of (3) for which closed-fom form solutions are known. We consider the following problem:
/ |
( - /| da,
inf (
(8)
where r TR.
R. - R is the indicator function of the unit ball in Rh. As f is a scalar-valued function in this problem, J [x] is vector, and [ [=)f(=)]l. This is instance of the celebrated

---

Seatin-Osher-Fateenn (ROF) model for image denoising [Rudin et al., 1992]. Meyer [2001, 36] shows that the exact solution (8) given this target function 7(z) is f(z) (1 rz) This is rescaled indicator function of the unit ball.
We parametrize multilayer perceptron (MIP) so and solve (8) along with the problem using our regularizer:
E fo D(D)
inf
( - -
where fo ge o hg. We approximate the integral over R by Monte Carlo integration over a box S centered at the origin. We experiment with n = 2 and 5 and in each case depict results for small and large regularization value 7). We track the objective values of problems (8) and (9) and show that they converge to the same value, predicted by Theorem 3.1. We also track the absolute error of both problem's solutions across training iterations and plot solutions to each problem at convergence for the 2D case. We give full implementation details in Appendix B.1.
(a) True solution to (8), 17 = 0.1
(b) Neural so- lution to (8)
(c) Neural so-
(d)
True
(c) Neural so-
(f) Neural solu- tion to (9)
lution to (9)
solution to (8), lution to (8)
0.25
Figure I: Comparison of exact and neural solutions to Problems (8) and (9) with n = and 0.1 (first three plots) and 0.25 (last three plots). The x- and yー represent the inputs to fe. and colors denote function values. Solving (9) recovers an accurate approximation to the true solution for both values of 1) while requiring no Jacobian nuclear norm computations.
2.40
4.0
(a) n 2, 0.1
(b) 12 2, 0.25
(a) 72 = 2, 0.1
(b) 72 2, 0.25
3401
3000
1 Hommm Arak
2003
(c) 5. 0.01
(d) 5, 0.05
5, 0.01
5, 0.05
Figure 2: Mean absolute enror of neural so- lutions to (8) (blue) and (9) (orange). Our regularizer obtains solutions with accuracy comparable to directly penalizing the Jaco- bian nuclear norm.
Figure 3: Log-objective values for (8) (blue) and (9) (orange) across training iterations. As predicted by Theorem 3.1, both problems con- verge to nearly identical objective values.
Figure depicts the exact solution to (8) for = 2 and two values of 1), along with neural solutions to the same problem (8) and the problem with our regularizer (9). Solving our Jacobian-free problem (9) with 10 draws of per training iteration yields accurate solutions to the ROF problem for both values of 77, with problem yielding slightly diffuse transitions across the boundary of the unit disc.

---

Figure 2 confirms the accuracy our our method's solutions, which attain absolute error comparable to the neural solutions to (8).
Figure depicts the objective values for Problems (8) and (9) on log scale across training iterations. As predicted by Theorem 3.1, both converge toward nearly identical objective values; the larger gap in Figure 3(c) is an artifact of the loss magnitudes being smaller and the plot being on log scale.
5 Applications
Unsupervised denoising. In this section, apply regularizer R(x; fo) unsupervised denoising. We learn a denoiser fo that maps noisy images x + c to clean images x given a training set of noisy images without their corresponding clean images. We motivate the use of our regularizer via a connection with denoising by singular value shrinkage, and demonstrate that our unsupervised denoiser nearly matches the performance of denoiser trained on clean-noisy image pairs.
Singular value shrinkage. A line of work beginning with Shabalin and Nobel [2010] studies denoising by singular value shrinkage (SVS). These works seek to recover low-rank data matrix X E TR DXN of unknown rank r given only single matrix Y = X + o. of clean data X corrupted by iid white noise Z. Since the clean data is low-rank, the components of Y corresponding to its small singular values contain mostly noise, so SVS denoises Y by applying a shrinkage function ø to its singular values σ.e This function shrinks small singular values of Y while leaving larger singular values untouched. For convenience, we denote the denoised matrix by é(Y).
Gavish and Donoho [2017] show that under certain assumptions the noise Z and data X, one can derive the optimal shrinker ó that asymptotically minimizes || - (I In Appendix A.4, we show that this optimal shrinker is also the solution to the following problem:
min
JAY
YI + 1|.
(10)
D 2N
where we set 77 of to be equal the noise variance. This problem a special case of the following instance of Problem (3)
|1 (1l v112 + +
inf E fo RD ((D)
(11)
when D(2) is an empirical distribution over N noisy training samples and fo is restricted to be linear map. Just as (10) yields an optimal shrinker for denoising low-rank data which globally lies in a low-dimensional subspace, we conjecture that solving (11) yields an effective denoiser for manifold-supported data such as images, which locally lie near low-dimensional subspaces even when trained on noisy images. We test this conjecture by solving (11) using neural denoiser fe. To make this problem tractable, we replace fe [9] ||+ with our regularizer R(y: fe). which we compute using a single draw of per training iteration.
Experiments. We train denoiser by solving (11) with D(2) being the empirical distribution over 288k noisy images from the Imagenet training set [Russakovsky et al., 2015]. Consequently,
PSNR (dB) 1
Imagenet
CBSD68
Method
1
o= 2
0=
BM3D
21.26 + 2.81
18.71 + 2.33
19.42 + 1.88
16.77 + 1.30
Ours
23.10 + 3.12
21.05
2.85
21.08 + 2.04
19.10 + 1.80
N2N Supervised
23.12
21.21
+ 3.02
20.37
1.71
19.37 + 1.89
23.37 + 3.25
21.39
2.97
11.62
19.54 + 1.95
Table 1: Denoiser performance via average PSNR on held-out images. Our method performs nearly
well supervised denoiser, despite being trained exclusively highly corrupted data without access to clean images.
7

---

(a) Ground truth (b) Noisy, σ
(c) BM3D
(d) Ours
(e) N2N
(f) Supervised
(g) Ground truth (h) Noisy,
BM3D
Ours
(k) N2N
() Supervised
Figure 4: Denoiser performance comparison held-out image corrupted by Gaussian noise with σ = 1 (first row) and a (second row). Our method performs nearly as well as a supervised denoiser, despite being trained exclusively highly corrupted data.
our denoiser does not see any clean images during training. The clean images' channel intensities lie in [-1, 1], and we corrupt them with Gaussian noise with standard deviations a E (1, We set o² when solving (11). We parametrize the denoiser fo go o hg as a Unet [Ronneberger et al., 2015], letting he and go its downsampling and upsampling blocks, resp.
We benchmark our method against a supervised denoiser trained with the usual MSE loss llfo + c) - x 1 on clean-noisy pairs, Lehtinen et al. [2018]'s Noise2Noise (N2N) method, which requires access to independent noisy copies of each ground truth image during training, and BM3D, a classical unsupervised denoiser [Dabov al., 2007]. We implement the supervised and N2N denoisers using the same Unet architecture as our denoiser, and train them on the same dataset with the same hyperparameters. We evaluate the denoisers via their average peak signal-to-noise ratio (PSNR) across the CBSD68 dataset [Martin et al., 2001] and across 100 randomly-drawn noisy images from the Imagenet validation set, randomly cropped to 256 256. We provide full details for this experiment in Appendix B.2.
We report each denoiser's performance in Table and include 1-sigma error bars computed across the test images. Despite being trained exclusively on highly corrupted images, our denoiser nearly matches the performance of ordinary supervised denoiser both noise levels and performs comparably to Noise2Noise, which requires independent noisy copies of each ground truth image during training.
We further illustrate the comparison in Figure 4. All neural meth- ods recover substantially more fine detail than the classical BM3D denoiser, particularly at the larger noise level a = 2. Notably, our method performs nearly well as a supervised denoiser, despite being trained exclusively on highly corrupted data.
Comparison of Jacobian singular values
dencleer
Lagio chequter cales
We also demonstrate the sparsity-inducing effect of our regularizer on the singular values So in Figure 5, where we plot the Jaco- bian singular values of our denoiser and a supervised denoiser at randomly-drawn validation image corrupted with o = 2 Gaussian noise. We normalize the singular values that each Jacobian's 's largest singular value is 1 and depict the singular values on log scale. As expected, our denoiser's Jacobian singular values decay more rapidly than those of the supervised denoiser at the same point.
2000 2000 4008 5000 Singuler
Jacobian singular values of supervised denoiser (blue) and our denoiser (or- ange) evaluated at a noisy held-out image with = 2.
Figure 5:
These results show that our regularizer (6) can be used to construct a tractable non-linear generalization of Gavish and Donoho [2017]'s optimal shrinker that performs nearly as well as supervised denoiser on image denoising tasks, despite being trained exclusively on highly corrupted images.
8

---

Figure 6: Traversals along Jacobian singular vectors our unregularized encoder in latent space. These traversals edit the colors of the outputs but not other meaningful attributes.
Figure 7: Traversals along Jacobian singular vectors of our regularized encoder in latent space. Our regularizer enables these traver- sals to edit the subject's facial expressions.
Representation learning. We now apply our method to unsupervised representation learning. We train a deterministic autoencoder consisting of an encoder so and a decoder go on the CelebA dataset [Liu et al., 2015] and approximately penalize the Jacobian nuclear norm J so [ar] || of the encoder at training data æ E D(2) using our regularizer Rax; fo). This encourages the encoder to locally behave like low-rank linear map whose image is low-dimensional. One may interpret this autoencoder with locally low-dimensional latent spaces. We demonstrate that the left-singular vectors of the encoder Jacobian Jr, [ar] are semantically meaningful directions of variation about training data in latent space. We provide full experimental details in Appendix B.3.
deterministic
To demonstrate our autoencoder's 's ability to learn meaningful representations, we select an arbitrary training point æ and traverse the latent space of our regularized autoencoder and an unregularized baseline along rays of the form = fo(x)) + (r)) where ug (x) is the d-th left-singular vector of the encoder Jacobian J [ These left-singular vectors form a basis for the image of J J [xr and approximate basis for the tangent space of the latent manifold fe().. We depict decoded images along this traversal for our regularized autoencoder in Figure 7 and for the baseline in Figure 6.
The traversals in Figure 7 are semantically meaningful. For instance, a traversal along the first singular vector edits the tint of the decoded image, and traversal along the second singular vector edits the facial expression of the image's s subject. The traversals of the unregularized autoencoder's latent space in Figure 6 edit the colors of the decoded image but are unable to control other attributes.
Figure 8: 8-VAE's latent traversals recover meaningful directions of varia- tion, but the decoded images are highly diffuse
We also follow Higgins et al. [2017] and visualize traver- sals along latent variables of a 3-VAE at the same training point x in Figure While the 3-VAE able to discover meaningful directions of variation, the decoded images are highly diffuse, as typical of VAEs. contrast, our autoencoder's 's reconstructions retain finer details. We conjecture that our model's ' improved capac- ity results from our autoencoder's ability to learn a locally low-dimensional latent space without constraining its global structure.
6
Conclusion
The Jacobian nuclear norm |]][m]]]+ is natural regularizer for learning problems, where it steers solutions towards having low-rank Jacobians. Such functions are locally sensitive to changes in their inputs in only few directions, which an especially desirable prior for data that is supported on low-dimensional manifold. However, computing []][=]]]|- naïvely requires both evaluating a Jacobian and taking its SVD; the combined cost of these operations is prohibitive for the high- dimensional maps f that often arise in deep learning.

---

Our work resolves this computational challenge by generalizing a surprising result (2) from matrix learning to non-linear learning problems. As they rely on parametrizing the learned function go h as a composition of functions ! and h, our methods are lailor-made for deep learning, where such parametrizations are ubiquitous. We anticipate that the deep learning community will discover additional applications of Jacobian nuclear norm regularization to make use of our efficient methods.
As an efficient implementation our regularizer relies on estimating the squared Jacobian Frobenius norm using Hutchinson's 's trace estimator, some error is inevitable. This error manifests itself in slightly diffuse boundaries in the solutions the Saaee-OOhhr--aeeee problem in Figure However, we do not find this error problematic for sigh-dimensional applications such as unsupervised denoising as in Section 5. Future implementations of our method may employ more accurate estimators of the squared Jacobian Frobenius norm for applications where accuracy is of paramount concern.
Acknowledgments and Disclosure of Funding
The MIT Geometric Data Processing Group acknowledges the generous support of Army Research Office grants W91 INF2010168 and W91 NNF2 10293, of National Science Foundation grant IIS- 2335492, from the CSAIL Future of Data program, from the MIT-IBM Watson AI Laboratory, from the Wistron Corporation, and from the Toyota-CSAIL Joint Research Center.
Christopher Scarvelis acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), funding reference number (GSD3-557558-22
References
G. Alain and Y. Bengio. What regularized auto-encoders learn from the data-generating distribution. The Journal of Machine Learning Research, 15(1):3563-3593, 2014.
C. M. Bishop. Training with noise is equivalent to tikhonov regularization. Neural Computation, 7 (1):108-116, 1995. doi: 10.1162/ncco. 1995.7.1.19990.
R. Cabral, F. De la Torre, J. P. Costeira, and A. Bemardino. Unifying nuclear norm and bilinear factor- ization approaches for low-rank matrix decomposition. In Proceedings of the IEEE international conference on computer vision, pages 1888-2495, 2013.
J.-F. Cai, E. Candès, and Z. Shen. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4): 2010. doi: 10.1137/080738970. URL https: //doi orge 10tgg/10.0 1111 /080738700
E. Candès and B. Recht. Exact matrix completion via convex optimization. Commun. ACM, doi: 10.1 10.11452184999921844453 URL https:
15(6):111-119, jun 2012. ISSN 0001-0782.
//doi.org/10. 1ee11111111111 114111111111/1111...111 2184343.
E. J. Candès and Tao. The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theor, 56(5):2053 20000000,00000 may 2010. ISSN 0018-9448, doi: 10.1009/TT22010224444661
URL attps:///ol: org/10. 1tt.:10..1191// 1109/TIT. 2010. 2044061.
E. J. Candès, X. Li. Ma, and J. Wright. Robust principal component analysis? ACM, 58(3), jun 201 ISSN 0004-5411. 1. doi: 10.1 001145//970392.1973999 URL https://doi. 0rg/10.110 1145/ 1970392. 1970395.
R. Т. Chen, Y. Rubanova. J. Bettencourt, and D. K. Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31, 2018
K. Dabov, A. Foi. V. Katkovnik, and K. Egiazarian. Image denoising by sparse 3-d tranfformddomn collaborative filtering. IEEE Transactions on Image Processing, 16(8):2000-0995 2007. doi: 10.1 1.11009/1P:20077 01000009911220 9012388.
Y. Dai, Li, and M. He. simple prior-free method for non-rigid stractureffrom-mmttin factoriza- tion. International Journal of Computer Vision, 107:101-122, 2014.
10

---

M. Elad, B. Kawar, and G. Vaksman. Image denoising: The deep learning revolution and be- yond survey paper. SIAM Journal on Imaging Sciences, 16(3):1594-00 1654, 2023. doi: 10.1 14111333MM555859 URL
C. Finlay, J.-H. Jacobsen, Nurbekyan, and A. M. Oberman. How to train your neural ode, arXiv preprint arXiv:2002.02299, 2, 2020.
Fritz. Nuclear norm as minimum of frobenius norm product. MathOverflow. URL https: /mathoverrllo.nne////282800 wtt.oo//..ee////...... URL.ihtsss/mmttovvrrooo...e///// (version: 2018-04-
/ //mathoeerflo.... 18).
M. Gavish and D. L.. Donoho. The optimal hard threshold for singular values is 4/v3. IEEE Transactions on Information Theory, 6048):5000-5053, 2014. doi: 10.10099T.22142223333.
M. Gavish and D. L. Donoho. Optimal shrinkage of singular values. IEEE Transactions Information Theory, 63(4)22137-2152, 2017.
1. Higgins. L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Lerch- ner. beta-VAE: Learning basic visual concepts with a constrained variational framework. In International Conference Learning Representations, 2017. URL https / http///pppeeeee..eeeeeeee weteeeeewwwwweeeeeeeeee....eeeee forum/id-SS2fa2Ugg1.
J. Hoffiman, D. A. Roberts, and S. Yaida. Robust learning with jacobian regularization, 2020. URL attps://openreviek/ net/ woroormmdddlllttee.
M. Hutchinson. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communication in Statistics- Simulation and Computation, 18:1059-1076, 01 1989. doi:
10.108000361091100888 12666.
D. Jakubovitz and R. Giryes. Improving dnn robustness to adversarial attacks using jacobian regularization. In Proceedings of the European conference on computer vision (ECCV), pages 514-529, 2018.
Z. Kadkhodaie, F. Guth, E. Simoncelli, and S. Mallat. Generalization in diffusion models arises from geometry-adaptve harmonic representations. In The Twelfth International Conference on Learning Representations, 2024. URL https: httttp:://ppeerviiee.. wwtp:/rrmteetiiieeeeeee Adt.ormmmmiiANN///22
J. Kelly, J. Bettencourt, M. J. Johnson, and D. K. Duvenaud. Learning differential equations that are easy solve. Advances in Neural Information Processing Systems, 33:4370-4380, 2020.
R. H. Keshavan, S. Oh, and A. Montanari. Matrix completion from few entries. In 2009 IEEE International Symposium Information Theory, pages 324-328, 2009, doi: 10.1 10.1100//S/T.2009 5205567.
J. Lehtinen, Munkberg, J. Hasselgren, S. Laine, Karras, M. Aittala, and T. Aila. Noise2noise: Learning image restoration without clean data. In International Conference on Machine Learning (ICML), volume 80, pages 2971-2980, March 2018.
Z. Liu, P. Luo, X. Wang, and X. Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL /ttps:///penrrvvior
D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statisties. In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, volume 2, pages 416-423 vol.2, 2001. doi: 10.1 1009/CCC.200011111111 1937655.
R. Mazumder, T. Hastie, and R. Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of Machine Learning Research, 21800)2287-2322, 2010. URI. http:// jmlr. wtggpapers/vili hwtp1///mmm/eeeeeee html.

---

Y. Meyer. Oscillating Patterns in Image Processing and Nonlinear Evolution Equations: The Fifteenth Dean Jacqueline B. Lewis Memorial Lectures. American Mathematical Society, USA, 2001. ISBN 0821829203.
R. Nadakuditi. Optshrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage. Information Theory, IEEE Transactions on, 60:3002-3018, 05 2014. doi: 10.1 (09/TTT.2014.2555 1661.
B. Recht. A simpler approach to matrix completion. J. Mach. Learn. Res., 12(null::311334433 dec 2011. ISSN 1532-4435.
J. D. M. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd International Conference Machine Learning, ICML '05, page 713-719, New York, NY, USA, 2005. Association for Computing Machinery. ISBN 1595931805. doi: 10.1 102351. 102441. URL https://doi http:///oooooo/////// 10. 1011/111111//1111 1102441.
S. Rifai, P. Vincent, X. Muller, X. Glorot, and Y. Bengio. Contractive auto-encoders: Explicit invariance during feature extraction. In Proceedings of the 28th international conference on international conference on machine learning, pages 833-840, 2011.
R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and Ommer. High-resolution image synthesis with latent diffusion models, 2021.
O. Ronneberger, P. Fischer, and T. Brox. U-net: Convolutional networks for biomedical image segmentation. Medical image computing and computer-usisted interventionMMICCAI 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pages 234-241. Springer, 2015.
L. I. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1-4):259-22)) 268, 1992.
O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei. ImageNet Large Scale Visual Recog- nition Challenge. International Journal of Computer Vision (IJCV), 115(3):211-22, 2015. doi: 10.1007/s1 1263-015-0816-)
A. Shabalin and A. Nobel. Reconstruction of low-rank matrix in the presence of gaussian noise. Journal of Multivariate Analysis, 118, 07 2010. doi: 0.11116..mmm
Sokolić, R. Giryes, G. Sapiro, and M. R. D. Rodrigues. Robust large margin deep neural networks. Trans. Sig. Proc., 65(16))4265-4285 aug 2017. ISSN 1053-587X. doi: 10.1 10.11097S522017.2700033 URL httph:tt:////tttt //doi. orgoorr./// 10. 1109/TSP /TPP. 2017 2708039.
M. Tancik, P. Srinivasan, B. Mildenhall, S. Fridovich- Keil, N. Raghavan, U. Singhal, Ramamoor- thi, J. Barron, and R. Ng. Fourier features let networks leam high frequency functions in low dimensional domains. Advances neural information processing systems, 33:7537-7547, 2020.
D. Varga, A. Csiszárik, and Z. Zombori. Gradient regularization improves accuracy of discriminative models. arXiv preprint 17X1v:1122.09936 2017.
P. Vincent, H. Larochelle, Y. Bengio, and P.-A. Manzagol. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference on Machine learning, pages 1096-1 103, 2008
Vincent, H. Larochelle, I. Lajoie. Y. Bengio, P.-. Manzagol, and L. Bottou. Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion. Journal of machine learning research, 11(12), 2010.
A. Webh. Functional approximation by feed-forward networks: least- squares approach to general- ization. IEEE Transactions on Neural Networks, 5(3):363-33) 371, 1994. doi: 10. 10.1109772.286008.
K. Zhang, Y. Li, W. Zuo, L. Zhang, L. Van Gool, and R. Timofte. Plug-and-play image restoration with deep denoiser prior. IEFE Transactions on Pattern Analysis and Machine Intelligence, 44 (10):6360-633 6376, 2021.
12

---

A Proofs
A.1 Proof of Equation (1)
We draw heavy inspiration from a proof by Fritz that appeared on MathOverflow. We will prove that
||||+
min U.V.VV =A [||U|*++||V]))
First suppose that U, V are matrices such that UVT A. By the matrix Hölder inequality,
||||| ||UV ||. | F- -IVI.
By the arithmetic meen-geemmtrii mean (AM-GM) inequality,
1113 1IVI3 = 1 (IUT1 + [[V[1))) |l| |V /IUB.
Combining these results, we obtain
||||- = IUV S inf
2 (|11) + |I
U.
To see that the inf is attained at ||Al|=, take the compact SVD A = UAEVI and set =
UA UAVE, = VAVE. Then clearly UV = A. and
1
+ - + - (IIEI1 + +[VE!
1
2
Σ oi + Σ a.
||||||
2
This proves Equation (1), An alternative proof using somewhat more complex methods is given in Mazumder et al. [2010].
A.2 Proof of Theorem 3.1
Let D(2) be a data distribution with measure μ supported on a compact set Q R" that is absolutely
continuously with respect to the Lebesgue measure A(22), and let & E C¹ (RR") be a continuously differentiable loss function. Let C (12) denote the set of infinitely differentiable functions on f2. We will show that:
inf (EC*(0) DDD(
E
[((f(x), + +[]]f[[]]1+]
inf
E x))(
((o(M(=)), (1)g(b(>))1 + [[Jh(=]11)] (12)
hEC (9) 900 (M({)
We denote the left-hand side objective by (f( and its inf by (L); denote the right-han hand side objective by Enzgg h) and its inf by (R). We prove that (I.) < (R) and (R) S (L).
A.2.1 (L) < (R)
This is the easy direction. The basic observation is that if we parametrize g h, then ff[z] Jhlp( and Srebro's identity (1) tells us that
|]
min uv:ovT=JJ(41
(IUI + |IVI S (IIggh(=))II+++ +1J
13

---

The rest of the proof is book-keeping,
We first verify that C (12 is closed under composition by showing that:
(2)= = ( h Ca g E (b(())))
(13)
The C inclusion is straightforward: given any f E C (S2), just choose h = f and = Id; these functions are clearly in the correct classes. The inclusion follows from the fact that the composition of C functions is C by the chain rule.
This yields:
inf El(f)= IEC (9t)
inf hEC (9)
El
(EC((((()))
We now use Srebro's identity as follows:
inf kEC gEC* (I(2))
E)
inf
E
[((((((())))) [[]]]l]]]
NEC (0)
z>D(At)
gEC (I(S2)
inf
hEC (Q) x>D(1))
SEC* (A(2))
inf
[(g(h(())), + " (|)0()))))))+00 +
hEC (0) z>1(
gEC (k(1)
inf NEO (Q)
ER(goh).
gEC* (h(2))
Consequently,
inf SEC=(1)
El(f)
S
inf
En(g o h)
heC (9)
gec* (h(R))
and hence (L) S (R).
A.2.2 (R) < (L)
This is the hard direction. The proof strategy is as follows:
1. We begin with a function fm E ( such that (z(fm) is arbitrarily close to its inf over C (12). We use fm construct parametric families of functions g... h whose composition is a good local approximation to fm. in a neighborhood of E S2, both pointwise and in terms of the energy contributions due to x Ω near z. This step relies crucially on our ability to construct optimal solutions to the RHS problem in (1).
2. We then stitch together these local approximations to form a sequence of global approxima- tions g h to fm. These functions are piecewise affine and hence not regular enough to lie in C (S)) as required by the right-hand side of Equation (12).
3. Finally, mollifying the piecewise affine functions oth h yields minimizing sequence of (2) functions gin.. h/,,, such that ER(g hxt h/_e)) approaches the inf of EL.
Local approximations to fm- To begin, let fm E C (P) be function that attains Er (fm) < inf fea (2) (f( + 1. m Fix some & E Ω take the thin SVD of Jf = Un (2) (z)
and use it to define two parametric families of affine functions:
(x) = Em (2 (m) (2)
14

---

and
( (2 v Em (2)y + fm(z) Jfmlz1]z.
These functions satisfy two key properties:
em (x)) = (f -2) = fmi(2) + (x),
(14)
where [ E O(Ix - =212) by Taylor's theorem, and
1) (I] Ih (h (x)]11 + [x1
" (IVEm(=))l II Em(z)
nlIJfmm [ (15)
2
Using (14), we obtain
Eggn (h (z)), ((fm(x) + Re (x),
(16)
The continuity of E ensures that make (x) + R (x), x)) arbitrarily close to 6(fm (x)
by making || - 2||2 sufficiently small. Furthermore,
| [=]] = J [xr + [[m[=]] [m]]l] <
[f][)]]] + +1[[sm][]] - J/
(17)
and as Jm E J is continuous function, so can make [=] J. [r]] arbitrarily small by making || - z|l sufficiently small.
The compositions of these functions gin hū are good local approximations to fm in a neighborhood of z, both pointwise (by (14)) and in terms of the energy contributions arising from near (by (16) and (17)).
Global piecewise affine approximations to fu- We now stitch together these local approximations to form sequence of global approximations 9h l to fm.
For each k. fix set of points Z (=x (=()) and use this set to partition Ω into Voronoi regions V,- Choose the centroids z; such that max || 2112 S
for EK > sufficiently small to ensure Im [=]]ll + [ (x) + ()), {(fm (x), æ) < for all V; and for all regions V, (The compactness of Ω and the uniform continuity of [m Il on Ω and l on its domain ensures that we can always find a finite set of centroids with this property.)
that [||J [2.]]l
Then let gh h be piecewise affine functions such that gh. (z) == gf (x) and h (x) := hxx()) for all x E int(V.). For all points x on Voronoi boundary, define -hh 1 by averaging over the interiors of the Voronoi cells incident on the boundary. This yields:
15

---

E x>D(
Elo (h (x)),
7 (1 [ (x)]1 + || || [=111²)))
N(K)
E (00
[ R JIIJ E
] a E vil
E w>L((
Σ ())
E D=1(
{(fm + n
= Em(fm) +
1
S inf fECm(R)
EL(f) + m
k
and hence ER(gi (in) S sec Ef(f) + 1 +
Mollifying the piecewise affine approximations. The functions gh N*t constructed in the previous section are piecewise affine and hence not regular enough lie in C (x2 as required by (R).. We now mollify these functions yield minimizing sequence of C (It functions o hy such that En (nmmee & e approaches inf (e) (f).
mollify ghe h by convolving them against standard mollifiers (infinitely differentiable and compactly supported on (00,e) e)) yield a sequence of C (S2) functions I hmm.. We need to show that
En(g m,n,)) S Ex(g N + m,,;,,
for some error (e; k) that vanishes as e - for any m, k. We proceed by individually controlling the terms in E ER( ER(gh.c hk hn..).
Controlling the error in
E [E(gth (h (x)), x))- We first show that it suffices to prove that 2nD((S)
llgh. o hhhh -9 o h ( + 0 for any k. (Recall that μ is the measure associated with the data distribution D(S)).)
Note that as l E C* and the image of the compact Ω under the piecewise affine function gh hk is bounded, l is L-Lipschitz on o (h (2))). For any sequence of functions fn converging to ff in L we then have:
11 ((In()) ((()))(()))))))))))))))))()) ((S(x)
$ ()() {(f(x),))) -(((())))))) dp
12
-
[1l - f(x)lladp
a
J (1f((()) - f(x)22244
Ll -fll
0
therefore suffices to show that t 1b Ihh h ( - 0 any m, k. To this end, we will use the bound
16

---

llom. o himee-sh om
ohhalllllee ((..)) S Ilome o -mmm oh (ooll'aa,,, (a, -llsmme oh Im
and show that each of the RHS terms goes to 0 as - O.
We begin by controlling Il h Im.. om ([..)) The obvious approach is to use the fact that om,e Lipschitz on the bounded domain N (52) and that || N (a,,) - 0 by standard properties of mollifiers. However, this naïve approach fails because the Lipschitz constant of g increases as + O: We need to bound it in terms of quantity independent e. We will instead use the fact that the un-mollified function 9m is piecewise affine and hence locally Lipschitz on the interior of each affine region.
Before proceeding with the remainder of the proof, we make a key observation. Given a Voronoi partition of the compact domain $2 into N (k) cells V,, constructed g h as piecewise affine functions such that gm (x) gi (ar) and hy (x) (x) for all int(V)) and for all points on a Voronoi boundary, we defined ghx h, by averaging over the interiors of the Voronoi cells incident on the boundary. The affine functions g h were constructed to have the following properties:
I.. (h (2)) fm(2) + Jfm[=]( - -2 =m (x)),
(18)
where [1 E O(I =11²) by Taylor's theorem, and
7) (1J [h (x)]]] + | = (1I (z)]l Em (z) -n|JSmm=>]] (19) 2
At any x on the interior of a Voronoi cell, thh and h,; are equal to some affine functions g h so by (19). 3 (IIJgh, mm [h [1) + || [=]]?+)) ) n [xi]ll < +oc. In particular, [| [Ag, (x)] and [| [x]]] must both be well-defined and finite at this x. This can only happen if h (r) lies on the interior of a Voronoi cell, since otherwise Jg [ (x)] would be undefined. Hence N maps the interior of Voronoi cells to the interior of Voronoi cells; the contrapositive is that h (r) lies on a Voronoi boundary, then also lies Voronoi boundary. It follows that the preimage of the Voronoi boundaries under h is a set of Lebesgue measure zero. Under the absolute continuity hypothesis, this is also set of j-measure zero. We use this fact extensively throughout the remainder of the proof.
For any m, k. let Sh C Ω be the set of Voronoi boundaries from the partition we constructed earlier; this Voronoi partition depends on m, but not on e. We then begin by stripping the Voronoi boundaries from Ω to obtain 2(m, k) = Ω St This only removes set of p-measure 0 from P and hence doesn't impact the remaining convergence results. Given e, we then partition 2(m, k) into two subsets:
Let Ro S Mmm, k) be the set of 3(m, k) such that d(x, S e. (We use d(p, S) to denote the distance from the point p from the set S.)
Let Pi (m, k; e) be its complement in Q(m, k): the set of x E 3(m, k) such that d(x; Sk) S e.
Do(m, k) will be our good set, and Q2 (m, k e) will be a bad set whose measure converges to 0 as E + O. We decompose llgt. o h - gmm o Ak k (( as follows:
llom. h sin (
-J (hm.ee(" th (hit (12d4
J (am(mtte)) (m.iie)
ll (1h, - gmm (h ( (2)
17

---

We begin by showing that l (h (2)) - sm, (h (z)) la for all æ E ao(m, k, c). To this end, first recall that the standard mollifier supported on (00, e) is defined as follows:
((c) exp
for |ylla S for |y/|2
1-
(20)
where C(e) > 0 is chosen to ensure that T)e integrates to 1. Now, if am ki, then d(z, Sth e and hence (xx,)) é) is entirely contained in the Voronoi cell Vi containing æ. (Note that æ cannot lie on Voronoi boundary, as we have stripped the p-measure zero set of Voronoi boundaries S from Ω before constructing Ro k, and Q (m,k,e).) On this ball B(x, e), the linearity of h (v) / Em (m))) y and the rotational symmetry of the mollifier T)e yields:
(x)
SECOSS 1 (1) - yddy
(21)
= - SBwO
V (2)(2)) I "ncc y)dy
(22)
VVm((=)V(((s))
Mel - vidy
(23)
B(0,e)
(z)()) (z:) h (z).
(24)
(25)
Hence for all Io(m, k (x))(x))= = hm (ar), and it follows that Ih ( (h),,(=)) (x)) = gm, (h (x)) and therefore (x)) Itm (h (x))]l2 O. We conclude that o
J 1oth (hi, (x)) 2 (ht, 12dz
To bound the second term, note that the following inequalities hold p-almost everywhere on Ωt
(Mi, (x:)) gin (h (x)))l2 = 2
sup ( S y (R(m,)))
Il (v)1l2 =: M (m, k).
sup
yekt (3(m,)))
(26)
The second inequality can be derived using Jensen's inequality by first showing the following for all y E hi, (5(m, k)):
I Im (#) me (2)dz ll2 :=)
=
B(y.c)
(2))lannnn))
B(yre)
<
sup
ll (u)llz
dne(2)
veΛt (D(m,))
B(y.e)
l (v)
sup
yeΛr (9(m)))
which implies that
18

---

sup y (R(m,)))
( 1
sup DeNt (3)(m,)))
I10m (1)ll2
Returning to (26), we can bound the integral over the bad set (ankk llom ( (x))
Im,e (h (dd as follows:
S Sanimass llssi ( (x)) (b (2) M(m,k) p(Qi((,,
where f (m, k)) is the measure of (m,, We will now show that u( (m, k, E)) 7 which will imply
Il (x)) - (h (x)) - O,
(m,,ke
and therefore allow conclude that
Ilg h gm,e h h (22 3o 0.
Proving that (m) ki e)) O. Recall that:
2 (m k. c) = {xr E 9mm,k) d(x, Sth) sc.
(27)
where d(xr, Sth denotes the distance from the point the union of Voronoi boundaries S Note that this set is union of cylinders of radius centered at the Voronoi boundaries S As 8 has Lebesgue measure O, Lebesgue measure the cylinders (mm, k. E) also goes to as the radius O. The absolute continuity of μ then implies that ((22mm. k. c)) - 0 as well.
Using these results, we obtain
Saamak l1o 1l (h (2)) - O,
c
and therefore conclude that
lgm. h Im,e h (1 30 0.
This completes the proof that lloth o h gh. o t ( - 0 as e + 0.
Controlling the second term light h,, shh o hh ((lllz(())))) is casier. Indeed, gi h
gh. hr, pointwise a.e. - 0 by standard properties of mollifiers. Furthermore, the sequence Fm,e o hi, is dominated almost everywhere by the function identically equal (componentwise) to compact domain. It follows from the dominated convergence theorem that ligh h gth h (1,))) -> as - 0.
max k) 5h (he,, (x:)): this function is in L L- μ)) because
We have shown that each of the following RHS terms goes to 0 as + 0:
llg oh - 9hh oh (l & lig oh sth oh ( Ilg oh gtt o (1,)
which allows to conclude that I|g h tth h (1lllo 0 and consequently
(hm znD(
[C(o (1)), =o
19

---

as + O, for any m, k. It remains to prove similar convergence results for the remaining terms in ER.
Controlling the error in " E mm [1 (z)]1 + [= We now show that
D(2)
Sn [l (z) (=)] + Sa Il Ih (z)] du via the dominated convergence theorem (DCT). First note that (m,, k) and f2 only differ by set of p-measure zero (the Voronoi boundaries S so we can equivalently prove
Jacn.k) (9m,k)
[J [h (2) - / I [h (z) c-0 ss(m.))
This allows us to avoid points æ such that or t (x) lie on Voronoi boundaries; these are problematic because h (x) lies on Voronoi boundary, then Jgmh [h (x)] undefined.
First note that as ghn ht are piecewise affine and the mollifiers are compactly supported, for any given z E (m,, k),, one can choose > 0 sufficiently small so that om [h [h, (x)] 9 [h (z)) and hence |Jo [h (1:)]]] || I (1:)
In particular, for any (m k:), let d(z, S and 62 d(h (2), Sth:: these can both be 0 because d(zz, Sth O, ddhh (x), 5th) > for E a(m, k). Then define min E2)- (x),
(21) shows why choosing 61 < d(z, Sth implies (x))(r) = h (æ);; similar arguments hold show that 62 d(h (r),, implies ( (x)) gh (h (x)). We then have gm,el (r)) " = Im (tm. (x)] as desired.
Hence for this choice of e, Jg Ittn (x)] Jomn (z)] and consequently || (=)])
g f [h (x)]]]? (Recall that J9th (x)] is well-defined for E Qmm, k).) It follows that (l.mme(at (x)]1l? - I1 [x",,))) (z)] pointwise on 9m k) and pointwise 4-ae on Ω.
|| [ Som..lhm.cc
Furthermore, another argument via Jensen's 's inequality shows that J (=),, [=)] is dominated by the funetion A that is identically equal SUPrEN((,.)) Jg (h*, (2:)]]] this function is inte- grable because Ω is compact.
The DCT then lets us conclude that || || (h (x)] | (h [=) in L and hence that
J |J Ih (+) 3o f I [h (z)]l
The same argument also allows us to conclude that
J [ (x)ll (x)liid to / |J (x)]
We have by now shown that
ER(g 1 S ER(g h m,
for some (i, k) 0 as Combining this with our earlier results, we get
En(g 1 h S ER(gh h (e) S inf Er(S) + 1 m fEC*(0)
1 + + k,)
As we can make 1 + + + m, k) arbitrarily small by first choosing m, sufficiently large and then choosing (m, k) > 0 make sb(e; m, k) sufficiently small, we can finally conclude that (R) < (L)
as desired.
This completes the proof of the theorem.
20

---

A.3 Proof of Theorem 3,2
We will show that
o² H
E c~
[1](x+)) [x)) +
Since f: 18" R is continuously differentiable, Taylor's theorem states that:
f(x =) J.[ale R(x + +),,
where |[ + c)ll2 E O(1c(13. Rearranging, taking squared Euclidean norms, and expanding the square, obtain:
| IIf( +
=11f(z +c) -f)-f) (f(x + ())
fxx), R(x 6)) + ||(( + c
$ ee) s + [1 + [15(x +) s(x)ll +1(ee))))
EO(1I+1))
EO(l]clIa)
[[[(x +c) - + = [l + - f(x) + (
Hutchinson's trace estimator implies that for any matrix A, || = E. E. In particular,
o² |]
[|]](r][[1]
c
E
[]][(x + + (()) 0(1+)
E
[]]f(x + +) [())
c01(0,2211
=
[]](( + [(a) + O
c=
which completes the proof of the result.
A.4 Optimal shrinkage via nuclear norm regularization
Let X RDN be low-rank matrix of clean data and Y X a.Z be matrix of data corrupted by iid white noise Z. In this appendix, we show that the solution to
min AEROX
LAY Y + m/|A||,,
(28)
2N
coincides with Gavish and Donoho [2017]'s optimal shrinker for the squared Frobenius norm loss
when 1) is set to the noise variance of and as the "aspect ratio" 3 = _ + 0.
A is optimal for problem (28) iff 0 @o(A"). Using well-known results from convex optimization, this condition is equivalent to:
(Y - A e all II=(A)).
(29)
N1
Furthermore, the subgradient of the nuclear norm is:
21

---

(1. (UAV] +W: U WV, max (W) - 1
(30)
where = UV is SVD A. We will show that the solution to (28) is
UTU
(31)
where Y =UEV an SVD of the noisy data matrix, and
Nu da 2 VNT
Ia
(32)
da S VNn.
The idea is to use the SVD Y UEVT and ansatz A = U to rewrite LHS of
inclusion (29) follows:
Nn (Y - AYYY =U (1 rYæ? UT.
N1
We then express the middle diagonal term as follows:
1 -(I - IT Nn
Nn (I (1-r)===
where IT is the identity matrix with all columns 2 set to zero (i.e. an orthogonal projection matrix onto the first T coordinates). This then yields
-1-11 (1--)))))) U- = +U Nn
(1- - UT. N1
where Ur UlT is U with all columns 2 T set to 0, and T is the first index such that or S VNT. As the optimal I' in (32) sets all entries corresponding to singular values aa S VNn to zero, we can in fact rewrite A" (UTT) It follows that U, (UIr) is also of the form UAV for valid SVD of A (the UIr serve both left- and right-singular vectors).
We have therefore expressed the LHS of the inclusion (29) as:
1
(Y A-YYYT = UAV +W
Nn
for UAVI = UT and W = M (1 - 11) UT, This W satisfies all of the conditions in (30). Furthermore, if we apply this optimal A" to the data matrix Y, we obtain A = -TEV. where
22 No
2 2 Nn Nn
(TE)
da
(33)
0,
we set v to be equal to the noise variance o², then this agrees exactly with the optimal shrinker for the case = R + from Gavish and Donoho [2017] under the same noise model Y X + o.Z.
B Experimental details
B.1 Validation experiments: Rudin-Osher-Fatemi (ROF) problem
Architecture, ROF experiments, we parametrize fo go ho, where go and he are both two-layer MLPs with 100 hidden units. We apply Fourier feature mapping [Tancii et al., 2020] to
22

---

the input coordinates z before passing them through hg. We use ELU activations in both neural nets and find the use of differentiable con-linarsities to be crucial for obtaining accurate solutions.
Training details. We train all neural models using the Adam optimizer [Loshchilov and Hutter, 2019] at learning rate of 10-4 for 100,000 iterations with a batch size of 10,000. In the n 2 case, we integrate over the box [-10, 10 and in the n case, we integrate over the box [-2, 2]
We employ warmup strategy for solving our problem (9). We first train our neural nets at 1) 0.05 in the = case and 77 = 0.01 in the n = 5 case for 10,000 iterations, and then increase 1 by 0.05 and 0.01, respectively, each 10,000 iterations until we reach the desired value of 1j. We then continue training until we reach 100,000 total iterations.
Each training run for (8) takes approximately 2 hours, and each training run for (9) takes approxi- mately 45 minutes on a single V100 GPU.
B.2 Denoising
Architecture. Our architecture for all denoising models is based on the UNet implemented in the Github repository for Zhang et al. [2021]. Each model is the form f = g h, where h consists of the head, downsampling blocks, and body block of the Unet, and g consists of repeated body block, the upsampling blocks, and the tail. We replace all ReLU activations with ELU but leave the remainder of the architecture unchanged.
Training details. All neural models are trained on 288,049 images from the ImageNet Large Scale Visual Recognition Challenge 2012 training set [Russakovsky et al., 2015] which we randomly crop and rescale 128 128. The code for loading and pre-processing this training data is borrowed from Rombach et al. [2021].
We train all neural models using the AdamW optimizer [Loshchilov and Hutter, 2019] for 2 epochs at a learning rate of 10-4 then for a final epoch with learning rate 10-5. Each denoising model takes approximately 5 hours train single V100 GPU.
The training objective for our denoiser is (1I) with v = a. The training objective for the supervised denoiser is the usual MSE loss:
1 fo ooe) ==12
inf fo:R +RP (D) (0.1)
where D(S2) now denotes the empirical distribution over clean training images. The training objective for the Noise2Noise denoiser is:
I 1 Il.o(( + aei) (xr + re2)
inf fo:R
E 20 D(2) (1.
-R
Note that this requires access to independent noisy copies of the same clean image during training.
Evaluation details. We evaluate each denoiser by measuring their average peak signal-to-noise ratio (PSNR) in decibels (dB) 100 randomly-drawe drawn images from the ImageNet validation set, randomly cropped to 256 x 256. We corrupt each held-out image with Gaussian noise with the same standard deviation that the respective models were trained on (o (1,2)) and denoise them using each neural model along with BM3D [Dabov et al., 2007], a popular classical baseline for unsupervised denoising.
B.3 Representation learning
We use the 3-VAE implementation from the AntixK PyTorch- VAE repo and use the default hyperpa- rameters (in particular, we set 3 = 10) but set the latent dimension to 32, as we find that this yields more meaningful latent traversals. Training this 3-VAE takes approximately 30 minutes on a single V100 GPU.
23

---

We describe the architecture and training details for our regularized and unregularized autoencoder which we use to generate the latent traversals in Figures 6 and 7. Training this autoencoder with the de
Deterministic autoencoder architecture. Our autoencoder operates on 256 256 images from the CelebA dataset. To reduce the memory and compute costs of our autoencoder, we perform a discrete cosine transform (DCT) using the torch-dct package and keep only the first DCT coefficients. We then pass these coefficients into our autoencoder.
Our deterministic autoencoder consists of encoder followed by decoder 9g- The encoder fo is parametrized as two-layer MLP with 10,000 hidden units; the latent space is 700-dimensional. The decoder 96 consists of a two-layer MLP with 10,000 hidden units and 80 80 19200 output dimensions, followed by an inverse DCT, and finally a UNet. We use the same UNet as in the denoising experiments described Appendix B.2.
Training details.
We train our autoencoders with the following objective:
} (loo)))(z)) =112 + nnRx; (fo)
inf E (.902~D(1))
(34)
where D(2)) is the CelebA training set [Liu et al., 2015].
This standard deterministic autoencoder objective, with our regularizer approximating the Jacobian nuclear norm fo [x]]|= of the encoder fo-
We train the unregularized autoencoder with r 0, and the regularized autoencoder with 1) 0.5. In both cases, we train on the CelebA training set for epochs using the A optimizer [Loshchilov and Hutter, 2019] with learning rate of 10-1, Training these autoencoders takes approximately hours each on a single V100 GPU.
Generating latent traversals. To generate the latent traversals for our autoencoder, draw point & from the training set, compute the encoder Jacobian J [o[[z]] and take its SVD to obtain [f[a UVVT. We then take the first 5 left-singular vectors (i.e. the first 5 columns of U) and compute fo(x) + (x), where uz (z:) denotes the d-th column of U. Here a denotes scalar coefficient; it ranges over 20000, 20000] for the unregularized autoencoder and 2-000, 2000] for the regularized autoencoder.
To generate the latent traversals for the 3-VAE, we encode the same training point æ and replace the d-th latent coordinate with equispaced traversal of [-3, 3] for d {1,2, 11]; these the first three meaningful latent traversals for this training point.
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Our main claim is have proven Theorem 3.1 which do in Appendix A.2. The simplicity our method is apparent - one can implement our regularizer a few lines of code and its efficiency follows directly from eliminating the need to compute SVDs or Jacobian matrices. We demonstrate our method's accuracy in Section 4.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our method's s primary limitation that the Hutchinson based estimator the squared Jacobian Frobenius norm introduced in Section 3.3 introduces error that manifests itself as somewhat diffuse boundaries in the 2D experiment in Section 4. We discuss this limitation in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
25

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We include full proofs of all theoretical results in Appendix A. We also include a proof sketch for our primary result (Theorem 3.1) in the main body of the paper; see Section 3.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Our primary contribution is our regularizer (6), which can be straightforwardly implemented from the formula in a few lines of code. We have included full experimental details in Appendix B and also attached code for our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
26

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have uploaded zip file with our submission that includes code for training models and running experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
iiyy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. wtc//ublic/guuieeee /oaeee//ooSSumissscc cimmmisssonn wwwsnsolol.. onoolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We include full experimental details in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In Table 1, we report I-sigma error bars for the PSNR attained by each denoiser across the held-out images.
Guidelines:
27

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We report runtimes for experiments and training throughout Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://eeurr http//eurrr.r/ee//eee/eee https////pppcccccccccccieeeeeeee
Answer: [Yes]
Justification:
Our work conforms with the Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdictio))
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This a primarily theoretical paper; we do not anticipate a direct path towards negative applications arising from this work.
28

---

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

---

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

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "j0mbNBazhC", "reviewer": "Reviewer_gXsR", "summary": "The paper describes an elegant and very efficient numerical scheme for minimizing a regularization term taking the form of the nuclear norm of the Jacobian $\\\\|Jf [x]\\\\|_*$ of a function $f$ at an input $x$. The numerical scheme can be applied when the function is written as a composition of two functions $f=g\\circ h$. The numerical scheme is supported by two theorems and experiments. The regularization term is supported by experiments.", "questions": "SVS and SVT are often interpreted as proximal operators. Can you please mention it in your introduction?", "limitations": "The main limitation is that there are gaps in the proof of the main theorem.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 4, "strengths": "The main body of the article is very well written and pleasant to read. The  regularization term is relevant and can be used in several contexts. The numerical scheme proposed by the authors is very effective. The experiments are convincing.", "weaknesses": "For me, the main weaknesses of the article lie in the proof of the theorems (see below).\n\nAnother point that is unclear to me is due to the discrepancy between Theorem 3.1 and its application. Specifically, as it is currently written, on the right-hand side of (4), there is an infimum on all smooth functions  $h$ ad $g$. The \"latent space\" (the output space of $h$ and the input space of $g$) is not specified, and my understanding is that the infimum is over the union of all possible \"latent spaces\". The infimum over this union can be much smaller than the infimum for a given \"latent space\"... and, in practice, only one latent space is considered. This point should be clarified. Perhaps the theorem can be adapted to allow the freedom to choose the latent space.\n\nSimilarly, in practice, neural networks (of fixed architecture) are not able to reach all the smooth functions. This could have an impact on the two infimums of (4). This limitation should at least be stated clearly. \n\nFinally, throughout the article, the reader would welcome hints on the choice of $g$ and $h$. In neural networks, we have $h_L \\\\circ...\\\\circ h_2 \\\\circ h_1$ and the reader doesn't know whether the choice of $h$ and $g$ resumes to choosing a layer separating them? or whether the method is extended to more than one composition in some other way? \n\nRobustness to adversarial attacks seems to be a natural advantage of the regularization term. The authors may wish to mention this, along with other perspectives they deem relevant, in the conclusion.\n\nIn (3) and all the developments, the authors write $l(f(x),x)$. It is much more common in machine learning to consider  $l(f(x),y)$, for an input/output pair $(x,y)$. The article would really gain to be extended to this setting.\n\nIn Theorem 3.2: I think it is a little o: $o(\\\\sigma^2)$, a quantity that goes to $0$ faster than $\\\\sigma^2$.\n\n{\\bf Comments on the appendices:}\n\nLine 455: Please define AM-GM.\n\nLine 457: Please remove 'compact'. It is the usual SVD.\n\nLine 492: A sentence like 'Consider $z\\\\in\\\\Omega$' would be welcome.\n\nIn (14), last term: I think it is $f_m(z) + R_m^z(x)$, not  $f_m(x) + R_m^z(x)$. This leads to several similar changes which (I think) do not have serious consequences. The changes are in (16), twice in line 498, once in line 509, and once below line 514.\n\nLine 503: Please replace 'These functions....' with 'The composition of these functions'.\n\nLine 509: I think the calculation would be simpler if you replace $ \\\\|Jf_m[z_i] - Jf_m[x]\\\\|_{*} $ \n\nby the absolute value of the difference between $  \\\\| Jf_m[z_i]\\\\|_{*} $ \n\nand $ \\\\| Jf_m[x]\\\\|_{*}  $.\n\nCalculus below Line 514: The layout is odd. Also, the calculation would gain clarity if you write the sum in $i$. and upper-bound each term.\n\nAbove Line 531 (and throughout the proof): Please write $\\\\epsilon \\\\rightarrow 0$ under the arrow in $\\\\rightarrow 0$.\n\nLine 533: Please define RHS\n\nLine 535: The fact that $\\\\|h^k_{m,\\\\epsilon} - h^k_m\\\\|_{L^1(\\\\Omega,\\\\mu)} \\rightarrow 0$ is not clear to me. For instance, $\\mu$ might involve a weighted Dirac mass at a point where $h^k_m$ is discontinuous. Although this paragraph is a sort of illustration, it is preferable to avoid saying something that might be false. Finally, at some other location in the proof, I think you need $\\mu$ to be absolutely continuous.\n\nLine 542: Please precise 'complement in $\\\\Omega$'.\n\nLine 545: It is $g^k_{m,\\\\epsilon}$, not $g^k_{m,e}$.\n\nEquation below Line 546: It is $B(h^k_m(x), \\\\epsilon)$ , not $B(h^k_m(x))$.\n\n**A major issue:** From lines 543 to 549, the authors try to prove an inequality which, I think, cannot hold. The problematic intermediate step is in the inequality below line 546. It is\n\n$\\\\|Jg^k_{m,\\\\epsilon} [H_m^k(x)]\\\\|_F \\\\leq \\\\sup_{y\\\\in h_m^k(\\\\Omega)  \\\\|Jg_m^k[y]\\\\|_F }.$\n\nIt cannot hold because $g^k_{m,\\\\epsilon}$ is a smooth approximation of $g^k_m$ which is typically discontinuous. It is possible to find $\\epsilon$ close to $0$ and points $y$ such that $\\\\|Jg^k_{m,\\\\epsilon} [y]\\\\|_F$ is arbitrary large. To me, there is no guarantee that $h^k_m(x)$ avoids such points. Said differently, to me, the first inequality below Line 546 does not hold when $B(h^k_m(x),\\\\epsilon) \\\\cup V_j\\\\neq \\\\emptyset$, where $V_j$ is a Voronoi cell such that $h^k_m(x)\\\\not\\\\in V_j$, which your hypotheses do not exclude. By the way, you might want to provide the formula for the mollification and detail the calculations similar to the first inequality below Line 546.\n\nAbove line 550: It is $L^1(\\\\Omega,\\\\mu)$, not $L^1(\\\\Omega)$\n\nLine 555: You state: 'As $h^k_{m,\\\\epsilon} \\\\rightarrow h^k_{m}$, $\\\\mu(\\\\Omega_1(m,k,\\\\epsilon)) \\rightarrow 0$.'. It would be useful to state in which sense $h^k_{m,\\\\epsilon} \\\\rightarrow h^k_{m}$ and to prove the details of the arguments guaranteeing that $\\\\mu(\\\\Omega_1(m,k,\\epsilon)) \\\\rightarrow 0$. As already said, I suspect you need $\\\\mu$ to be absolutely continuous for the conclusion to hold. If I am correct, this hypothesis should appear in Theorem 3.1.\n\n**A major issue:** Line 568, you state $\\\\int_\\\\Omega \\\\|Jg^k_{m,\\\\epsilon} [h^k_{m,\\\\epsilon} (x)]  \\\\|^2_F d\\\\mu \\\\rightarrow \\\\int_\\\\Omega \\\\|Jg^k_{m} [h^k_{m} (x)]  \\\\|^2_F d\\\\mu$. The sense of the term on the right of the equality is not clear to me since $g^k_{m}$ is piecewise linear, and might even be discontinuous. Even worth, I think nothing excludes $h^k_m$ to be constant on one of the Voronoi cell $V$. If this happens and if the constant turns out to be a point such that $Jg^k_{m}$ does not exist, the problem occurs on $V$ and we generally have $\\\\mu(V) \\\\neq 0$. Concerning the term on the left of equality sign, I fear you encounter problems similar to those you may be familiar with since you mention the Total Variation in your article. The term on the left takes the jumps into account and might even go to infinity since you have a square. Looking at the proof of this statement, we find a possible cause for the mistake in lines 569-570. There, you state `...for any given $x\\\\in\\\\Omega$ one can choose $\\\\epsilon>0$ sufficiently small so that $g^k_{m,\\\\epsilon}(h^k_{m,\\\\epsilon} (x)) = g^k_m(h^k_{m} (x))$...'. This is not true if $x$ is on the boundary of the Voronoi cells defining $h^k_m$ or is such that $h^k_{m} (x)$ is the boundary of two Voronoi cells defining $g^k_m$.\n\nAppendix A.3: You always use the (big) $O$ but sometimes you have to write the (little) $o$. You need to distinguish between the two notations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review of our paper. We would be pleased to make the edits you have suggested for clarity and fix the typos you have pointed out in the camera-ready version of our paper. We have updated our proof of Theorem 3.1 to address your major issues; as we cannot upload revised manuscripts during the rebuttal period, we summarize our revised arguments below.\n\n1. Our proof requires $\\mu$ to be absolutely continuous wrt the Lebesgue measure $\\lambda$ to transfer results of the form $\\lambda(E) = 0$ or $\\lambda(E_n) \\rightarrow 0$ for sets $E_n, E \\subseteq \\Omega$ to $\\mu(E) = 0, \\mu(E_n) \\rightarrow 0$, resp. Thank you for pointing this out; we will add this hypothesis to Theorem 3.1 in the camera-ready.\n\n2. For any Voronoi partition $V_i, i=1,...,N(k)$ and corresponding functions $h_m^k, g_m^k$ that we construct in our proof, the preimage of the union of Voronoi boundaries (which we call $S_m^k$) under $h_m^k$ is a set of Lebesgue measure zero. If $\\mu \\ll \\lambda$, then the preimage has $\\mu$-measure zero as well. Our reasoning is as follows:\n\nIn lines 507-514, we define $g_m^k, h_m^k$ as piecewise affine functions such that $g_m^k(x) := g_m^{z_i}(x)$ and $h_m^k(x) := h_m^{z_i}(x)$ for all $x \\in \\textrm{int}(V_i)$. The affine functions $g_m^{z_i}, h_m^{z_i}$ have the key property that $\\frac{\\eta}{2}\\left( \\|Jg_m^{z_i}[h_m^{z_i}(x)]\\|_F^2 + \\|Jh_m^{z_i}[x]\\|_F^2 \\right) = \\eta \\|J f_m[z_i]\\|\\_*.$ \n\nAt any $x$ on the interior of a Voronoi cell $V_i$, $g_m^k$ and $h_m^k$ are equal to $g_m^{z_i}, h_m^{z_i}$, resp, so by the key property above, $\\frac{\\eta}{2}\\left( \\|Jg_m^k[h_m^k(x)]\\|_F^2 + \\|Jh_m^k[x]\\|_F^2 \\right) = \\eta \\|J f_m[z_i]\\|\\_* < + \\infty$. In particular, $\\|Jg_m^k[h_m^k(x)]\\|_F^2$ and $\\|Jh_m^k[x]\\|_F^2$ must both be well-defined and finite at this $x$. This can only happen if $h_m^k(x)$ lies on the interior of a Voronoi cell, as otherwise $Jg_m^k[h_m^k(x)]$ would be undefined. Hence $h_m^k$ maps the interiors of Voronoi cells to the interiors of Voronoi cells; the contrapositive is that if $h_m^k(x)$ lies on a Voronoi boundary, then $x$ also lies on a Voronoi boundary. Consequently, the preimage of the Voronoi boundaries under $h_m^k$ is a set of Lebesgue measure zero. If $\\mu \\ll \\lambda$, this is also a set of $\\mu$-measure zero.\n\nUsing this fact, we can replace all integrals over $\\Omega$ from line 525 onwards with integrals over $\\Omega(m,k) := \\Omega \\setminus S_m^k$ without changing their value. In particular, $Jg_m^k[h_m^k(x)]$ is well-defined $\\mu$-ae, which should resolve your concerns re: line 568, for which you note *\"I think nothing excludes $h_m^k$ to be constant on one of the Voronoi cell $V$. If this happens and if the constant turns out to be a point such that $Jg_m^k$ does not exist, the problem occurs on $V$ and we generally have $\\mu(V) = 0$.\"* It should also resolve your concerns re: lines 569-570, for which you state that one cannot always find $\\epsilon>0$ so that $g_{m,\\epsilon}^k[h_{m,\\epsilon}^k(x)] = g_m^k[h_m^k(x)]$. One can in fact find such $\\epsilon$ for $\\mu$-almost all $x$, which is sufficient to apply the dominated convergence theorem.\n\n3. We use an alternative approach to show that $\\|g_{m,\\epsilon}^k \\circ h_{m,\\epsilon}^k - g_{m,\\epsilon}^k \\circ h_{m}^k\\|_{L^1(\\Omega,\\mu)} \\rightarrow 0$ that avoids the issue you highlight re: lines 543-549. We employ a different decomposition of $\\Omega \\setminus S_m^k$ into good and bad sets:\n\n- The good set $\\Omega_0(m,k,\\epsilon) \\subseteq \\Omega(m,k)$ is the set of $x \\in \\Omega(m,k)$ such that $d(x, S_m^k) > \\epsilon$. ($d(p,S)$ denotes the distance from point $p$ from set $S$.)\n- The bad set $\\Omega_1(m,k,\\epsilon)$ is $\\Omega(m,k) \\setminus \\Omega_0(m,k,\\epsilon) = \\(x \\in \\Omega(m,k) : d(x, S_m^k) \\leq \\epsilon \\)$.\n\nFor all $x \\in \\Omega_0(m,k,\\epsilon)$, $h_{m,\\epsilon}^k(x) = h_m^k(x)$ because $d(x, S_m^k) > \\epsilon$ and we employ the standard mollifier supported on $B(0,\\epsilon)$. Consequently, $g_{m,\\epsilon}^k(h_{m,\\epsilon}^k(x)) = g_{m,\\epsilon}^k(h_m^k(x))$ and therefore $\\|g_{m,\\epsilon}^k(h_{m,\\epsilon}^k(x)) - g_{m,\\epsilon}^k(h_{m}^k(x)) \\|\\_2 = 0$, so $\\int_{\\Omega_0(m,k,\\epsilon)} \\|g_{m,\\epsilon}^k(h_{m,\\epsilon}^k(x)) - g_{m,\\epsilon}^k(h_{m}^k(x)) \\|_2 d\\mu = 0$. We no longer need the reasoning in lines 543-549 to prove this integral converges to 0.\n\nWe now address $\\int_{\\Omega_1(m,k,\\epsilon)} \\|g_{m,\\epsilon}^k(h_{m,\\epsilon}^k(x)) - g_{m,\\epsilon}^k(h_{m}^k(x)) \\|\\_2 d\\mu$. We employ the same bound on the integrand as under line 552 for the new bad set $\\Omega_1(m,k,\\epsilon)$. To see that $\\mu(\\Omega_1(m,k,\\epsilon)) \\rightarrow 0$, note that $\\lambda(\\Omega_1(m,k,\\epsilon)) \\rightarrow 0$, as $\\Omega_1(m,k,\\epsilon)$ is a union of cylinders of radius $\\epsilon$ centered at the Voronoi boundaries $S_m^k$, which have Lebesgue measure zero. Under our new assumption $\\mu \\ll \\lambda$, it follows that $\\mu(\\Omega_1(m,k,\\epsilon)) \\rightarrow 0$.\n\nThese results jointly show that $\\|g_{m,\\epsilon}^k \\circ h_{m,\\epsilon}^k - g_{m,\\epsilon}^k \\circ h_{m}^k\\|_{L^1(\\Omega,\\mu)}$ while avoiding the issue you highlight re: lines 543-549.\n\nWe hope this resolves your concerns regarding our proof. If you are satisfied with our response, we respectfully ask that you raise your score for our submission. Otherwise, we would be please to continue this discussion during the author-reviewer discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZnHrXHiJa0", "reviewer": "Reviewer_82sN", "summary": "The authors present an efficient method for regularizing the Jacobian of deep networks such that it is low-rank. This work is motivated by the fact that penalizing the Jacobian by the nuclear norm regularization is in general a computationally difficult task, as it needs to (i) actually compute the Jacobian and (ii) take the SVD of a large matrix. The authors' proposed method comes from the observation that the nuclear norm of a matrix can be computed by a non-convex optimization problem, which I believe is somewhat commonly considered in the matrix factorization literature. Then, they propose their method for estimating the Jacobian Frobenius norm, which is equivalent to computing the nuclear norm (roughly speaking).", "questions": "I do not have any specific questions besides the ones in the weaknesses.", "limitations": "The limitations are listed in the weaknesses section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I think the idea is neat and well-motivated. It stems from a tactic that I think is commonly used in matrix factorization literature (see [1] for example).\n- The theoretical results seem to fit well with the main idea of the paper and overall strengthens the paper.\n- I think this method could be a good starting point for future papers that need to consider computing the Jacobian (or at least regularize it). For example, there are papers in the topic of image editing, and I think there could be applications within that field that could use this method to circumvent costly evaluation of the Jacobian and computing its SVD.\n\n[1] Lijun Ding, Dmitriy Drusvyatskiy, Maryam Fazel, Zaid Harchaoui. \"Flat minima generalize for low-rank matrix recovery\".", "weaknesses": "- I think the main weakness of the paper is its experimental section. While I think this method could be a good starting point for other future papers, the current experiments don't really sell the effectiveness of the method. It seems that one of the main benefits of this method as shown in the experimental results in Table 1 is that the proposed denoiser is almost as good as supervised denoiser, despite having no corresponding clean images for training. But isn't N2N also unsupervised in the sense that it doesn't need clean pairs of images? It doesn't seem to have impressive performance gains over N2N or BM3D.\n- Building upon the previous weakness, I wonder if there is a way of showing the effectiveness of this method through other means -- for example computational efficiency. This paper was motivated by the fact that it can circumvent costly Jacobian + SVD computations. Could the authors show with a small scale experiment showing the computational gains? I think that would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our manuscript. We are glad that you appreciate our theoretical contributions and view our method as well-motivated. In this rebuttal, we will address the questions in your review. If you are satisfied with our answers, we respectfully ask that you raise your score for our submission.\n\n*\"It seems that one of the main benefits of this method as shown in the experimental results in Table 1 is that the proposed denoiser is almost as good as supervised denoiser, despite having no corresponding clean images for training. But isn't N2N also unsupervised in the sense that it doesn't need clean pairs of images? It doesn't seem to have impressive performance gains over N2N or BM3D.\"*\n\nAs you note, our method performs nearly as well as a supervised denoiser and comparably to Noise2Noise (N2N), despite being trained exclusively on highly corrupted data without access to clean images. While N2N is also an unsupervised denoising method, training a denoiser using N2N requires *several noisy samples* of each clean image. Given a clean image $x$, these samples are of the form $x + \\epsilon_i$, where the $\\epsilon_i$ are distinct realizations of zero-mean noise. Such data is typically unavailable if one lacks access to the clean images, rendering N2N impractical for real-world applications. In contrast, our method requires only a *single* realization of each noisy image and can hence be applied to arbitrary datasets of noisy images, which can be easily obtained in the wild.\n\n*\"This paper was motivated by the fact that it can circumvent costly Jacobian + SVD computations. Could the authors show with a small scale experiment showing the computational gains? I think that would strengthen the paper.\"*\n\nIn our rebuttal PDF attached to the global response, we have included a figure comparing time per training step at batch size 1 for the denoising problem (11) using our regularizer and a naive Pytorch implementation of the Jacobian nuclear norm. We experiment with images drawn from Imagenet downsampled to sizes $S \\times S$ for $S \\in \\{8,16,32,64\\}$; our V100 GPU's memory overflows for $S \\geq 128$. Whereas time per training step with the naive nuclear norm implementation rises to nearly 129 seconds per iteration for $64 \\times 64$ images, each training step with our regularizer takes under 120 milliseconds. We additionally highlight that a key advantage of our regularizer is that it is tractable for problem sizes where simply computing the model Jacobian is infeasible. For example, in our denoising experiments, we trained our denoiser on $256 \\times 256$ RGB images. The model Jacobian in this case is a $(3 \\times 256 \\times 256) \\times (3 \\times 256 \\times 256) = 196608 \\times 196608$ matrix, which occupies over 154 GB of memory if stored in float32 format and therefore cannot be stored on most GPUs. As our regularizer does not require any Jacobian computations, it can be applied to problems such as denoising where Jacobian computations are prohibitive.\n\nWe hope this resolves your concerns. If you are satisfied with our response, we respectfully ask that you raise your score for our submission. Otherwise, we would be please to continue this discussion during the author-reviewer discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kmRwiVHsIV", "reviewer": "Reviewer_P8Q4", "summary": "The paper proposes a computationally tractable method to induce low-rankness of a neural network's Jacobian. The method essentially generalizes the max-norm from Renni and Srebro, 2005, to more general compositions of functions, as it is common in neural networks. The method is made computationally efficient by estimating the Frobenius norm of the Jacobian. Experiments for denoising and representation learning are used to validate the efficacy of the method.", "questions": "How are hyperparameters (e.g., the regularization factor eta) in the provided applications set?\n\nDenoising and representation learning can be accomplished with other means as well, and existing state-of-the-art methods are likely to outperform the proposed approach. Is there any application that would uniquely benefit from the proposed regularizer, i.e., in which no other existing method can be used?", "limitations": "I do not see a specific limitation that was not discussed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea of penalizing the rank of a function's Jacobian is practically useful in certain machine-learning applications. The proposed method enables one to do so in a computationally tractable manner that enables its use in applications where brute-force computation of an SVD and the Jacobian is infeasible. \n\nThe paper is technically solid and the method is evaluated on two realistic example tasks.", "weaknesses": "While the preliminaries in Section 3.1 are easy to follow, large parts of Section 3.2, which contains the main contribution, would be easier to follow if the authors would give a concrete example early on for the functions f and g. An illustrative example would make the idea more accessible.\n\nOne of the key arguments of the paper is that the method scales to high-dimensional problems and very large neural networks. The application examples, however, consider relatively small and simple problems with relatively simple architectures (for both the denoising of not-so-large images and autoencoder-based representation learning of images tasks). It is therefore not demonstrated that the method indeed scales to high-dimensional problems and complex neural networks.\n\nThe impact of estimating the Frobenius norm of the Jacobian (as detailed in Section 3.3) on the performance of applications was not studied. The authors claim that a single draw of eps is sufficient to evaluate (6), but it is unclear to me what the impact of this choice is. \n\nIt might be good if the authors could quantify the complexity of the proposed method, when used during training (either in run-time or in the number of operations/multiplications). This could also provide insight into the scalability to large-dimensional problems with very large neural networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our manuscript. We are glad that you appreciate our technical contributions and the practical utility of our method.\n\n*\"One of the key arguments of the paper is that the method scales to high-dimensional problems and very large neural networks. The application examples, however, consider relatively small and simple problems with relatively simple architectures (for both the denoising of not-so-large images and autoencoder-based representation learning of images tasks). It is therefore not demonstrated that the method indeed scales to high-dimensional problems and complex neural networks.\"*\n\nIn our denoising experiment, we apply our regularizer to a function of the form $f_\\theta : \\mathbb{R}^d \\rightarrow \\mathbb{R}^d$, where $d = 3 \\times 256 \\times 256$ since it operates on $256 \\times 256$ RGB images. In this case, $Jf_\\theta[x]$ is a $(3 \\times 256 \\times 256) \\times (3 \\times 256 \\times 256) = 196608 \\times 196608$ matrix, which occupies over 154 GB of memory if stored in float32 format and therefore cannot be stored on most GPUs. As our regularizer does not require any Jacobian computations, it can be successfully applied to this problem. In contrast, naive Jacobian nuclear norm regularization would be intractable due to the need to compute and take the SVD of the $196608 \\times 196608$ denoiser Jacobians.\n\n*\"It might be good if the authors could quantify the complexity of the proposed method, when used during training (either in run-time or in the number of operations/multiplications). This could also provide insight into the scalability to large-dimensional problems with very large neural networks.\"*\n\nWe provide the formula for our regularizer in Equation (6) in Section 3.3 of our manuscript. As $f(x) = g(h(x))$, one must evaluate the $h(x)$ and $g(h(x))$ terms to train $f$ regardless of the training objective. Our regularizer requires additionally computing $h(x+\\epsilon)$ and $g(h(x) + \\epsilon)$, so if one computes the regularizer with $N$ noise samples, our regularizer requires an additional $2N$ function evaluations. As we used $N=1$ noise sample to compute our regularizer in our denoising and autoencoding experiments, the marginal cost of our regularizer was 2 function evaluations per iteration. \n\nThis compares favorably to computing the Jacobian, which requires $O(d)$ function evaluations for a function $f : \\mathbb{R}^d \\rightarrow \\mathbb{R}^d$, and to the $O(d^3)$ SVD computation which is then required to compute the gradient of the Jacobian nuclear norm. Furthermore, as noted above, merely *storing* the Jacobian matrix is intractable for high-dimensional problems such as denoising. \n\n*\"How are hyperparameters (e.g., the regularization factor eta) in the provided applications set?\"*\n\nIn the denoising experiments, we set $\\eta = \\sigma^2$, where $\\sigma^2$ is the noise variance. (In our current manuscript, we have indicated that we set $\\eta = \\sigma$ in these experiments; this is a typo that we will correct in the camera-ready.) This choice of $\\eta$ is motivated by results on optimal singular value shrinkage from Gavish and Donoho [2017], whose optimal shrinker solves a special case of our proposed denoising problem (11). (See our section \"Singular value shrinkage\" from line 230 onwards for details.) We set $\\eta$ empirically in the autoencoder experiment via grid search.\n\n*\"Denoising and representation learning can be accomplished with other means as well, and existing state-of-the-art methods are likely to outperform the proposed approach. Is there any application that would uniquely benefit from the proposed regularizer, i.e., in which no other existing method can be used?\"*\n\nOur primary contribution is a tractable and well-grounded method for Jacobian nuclear norm regularization that can be applied to high-dimensional deep learning problems. There are few problems for which some given regularizer is strictly necessary and no other approach can be used, and our regularizer is no exception to this principle. Our goal in our experiments was to demonstrate the practical value of our proposed regularizer in high-dimensional learning problems by showing that it performs well in two tasks of interest to the machine learning community. The efficiency and simplicity of our method will enable the community to build on our work and discover new applications for Jacobian nuclear norm regularization.\n\nWe hope this answers your questions and would be pleased to continue this conversation during the author-reviewer discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nVF5k8y3lX", "reviewer": "Reviewer_Gitn", "summary": "The paper proposes a method to regularize the nuclear norm of the Jacobian of a function, e.g., one that represents a neural network. This method builds on prior art and includes the authors’ novel contribution as follows: The authors reference prior art for an equivalent problem formulation of nuclear norm regularization that avoids the computation of SVD. This equivalence also enables the authors’ novel result, which is that the nuclear norm of the Jacobian $Jf$ of a composite function $f=g \\circ h $ is equal to the average of the squared Frobenius norms of $Jg$ and $Jh$; this result makes the proposed method perfectly apt for neural network training. The authors then use an approximation to the Frobenius norm of the Jacobians to avoid explicitly calculating a large Jacobian matrix, which significantly reduces computational cost and storage. The method is validated with a nuclear norm-regularized problem whose closed form solution is known. Finally, the efficacy of the method is shown on two applications: unsupervised denoising and representation learning.", "questions": "Please see Weaknesses.", "limitations": "The authors briefly comment on the limitation of their method regarding the approximation of the squared Frobenius norm of the Jacobian in Conclusions. I think this is sufficient.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "-\tThe authors’ key finding on the Jacobian of a composite function is interesting, \noriginal and significant. \n-\tThe paper is clear and well-written. \n-\tThe authors have given a good summary of the background and preliminaries.\n-\tThe authors have clearly identified the parts of their method based on prior art and based on their own contribution.\n-\tThe validation and application examples that demonstrate the proposed method’s efficacy are generally convincing.\n-\tThe experiments of the paper seem reproducible.", "weaknesses": "Major comment:\n- In the representation learning application, we only see the method’s efficacy on a single image. Could there be a way to quantify the performance of the method over a whole test dataset? \n\nMinor comments: \n- I found the following two references that also compute nuclear norm without the SVD. Could the authors either mention these references in their manuscript or clarify why these aren’t relevant?\n[1] https://icml.cc/Conferences/2010/papers/196.pdf\n[2] https://www.ijcai.org/proceedings/2017/0436.pdf\n\n- Figure 1 has only the color legend. Could the authors confirm (and explicitly state on their manuscript) that the x- and y-axes correspond to each coordinate of the input x?\n- In the caption of Figure 3, the authors say that “As predicted by Theorem 3.1, both problems converge to the same objective value.“ Could they use a less strong claim here? Possibly “nearly identical” as they said in the main text; otherwise, the gap in 3(c) is confusing.\n- Could the authors reformat the subsection titles in Section 5 so that it is clear in a glance that “Unsupervised denoising” and “Representation learning” are the two application examples, and “Singular value shrinkage” and “Experiments” are under “Unsupervised denoising”?\n- The PSNR values in Table 1 are based on averaging over only 100 images. Is there a reason why more images were not used? Could the authors repeat the experiment by averaging over more images?\n- It is slightly confusing that the order of the methods in the Table 1 and Figure 4 do not match each other. Could the authors follow the same order?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our manuscript. We are glad you appreciate the originality and significance of our method for Jacobian nuclear norm regularization.\n\n*\"In the representation learning application, we only see the method’s efficacy on a single image. Could there be a way to quantify the performance of the method over a whole test dataset?\"*\n\nWe depict latent traversals in our autoencoder's latent space for a single non-cherry-picked image due to space constraints in the manuscript. We have included a few more examples in our rebuttal PDF attached to the global response, and we would be happy to include these in an appendix in the camera-ready. Whether our autoencoder recovers semantically meaningful directions of variation in latent space is ultimately a subjective judgment, and we do not believe that readers would gain additional insight regarding our method's performance on this task by including quantitative metrics.\n\n*\"I found the following two references that also compute nuclear norm without the SVD. Could the authors either mention these references in their manuscript or clarify why these aren’t relevant?\"*\n\nWe would be pleased to add these references to the related work section. However, note that both of these papers propose methods for nuclear norm regularization in matrix learning problems, where one seeks to learn a single matrix $A \\in \\mathbb{R}^{m\\times n}$. In contrast, our work generalizes the efficient method of Rennie and Srebro [2005] to non-linear learning problems, where the appropriate analog to penalizing the nuclear norm of a matrix is penalizing the nuclear norm of the Jacobian of the function being learned.\n\n*\"Figure 1 has only the color legend. Could the authors confirm (and explicitly state on their manuscript) that the x- and y-axes correspond to each coordinate of the input x?\"*\n\nThat is correct. We will clarify this in the camera-ready.\n\n*\"The PSNR values in Table 1 are based on averaging over only 100 images. Is there a reason why more images were not used? Could the authors repeat the experiment by averaging over more images?\"*\n\nThe standard test sets in the denoising literature are quite small; for example, our other test set \"CBSD68\" contains 68 images. We built our Imagenet test set using 100 random images to approximately match test set sizes that are common in the denoising literature. We do not expect that the results of our comparison would be significantly different if we used a larger test set.\n\nWe would be happy to incorporate the rest of your suggested changes to our paper's formatting in the camera-ready.\n\nWe hope this answers your questions and would be pleased to continue this conversation in the author-reviewer discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you for your thoughtful reviews of our submission. We have attached a PDF containing four figures:

1. For Reviewer 82sN, we have included a figure (top-left) comparing time per training step at batch size 1 for the denoising problem (11) using our regularizer and a naive Pytorch implementation of the Jacobian nuclear norm. We experiment with images drawn from Imagenet downsampled to sizes $S \times S$ for $S \in \{8,16,32,64\}$; our V100 GPU's memory overflows for $S \geq 128$. Whereas time per training step with the naive nuclear norm implementation rises to nearly 129 seconds per iteration for $64 \times 64$ images, each training step with our regularizer takes under 120 milliseconds.

2. For Reviewer Gitn, we have included three more sets of latent traversals in our autoencoder's latent space (top-right, bottom-left, and bottom-right).

Meta-review: This paper addresses the computational challenges in regularizing deep learning with the nuclear norm of the Jacobian matrix.  The key discovery is that that for functions parametrized as compositions $f = g \circ h$, the regularizer is equivalent to the average squared Frobenius norms of $Jg$ and $Jh$.  The latter two are then efficiently computed via a denoising-style approximation.  Empirical superiority is also shown in denoising and representation learning. 

The paper addresses a common challenge with a neat and effective solution.  The new proof in the rebuttal to Reviewer gXsR appears correct in my opinion, and I recommend the authors to rewrite the paper to reflect the changes.  Although the experiments can still be much improved as the reviewers suggested, it appears agreed that the merits of the paper are sufficient to warrant publication at the conference.
Decision: Accept (poster)