math.PR

arXiv:2303.15463v2 Announce Type: replace Abstract: We prove a general criterion providing sufficient conditions under which a time-discretiziation of a given Stochastic Differential Equation (SDE) is a uniform in time approximation of the SDE. The criterion is also, to a certain extent, discussed in the paper, necessary. Using such a criterion we then analyse the convergence properties of numerical methods for solutions of SDEs; we consider Explicit and Implicit Euler, split-step and (truncated) tamed Euler methods. In particular, we show that, under mild conditions on the coefficients of the SDE (locally Lipschitz and strictly monotonic), these methods produce approximations of the law of the solution of the SDE that converge uniformly in time. The theoretical results are verified by numerical examples.

arXiv:2310.15581v4 Announce Type: replace Abstract: In this paper we consider PIDEs with gradient-independent Lipschitz continuous nonlinearities and prove that deep neural networks with ReLU activation function can approximate solutions of such semilinear PIDEs without curse of dimensionality in the sense that the required number of parameters in the deep neural networks increases at most polynomially in both the dimension $ d $ of the corresponding PIDE and the reciprocal of the prescribed accuracy $\epsilon $.

arXiv:2501.10482v1 Announce Type: cross Abstract: Random fuzzy variables join the modeling of the impreciseness (due to their ``fuzzy part'') and randomness. Statistical samples of such objects are widely used, and their direct, numerically effective generation is therefore necessary. Usually, these samples consist of triangular or trapezoidal fuzzy numbers. In this paper, we describe theoretical results and simulation algorithms for another family of fuzzy numbers -- LR fuzzy numbers with interval-valued cores. Starting from a simulation perspective on the piecewise linear LR fuzzy numbers with the interval-valued cores, their limiting behavior is then considered. This leads us to the numerically efficient algorithm for simulating a sample consisting of such fuzzy values.

arXiv:2501.11393v1 Announce Type: new Abstract: In this paper, we derive an expression for the expected number of runs in a trace of a binary sequence $x \in \{0,1\}^n$ obtained by passing $x$ through a deletion channel that independently deletes each bit with probability $q$. We use this expression to show that if $x$ is a codeword of a first-order Reed-Muller code, and the deletion probability $q$ is 1/2, then $x$ can be reconstructed, with high probability, from $\tilde{O}(n)$ many of its traces.

arXiv:2501.11226v1 Announce Type: cross Abstract: Small-world networks, known for their high local clustering and short average path lengths, are a fundamental structure in many real-world systems, including social, biological, and technological networks. We apply the theory of local convergence (Benjamini-Schramm convergence) to derive the limiting behavior of the local structures for two of the most commonly studied small-world network models: the Watts-Strogatz model and the Kleinberg model. Establishing local convergence enables us to show that key network measures, such as PageRank, clustering coefficients, and maximum matching size, converge as network size increases with their limits determined by the graph's local structure. Additionally, this framework facilitates the estimation of global phenomena, such as information cascades, using local information from small neighborhoods. As an additional outcome of our results, we observe a critical change in the behavior of the limit exactly when the parameter governing long-range connections in the Kleinberg model crosses the threshold where decentralized search remains efficient, offering a new perspective on why decentralized algorithms fail in certain regimes.

arXiv:2501.11092v1 Announce Type: cross Abstract: M. E. Larsen evaluated the Wronskian determinant of functions $\{\sin(mx)\}_{1\le m \le n}$. We generalize this result and compute the Wronskian of $\{\sin(mx)\}_{1\le m \le n-1}\cup \{\sin((k+n)x\} $. We show that this determinant can be expressed in terms of Gegenbauer orthogonal polynomials and we give two proofs of this result: a direct proof using recurrence relations and a less direct (but, possibly, more instructive) proof based on Darboux-Crum transformations.

arXiv:2501.12212v1 Announce Type: cross Abstract: Stochastic iterative algorithms, including stochastic gradient descent (SGD) and stochastic gradient Langevin dynamics (SGLD), are widely utilized for optimization and sampling in large-scale and high-dimensional problems in machine learning, statistics, and engineering. Numerous works have bounded the parameter error in, and characterized the uncertainty of, these approximations. One common approach has been to use scaling limit analyses to relate the distribution of algorithm sample paths to a continuous-time stochastic process approximation, particularly in asymptotic setups. Focusing on the univariate setting, in this paper, we build on previous work to derive non-asymptotic functional approximation error bounds between the algorithm sample paths and the Ornstein-Uhlenbeck approximation using an infinite-dimensional version of Stein's method of exchangeable pairs. We show that this bound implies weak convergence under modest additional assumptions and leads to a bound on the error of the variance of the iterate averages of the algorithm. Furthermore, we use our main result to construct error bounds in terms of two common metrics: the L\'{e}vy-Prokhorov and bounded Wasserstein distances. Our results provide a foundation for developing similar error bounds for the multivariate setting and for more sophisticated stochastic approximation algorithms.

arXiv:2501.11743v1 Announce Type: new Abstract: We consider the constrained sampling problem where the goal is to sample from a target distribution on a constrained domain. We propose skew-reflected non-reversible Langevin dynamics (SRNLD), a continuous-time stochastic differential equation with skew-reflected boundary. We obtain non-asymptotic convergence rate of SRNLD to the target distribution in both total variation and 1-Wasserstein distances. By breaking reversibility, we show that the convergence is faster than the special case of the reversible dynamics. Based on the discretization of SRNLD, we propose skew-reflected non-reversible Langevin Monte Carlo (SRNLMC), and obtain non-asymptotic discretization error from SRNLD, and convergence guarantees to the target distribution in 1-Wasserstein distance. We show better performance guarantees than the projected Langevin Monte Carlo in the literature that is based on the reversible dynamics. Numerical experiments are provided for both synthetic and real datasets to show efficiency of the proposed algorithms.

arXiv:2302.05133v3 Announce Type: replace-cross Abstract: We study a class of McKean--Vlasov Stochastic Differential Equations (MV-SDEs) with drifts and diffusions having super-linear growth in measure and space -- the maps have general polynomial form but also satisfy a certain monotonicity condition. The combination of the drift's super-linear growth in measure (by way of a convolution) and the super-linear growth in space and measure of the diffusion coefficient requires novel technical elements in order to obtain the main results. We establish wellposedness, propagation of chaos (PoC), and under further assumptions on the model parameters, we show an exponential ergodicity property alongside the existence of an invariant distribution. No differentiability or non-degeneracy conditions are required. Further, we present a particle system based Euler-type split-step scheme (SSM) for the simulation of this type of MV-SDEs. The scheme attains, in stepsize, the strong error rate $1/2$ in the non-path-space root-mean-square error metric and we demonstrate the property of mean-square contraction. Our results are illustrated by numerical examples including: estimation of PoC rates across dimensions, preservation of periodic phase-space, and the observation that taming appears to be not a suitable method unless strong dissipativity is present.

arXiv:2501.06427v1 Announce Type: cross Abstract: It is a folklore belief in the theory of spin glasses and disordered systems that out-of-equilibrium dynamics fail to find stable local optima exhibiting e.g. local strict convexity on physical time-scales. In the context of the Sherrington--Kirkpatrick spin glass, Behrens-Arpino-Kivva-Zdeborov\'a and Minzer-Sah-Sawhney have recently conjectured that this obstruction may be inherent to all efficient algorithms, despite the existence of exponentially many such optima throughout the landscape. We prove this search problem exhibits strong low degree hardness for polynomial algorithms of degree $D\leq o(N)$: any such algorithm has probability $o(1)$ to output a stable local optimum. To the best of our knowledge, this is the first result to prove that even constant-degree polynomials have probability $o(1)$ to solve a random search problem without planted structure. To prove this, we develop a general-purpose enhancement of the ensemble overlap gap property, and as a byproduct improve previous results on spin glass optimization, maximum independent set, random $k$-SAT, and the Ising perceptron to strong low degree hardness. Finally for spherical spin glasses with no external field, we prove that Langevin dynamics does not find stable local optima within dimension-free time.

arXiv:2405.09541v3 Announce Type: replace-cross Abstract: It is well-known that randomly initialized, push-forward, fully-connected neural networks weakly converge to isotropic Gaussian processes, in the limit where the width of all layers goes to infinity. In this paper, we propose to use the angular power spectrum of the limiting field to characterize the complexity of the network architecture. In particular, we define sequences of random variables associated with the angular power spectrum, and provide a full characterization of the network complexity in terms of the asymptotic distribution of these sequences as the depth diverges. On this basis, we classify neural networks as low-disorder, sparse, or high-disorder; we show how this classification highlights a number of distinct features for standard activation functions, and in particular, sparsity properties of ReLU networks. Our theoretical results are also validated by numerical simulations.

arXiv:2405.01346v2 Announce Type: replace Abstract: We study the weak convergence behaviour of the Leimkuhler--Matthews method, a non-Markovian Euler-type scheme with the same computational cost as the Euler scheme, for the approximation of the stationary distribution of a one-dimensional McKean--Vlasov Stochastic Differential Equation (MV-SDE). The particular class under study is known as mean-field (overdamped) Langevin equations (MFL). We provide weak and strong error results for the scheme in both finite and infinite time. We work under a strong convexity assumption. Based on a careful analysis of the variation processes and the Kolmogorov backward equation for the particle system associated with the MV-SDE, we show that the method attains a higher-order approximation accuracy in the long-time limit (of weak order convergence rate $3/2$) than the standard Euler method (of weak order $1$). While we use an interacting particle system (IPS) to approximate the MV-SDE, we show the convergence rate is independent of the dimension of the IPS and this includes establishing uniform-in-time decay estimates for moments of the IPS, the Kolmogorov backward equation and their derivatives. The theoretical findings are supported by numerical tests.

arXiv:2411.00792v2 Announce Type: replace Abstract: With the development of information technology, requirements for data flow have become diverse. When multi-type data flow (MDF) is used, games, videos, calls, \textit{etc.} are all requirements. There may be a constant switch between these requirements, and also multiple requirements at the same time. Therefore, the demands of users change over time, which makes traditional teletraffic analysis not directly applicable. This paper proposes probabilistic models for the requirement of MDF, and analyzes in three states: non-tolerance, tolerance and delay. When the requirement random variables are co-distributed with respect to time, we prove the practicability of the Erlang Multirate Loss Model (EMLM) from a mathematical perspective by discretizing time and error analysis. An algorithm of pre-allocating resources is given to guild the construction of base resources.

arXiv:2501.06701v1 Announce Type: cross Abstract: This paper investigates the investment problem of constructing an optimal no-short sequential portfolio strategy in a market with a latent dependence structure between asset prices and partly unobservable side information, which is often high-dimensional. The results demonstrate that a dynamic strategy, which forms a portfolio based on perfect knowledge of the dependence structure and full market information over time, may not grow at a higher rate infinitely often than a constant strategy, which remains invariant over time. Specifically, if the market is stationary, implying that the dependence structure is statistically stable, the growth rate of an optimal dynamic strategy, utilizing the maximum capacity of the entire market information, almost surely decays over time into an equilibrium state, asymptotically converging to the growth rate of a constant strategy. Technically, this work reassesses the common belief that a constant strategy only attains the optimal limiting growth rate of dynamic strategies when the market process is identically and independently distributed. By analyzing the dynamic log-optimal portfolio strategy as the optimal benchmark in a stationary market with side information, we show that a random optimal constant strategy almost surely exists, even when a limiting growth rate for the dynamic strategy does not. Consequently, two approaches to learning algorithms for portfolio construction are discussed, demonstrating the safety of removing side information from the learning process while still guaranteeing an asymptotic growth rate comparable to that of the optimal dynamic strategy.

arXiv:2410.00355v2 Announce Type: replace-cross Abstract: Finding eigenvalue distributions for a number of sparse random matrix ensembles can be reduced to solving nonlinear integral equations of the Hammerstein type. While a systematic mathematical theory of such equations exists, it has not been previously applied to sparse matrix problems. We close this gap in the literature by showing how one can employ numerical solutions of Hammerstein equations to accurately recover the spectra of adjacency matrices and Laplacians of random graphs. While our treatment focuses on random graphs for concreteness, the methodology has broad applications to more general sparse random matrices.

arXiv:2501.03379v1 Announce Type: cross Abstract: An independent set may not contain both a vertex and one of its neighbours. This basic fact makes the uniform distribution over independent sets rather special. We consider the hard-core model, an essential generalization of the uniform distribution over independent sets. We show how its local analysis yields remarkable insights into the global structure of independent sets in the host graph, in connection with, for instance, Ramsey numbers, graph colourings, and sphere packings.

arXiv:2501.01716v1 Announce Type: cross Abstract: The Certainty Equivalent heuristic (CE) is a widely-used algorithm for various dynamic resource allocation problems in OR and OM. Despite its popularity, existing theoretical guarantees of CE are limited to settings satisfying restrictive fluid regularity conditions, particularly, the non-degeneracy conditions, under the widely held belief that the violation of such conditions leads to performance deterioration and necessitates algorithmic innovation beyond CE. In this work, we conduct a refined performance analysis of CE within the general framework of online linear programming. We show that CE achieves uniformly near-optimal regret (up to a polylogarithmic factor in $T$) under only mild assumptions on the underlying distribution, without relying on any fluid regularity conditions. Our result implies that, contrary to prior belief, CE effectively beats the curse of degeneracy for a wide range of problem instances with continuous conditional reward distributions, highlighting the distinction of the problem's structure between discrete and non-discrete settings. Our explicit regret bound interpolates between the mild $(\log T)^2$ regime and the worst-case $\sqrt{T}$ regime with a parameter $\beta$ quantifying the minimal rate of probability accumulation of the conditional reward distributions, generalizing prior findings in the multisecretary setting. To achieve these results, we develop novel algorithmic analytical techniques. Drawing tools from the empirical processes theory, we establish strong concentration analysis of the solutions to random linear programs, leading to improved regret analysis under significantly relaxed assumptions. These techniques may find potential applications in broader online decision-making contexts.

arXiv:2402.14434v3 Announce Type: replace-cross Abstract: We study the problem of sampling from a target probability density function in frameworks where parallel evaluations of the log-density gradient are feasible. Focusing on smooth and strongly log-concave densities, we revisit the parallelized randomized midpoint method and investigate its properties using recently developed techniques for analyzing its sequential version. Through these techniques, we derive upper bounds on the Wasserstein distance between sampling and target densities. These bounds quantify the substantial runtime improvements achieved through parallel processing.

arXiv:2501.01474v1 Announce Type: cross Abstract: This paper is devoted to order-one explicit approximations of random periodic solutions to multiplicative noise driven stochastic differential equations (SDEs) with non-globally Lipschitz coefficients. The existence of the random periodic solution is demonstrated as the limit of the pull-back of the discretized SDE. A novel approach is introduced to analyze mean-square error bounds of the proposed scheme that does not depend on a prior high-order moment bounds of the numerical approximations. Under mild assumptions, the proposed scheme is proved to achieve an expected order-one mean square convergence in the infinite time horizon. Numerical examples are finally provided to verify the theoretical results.

arXiv:2501.00762v1 Announce Type: new Abstract: Graph neural networks (GNNs) have achieved remarkable empirical success in processing and representing graph-structured data across various domains. However, a significant challenge known as "oversmoothing" persists, where vertex features become nearly indistinguishable in deep GNNs, severely restricting their expressive power and practical utility. In this work, we analyze the asymptotic oversmoothing rates of deep GNNs with and without residual connections by deriving explicit convergence rates for a normalized vertex similarity measure. Our analytical framework is grounded in the multiplicative ergodic theorem. Furthermore, we demonstrate that adding residual connections effectively mitigates or prevents oversmoothing across several broad families of parameter distributions. The theoretical findings are strongly supported by numerical experiments.