Neural networks are dense among Lipschitz functions with fixed Lipschitz constant.
problem Characterizing neural network approximations to Lipschitz functions.
method Analyzing L-Lipschitz neural networks and their density in L-Lipschitz functions. result One layer neural networks are dense in the set of all L-Lipschitz functions. Training neural networks under a strict Lipschitz constraint is useful for provable adversarial robustness, generalization bounds, interpretable gradients, and Wasserstein distance estimation. By the composition property of Lipschitz functions, it suffices to ensure that each individual affine transformation or nonline…
The paper proves inequalities linking geometric norms and Thurston norms in hyperbolic 3-manifolds.
problem Inequalities linking geometric norms and Thurston norms in hyperbolic 3-manifolds.
method Analyzes geometric L2-norms, Thurston norms, and Lipschitz maps to prove inequalities. result Proves an inequality between geometric L2-norm and Thurston norm, qualitatively sharp. New method for efficient proximal mapping of 1-path-norm in shallow networks.
problem Efficiently handling the 1-path-norm of shallow neural networks.
method Closed-form proximal operator for efficient computation and upper bound on Lipschitz constant.
result Proximal mapping allows robust training against adversarial perturbations.
We model how Lipschitz continuity changes during neural network training.
problem Understanding how Lipschitz continuity evolves during training.
method We use a system of stochastic differential equations to capture the dynamics of Lipschitz continuity under SGD.
result We identify three factors driving the evolution of Lipschitz continuity: gradient flow projection, gradient noise, and Hessian projection.
New method for differentially private optimization with general Lipschitz conditions.
problem Differentially private optimization under general Lipschitz conditions.
method Generalized Lipschitz condition for per-sample gradients, tuning clip norm based on minimum per-sample Lipschitz constant.
result Efficacy of the recommended clip norm tuning method verified on 8 datasets.
The paper examines convergence of distances in Lipschitz structures on manifolds.
problem Convergence of distances in Lipschitz vector fields and norms on manifolds.
method Analysis of convergence of distances associated to converging structures of Lipschitz vector fields and norms.
result Under mild controllability assumption, distances converge locally uniformly to the limit Carnot-Carathéodory distance.
CNN layers with large norms are still robust to adversarial attacks.
problem Understanding the relationship between layer norms and adversarial robustness in CNNs.
method Theoretical analysis of ℓ1 and ℓ∞ norms, norm decay method, adversarial training frameworks. result Adversarially robust CNNs can have comparable or larger layer norms than non-adversarially robust ones.
Lipschitz constraints under L2 norm on deep neural networks are useful for provable adversarial robustness bounds, stable training, and Wasserstein distance estimation. While heuristic approaches such as the gradient penalty have seen much practical success, it is challenging to achieve similar practical performance wh…
This paper proposes a mechanism to produce equivalent Lipschitz surrogates for zero-norm and rank optimization problems by means of the global exact penalty for their equivalent mathematical programs with an equilibrium constraint (MPECs). Specifically, we reformulate these combinatorial problems as equivalent MPECs by…
Generative adversarial networks (GANs) are one of the most popular approaches when it comes to training generative models, among which variants of Wasserstein GANs are considered superior to the standard GAN formulation in terms of learning stability and sample quality. However, Wasserstein GANs require the critic to b…
We study the asymmetry of the Lipschitz metric d on Outer space. We introduce an (asymmetric) Finsler norm that induces d. There is an Out(F_n)-invariant potential Ψon Outer space such that when the Lipschitz norm is corrected by the derivative of Ψ, the resulting norm is quasisymmetric. As an application, we give new …
RVFL networks can efficiently approximate Lipschitz functions in L∞ norm.
problem Efficiently approximating Lipschitz continuous functions in L∞ norm.
method Random Vector Functional Link (RVFL) network with ReLU activation functions, proving approximation in L∞ norm.
result An RVFL with ReLU activation functions can approximate Lipschitz continuous functions in L∞ norm.
We show that the log-likelihood of several probabilistic graphical models is Lipschitz continuous with respect to the lp-norm of the parameters. We discuss several implications of Lipschitz parametrization. We present an upper bound of the Kullback-Leibler divergence that allows understanding methods that penalize the …
We prove that the Hilbert Geometry of a convex set is bi-lipschitz equivalent to a normed vector space if and only if the convex is a polytope.
We investigate the effect of explicitly enforcing the Lipschitz continuity of neural networks with respect to their inputs. To this end, we provide a simple technique for computing an upper bound to the Lipschitz constant---for multiple p-norms---of a feed forward neural network composed of commonly used layer types.…
Revisits shallow neural networks using Lipschitz norms and measures.
problem Existence and compactness of minimizers in neural network formulations.
method Mean field parametrization, signed measures, duality pairings, Kantorovich-Rubinstein norms.
result Compactness results and uniform large data limits for empirical risk minimization.
In binary classification and regression problems, it is well understood that Lipschitz continuity and smoothness of the loss function play key roles in governing generalization error bounds for empirical risk minimization algorithms. In this paper, we show how these two properties affect generalization error bounds in …
Proves continuum limits of Lipschitz learning using Γ-convergence.
problem Semi-supervised learning with graph-based methods and continuum limits of p-Laplacian learning. method Proves continuum limits of Lipschitz learning using Γ-convergence.
result Proves Γ-convergence in the L∞-topology to the supremum norm of the gradient. We augment adversarial training (AT) with worst case adversarial training (WCAT) which improves adversarial robustness by 11% over the current state-of-the-art result in the ℓ2 norm on CIFAR-10. We obtain verifiable average case and worst case robustness guarantees, based on the expected and maximum values of the…
Bi-Lipschitz proof for 2-varifolds near critical Allard condition.
problem Proving bi-Lipschitz homeomorphism for 2-varifolds near critical Allard condition.
method Analyzing 2-varifolds with critical Allard condition and small mean curvature.
result 2-varifold is bi-Lipschitz homeomorphic to a flat disk.
We compute the local Lipschitz constant of ReLU networks precisely.
problem Estimating the local Lipschitz constant of ReLU networks is hard.
method We use a novel approach involving the generalized Jacobian and backpropagation.
result We provide an algorithm to compute the exact Lipschitz constant of ReLU networks.
Scalable method bounds Lipschitz constant of generative models.
problem Bounding the Lipschitz constant of generative models.
method Layerwise convex approximations using zonotopes.
result Efficient and tight bounds on generative models.
The paper examines partial regularity of Lipschitz solutions to minimal surface system.
problem Understanding the regularity of solutions to the minimal surface system.
method Investigation of stationary, integral weak, and viscosity solutions; interior gradient estimate using maximum principle.
result Partial regularity results for Lipschitz solutions, including interior gradient estimate.
New bounds for neural networks ensure robustness and accuracy.
problem Ensuring robustness of neural networks by computing Lipschitz constants.
method Analyzed and proposed new bounds for l1 and l∞ norms, using explicit and implicit methods for convnets. result One of the new bounds is optimal and more accurate than existing ones.
We present a lower bound for a fragmentation norm and construct a bi-Lipschitz embedding I:Rn→Ham(M) with respect to the fragmentation norm on the group Ham(M) of Hamiltonian diffeomorphisms of a symplectic manifold (M,ω). As an application, we provide an answer to Brandenbursk…
PSiLON Net uses L1 weight normalization and 1-path-norm regularization for efficient learning and sparsity.
problem Efficient learning and sparsity in neural networks with limited data.
method PSiLON Net employs L1 weight normalization and 1-path-norm regularization to simplify the 1-path-norm and achieve efficient learning and near-sparse parameters. result PSiLON Net achieves reliable optimization and strong performance in the small data regime.
Develops risk measures on Lipschitz spaces for financial positions.
problem Lack of standard cash-additive methods in Lipschitz spaces.
method Proposes Lipschitz-free space, uses additivity along benchmark-deviation instruments.
result Derives dual representations for convex and coherent risk measures.
We consider the mean curvature flow of entire Lagrangian graphs with Lipschitz continuous initial data. Assuming only a certain bound on the Lipschitz norm of an initial entire Lagrangian graph in R2n, we show that the parabolic equation \eqref{PMA} for the Lagrangian potential has a longtime solution which is sm…
Two-layer neural networks need more neurons to be robust.
problem Understanding the robustness of two-layer neural networks and the role of overparametrization.
method Investigation of the tradeoffs between network size and robustness, using Lipschitz constant as a measure.
result A conjecture that robustness requires overparametrization, with precise bounds for different cases.
Study improves Poincaré-Sobolev inequalities for differential forms.
problem Improving Sobolev space embeddings for differential forms.
method Utilizes Lq,p-cohomology and bi-Lipschitz images to estimate embedding norms. result Estimates for embedding norms in Euclidean balls and their images.
New framework for private convex optimization in arbitrary norms.
problem Private optimization of convex functions in non-Euclidean settings.
method Regularized exponential mechanism based on localization tools from convex geometry.
result First optimal privacy-utility tradeoffs for ℓp norms and Schatten-p norms. The heavy-tailed distributions of corrupted outliers and singular values of all channels in low-level vision have proven effective priors for many applications such as background modeling, photometric stereo and image alignment. And they can be well modeled by a hyper-Laplacian. However, the use of such distributions g…
The paper explores how close two Lipschitz functions can be without their difference exceeding a certain bound.
problem Understanding the closeness of two Lipschitz functions and their difference.
method Investigates the relationship between two Lip(γ) functions being close throughout a subset of their domain and the bound on the difference's Lipschitz norm. result The Lipschitz norm of the difference between two functions is bounded by a small value when the distance to a subset is small.
The mean curvature flow is the gradient flow of volume functionals on the space of submanifolds. We prove a fundamental regularity result of the mean curvature flow in this paper: a Lipschitz submanifold with small local Lipschitz norm becomes smooth instantly along the mean curvature flow. This generalizes the regular…
The purpose of the paper is to characterize the dimension of sublinear Higson corona νL(X) of X in terms of Lipschitz extensions of functions: Theorem: Suppose (X,d) is a proper metric space. The dimension of the sublinear Higson corona νL(X) of X is the smallest integer m≥0 with the following property…
Existing Rademacher complexity bounds for neural networks rely only on norm control of the weight matrices and depend exponentially on depth via a product of the matrix norms. Lower bounds show that this exponential dependence on depth is unavoidable when no additional properties of the training data are considered. We…
The paper shows how Hamiltonian diffeomorphisms and homeomorphisms can be broken down into smaller, manageable pieces.
problem Fragmenting Hamiltonian diffeomorphisms and homeomorphisms on surfaces.
method Develops a C0-fragmentation property for Hamiltonian diffeomorphisms and homeomorphisms on surfaces, proving it with a Lipschitz estimate. result Hamiltonian diffeomorphisms and homeomorphisms can be decomposed into smaller, compactly supported pieces with a Lipschitz estimate on the C0-norm. New approach to certifiably robust neural networks using Boolean function perspective.
problem Lack of principled understanding and certified robustness for ℓ∞ perturbations. method New perspective on Boolean functions, deriving impossibility results, and developing a unified Lipschitz network.
result Unified Lipschitz network that bypasses expressive power limitations and achieves better certified robustness.
Let A be an expanding d×d matrix with integer entries and D⊂Zd be a finite digit set. Then the pair (A,D) defines a unique integral self-affine set K=A−1(K+D). In this paper, by replacing the Euclidean norm with a pseudo-norm w in terms of A, we…
We show the existence of a global unique and analytic solution for the mean curvature flow, the surface diffusion flow and the Willmore flow of entire graphs for Lipschitz initial data with small Lipschitz norm. We also show the existence of a global unique and analytic solution to the Ricci-DeTurck flow on euclidean s…
Characterizes isometries between non-reversible Finsler manifolds.
problem Understanding isometries in non-reversible Finsler manifolds.
method Generalization of Myers-Nakai Theorem for Riemannian manifolds, modification of function spaces to accommodate asymmetric structure.
result Functional characterization of isometries between non-reversible Finsler manifolds.
New algorithms reduce regret for convex bandits with small comparator norms.
problem Optimizing in bandit convex optimization with varying comparator norms.
method Developed algorithms using techniques from full-information setting and new gradient estimators.
result Regret bounds are small when comparator norm is small.
In this work we study input gradient regularization of deep neural networks, and demonstrate that such regularization leads to generalization proofs and improved adversarial robustness. The proof of generalization does not overcome the curse of dimensionality, but it is independent of the number of layers in the networ…
New bound relaxes uniform gradient norm assumptions for PAC-Bayesian bounds.
problem Generalization bounds with strict assumptions like uniformly bounded loss.
method Relax uniform bounds assumptions to on-average bounded loss and gradient norm.
result Proposes a new generalization bound with a surrogate of model complexity.
New framework improves robustness of implicit neural networks.
problem Ill-posedness and convergence instability in implicit neural networks.
method NEMON framework based on contraction theory for ℓ∞ norm, including well-posedness condition, average iteration, and input-output Lipschitz constant regularization. result Improved accuracy and robustness of implicit models with smaller input-output Lipschitz bounds.
New neural network design resists small ℓ∞-norm adversarial perturbations.
problem Vulnerability of neural networks to small ℓ∞-norm adversarial perturbations. method Designing ℓ∞-dist neurons and constructing ℓ∞-dist nets, proving their 1-Lipschitz property and expressive power. result Certified robustness of ℓ∞-dist nets with state-of-the-art performance on various datasets. Efficient local Lipschitz bounds improve neural network robustness.
problem Certifying robustness of neural networks is challenging and often leads to over-regularization.
method Proposes an efficient trainable local Lipschitz upper bound by considering activation functions and weight matrices.
result Consistently outperforms state-of-the-art methods in clean and certified accuracy on various datasets.