Search

We extend the classical preferential attachment random graph model to random simplicial complexes. At each stage of the model, we choose one of the existing $k$-simplices with probability proportional to its $k$-degree. The chosen $k$-simplex then forms a $(k+1)$-simplex with a newly arriving vertex. We establish a strong law of large numbers for the degree counts across multiple dimensions. The limiting probability mass function is expressed as a mixture of mass functions of different types of negative binomial random variables. This limiting distribution has power-law characteristics and we explore the limiting extremal dependence of the degree counts across different dimensions in the framework of multivariate regular variation. Finally, we prove multivariate weak convergence, under appropriate normalization, of degree counts in different dimensions, of ordered $k$-simplices. The resulting weak limit can be represented as a function of independent linear birth processes with immigration.

This paper considers an empirical risk minimization problem under heavy-tailed settings, where data does not have finite variance, but only has $p$-th moment with $p \in (1,2)$. Instead of using estimation procedure based on truncated observed data, we choose the optimizer by minimizing the risk value. Those risk values can be robustly estimated via using the remarkable Catoni's method (Catoni, 2012). Thanks to the structure of Catoni-type influence functions, we are able to establish excess risk upper bounds via using generalized generic chaining methods. Moreover, we take computational issues into consideration. We especially theoretically investigate two types of optimization methods, robust gradient descent algorithm and empirical risk-based methods. With an extensive numerical study, we find that the optimizer based on empirical risks via Catoni-style estimation indeed shows better performance than other baselines. It indicates that estimation directly based on truncated data may lead to unsatisfactory results.

We consider the multiparameter random simplicial complex on a vertex set $\{ 1,\dots,n \}$, which is parameterized by multiple connectivity probabilities. Our key results concern the topology of this complex of dimensions higher than the critical dimension. We show that the higher-dimensional Betti numbers satisfy strong laws of large numbers and central limit theorems. Moreover, lower tail large deviations for these Betti numbers are also discussed. Some of our results indicate an occurrence of phase transitions in terms of the scaling constants of the central limit theorem, and the exponentially decaying rate of convergence of lower tail large deviation probabilities.

We introduce Epsilon*, a new privacy metric for measuring the privacy risk of a single model instance prior to, during, or after deployment of privacy mitigation strategies. The metric requires only black-box access to model predictions, does not require training data re-sampling or model re-training, and can be used to measure the privacy risk of models not trained with differential privacy. Epsilon* is a function of true positive and false positive rates in a hypothesis test used by an adversary in a membership inference attack. We distinguish between quantifying the privacy loss of a trained model instance, which we refer to as empirical privacy, and quantifying the privacy loss of the training mechanism which produces this model instance. Existing approaches in the privacy auditing literature provide lower bounds for the latter, while our metric provides an empirical lower bound for the former by relying on an (${\epsilon}$, ${\delta}$)-type of quantification of the privacy of the trained model instance. We establish a relationship between these lower bounds and show how to implement Epsilon* to avoid numerical and noise amplification instability. We further show in experiments on benchmark public data sets that Epsilon* is sensitive to privacy risk mitigation by training with differential privacy (DP), where the value of Epsilon* is reduced by up to 800% compared to the Epsilon* values of non-DP trained baseline models. This metric allows privacy auditors to be independent of model owners, and enables visualizing the privacy-utility landscape to make informed decisions regarding the trade-offs between model privacy and utility.

In many practical applications of differential privacy, practitioners seek to provide the best privacy guarantees subject to a target level of accuracy. A recent line of work by Ligett et al. '17 and Whitehouse et al. '22 has developed such accuracy-first mechanisms by leveraging the idea of noise reduction that adds correlated noise to the sufficient statistic in a private computation and produces a sequence of increasingly accurate answers. A major advantage of noise reduction mechanisms is that the analysts only pay the privacy cost of the least noisy or most accurate answer released. Despite this appealing property in isolation, there has not been a systematic study on how to use them in conjunction with other differentially private mechanisms. A fundamental challenge is that the privacy guarantee for noise reduction mechanisms is (necessarily) formulated as ex-post privacy that bounds the privacy loss as a function of the released outcome. Furthermore, there has yet to be any study on how ex-post private mechanisms compose, which allows us to track the accumulated privacy over several mechanisms. We develop privacy filters [Rogers et al. '16, Feldman and Zrnic '21, and Whitehouse et al. '22'] that allow an analyst to adaptively switch between differentially private and ex-post private mechanisms subject to an overall differential privacy guarantee.

Given a traversal algorithm, cover time is the expected number of steps needed to visit all nodes in a given graph. A smaller cover time means a higher exploration efficiency of traversal algorithm. Although random walk algorithms have been studied extensively in the existing literature, there has been no cover time result for any non-Markovian method. In this work, we stand on a theoretical perspective and show that the negative feedback strategy (a count-based exploration method) is better than the naive random walk search. In particular, the former strategy can locally improve the search efficiency for an arbitrary graph. It also achieves smaller cover times for special but important graphs, including clique graphs, tree graphs, etc. Moreover, we make connections between our results and reinforcement learning literature to give new insights on why classical UCB and MCTS algorithms are so useful. Various numerical results corroborate our theoretical findings., Comment: 25 pages

The preferential attachment model is a natural and popular random graph model for a growing network that contains very well-connected ``hubs''. We study the higher-order connectivity of such a network by investigating the topological properties of its clique complex. We concentrate on the expected Betti numbers, a sequence of topological invariants of the complex related to the numbers of holes of different dimensions. We determine the asymptotic growth rates of the expected Betti numbers, and prove that the expected Betti number at dimension 1 grows linearly fast, while those at higher dimensions grow sublinearly fast. Our theoretical results are illustrated by simulations. (Changes are made in this version to generalize Proposition 14 and to streamline proofs. These changes are shown in blue.), Comment: 28 pages, 8 figures; changes in v2: stylistic changes to improved readability, no change in the mathematical contents; changes in v3: Proposition 14 slightly generalized, proofs streamlined, changes highlighted in blue

We investigate how large deviations events cluster in the framework of an infinite moving average process with light-tailed noise and long memory. The long memory makes clusters larger, and the asymptotic behaviour of the size of the cluster turns out to be described by the first hitting time of a randomly shifted fractional Brownian motion with drift.

We propose kernel PCA as a method for analyzing the dependence structure of multivariate extremes and demonstrate that it can be a powerful tool for clustering and dimension reduction. Our work provides some theoretical insight into the preimages obtained by kernel PCA, demonstrating that under certain conditions they can effectively identify clusters in the data. We build on these new insights to characterize rigorously the performance of kernel PCA based on an extremal sample, i.e., the angular part of random vectors for which the radius exceeds a large threshold. More specifically, we focus on the asymptotic dependence of multivariate extremes characterized by the angular or spectral measure in extreme value theory and provide a careful analysis in the case where the extremes are generated from a linear factor model. We give theoretical guarantees on the performance of kernel PCA preimages of such extremes by leveraging their asymptotic distribution together with Davis-Kahan perturbation bounds. Our theoretical findings are complemented with numerical experiments illustrating the finite sample performance of our methods.

We study an important variant of the stochastic multi-armed bandit (MAB) problem, which takes penalization into consideration. Instead of directly maximizing cumulative expected reward, we need to balance between the total reward and fairness level. In this paper, we present some new insights in MAB and formulate the problem in the penalization framework, where rigorous penalized regret can be well defined and more sophisticated regret analysis is possible. Under such a framework, we propose a hard-threshold UCB-like algorithm, which enjoys many merits including asymptotic fairness, nearly optimal regret, better tradeoff between reward and fairness. Both gap-dependent and gap-independent regret bounds have been established. Multiple insightful comments are given to illustrate the soundness of our theoretical analysis. Numerous experimental results corroborate the theory and show the superiority of our method over other existing methods.

We describe the cluster of large deviations events that arise when one such large deviations event occurs. We work in the framework of an infinite moving average process with a noise that has finite exponential moments., Comment: To appear in the Annals of Applied Probability

In this paper, we provide an extension of confidence sequences for settings where the variance of the data-generating distribution does not exist or is infinite. Confidence sequences furnish confidence intervals that are valid at arbitrary data-dependent stopping times, naturally having a wide range of applications. We first establish a lower bound for the width of the Catoni-style confidence sequences for the finite variance case to highlight the looseness of the existing results. Next, we derive tight Catoni-style confidence sequences for data distributions having a relaxed bounded~$p^{th}-$moment, where~$p \in (1,2]$, and strengthen the results for the finite variance case of~$p =2$. The derived results are shown to better than confidence sequences obtained using Dubins-Savage inequality., Comment: 10 pages

A novel topological-data-analytical (TDA) method is proposed to distinguish, from noise, small holes surrounded by high-density regions of a probability density function. The proposed method is robust against additive noise and outliers. Traditional TDA tools, like those based on the distance filtration, often struggle to distinguish small features from noise, because both have short persistences. An alternative filtration, called the Robust Density-Aware Distance (RDAD) filtration, is proposed to prolong the persistences of small holes of high-density regions. This is achieved by weighting the distance function by the density in the sense of Bell et al. The concept of distance-to-measure is incorporated to enhance stability and mitigate noise. The persistence-prolonging property and robustness of the proposed filtration are rigorously established, and numerical experiments are presented to demonstrate the proposed filtration's utility in identifying small holes., Comment: 39 pages, 38 figs, J Appl. and Comput. Topology (2024). GitHub: [github.com/c-siu/RDAD]. Published version: [rdcu.be/dCXLa]. Diff of v2/3: added publication info, NO post-submission improvements (Cor2-3 rephrased and proven, setup of Sec4.1 explained, complexity computed in Sec6.1, Thm5 simplified, comparison with DTM in Sec1,8, streamlining), so no change in pdf. Diff of v1/2: more thms, more discussion on conformality, fewer egs

We consider the multi-parameter random simplicial complex as a higher dimensional extension of the classical Erd\"os-R\'enyi graph. We investigate appearance of "unusual" topological structures in the complex from the point of view of large deviations. We first study upper tail large deviation probabilities for subcomplex counts, deriving the order of magnitude of such probabilities at the logarithmic scale precision. The obtained results are then applied to analyze large deviations for the number of simplices at the critical dimension and below. Finally, these results are also used to deduce large deviation estimates for Betti numbers of the complex in the critical dimension.

A surprising result of Pillai and Meng (2016) showed that a transformation $\sum_{j=1}^n w_j X_j/Y_j$ of two iid centered normal random vectors, $(X_1,\ldots, X_n)$ and $(Y_1,\ldots, Y_n)$, $n>1$, for any weights $0\leq w_j\leq 1$, $ j=1,\ldots, n$, $\sum_{j=1}^n w_j=1$, has a Cauchy distribution regardless of any correlations within the normal vectors. The correlations appear to lose out in the competition with the heavy tails. To clarify how extensive this phenomenon is, we analyze two other transformations of two iid centered normal random vectors. These transformations are similar in spirit to the transformation considered by Pillai and Meng (2016). One transformation involves absolute values: $\sum_{j=1}^n w_j X_j/|Y_j|$. The second involves randomly stopped Brownian motions: $\sum_{j=1}^n w_j X_j\bigl(Y_j^{-2}\bigr)$, where $\bigl\{\bigl( X_1(t),\ldots, X_n(t)\bigr), \, t\geq 0\bigr\},\ n>1,$ is a Brownian motion with positive variances; $(Y_1,\ldots, Y_n)$ is a centered normal random vector with the same law as $( X_1(1),\ldots, X_n(1))$ and independent of it; and $X(Y^{-2})$ is the value of the Brownian motion $X(t)$ evaluated at the random time $t=Y^{-2}$. All three transformations result in a Cauchy distribution if the covariance matrix of the normal components is diagonal, or if all the correlations implied by the covariance matrix equal 1. However, while the transformation Pillai and Meng (2016) considered produces a Cauchy distribution regardless of the normal covariance matrix. the transformations we consider here do not always produce a Cauchy distribution. The correlations between jointly normal random variables are not always overwhelmed by the heaviness of the marginal tails. The mysteries of the connections between normal and Cauchy laws remain to be understood.

We propose a spectral clustering algorithm for analyzing the dependence structure of multivariate extremes. More specifically, we focus on the asymptotic dependence of multivariate extremes characterized by the angular or spectral measure in extreme value theory. Our work studies the theoretical performance of spectral clustering based on a random $k$-nearest neighbor graph constructed from an extremal sample, i.e., the angular part of random vectors for which the radius exceeds a large threshold. In particular, we derive the asymptotic distribution of extremes arising from a linear factor model and prove that, under certain conditions, spectral clustering can consistently identify the clusters of extremes arising in this model. Leveraging this result we propose a simple consistent estimation strategy for learning the angular measure. Our theoretical findings are complemented with numerical experiments illustrating the finite sample performance of our methods.

We consider a multi-armed bandit problem motivated by situations where only the extreme values, as opposed to expected values in the classical bandit setting, are of interest. We propose distribution free algorithms using robust statistics and characterize the statistical properties. We show that the provided algorithms achieve vanishing extremal regret under weaker conditions than existing algorithms. Performance of the algorithms is demonstrated for the finite-sample setting using numerical experiments. The results show superior performance of the proposed algorithms compared to the well known algorithms.

Extremal clusters of stationary processes with long memory can be quite intricate. For certain stationary infinitely divisible processes with subexponential tails, including both power-like tails and certain lighter tails, e.g. lognormal-like tails, such clusters may take the shape of stable regenerative sets. In this paper we show that for semi-exponential tails, which are even lighter, a new shape of extremal clusters arises. In this case each stable regenerative set supports a random panoply of varying extremes., Comment: 41 pages

We make an observation that facilitates exact likelihood-based inference for the parameters of the popular ARFIMA model without requiring stationarity by allowing the upper bound $\bar{d}$ for the memory parameter $d$ to exceed $0.5$. We observe that estimating the parameters of a single non-stationary ARFIMA model is equivalent to estimating the parameters of a sequence of stationary ARFIMA models, which allows for the use of existing methods for evaluating the likelihood for an invertible and stationary ARFIMA model. This enables improved inference because many standard methods perform poorly when estimates are close to the boundary of the parameter space. It also allows us to leverage the wealth of likelihood approximations that have been introduced for estimating the parameters of a stationary process. We explore how estimation of the memory parameter $d$ depends on the upper bound $\bar{d}$ and introduce adaptive procedures for choosing $\bar{d}$. Via simulations, we examine the performance of our adaptive procedures for estimating the memory parameter when the true value is as large as $2.5$. Our adaptive procedures estimate the memory parameter well, can be used to obtain confidence intervals for the memory parameter that achieve nominal coverage rates, and perform favorably relative to existing alternatives.

We study clustering of the extremes in a stationary sequence with subexponential tails in the maximum domain of attraction of the Gumbel We obtain functional limit theorems in the space of random sup-measures and in the space $D(0,\infty)$. The limits have the Gumbel distribution if the memory is only moderately long. However, as our results demonstrate rather strikingly, the "heuristic of a single big jump" could fail even in a moderately long range dependence setting. As the tails become lighter, the extremal behavior of a stationary process may depend on multiple large values of the driving noise.

Topological study of existing random simplicial complexes is non-trivial and has led to several seminal works. However, the applicability of such studies is limited since the randomness there is usually governed by a single parameter. With this in mind, we focus here on the topology of the recently proposed multi-parameter random simplicial complex and, more importantly, of its dynamic analogue that we introduce here. In this dynamic setup, the temporal evolution of simplices is determined by stationary and possibly non-Markovian processes with a renewal structure. The dynamic versions of the clique complex and the Linial-Meshulum complex are special cases of our setup. Our key result concerns the regime where face-counts of a particular dimension dominate. We show that the Betti numbers corresponding to this dimension and the Euler characteristic satisfy functional strong law of large numbers and functional central limit theorems. Surprisingly, in the latter result, the limiting Gaussian process depends only upon the dynamics in the smallest non-trivial dimension., Comment: 42 pages, 1 figure

In this short note we study the asymptotic behaviour of the minima over compact intervals of Gaussian processes, whose paths are not necessarily smooth. We show that, beyond the logarithmic large deviation Gaussian estimates, this problem is closely related to the classical small-ball problem. Under certain conditions we estimate the term describing the correction to the large deviation behaviour. In addition, the asymptotic distribution of the location of the minimum, conditionally on the minimum exceeding a high threshold, is also studied., Comment: A few typos are corrected. The paper will appear in Electronic Communications in Probability

We study the extremes for a class of a symmetric stable random fields with long range dependence. We prove functional extremal theorems both in the space of sup measures and in the space of cadlag functions of several variables. The limits in both types of theorems are of a new kind, and only in a certain range of parameters these limits have the Fr\'{e}chet distribution.

We study the extremes of multivariate regularly varying random fields. The crucial tools in our study are the tail field and the spectral field, notions that extend the tail and spectral processes of Basrak and Segers (2009). The spatial context requires multiple notions of extremal index, and the tail and spectral fields are applied to clarify these notions and other aspects of extremal clusters. An important application of the techniques we develop is to the Brown-Resnick random fields., Comment: 1 figure

Given an iid sequence of pairs of stochastic processes on the unit interval we construct a measure of independence for the components of the pairs. We define distance covariance and distance correlation based on approximations of the component processes at finitely many discretization points. Assuming that the mesh of the discretization converges to zero as a suitable function of the sample size, we show that the sample distance covariance and correlation converge to limits which are zero if and only if the component processes are independent. To construct a test for independence of the discretized component processes we show consistency of the bootstrap for the corresponding sample distance covariance/correlation., Comment: 41 pages, original article

In this paper we are concerned with the analysis of heavy-tailed data when a portion of the extreme values is unavailable. This research was motivated by an analysis of the degree distributions in a large social network. The degree distributions of such networks tend to have power law behavior in the tails. We focus on the Hill estimator, which plays a starring role in heavy-tailed modeling. The Hill estimator for this data exhibited a smooth and increasing "sample path" as a function of the number of upper order statistics used in constructing the estimator. This behavior became more apparent as we artificially removed more of the upper order statistics. Building on this observation we introduce a new version of the Hill estimator. It is a function of the number of the upper order statistics used in the estimation, but also depends on the number of unavailable extreme values. We establish functional convergence of the normalized Hill estimator to a Gaussian process. An estimation procedure is developed based on the limit theory to estimate the number of missing extremes and extreme value parameters including the tail index and the bias of Hill's estimator. We illustrate how this approach works in both simulations and real data examples.

We investigate the randomized Karlin model with parameter $\beta\in(0,1)$, which is based on an infinite urn scheme. It has been shown before that when the randomization is bounded, the so-called odd-occupancy process scales to a fractional Brownian motion with Hurst index $\beta/2\in(0,1/2)$. We show here that when the randomization is heavy-tailed with index $\alpha\in(0,2)$, then the odd-occupancy process scales to a $(\beta/\alpha)$-self-similar symmetric $\alpha$-stable process with stationary increments., Comment: 16 pages; minor revision

Our contribution is to widen the scope of extreme value analysis applied to discrete-valued data. Extreme values of a random variable $X$ are commonly modeled using the generalized Pareto distribution, a method that often gives good results in practice. When $X$ is discrete, we propose two other methods using a discrete generalized Pareto and a generalized Zipf distribution respectively. Both are theoretically motivated and we show that they perform well in estimating rare events in several simulated and real data cases such as word frequency, tornado outbreaks and multiple births.

The distance covariance of two random vectors is a measure of their dependence. The empirical distance covariance and correlation can be used as statistical tools for testing whether two random vectors are independent. We propose an analogs of the distance covariance for two stochastic processes defined on some interval. Their empirical analogs can be used to test the independence of two processes., Comment: Contribution to T. Rolski special issue of Probability and Mathematical Statistics

We prove limit theorems of an entirely new type for certain long memory regularly varying stationary infinitely divisible random processes. These theorems involve multiple phase transitions governed by how long the memory is. Apart from one regime, our results exhibit limits that are not among the classical extreme value distributions. Restricted to the one-dimensional case, the distributions we obtain interpolate, in the appropriate parameter range, the $\alpha$-Fr\'echet distribution and the skewed $\alpha$-stable distribution. In general, the limit is a new family of stationary and self-similar random sup-measures with parameters $\alpha\in(0,\infty)$ and $\beta\in(0,1)$, with representations based on intersections of independent $\beta$-stable regenerative sets. The tail of the limit random sup-measure on each interval with finite positive length is regularly varying with index $-\alpha$. The intriguing structure of these random sup-measures is due to intersections of independent $\beta$-stable regenerative sets and the fact that the number of such sets intersecting simultaneously increases to infinity as $\beta$ increases to one. The results in this paper extend substantially previous investigations where only $\alpha\in(0,2)$ and $\beta\in(0,1/2)$ have been considered., Comment: 29 pages. A major revision that in particular corrected mistakes in the previous version

We investigate what happens when an entire sample path of a smooth Gaussian process on a compact interval lies above a high level. Specifically, we determine the precise asymptotic probability of such an event, the extent to which the high level is exceeded, the conditional shape of the process above the high level, and the location of the minimum of the process given that the sample path is above a high level., Comment: 31 pages, 1 figure. To appear in Stochastic Processes and their Applications

We propose a new definition of a multivariate subexponential distribution. We compare this definition with the two existing notions of multivariate subexponentiality, and compute the asymptotic behaviour of the ruin probability in the context of an insurance portfolio, when multivariate subexponentiality holds. Previously such results were available only in the case of multivariate regularly varying claims.

Preferential attachment is a widely adopted paradigm for understanding the dynamics of social networks. Formal statistical inference,for instance GLM techniques, and model verification methods will require knowing test statistics are asymptotically normal even though node or count based network data is nothing like classical data from independently replicated experiments. We therefore study asymptotic normality of degree counts for a sequence of growing simple undirected preferential attachment graphs. The methods of proof rely on identifying martingales and then exploiting the martingale central limit theorems.

We prove a functional central limit theorem for partial sums of symmetric stationary long range dependent heavy tailed infinitely divisible processes with a certain type of negative dependence. Previously only positive dependence could be treated. The negative dependence involves cancellations of the Gaussian second order. This leads to new types of limiting processes involving stable random measures, due to heavy tails, Mittag-Leffler processes, due to long memory, and Brownian motions, due to the Gaussian second order cancellations., Comment: 35 pages

How likely is the high level of a continuous Gaussian random field on an Euclidean space to have a "hole" of a certain dimension and depth? Questions of this type are difficult, but in this paper we make progress on questions shedding new light in existence of holes. How likely is the field to be above a high level on one compact set (e.g. a sphere) and to be below a fraction of that level on some other compact set, e.g. at the center of the corresponding ball? How likely is the field to be below that fraction of the level {\it anywhere} inside the ball? We work on the level of large deviations.

A functional limit theorem for the partial maxima of a long memory stable sequence produces a limiting process that can be described as a $\beta$-power time change in the classical Fr\'echet extremal process, for $\beta$ in a subinterval of the unit interval. Any such power time change in the extremal process for $0<\beta<1$ produces a process with stationary max-increments. This deceptively simple time change hides the much more delicate structure of the resulting process as a self-affine random sup measure. We uncover this structure and show that in a certain range of the parameters this random measure arises as a limit of the partial maxima of the same long memory stable sequence, but in a different space. These results open a way to construct a whole new class of self-similar Fr\'echet processes with stationary max-increments., Comment: Published at http://dx.doi.org/10.3150/15-BEJ717 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

Abel-Tauberian theorems relate power law behavior of distributions and their transforms. We formulate and prove a multivariate version for non-standard regularly varying measures on $\mathbb{R}_+^p$ and then apply it to prove that the joint distribution of in- and out-degree in a directed edge preferential attachement model has jointly regularly varying tails., Comment: 16 pages

For the directed edge preferential attachment network growth model studied by Bollobas et al. (2003) and Krapivsky and Redner (2001), we prove that the joint distribution of in-degree and out-degree has jointly regularly varying tails. Typically the marginal tails of the in-degree distribution and the out-degree distribution have different regular variation indices and so the joint regular variation is non-standard. Only marginal regular variation has been previously established for this distribution in the cases where the marginal tail indices are different.

Regular variation of distributional tails is known to be preserved by various linear transformations of some random structures. An inverse problem for regular variation aims at understanding whether the regular variation of a transformed random object is caused by regular variation of components of the original random structure. In this paper we build up on previous work and derive results in the multivariate case and in situations where regular variation is not restricted to one particular direction or quadrant.