Related papers: Stochastic optimization on matrices and a graphon McKean-Vlasov limit

Stochastic optimization on matrices and a graphon McKean-Vlasov limit

URL: http://arxiv.org/abs/2210.00422v3
Date: Mon, 27 May 2024 23:34:26 GMT
Title: Stochastic optimization on matrices and a graphon McKean-Vlasov limit
Authors: Zaid Harchaoui, Sewoong Oh, Soumik Pal, Raghav Somani, Raghavendra Tripathi,
Abstract summary: We consider gradient descents on the space of large symmetric matrices of suitable functions that are invariant under permuting the rows and columns using the same permutation. We establish deterministic limits of these random curves as the dimensions of the matrices go to infinity while the entries remain bounded.
Score: 26.906770707395832
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider stochastic gradient descents on the space of large symmetric matrices of suitable functions that are invariant under permuting the rows and columns using the same permutation. We establish deterministic limits of these random curves as the dimensions of the matrices go to infinity while the entries remain bounded. Under a ``small noise'' assumption the limit is shown to be the gradient flow of functions on graphons whose existence was established in~\cite{oh2021gradient}. We also consider limits of stochastic gradient descents with added properly scaled reflected Brownian noise. The limiting curve of graphons is characterized by a family of stochastic differential equations with reflections and can be thought of as an extension of the classical McKean-Vlasov limit for interacting diffusions to the graphon setting. The proofs introduce a family of infinite-dimensional exchangeable arrays of reflected diffusions and a novel notion of propagation of chaos for large matrices of diffusions converging to such arrays in a suitable sense.

Related papers

Asymmetric matrix sensing by gradient descent with small random initialization [0.8611782340880084]
We study the problem of reconstructing a low-rank matrix from a few linear measurements. Our key contribution is introducing a continuous gradient flow equation that we call the $texted gradient flow$.
arXiv Detail & Related papers (2023-09-04T20:23:35Z)
Path convergence of Markov chains on large graphs [3.693375843298262]
We show that as the size of a graph goes to infinity, the random trajectories of the processes converge to deterministic curves on the space of measure-valued graphons. A novel feature of this approach is that it provides a precise exponential convergence rate for the Metropolis chain in a certain limiting regime.
arXiv Detail & Related papers (2023-08-18T00:13:59Z)
Hessian Based Smoothing Splines for Manifold Learning [0.228438857884398]
We propose a multidimensional smoothing spline algorithm in the context of manifold learning. We generalize the bending energy penalty of thin-plate splines to a quadratic form on the Sobolev space of a flat manifold. The existence and uniqueness of the solution is shown by applying the theory of reproducing Hilbert spaces.
arXiv Detail & Related papers (2023-02-10T02:49:05Z)
Dynamical chaos in nonlinear Schr\"odinger models with subquadratic power nonlinearity [137.6408511310322]
We deal with a class of nonlinear Schr"odinger lattices with random potential and subquadratic power nonlinearity. We show that the spreading process is subdiffusive and has complex microscopic organization. The limit of quadratic power nonlinearity is also discussed and shown to result in a delocalization border.
arXiv Detail & Related papers (2023-01-20T16:45:36Z)
Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
arXiv Detail & Related papers (2022-05-21T01:47:17Z)
Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
arXiv Detail & Related papers (2021-07-13T12:31:06Z)
Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
arXiv Detail & Related papers (2021-05-03T16:36:27Z)
Scaling limits of lattice quantum fields by wavelets [62.997667081978825]
The renormalization group is considered as an inductive system of scaling maps between lattice field algebras. We show that the inductive limit of free lattice ground states exists and the limit state extends to the familiar massive continuum free field.
arXiv Detail & Related papers (2020-10-21T16:30:06Z)
Boundary effects on symmetry resolved entanglement [0.0]
We study the symmetry resolved entanglement entropies in one-dimensional systems with boundaries. We derive exact formulas for the charged and symmetry resolved entropies based on theorems and conjectures.
arXiv Detail & Related papers (2020-09-17T19:34:34Z)
Operator-algebraic renormalization and wavelets [62.997667081978825]
We construct the continuum free field as the scaling limit of Hamiltonian lattice systems using wavelet theory. A renormalization group step is determined by the scaling equation identifying lattice observables with the continuum field smeared by compactly supported wavelets.
arXiv Detail & Related papers (2020-02-04T18:04:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.