Generative model controls heterophily in graph signals.
problem Controlling heterophily in graph signals for better model effectiveness.
method Combines graphon-based generator with spectral filtering of Gaussian node features.
result Establishes theoretical guarantees for heterophily control and convergence.
Stable algebraic filters improve neural network performance.
problem Improving neural network stability to deformations.
method Analyzed stability of algebraic filters and neural networks under deformations of the homomorphism.
result Stable algebraic filters have frequency responses whose derivative is inversely proportional to frequency.
Gradient filters track moving parameters under noisy data and misspecification.
problem Tracking multidimensional time-varying parameters under noisy observations and model misspecification.
method Gradient-based filters update parameters using the gradient of a postulated objective function, evaluated at either the predicted or updated parameters.
result Novel sufficient conditions for exponential stability of the filtered parameter path, and finite-sample and asymptotic mean squared error bounds.
A bandit problem with filtered Poisson process data.
problem Maximizing points revealed from a continuum action space.
method Upper confidence bound algorithm with data-adaptive discretisation.
result Regret bound of O(T^(2/3)) under Lipschitz assumption.
GNNs maintain stability under minor graph topology changes.
problem Stability of GNNs to small graph topology changes.
method Proved stability of GNNs with integral Lipschitz filters.
result GNNs output change is bounded by relative graph topology change.
A major issue in harmonic analysis is to capture the phase dependence of frequency representations, which carries important signal properties. It seems that convolutional neural networks have found a way. Over time-series and images, convolutional networks often learn a first layer of filters which are well localized i…
Deep convolutional neural networks have led to breakthrough results in numerous practical machine learning tasks such as classification of images in the ImageNet data set, control-policy-learning to play Atari games or the board game Go, and image captioning. Many of these applications first perform feature extraction …
Transformers can solve complex filtering problems for non-Gaussian signals.
problem Non-linear and non-Markovian filtering problems for conditionally Gaussian signals.
method Continuous-time transformer models called filterformers.
result Filterformers can approximate the conditional law of non-Markovian and conditionally Gaussian signal processes.
This paper converts ADMM to proximal gradient for efficient sparse estimation.
problem Sparse estimation problems like fused lasso and convex clustering.
method General method converting ADMM to proximal gradient, assuming Lipschitz continuity of derivative.
result Significant improvement in efficiency for sparse estimation problems.
Paper introduces a new metric to select optimal Graph Shift Operator for GNNs.
problem Empirical selection of Graph Shift Operator remains challenging.
method Introduces a novel alignment gain metric connecting geometric distortion to generalization bounds via spectral proxy.
result Provides a principled, computation-efficient criterion to rank and select optimal GSO.
New algorithm improves sampling from constrained spaces.
problem Sampling from constrained spaces efficiently.
method Metropolis-adjusted Mirror Langevin algorithm.
result Unbiased sampling with improved mixing time.
New algorithm reduces sample complexity for learning CNNs.
problem Learning one-hidden-layer CNNs with various activation functions.
method Approximate gradient descent algorithm for training CNNs.
result Sample complexity matches information-theoretic lower bound for linear activation functions.
CGNNs use wavelets for continuous function generation in infinite-dimensional spaces.
problem Generating continuous functions in infinite-dimensional spaces for applications like inverse problems.
method Inspired by DCGAN, CGNNs use wavelet multiresolution analysis with convolutional and nonlinear layers.
result CGNNs can be injective under certain conditions on filters and nonlinearity, leading to Lipschitz stability estimates.
Graph neural networks (GNNs) have emerged as a powerful tool for nonlinear processing of graph signals, exhibiting success in recommender systems, power outage prediction, and motion planning, among others. GNNs consists of a cascade of layers, each of which applies a graph convolution, followed by a pointwise nonlinea…
Algorithm efficiently learns deep ReLU networks with polynomial runtime in depth and parameters.
problem Learning deep ReLU networks with polynomial runtime.
method Algorithm using filtered PCA and lattice polynomial analysis.
result First nontrivial results for networks of depth more than two with polynomial runtime.
LiuBei is a resilient ML algorithm that tolerates Byzantine workers and servers without trusting any component.
problem Byzantine failures in distributed ML solutions.
method Byzantine-resilient ML algorithm that aggregates gradients and replicates parameter servers, using a filtering mechanism and scatter/gather protocol.
result LiuBei achieves Byzantine resilience to both servers and workers and guarantees convergence, with an accuracy loss of around 5% and a 24% convergence overhead.
First steps towards a mathematical theory of deep convolutional neural networks for feature extraction were made---for the continuous-time case---in Mallat, 2012, and Wiatowski and Bölcskei, 2015. This paper considers the discrete case, introduces new convolutional neural network architectures, and proposes a mathemati…
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. Constructs a map with prescribed local Lipschitz constants on a subset of a manifold.
problem Creating a Lipschitz map with specific local Lipschitz constants on a subset of a manifold.
method Constructs a Lipschitz map that matches a given map on a subset and has a local Lipschitz constant defined by a continuous function.
result A Lipschitz map can be constructed with a local Lipschitz constant prescribed by a continuous function.
Maps between certain Lipschitz manifolds are isometries if they preserve volume.
problem Volume preservation and isometry conditions for Lipschitz manifolds.
method Volume-preserving 1-Lipschitz maps from integral currents onto infinitesimally Euclidean Lipschitz manifolds.
result Volume-preserving maps are isometries under given conditions.
Abstract: Lipschitz homeomorphisms are deformed using Perelman's methods.
problem Deformation of Lipschitz homeomorphisms
method Lipschitz analogues of Siebenmann's and Perelman's homeomorphism theory
result Lipschitz stability theorem and gluing theorem
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.
Study shows infinite distinct outer metric Lipschitz classes for knots in S3.
problem Lipschitz classification of surface singularities in R4. method Outer metric Lipschitz equivalence and topological equivalence of knots.
result Infinitely many distinct outer metric Lipschitz classes for knots in S3. The study examines the limitations of bi-Lipschitz Normalizing Flows in approximating certain distributions.
problem The expressivity of bi-Lipschitz Normalizing Flows in approximating specific target distributions.
method Characterization of expressivity through lower bounds on Total Variation distance and discussion of potential remedies.
result Several target distributions are difficult to approximate using bi-Lipschitz Normalizing Flows, and lower bounds on their approximation are provided.
Novikov conjecture reduced to Lipschitz cohomology of groups.
problem Novikov higher signature conjecture for groups.
method Introducing Lipschitz cohomology classes and reducing the conjecture.
result Reduced Novikov conjecture to Lipschitz cohomology.
We examine the impact of learning Lipschitz continuous models in the context of model-based reinforcement learning. We provide a novel bound on multi-step prediction error of Lipschitz models where we quantify the error using the Wasserstein metric. We go on to prove an error bound for the value-function estimate arisi…
New MIP formulations for neural network Lipschitz constant estimation.
problem Ensuring robustness of neural networks by calculating their Lipschitz constant.
method Reformulating the neural network Lipschitz estimation problem as a Quadratically Constrained MIP (MIQCQP) problem.
result Solutions of the MIQCQP formulations provide bounds on the Lipschitz constant, with conditions for exactness.
Lipschitz-volume rigidity holds for smooth manifolds but fails for singular spaces.
problem Lipschitz-volume rigidity on singular spaces with lower curvature bounds.
method Survey of Lipschitz-volume rigidity theorems on singular spaces.
result Lipschitz-volume rigidity doesn't hold for all singular spaces.
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 studies properties of intrinsically Lipschitz constants in metric spaces.
problem Investigating properties of intrinsically Lipschitz constants.
method Introduced Leibniz and product formulas for intrinsic slope.
result Formulated Leibniz and product formulas for intrinsic slope.
New scalable Lipschitz bounds improve neural network robustness analysis.
problem Computing tight Lipschitz bounds for deep neural networks is challenging and computationally expensive.
method Derived new closed-form Lipschitz bounds using more general feasible points of LipSDP, avoiding SDP solvers.
result Improved scalability and precision of Lipschitz estimation for large neural networks.
The paper studies Lipschitz bounds for integral kernels under differentiability assumptions.
problem Understanding the Lipschitz continuity of feature maps associated with integral kernels.
method Analyzes differentiability assumptions to derive explicit formulas for Lipschitz constants and conditions for non-Lipschitz continuity.
result Explicit formulas and conditions for Lipschitz continuity of feature maps associated with various kernels.
We characterize locally Lipschitz mappings and existence of Lipschitz extensions through a first order nonlinear system of PDEs. We extend this study to graded group-valued Lipschitz mappings defined on compact Riemannian manifolds. Through a simple application, we emphasize the connection between these PDEs and the Ru…
Geodesically complete spaces with curvature bounded above have maps with finite energy that are Lipschitz.
problem Analyzing the properties of geodesically complete spaces with curvature constraints.
method Geometric perturbations of geodesics to curves with zero length on singular sets.
result Every Sobolev map in W1,∞ space has a Lipschitz representative with the same Lipschitz constant as its infinity energy. We construct a smooth compact n-dimensional manifold Y with one point singularity such that all its Lipschitz homotopy groups are trivial, but Lipschitz mappings Lip(S^n,Y) are not dense in the Sobolev space W^{1,n}(S^n,Y). On the other hand we show that if a metric space Y is Lipschitz (n-1)-connected, then Lipschitz …
Paper investigates Lipschitz constants of self-attention modules in neural networks.
problem Lipschitz constants of self-attention modules in neural networks.
method Proved standard dot-product self-attention is not Lipschitz for unbounded input domain. Proposed L2 self-attention that is Lipschitz. Derived upper bound on L2 self-attention's Lipschitz constant.
result Proved standard self-attention is not Lipschitz for unbounded input domain and proposed an alternative L2 self-attention that is Lipschitz.
Proves rigidity for maps between manifolds using degree theory and current developments.
problem Lipschitz-volume rigidity for maps between metric manifolds and Riemannian manifolds.
method Degree theory and recent developments of Lipschitz-volume rigidity for integral currents.
result Proves a Lipschitz-volume rigidity result for 1-Lipschitz maps.
The thesis defines and proves invariants for manifolds of bounded geometry.
problem Lipschitz-homotopy invariants for manifolds of bounded geometry.
method Definition of a controvariant functor and invariance of the Roe index and ρ-class.
result Lipschitz-homotopy invariants are defined and proven for manifolds of bounded geometry.
Defines a new modulus for Lipschitz surfaces and proves a homological duality theorem.
problem Lipschitz homology classes and their moduli.
method Defining a new modulus dModp and proving a homological duality theorem. result Every relative Lipschitz k-homology class has a unique dual class satisfying a specific modulus product equality. Bi-Lipschitz mappings can embed certain algebraic sets into high-dimensional spaces.
problem Embedding algebraic sets into high-dimensional spaces while preserving distances.
method Developed a bi-Lipschitz embedding for semialgebraic sets into Rn. result Embedding is possible for n≥2k+1 and unique for n≥2k+2. Investigates Lipschitz continuity in neural networks across various settings.
problem Understanding the Lipschitz behavior of neural networks.
method Empirical investigation of Lipschitz bounds in different neural network architectures and datasets.
result Remarkable fidelity of the lower Lipschitz bound and a Double Descent trend in both upper and lower bounds.
New Transformers maintain Lipschitz continuity for robustness.
problem Ensuring robustness in Transformers for safety-sensitive applications.
method Introducing gradient-descent-type in-context Transformers with explicit Euler steps of negative gradient flows.
result Universal approximation theorem for Lipschitz continuous Transformers.
The paper extends a measure preserving property to bi-Lipschitz maps between Moran sets.
problem Extending the measure preserving property to Moran sets.
method Analyzing bi-Lipschitz maps between Moran sets.
result Bi-Lipschitz maps between Moran sets preserve measure locally.
Study maps in semidirect products of groups, proving Lipschitz properties without intrinsic dilations.
problem Proving Lipschitz conditions in semidirect products of groups without intrinsic dilations.
method Using equivalent conditions and properties of projection maps in metric spaces.
result Proves the same Lipschitz results as in Carnot groups, without intrinsic dilations.
New metric measure space theory for Lipschitz constants.
problem Defining and characterizing Cheeger energy in metric measure spaces.
method Adapting Cheeger theory to intrinsically Lipschitz sections.
result Characterization of intrinsic Cheeger energy in terms of relaxed slope.
Extends Lipschitz functions while preserving local constants.
problem Extending Lipschitz functions on metric spaces while maintaining local constants.
method Extends Lipschitz functions on metric spaces while locally preserving the asymptotic Lipschitz constant.
result Sobolev spaces on metric measure spaces are invariant under isomorphism of mm-structures.
Guarantees uniform convergence for square-root Lipschitz losses.
problem Uniform convergence guarantees for square-root Lipschitz losses.
method Using Rademacher complexity and square root of scalar loss function Lipschitz constant.
result Generalizes previous results and handles non-smooth loss functions.
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.