More Like this

1. Finite dimensional models for extremes of Gaussian and non-Gaussian processes

   H, Xu; M. Grigoriu (January 2022, Probabilistic engineering mechanics)

   Numerical solutions of stochastic problems involving random processes 𝑋(𝑡), which constitutes infinite families of random variables, require to represent these processes by finite dimensional (FD) models 𝑋𝑑 (𝑡), i.e., deterministic functions of time depending on finite numbers 𝑑 of random variables. Most available FD models match the mean, correlation, and other global properties of 𝑋(𝑡). They provide useful information to a broad range of problems, but cannot be used to estimate extremes or other sample properties of 𝑋(𝑡). We develop FD models 𝑋𝑑 (𝑡) for processes 𝑋(𝑡) with continuous samples and establish conditions under which these models converge weakly to 𝑋(𝑡) in the space of continuous functions as 𝑑 → ∞. These theoretical results are illustrated by numerical examples which show that, under the conditions established in this study, samples and extremes of 𝑋(𝑡) can be approximated by samples and extremes of 𝑋𝑑 (𝑡) and that the discrepancy between samples and extremes of these processes decreases with 𝑑. 

   more » « less
2. Finite dimensional (FD) Slepian models for non-Gaussian processes

   https://doi.org/10.1016/j.probengmech.2022.103323  

   M. Grigoriu (June 2022, Probabilistic engineering mechanics)

   Conditions under which samples of continuous stochastic processes 𝑋(𝑡) on bounded time intervals [0, 𝜏] can be represented by samples of finite dimensional (FD) processes 𝑋𝑑 (𝑡) are augmented such that samples of Slepian models 𝑆𝑑,𝑎(𝑡) of 𝑋𝑑 (𝑡) can be used as surrogates for samples of Slepian models 𝑆𝑎(𝑡) of 𝑋(𝑡). FD processes are deterministic functions of time and 𝑑 < ∞ random variables. The discrepancy between target and FD samples is quantified by the metric of the space 𝐶[0, 𝜏] of continuous functions. The numerical illustrations, which include Gaussian/non-Gaussian FD processes and solutions of linear/nonlinear random vibration problems, are consistent with the theoretical findings in the paper. 

   more » « less
3. Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering

   https://doi.org/10.1145/3313276.3316350  

   Makarychev, Konstantin; Makarychev, Yury; Razenshteyn, Ilya (June 2019, Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering)

   Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+ε) under a projection onto a random O(log(k /ε) / ε2)-dimensional subspace. Further, the cost of every clustering is preserved within (1+ε). More generally, our result applies to any dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant p. For k-means, our result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu (STOC 2015); for k-medians, it answers a question raised by Kannan. 

   more » « less
4. Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions

   Asi, Hilal; Liu, Daogao; Tian, Kevin (June 2024, https://doi.org/10.48550/arXiv.2406.02789)

   This paper studies differentially private stochastic convex optimization (DP-SCO) in the presence of heavy-tailed gradients, where only a 𝑘 kth-moment bound on sample Lipschitz constants is assumed, instead of a uniform bound. The authors propose a reduction-based approach that achieves the first near-optimal error rates (up to logarithmic factors) in this setting. Specifically, under ( 𝜖 , 𝛿 ) (ϵ,δ)-approximate differential privacy, they achieve an error bound of 𝐺 2 𝑛 + 𝐺 𝑘 ⋅ ( 𝑑 𝑛 𝜖 ) 1 − 1 𝑘 , n ​ G 2 ​ ​ +G k ​ ⋅( nϵ d ​ ​ ) 1− k 1 ​ , up to a mild polylogarithmic factor in 1 𝛿 δ 1 ​ , where 𝐺 2 G 2 ​ and 𝐺 𝑘 G k ​ are the 2nd and 𝑘 kth moment bounds on sample Lipschitz constants. This nearly matches the lower bound established by Lowy and Razaviyayn (2023). Beyond the basic result, the authors introduce a suite of private algorithms that further improve performance under additional assumptions: an optimal algorithm under a known-Lipschitz constant, a near-linear time algorithm for smooth functions, and an optimal linear-time algorithm for smooth generalized linear models. 

   more » « less
5. Projection‐based techniques for high‐dimensional optimal transport problems

   https://doi.org/10.1002/wics.1587  

   Zhang, Jingyi; Ma, Ping; Zhong, Wenxuan; Meng, Cheng (May 2022, WIREs Computational Statistics)

   Abstract Optimal transport (OT) methods seek a transformation map (or plan) between two probability measures, such that the transformation has the minimum transportation cost. Such a minimum transport cost, with a certain power transform, is called the Wasserstein distance. Recently, OT methods have drawn great attention in statistics, machine learning, and computer science, especially in deep generative neural networks. Despite its broad applications, the estimation of high‐dimensional Wasserstein distances is a well‐known challenging problem owing to the curse‐of‐dimensionality. There are some cutting‐edge projection‐based techniques that tackle high‐dimensional OT problems. Three major approaches of such techniques are introduced, respectively, the slicing approach, the iterative projection approach, and the projection robust OT approach. Open challenges are discussed at the end of the review. This article is categorized under:Statistical and Graphical Methods of Data Analysis > Dimension ReductionStatistical Learning and Exploratory Methods of the Data Sciences > Manifold Learning 

   more » « less