Asynchronous stochastic approximations (SAs) are an important class of model-free algorithms, tools, and techniques that are popular in multiagent and distributed control scenarios. To counter ...Bellman's curse of dimensionality, such algorithms are coupled with function approximations. Although the learning/control problem becomes more tractable, function approximations affect stability and convergence. In this article, we present verifiable sufficient conditions for stability and convergence of asynchronous SAs with biased approximation errors. The theory developed herein is used to analyze policy gradient methods and noisy value iteration schemes. Specifically, we analyze the asynchronous approximate counterparts of the policy gradient (A2PG) and value iteration (A2VI) schemes. It is shown that the stability of these algorithms is unaffected by biased approximation errors, provided that they are asymptotically bounded. With respect to convergence (of A2VI and A2PG), a relationship between the limiting set and the approximation errors is established. Finally, experimental results that support the theory are presented.
libxc is a library of exchange–correlation functionals for density-functional theory. We are concerned with semi-local functionals (or the semi-local part of hybrid functionals), namely local-density ...approximations, generalized-gradient approximations, and meta-generalized-gradient approximations. Currently we include around 400 functionals for the exchange, correlation, and the kinetic energy, spanning more than 50 years of research. Moreover, libxc is by now used by more than 20 codes, not only from the atomic, molecular, and solid-state physics, but also from the quantum chemistry communities.
This book covers adaptive mesh generation and moving mesh methods for solving time-dependent PDEs. It gives a general description of the components of moving mesh methods as well as examples of their ...application for a number of nontrivial physical problems.
Generalized probabilistic approximations of incomplete data Grzymala-Busse, Jerzy W.; Clark, Patrick G.; Kuehnhausen, Martin
International journal of approximate reasoning,
January 2014, 2014-01-00, Letnik:
55, Številka:
1
Journal Article
Recenzirano
Odprti dostop
•We discuss a generalization of probabilistic approximations.•We propose global and local probabilistic approximations.•Approximations are compared experimentally using 16 data sets.•The best ...approach should be selected individually.•We found that the number of distinct probabilistic approximations is limited.
In this paper we discuss a generalization of the idea of probabilistic approximations. Probabilistic (or parameterized) approximations, studied mostly in variable precision rough set theory, were originally defined using equivalence relations. Recently, probabilistic approximations were defined for arbitrary binary relations. Such approximations have an immediate application to data mining from incomplete data because incomplete data sets are characterized by a characteristic relation which is reflexive but not necessarily symmetric or transitive. In contrast, complete data sets are described by indiscernibility which is an equivalence relation.
The main objective of this paper was to compare experimentally, for the first time, two generalizations of probabilistic approximations: global and local. Additionally, we explored the problem how many distinct probabilistic approximations may be defined for a given data set.
Low Phase-Rank Approximation Zhao, Di; Ringh, Axel; Qiu, Li ...
Linear algebra and its applications,
04/2022, Letnik:
639
Journal Article
Recenzirano
In this paper, we propose and solve low phase-rank approximation problems, which serve as a counterpart to the well-known low-rank approximation problem and the Schmidt-Mirsky theorem. It is well ...known that a nonzero complex number can be specified by its gain and phase, and while it is generally accepted that the gains of a matrix may be defined by its singular values, there is no widely accepted definition for its phases. In this work, we consider sectorial matrices, whose numerical ranges do not contain the origin, and adopt the canonical angles of such matrices as their phases. Similarly to the rank of a matrix being defined as the number of its nonzero singular values, we define the phase-rank of a sectorial matrix as the number of its nonzero phases. While a low-rank approximation problem is associated with the matrix arithmetic mean, it turns out that a natural parallel for the low phase-rank approximation problem is to use the matrix geometric mean to measure the approximation error. Importantly, we derive a majorization inequality between the phases of the geometric mean and the arithmetic mean of the phases, similarly to the Ky-Fan inequality for eigenvalues of Hermitian matrices. A characterization of the solutions to the proposed problem, with the same flavor as the Schmidt-Mirsky theorem, is then obtained in the case where both the objective matrix and the approximant are restricted to be positive-imaginary. In addition, we provide an alternative formulation of the low phase-rank approximation problem using geodesic distances between sectorial matrices. The two formulations give rise to the exact same set of solutions when the involved matrices are additionally assumed to be unitary.
The vast quantity of information brought by big data as well as the evolving computer hardware encourages success stories in the machine learning community. In the meanwhile, it poses challenges for ...the Gaussian process regression (GPR), a well-known nonparametric, and interpretable Bayesian model, which suffers from cubic complexity to data size. To improve the scalability while retaining desirable prediction quality, a variety of scalable GPs have been presented. However, they have not yet been comprehensively reviewed and analyzed to be well understood by both academia and industry. The review of scalable GPs in the GP community is timely and important due to the explosion of data size. To this end, this article is devoted to reviewing state-of-the-art scalable GPs involving two main categories: global approximations that distillate the entire data and local approximations that divide the data for subspace learning. Particularly, for global approximations, we mainly focus on sparse approximations comprising prior approximations that modify the prior but perform exact inference, posterior approximations that retain exact prior but perform approximate inference, and structured sparse approximations that exploit specific structures in kernel matrix; for local approximations, we highlight the mixture/product of experts that conducts model averaging from multiple local experts to boost predictions. To present a complete review, recent advances for improving the scalability and capability of scalable GPs are reviewed. Finally, the extensions and open issues of scalable GPs in various scenarios are reviewed and discussed to inspire novel ideas for future research avenues.
We present a novel kind of neighborhood, named subset neighborhood and denoted as Sρ-neighborhood. It is defined under an arbitrary binary relation using the inclusion relations between ...Nρ-neighborhoods. We study its relationships with some kinds of neighborhood systems given in the literature. Then, we formulate the concepts of Sρ-lower and Sρ-upper approximations, and Sρ-accuracy and roughness measures based on Sρ-neighborhoods. We show in which cases the Sρ-accuracy measure is the highest among related approximations and investigate under which conditions the Sρ-accuracy and Sρ-roughness measures are monotonic. Moreover, we compare our approach with two existing ones and elucidate the advantages of our technique to obtain accuracy measures under some specific relations. To support the obtained results, we provide two medical examples.
This work proposes and analyzes an anisotropic sparse grid stochastic collocation method for solving partial differential equations with random coefficients and forcing terms (input data of the ...model). The method consists of a Galerkin approximation in the space variables and a collocation, in probability space, on sparse tensor product grids utilizing either Clenshaw—Curtis or Gaussian knots. Even in the presence of nonlinearities, the collocation approach leads to the solution of uncoupled deterministic problems, just as in the Monte Carlo method. This work includes a priori and a posteriori procedures to adapt the anisotropy of the sparse grids to each given problem. These procedures seem to be very effective for the problems under study. The proposed method combines the advantages of isotropic sparse collocation with those of anisotropic full tensor product collocation: the first approach is effective for problems depending on random variables which weigh approximately equally in the solution, while the benefits of the latter approach become apparent when solving highly anisotropic problems depending on a relatively small number of random variables, as in the case where input random variables are Karhunen—Loève truncations of "smooth" random fields. This work also provides a rigorous convergence analysis of the fully discrete problem and demonstrates (sub)exponential convergence in the asymptotic regime and algebraic convergence in the preasymptotic regime, with respect to the total number of collocation points. It also shows that the anisotropic approximation breaks the curse of dimensionality for a wide set of problems. Numerical examples illustrate the theoretical results and are used to compare this approach with several others, including the standard Monte Carlo. In particular, for moderately large-dimensional problems, the sparse grid approach with a properly chosen anisotropy seems to be very efficient and superior to all examined methods.
The arrival of molecules in molecular communication via diffusion obeys, by its nature, the binomial distribution, considering the hitting probability as the success probability. It is, however, hard ...to work with the binomial cumulative distribution function (CDF) when considering consecutively sent symbols as it is necessary to add the distribution. Therefore, in the literature, two approximations of the binomial distribution are used. In the present reported work, the Gaussian and Poisson approximations of the binomial model of the molecule arrival process have been analysed. Considering the distance and the number of emitted molecules, the regions in which the Poisson or Gaussian model is better in terms of root mean squared error of CDFs are investigated and the regions using numerical simulations are confirmed.
Randomized Dimensionality Reduction for k -Means Clustering Boutsidis, Christos; Zouzias, Anastasios; Mahoney, Michael W. ...
IEEE transactions on information theory,
2015-Feb., 2015-2-00, 20150201, Letnik:
61, Številka:
2
Journal Article
Recenzirano
Odprti dostop
We study the topic of dimensionality reduction for k-means clustering. Dimensionality reduction encompasses the union of two approaches: 1) feature selection and 2) feature extraction. A feature ...selection-based algorithm for k-means clustering selects a small subset of the input features and then applies k-means clustering on the selected features. A feature extraction-based algorithm for k-means clustering constructs a small set of new artificial features and then applies k-means clustering on the constructed features. Despite the significance of k-means clustering as well as the wealth of heuristic methods addressing it, provably accurate feature selection methods for k-means clustering are not known. On the other hand, two provably accurate feature extraction methods for k-means clustering are known in the literature; one is based on random projections and the other is based on the singular value decomposition (SVD). This paper makes further progress toward a better understanding of dimensionality reduction for k-means clustering. Namely, we present the first provably accurate feature selection method for k-means clustering and, in addition, we present two feature extraction methods. The first feature extraction method is based on random projections and it improves upon the existing results in terms of time complexity and number of features needed to be extracted. The second feature extraction method is based on fast approximate SVD factorizations and it also improves upon the existing results in terms of time complexity. The proposed algorithms are randomized and provide constant-factor approximation guarantees with respect to the optimal k-means objective value.
PDF
