We propose local space-time approximation spaces for parabolic problems that are optimal in the sense of Kolmogorov and may be employed in multiscale and domain decomposition methods. The diffusion coefficient can be arbitrarily rough in space and time. To construct local approximation spaces we consider a compact transfer operator that acts on the space of local solutions and covers the full time dimension. The optimal local spaces are then given by the left singular vectors of the transfer operator. To prove compactness of the latter we combine a suitable parabolic Caccioppoli inequality with the compactness theorem of Aubin-Lions. In contrast to the elliptic setting [I. Babu\v{s}ka and R. Lipton, Multiscale Model. Simul., 9 (2011), pp. 373-406] we need an additional regularity result to combine the two results. Furthermore, we employ the generalized finite element method to couple local spaces and construct an approximation of the global solution. Since our approach yields reduced space-time bases, the computation of the global approximation does not require a time stepping method and is thus computationally efficient. Moreover, we derive rigorous local and global a priori error bounds. In detail, we bound the global approximation error in a graph norm by the local errors in the $L^2(H^1)$-norm, noting that the space the transfer operator maps to is equipped with this norm. Numerical experiments demonstrate an exponential decay of the singular values of the transfer operator and the local and global approximation errors for problems with high contrast or multiscale structure regarding space and time.
相關內容
Nonlinear metrics, such as the F1-score, Matthews correlation coefficient, and Fowlkes-Mallows index, are often used to evaluate the performance of machine learning models, in particular, when facing imbalanced datasets that contain more samples of one class than the other. Recent optimal decision tree algorithms have shown remarkable progress in producing trees that are optimal with respect to linear criteria, such as accuracy, but unfortunately nonlinear metrics remain a challenge. To address this gap, we propose a novel algorithm based on bi-objective optimisation, which treats misclassifications of each binary class as a separate objective. We show that, for a large class of metrics, the optimal tree lies on the Pareto frontier. Consequently, we obtain the optimal tree by using our method to generate the set of all nondominated trees. To the best of our knowledge, this is the first method to compute provably optimal decision trees for nonlinear metrics. Our approach leads to a trade-off when compared to optimising linear metrics: the resulting trees may be more desirable according to the given nonlinear metric at the expense of higher runtimes. Nevertheless, the experiments illustrate that runtimes are reasonable for majority of the tested datasets.
In this paper, we propose a data-driven model reduction method to solve parabolic inverse source problems efficiently. Our method consists of offline and online stages. In the off-line stage, we explore the low-dimensional structures in the solution space of the parabolic partial differential equations (PDEs) in the forward problem with a given class of source functions and construct a small number of proper orthogonal decomposition (POD) basis functions to achieve significant dimension reduction. Equipped with the POD basis functions, we can solve the forward problem extremely fast in the online stage. Thus, we develop a fast algorithm to solve the optimization problem in the parabolic inverse source problems, which is referred to as the POD algorithm in this paper. Under a weak regularity assumption on the solution of the parabolic PDEs, we prove the convergence of the POD algorithm in solving the forward parabolic PDEs. In addition, we obtain the error estimate of the POD algorithm for parabolic inverse source problems. Finally, we present numerical examples to demonstrate the accuracy and efficiency of the proposed method. Our numerical results show that the POD algorithm provides considerable computational savings over the finite element method.
Implicit Processes (IPs) are flexible priors that can describe models such as Bayesian neural networks, neural samplers and data generators. IPs allow for approximate inference in function-space. This avoids some degenerate problems of parameter-space approximate inference due to the high number of parameters and strong dependencies. For this, an extra IP is often used to approximate the posterior of the prior IP. However, simultaneously adjusting the parameters of the prior IP and the approximate posterior IP is a challenging task. Existing methods that can tune the prior IP result in a Gaussian predictive distribution, which fails to capture important data patterns. By contrast, methods producing flexible predictive distributions by using another IP to approximate the posterior process cannot fit the prior IP to the observed data. We propose here a method that can carry out both tasks. For this, we rely on an inducing-point representation of the prior IP, as often done in the context of sparse Gaussian processes. The result is a scalable method for approximate inference with IPs that can tune the prior IP parameters to the data, and that provides accurate non-Gaussian predictive distributions.
We investigate a family of bilevel imaging learning problems where the lower-level instance corresponds to a convex variational model involving first- and second-order nonsmooth regularizers. By using geometric properties of the primal-dual reformulation of the lower-level problem and introducing suitable changes of variables, we are able to reformulate the original bilevel problems as Mathematical Programs with Complementarity Constraints (MPCC). For the latter, we prove tight constraint qualification conditions (MPCC-MFCQ and partial MPCC-LICQ) and derive Mordukovich (M-) and Strong (S-) stationarity conditions. The S-stationarity system for the MPCC turns also into S-stationarity conditions for the original formulation. Second-order sufficient optimality conditions are derived as well. The proposed reformulation may be extended to problems in function spaces, leading to MPCC's with additional constraints on the gradient of the state. Finally, we report on some numerical results obtained by using the proposed MPCC reformulations together with available large-scale nonlinear programming solvers.
A new method for estimating structural equation models (SEM) is proposed and evaluated. In contrast to most other methods, it is based directly on the data, not on the covariance matrix of the data. The new approach is flexible enough to handle non-linear and non-smooth models and allows to model various constraints. Principle strengths and weaknesses of this approach are discussed and simulation studies are performed to reveal problems and potentials of this approach.
A data-driven analysis method known as dynamic mode decomposition (DMD) approximates the linear Koopman operator on projected space. In the spirit of Johnson-Lindenstrauss Lemma, we will use random projection to estimate the DMD modes in reduced dimensional space. In practical applications, snapshots are in high dimensional observable space and the DMD operator matrix is massive. Hence, computing DMD with the full spectrum is infeasible, so our main computational goal is estimating the eigenvalue and eigenvectors of the DMD operator in a projected domain. We will generalize the current algorithm to estimate a projected DMD operator. We focus on a powerful and simple random projection algorithm that will reduce the computational and storage cost. While clearly, a random projection simplifies the algorithmic complexity of a detailed optimal projection, as we will show, generally the results can be excellent nonetheless, and quality understood through a well-developed theory of random projections. We will demonstrate that modes can be calculated for a low cost by the projected data with sufficient dimension. Keyword: Koopman Operator, Dynamic Mode Decomposition(DMD), Johnson-Lindenstrauss Lemma, Random Projection, Data-driven method.
Sampling methods (e.g., node-wise, layer-wise, or subgraph) has become an indispensable strategy to speed up training large-scale Graph Neural Networks (GNNs). However, existing sampling methods are mostly based on the graph structural information and ignore the dynamicity of optimization, which leads to high variance in estimating the stochastic gradients. The high variance issue can be very pronounced in extremely large graphs, where it results in slow convergence and poor generalization. In this paper, we theoretically analyze the variance of sampling methods and show that, due to the composite structure of empirical risk, the variance of any sampling method can be decomposed into \textit{embedding approximation variance} in the forward stage and \textit{stochastic gradient variance} in the backward stage that necessities mitigating both types of variance to obtain faster convergence rate. We propose a decoupled variance reduction strategy that employs (approximate) gradient information to adaptively sample nodes with minimal variance, and explicitly reduces the variance introduced by embedding approximation. We show theoretically and empirically that the proposed method, even with smaller mini-batch sizes, enjoys a faster convergence rate and entails a better generalization compared to the existing methods.
We propose a scalable Gromov-Wasserstein learning (S-GWL) method and establish a novel and theoretically-supported paradigm for large-scale graph analysis. The proposed method is based on the fact that Gromov-Wasserstein discrepancy is a pseudometric on graphs. Given two graphs, the optimal transport associated with their Gromov-Wasserstein discrepancy provides the correspondence between their nodes and achieves graph matching. When one of the graphs has isolated but self-connected nodes ($i.e.$, a disconnected graph), the optimal transport indicates the clustering structure of the other graph and achieves graph partitioning. Using this concept, we extend our method to multi-graph partitioning and matching by learning a Gromov-Wasserstein barycenter graph for multiple observed graphs; the barycenter graph plays the role of the disconnected graph, and since it is learned, so is the clustering. Our method combines a recursive $K$-partition mechanism with a regularized proximal gradient algorithm, whose time complexity is $\mathcal{O}(K(E+V)\log_K V)$ for graphs with $V$ nodes and $E$ edges. To our knowledge, our method is the first attempt to make Gromov-Wasserstein discrepancy applicable to large-scale graph analysis and unify graph partitioning and matching into the same framework. It outperforms state-of-the-art graph partitioning and matching methods, achieving a trade-off between accuracy and efficiency.
UMAP (Uniform Manifold Approximation and Projection) is a novel manifold learning technique for dimension reduction. UMAP is constructed from a theoretical framework based in Riemannian geometry and algebraic topology. The result is a practical scalable algorithm that applies to real world data. The UMAP algorithm is competitive with t-SNE for visualization quality, and arguably preserves more of the global structure with superior run time performance. Furthermore, UMAP has no computational restrictions on embedding dimension, making it viable as a general purpose dimension reduction technique for machine learning.
This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191