Browsing by Subject "cs.NA"

Now showing 1 - 7 of 7
  • Thumbnail Image
    ItemOpen Access
    A Priori Generalization Analysis of the Deep Ritz Method for Solving High Dimensional Elliptic Equations
    Lu, Jianfeng; Lu, Yulong; Wang, Min
    This paper concerns the a priori generalization analysis of the Deep Ritz Method (DRM) [W. E and B. Yu, 2017], a popular neural-network-based method for solving high dimensional partial differential equations. We derive the generalization error bounds of two-layer neural networks in the framework of the DRM for solving two prototype elliptic PDEs: Poisson equation and static Schr\"odinger equation on the $d$-dimensional unit hypercube. Specifically, we prove that the convergence rates of generalization errors are independent of the dimension $d$, under the a priori assumption that the exact solutions of the PDEs lie in a suitable low-complexity space called spectral Barron space. Moreover, we give sufficient conditions on the forcing term and the potential function which guarantee that the solutions are spectral Barron functions. We achieve this by developing a new solution theory for the PDEs on the spectral Barron space, which can be viewed as an analog of the classical Sobolev regularity theory for PDEs.
  • Thumbnail Image
    ItemOpen Access
    Complexity of randomized algorithms for underdamped Langevin dynamics
    Cao, Y; Lu, J; Wang, L
    We establish an information complexity lower bound of randomized algorithms for simulating underdamped Langevin dynamics. More specifically, we prove that the worst $L^2$ strong error is of order $\Omega(\sqrt{d}\, N^{-3/2})$, for solving a family of $d$-dimensional underdamped Langevin dynamics, by any randomized algorithm with only $N$ queries to $\nabla U$, the driving Brownian motion and its weighted integration, respectively. The lower bound we establish matches the upper bound for the randomized midpoint method recently proposed by Shen and Lee [NIPS 2019], in terms of both parameters $N$ and $d$.
  • Thumbnail Image
    ItemOpen Access
    Complexity of zigzag sampling algorithm for strongly log-concave distributions
    Lu, Jianfeng; Wang, Lihan
    We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. The zigzag process has the advantage of not requiring time discretization for implementation, and that each proposed bouncing event requires only one evaluation of partial derivative of the potential, while its convergence rate is dimension independent. Using these properties, we prove that the zigzag sampling algorithm achieves $\varepsilon$ error in chi-square divergence with a computational cost equivalent to $O\bigl(\kappa^2 d^\frac{1}{2}(\log\frac{1}{\varepsilon})^{\frac{3}{2}}\bigr)$ gradient evaluations in the regime $\kappa \ll \frac{d}{\log d}$ under a warm start assumption, where $\kappa$ is the condition number and $d$ is the dimension.
  • Thumbnail Image
    ItemOpen Access
    Existence and computation of generalized Wannier functions for non-periodic systems in two dimensions and higher
    Lu, Jianfeng; Stubbs, Kevin D; Watson, Alexander B
    Exponentially-localized Wannier functions (ELWFs) are a basis of the Fermi projection of a material consisting of functions which decay exponentially fast away from their maxima. When the material is insulating and crystalline, conditions which guarantee existence of ELWFs in dimensions one, two, and three are well-known, and methods for constructing the ELWFs numerically are well-developed. We consider the case where the material is insulating but not necessarily crystalline, where much less is known. In one spatial dimension, Kivelson and Nenciu-Nenciu have proved ELWFs can be constructed as the eigenfunctions of a self-adjoint operator acting on the Fermi projection. In this work, we identify an assumption under which we can generalize the Kivelson-Nenciu-Nenciu result to two dimensions and higher. Under this assumption, we prove that ELWFs can be constructed as the eigenfunctions of a sequence of self-adjoint operators acting on the Fermi projection. We conjecture that the assumption we make is equivalent to vanishing of topological obstructions to the existence of ELWFs in the special case where the material is crystalline. We numerically verify that our construction yields ELWFs in various cases where our assumption holds and provide numerical evidence for our conjecture.
  • Thumbnail Image
    ItemOpen Access
    Multi-Scale Merge-Split Markov Chain Monte Carlo for Redistricting
    Autry, Eric A; Carter, Daniel; Herschlag, Gregory; Hunter, Zach; Mattingly, Jonathan C
    We develop a Multi-Scale Merge-Split Markov chain on redistricting plans. The chain is designed to be usable as the proposal in a Markov Chain Monte Carlo (MCMC) algorithm. Sampling the space of plans amounts to dividing a graph into a partition with a specified number of elements which each correspond to a different district. The districts satisfy a collection of hard constraints and the measure may be weighted with regard to a number of other criteria. The multi-scale algorithm is similar to our previously developed Merge-Split proposal, however, this algorithm provides improved scaling properties and may also be used to preserve nested communities of interest such as counties and precincts. Both works use a proposal which extends the ReCom algorithm which leveraged spanning trees merge and split districts. In this work we extend the state space so that each district is defined by a hierarchy of trees. In this sense, the proposal step in both algorithms can be seen as a "Forest ReCom." We also expand the state space to include edges that link specified districts, which further improves the computational efficiency of our algorithm. The collection of plans sampled by the MCMC algorithm can serve as a baseline against which a particular plan of interest is compared. If a given plan has different racial or partisan qualities than what is typical of the collection of plans, the given plan may have been gerrymandered and is labeled as an outlier.
  • Thumbnail Image
    ItemOpen Access
    Solving high-dimensional eigenvalue problems using deep neural networks: A diffusion Monte Carlo like approach
    (Journal of Computational Physics, 2020-12-15) Han, J; Lu, J; Zhou, M
    © 2020 Elsevier Inc. We propose a new method to solve eigenvalue problems for linear and semilinear second order differential operators in high dimensions based on deep neural networks. The eigenvalue problem is reformulated as a fixed point problem of the semigroup flow induced by the operator, whose solution can be represented by Feynman-Kac formula in terms of forward-backward stochastic differential equations. The method shares a similar spirit with diffusion Monte Carlo but augments a direct approximation to the eigenfunction through neural-network ansatz. The criterion of fixed point provides a natural loss function to search for parameters via optimization. Our approach is able to provide accurate eigenvalue and eigenfunction approximations in several numerical examples, including Fokker-Planck operator and the linear and nonlinear Schrödinger operators in high dimensions.
  • Thumbnail Image
    ItemOpen Access
    Stable Phase Retrieval from Locally Stable and Conditionally Connected Measurements.
    (CoRR, 2020) Cheng, C; Daubechies, I; Dym, N; Lu, J
    This paper is concerned with stable phase retrieval for a family of phase retrieval models we name "locally stable and conditionally connected" (LSCC) measurement schemes. For every signal $f$, we associate a corresponding weighted graph $G_f$, defined by the LSCC measurement scheme, and show that the phase retrievability of the signal $f$ is determined by the connectivity of $G_f$. We then characterize the phase retrieval stability of the signal $f$ by two measures that are commonly used in graph theory to quantify graph connectivity: the Cheeger constant of $G_f$ for real valued signals, and the algebraic connectivity of $G_f$ for complex valued signals. We use our results to study the stability of two phase retrieval models that can be cast as LSCC measurement schemes, and focus on understanding for which signals the "curse of dimensionality" can be avoided. The first model we discuss is a finite-dimensional model for locally supported measurements such as the windowed Fourier transform. For signals "without large holes", we show the stability constant exhibits only a mild polynomial growth in the dimension, in stark contrast with the exponential growth which uniform stability constants tend to suffer from; more precisely, in $R^d$ the constant grows proportionally to $d^{1/2}$, while in $C^d$ it grows proportionally to $d$. We also show the growth of the constant in the complex case cannot be reduced, suggesting that complex phase retrieval is substantially more difficult than real phase retrieval. The second model we consider is an infinite-dimensional phase retrieval problem in a principal shift invariant space. We show that despite the infinite dimensionality of this model, signals with monotone exponential decay will have a finite stability constant. In contrast, the stability bound provided by our results will be infinite if the signal's decay is polynomial.