This paper deals with unconstrained optimization problems based on numerical analysis of ordinary differential equations (ODEs). Although it has been known for a long time that there is a relation between optimization methods and discretization of ODEs, research in this direction has recently been gaining attention. In recent studies, the dissipation laws of ODEs have often played an important role. By contrast, in the context of numerical analysis, a technique called geometric numerical integration, which explores discretization to maintain geometrical properties such as the dissipation law, is actively studied. However, in research investigating the relationship between optimization and ODEs, techniques of geometric numerical integration have not been sufficiently investigated. In this paper, we show that a recent geometric numerical integration technique for gradient flow reads a new step-size criterion for the steepest descent method. Consequently, owing to the discrete dissipation law, convergence rates can be proved in a form similar to the discussion in ODEs. Although the proposed method is a variant of the existing steepest descent method, it is suggested that various analyses of the optimization methods via ODEs can be performed in the same way after discretization using geometric numerical integration.
相關內容
A trivializing map is a field transformation whose Jacobian determinant exactly cancels the interaction terms in the action, providing a representation of the theory in terms of a deterministic transformation of a distribution from which sampling is trivial. Recently, a proof-of-principle study by Albergo, Kanwar and Shanahan [arXiv:1904.12072] demonstrated that approximations of trivializing maps can be `machine-learned' by a class of invertible, differentiable neural models called \textit{normalizing flows}. By ensuring that the Jacobian determinant can be computed efficiently, asymptotically exact sampling from the theory of interest can be performed by drawing samples from a simple distribution and passing them through the network. From a theoretical perspective, this approach has the potential to become more efficient than traditional Markov Chain Monte Carlo sampling techniques, where autocorrelations severely diminish the sampling efficiency as one approaches the continuum limit. A major caveat is that it is not yet understood how the size of models and the cost of training them is expected to scale. As a first step, we have conducted an exploratory scaling study using two-dimensional $\phi^4$ with up to $20^2$ lattice sites. Although the scope of our study is limited to a particular model architecture and training algorithm, initial results paint an interesting picture in which training costs grow very quickly indeed. We describe a candidate explanation for the poor scaling, and outline our intentions to clarify the situation in future work.
In this paper, we propose a deterministic particle-FEM discretization to micro-macro models of dilute polymeric fluids, which combines a finite element discretization to the macroscopic fluid dynamic equation with a variational particle scheme to the microscopic Fokker-Planck equation. The discretization is constructed by a discrete energetic variational approach, and preserves the microscopic variational structure in the semi-discrete level. Numerical examples demonstrate the accuracy and robustness of the proposed numerical scheme for some special external flows with a wide range of flow rates.
We develop a lowest-order nonconforming virtual element method for planar linear elasticity, which can be viewed as an extension of the idea in Falk (1991) to the virtual element method (VEM), with the family of polygonal meshes satisfying a very general geometric assumption. The method is shown to be uniformly convergent for the nearly incompressible case with optimal rates of convergence. The crucial step is to establish the discrete Korn's inequality, yielding the coercivity of the discrete bilinear form. We also provide a unified locking-free scheme both for the conforming and nonconforming VEMs in the lowest order case. Numerical results validate the feasibility and effectiveness of the proposed numerical algorithms.
Trimming consists of cutting away parts of a geometric domain, without reconstructing a global parametrization (meshing). It is a widely used operation in computer aided design, which generates meshes that are unfitted with the described physical object. This paper develops an adaptive mesh refinement strategy on trimmed geometries in the context of hierarchical B-spline based isogeometric analysis. A residual a posteriori estimator of the energy norm of the numerical approximation error is derived, in the context of Poisson equation. The reliability of the estimator is proven, and the effectivity index is shown to be independent from the number of hierarchical levels and from the way the trimmed boundaries cut the underlying mesh. In particular, it is thus independent from the size of the active part of the trimmed mesh elements. Numerical experiments are performed to validate the presented theory.
This paper deals with a special type of Lyapunov functions, namely the solution of Zubov's equation. Such a function can be used to characterize the domain of attraction for systems of ordinary differential equations. We derive and prove an integral form solution to Zubov's equation. For numerical computation, we develop two data-driven methods. One is based on the integration of an augmented system of differential equations; and the other one is based on deep learning. The former is effective for systems with a relatively low state space dimension and the latter is developed for high dimensional problems. The deep learning method is applied to a New England 10-generator power system model. We prove that a neural network approximation exists for the Lyapunov function of power systems such that the approximation error is a cubic polynomial of the number of generators. The error convergence rate as a function of n, the number of neurons, is proved.
Analysis and use of stochastic models represented by a discrete-time Markov Chain require evaluation of performance measures and characterization of its stationary distribution. Analytical solutions are often unavailable when the system states are continuous or mixed. This paper presents a new method for computing the stationary distribution and performance measures for stochastic systems represented by continuous-, or mixed-state Markov chains. We show the asymptotic convergence and provide deterministic non-asymptotic error bounds for our method under the supremum norm. Our finite approximation method is near-optimal among all discrete approximate distributions, including empirical distributions obtained from Markov chain Monte Carlo (MCMC). Numerical experiments validate the accuracy and efficiency of our method and show that it significantly outperforms MCMC based approach.
The Banach-Picard iteration is widely used to find fixed points of locally contractive (LC) maps. This paper extends the Banach-Picard iteration to distributed settings; specifically, we assume the map of which the fixed point is sought to be the average of individual (not necessarily LC) maps held by a set of agents linked by a communication network. An additional difficulty is that the LC map is not assumed to come from an underlying optimization problem, which prevents exploiting strong global properties such as convexity or Lipschitzianity. Yet, we propose a distributed algorithm and prove its convergence, in fact showing that it maintains the linear rate of the standard Banach-Picard iteration for the average LC map. As another contribution, our proof imports tools from perturbation theory of linear operators, which, to the best of our knowledge, had not been used before in the theory of distributed computation.
This paper develops a lowest-order conforming virtual element method for planar linear elasticity in the displacement/traction formulation, which can be viewed as an extension of the idea in Brenner \& Sung (1992) to the virtual element method, with the family of polygonal meshes satisfying a very general geometric assumption. The method is shown to be uniformly convergent with the Lam\'{e} constant with the optimal rates of convergence.
Escaping saddle points is a central research topic in nonconvex optimization. In this paper, we propose a simple gradient-based algorithm such that for a smooth function $f\colon\mathbb{R}^n\to\mathbb{R}$, it outputs an $\epsilon$-approximate second-order stationary point in $\tilde{O}(\log n/\epsilon^{1.75})$ iterations. Compared to the previous state-of-the-art algorithms by Jin et al. with $\tilde{O}((\log n)^{4}/\epsilon^{2})$ or $\tilde{O}((\log n)^{6}/\epsilon^{1.75})$ iterations, our algorithm is polynomially better in terms of $\log n$ and matches their complexities in terms of $1/\epsilon$. For the stochastic setting, our algorithm outputs an $\epsilon$-approximate second-order stationary point in $\tilde{O}((\log n)^{2}/\epsilon^{4})$ iterations. Technically, our main contribution is an idea of implementing a robust Hessian power method using only gradients, which can find negative curvature near saddle points and achieve the polynomial speedup in $\log n$ compared to the perturbed gradient descent methods. Finally, we also perform numerical experiments that support our results.
Deep learning is the mainstream technique for many machine learning tasks, including image recognition, machine translation, speech recognition, and so on. It has outperformed conventional methods in various fields and achieved great successes. Unfortunately, the understanding on how it works remains unclear. It has the central importance to lay down the theoretic foundation for deep learning. In this work, we give a geometric view to understand deep learning: we show that the fundamental principle attributing to the success is the manifold structure in data, namely natural high dimensional data concentrates close to a low-dimensional manifold, deep learning learns the manifold and the probability distribution on it. We further introduce the concepts of rectified linear complexity for deep neural network measuring its learning capability, rectified linear complexity of an embedding manifold describing the difficulty to be learned. Then we show for any deep neural network with fixed architecture, there exists a manifold that cannot be learned by the network. Finally, we propose to apply optimal mass transportation theory to control the probability distribution in the latent space.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191