Search

The author considers a practical algorithm for estimating an unknown parameter of the mathematical model of a Markov process with local interaction based on the Gibbs distribution. It is proposed to apply the stochastic quasi-gradient method to the maximum likelihood function, which is constructed from the observations of the realizations of the Gibbs field. The obtained results have a wide application scope in the modeling of stochastic processes. [ABSTRACT FROM AUTHOR]

Logit dynamics is a form of randomized game dynamics in which players have a bias toward strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converge to the so-called Gibbs distribution over the set of all strategy profiles when interpreted as a Markov chain. In general, logit dynamics can converge slowly to the Gibbs distribution, but beyond that, not much is known about its algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: (i) Is there an efficient algorithm for sampling from the Gibbs distribution? (ii) If yes, does there also exist natural randomized dynamics that converge quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics that converges quickly to the Gibbs distribution in such games. We also address the first question for the class of so-called capacitated uniform congestion games and the second question for max cut games played on a complete graph. To prove our results, we rely on the recent breakthrough work of Anari et al. (2019) regarding the approximate sampling of a base of a matroid according to a strongly log-concave probability distribution. [ABSTRACT FROM AUTHOR]

The author considers a practical algorithm for estimating an unknown parameter of the mathematical model of a Markov process with local interaction based on the Gibbs distribution. It is proposed to apply the stochastic quasi-gradient method to the maximum likelihood function, which is constructed from the observations of the realizations of the Gibbs field. The obtained results have a wide application scope in the modeling of stochastic processes. [ABSTRACT FROM AUTHOR]

Mean-field molecular dynamics based on path integrals is used to approximate canonical quantum observables for particle systems consisting of nuclei and electrons. A computational bottleneck is the Monte Carlo sampling from the Gibbs density of the electron operator, which due to the fermion sign problem has a computational complexity that scales exponentially with the number of electrons. In this work, we construct an algorithm that approximates the mean-field Hamiltonian by path integrals for fermions. The algorithm is based on the determinant of a matrix with components built on Brownian bridges connecting permuted electron coordinates. The computational work for n electrons is O (n 3) , which reduces the computational complexity associated with the fermion sign problem. We analyze a bias resulting from this approximation and provide a rough computational error indicator. It remains to rigorously explain the surprisingly high accuracy for high temperatures. The method becomes infeasible at low temperatures due to a large sample variance. [ABSTRACT FROM AUTHOR]

This paper focuses on entropic regularization and its multiscale extension in neural network learning. We leverage established results that characterize the optimizer of entropic regularization methods and their connection with generalization bounds. To avoid the significant computational complexity involved in sampling from the optimal multiscale Gibbs distributions, we describe how to make measured concessions in optimality by using self-similar approximating distributions. We study such scale-invariant approximations for linear neural networks and further extend the approximations to neural networks with nonlinear activation functions. We then illustrate the application of our proposed approach through empirical simulation. By navigating the interplay between optimization and computational efficiency, our research contributes to entropic regularization theory, proposing a practical method that embraces symmetry across scales. [ABSTRACT FROM AUTHOR]

Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least 2 1 / α for the hard-core model on bipartite α -expanders. [ABSTRACT FROM AUTHOR]

We introduce a new perfect sampling technique that can be applied to general Gibbs distributions and runs in linear time if the correlation decays faster than the neighborhood growth. In particular, in graphs with subexponential neighborhood growth like ℤd, our algorithm achieves linear running time as long as Gibbs sampling is rapidly mixing. As concrete applications, we obtain the currently best perfect samplers for colorings and for monomer‐dimer models in such graphs. [ABSTRACT FROM AUTHOR]

It is shown that there are three characteristic time scales for the establishment of thermodynamic equilibrium: the time for the thermalization of the system; the time for establishing a uniform temperature in the system after contact with the thermostat; and, finally, the time for establishing full ergodicity in the system. The first time is determined by particle collisions (in fluids) or multiphonon processes (in condensed media) and lies in the range from tens of picoseconds (in dense fluids) to microseconds (in pure crystals at low temperatures). The second time is determined by the thermal diffusivity and the size of the system and, for millimeter-sized samples, lasts for seconds. The third time is determined by the particle diffusion rates and can vary from hundreds of picoseconds (in gases and liquids) to astronomical times (in solids at low temperatures). The concept of ergodicity as applied to crystals and glasses is discussed. [ABSTRACT FROM AUTHOR]

A Gibbs distribution based combinatorial optimization algorithm for joint antenna splitting and user scheduling problem in full duplex massive multiple-input multiple-output (MIMO) system is proposed in this paper. The optimal solution of this problem can be determined by exhaustive search. However, the complexity of this approach becomes prohibitive in practice when the sample space is large, which is usually the case in massive MIMO systems. Our algorithm overcomes this drawback by converting the original problem into a Kullback-Leibler (KL) divergence minimization problem, and solving it through a related dynamical system via a stochastic gradient descent method. Using this approach, we improve the spectral efficiency (SE) of the system by performing joint antenna splitting and user scheduling. Additionally, numerical results show that the SE curves obtained with our proposed algorithm overlap with the curves achieved by exhaustive search for user scheduling. [ABSTRACT FROM AUTHOR]

In image classification, deriving robust image representations is a key process that determines the performance of vision systems. Numerous image features and descriptors have been developed manually over the years. As an alternative, however, deep neural networks, in particular convolutional neural networks (CNNs), have become popular for learning image features or representations from data and have demonstrated remarkable performance in many real-world applications. But CNNs often require huge amount of labelled data, which may be prohibitive in many applications, as well as long training times. This paper considers an alternative, data-independent means of obtaining features for CNNs. The proposed framework makes use of the Markov random field (MRF) and self-organising map (SOM) to generate basic features and model both intra- and inter-image dependencies. Various MRF textures are synthesized first, and are then clustered by a convolutional translation-invariant SOM, to form generic image features. These features can be directly applied as early convolutional filters of the CNN, leading to a new way of deriving effective features for image classification. The MRF framework also offers a theoretical and transparent way to examine and determine the influence of image features on performance of CNNs. Comprehensive experiments on the MNIST, rotated MNIST, CIFAR-10 and CIFAR-100 datasets were conducted with results outperforming most state-of-the-art models of similar complexity. [ABSTRACT FROM AUTHOR]

The world’s first 2 $\times $ 30k-spin multi-chip CMOS annealing processor (AP)—based on the processing-in-memory approach for solving large-scale combinatorial optimization problem—was developed. To expand the bit width of coefficients and enhance the scalability of the AP, it has three key features: an expandable and high-accuracy spin operator for local communication, a highly integrated spin circuit using direct access to SRAM, and a low-latency inter-chip interface that does not affect the runtime or results of the annealing process. The AP is fabricated on the basis of 40-nm CMOS technology. It was experimentally demonstrated that the spin-flip ratio of the processor agrees well with theoretical values based on the Gibbs distribution over a wide temperature range. As a result, under two-chip operation with 2 $\times $ 30k spins, the AP achieves an annealing time of 22 $\mu \text{s}$ , which is 455 times and 2.6 $\times $ 104 times faster than those achieved by our previous CMOS-AP and a conventional CPU, respectively. Moreover, its energy efficiency is 1.75 $\times $ 105 times higher than that of a conventional CPU-based algorithm. [ABSTRACT FROM AUTHOR]

We investigate a probabilistic model for routeing in a multihop ad hoc communication network, where each user sends a message to the base station. Messages travel in hops via other users, used as relays. Their trajectories are chosen at random according to a Gibbs distribution, which favors trajectories with low interference, measured in terms of signal-to-interference ratio. This model was introduced in our earlier paper, where we expressed, in the limit of a high density of users, the typical distribution of the family of trajectories in terms of a law of large numbers. In this paper, we derive its qualitative properties. We analytically identify the emerging typical scenarios in three extreme regimes. We analyze the typical number of hops and the typical length of a hop and the deviation of the trajectory from the straight line, regime 1 in the limit of a large communication area and large distances and regime 2 in the limit of a strong interference weight. In both the regimes, the typical trajectory approaches a straight line quickly, in regime 1 with equal hop lengths. Interestingly, in regime 2, the typical length of a hop diverges logarithmically in the distance of the transmitter to the base station. We further analyze (regime 3) local and global repulsive effects of a densely populated subarea on the trajectories. [ABSTRACT FROM AUTHOR]

Synthetic aperture radar (SAR) provides rich information about the Earth's surface under all-weather and day-and-night conditions, and is applied in many relevant fields. SAR imagery semantic segmentation, which can be a final product for end users and a fundamental procedure to support other applications, is one of the most difficult challenges. This paper proposes an encoding-decoding network based on Deeplabv3+ to semantically segment SAR imagery. A new potential energy loss function based on the Gibbs distribution is proposed here to establish the semantic dependence among different categories through the relationship among different cliques in the neighborhood system. This paper introduces an improved channel and spatial attention module to the Mobilenetv2 backbone to improve the recognition accuracy of small object categories in SAR imagery. The experimental results show that the proposed method achieves the highest mean intersection over union (mIoU) and global accuracy (GA) with the least running time, which verifies the effectiveness of our method. [ABSTRACT FROM AUTHOR]