A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
This paper simplifies computing higher-order -statistics efficiently.
We study the fundamental tradeoffs between computational tractability and statistical accuracy for a general family of hypothesis testing problems with combinatorial structures. Based upon an oracle model of computation, which captures the interactions between algorithms and data, we establish a general lower bound tha…
Establishes statistical and computational bounds for influence diagnostics.
Noise Sensitivity Exponent controls statistical-computational gaps in learning.
Survey on using low-degree polynomials to assess statistical tasks complexity.
Improved statistical computation through efficient matrix sampling.
Nyström KPCA balances computational efficiency and statistical accuracy.
Study trade-offs between statistical and computational efficiency in variational inference.
Approximate Bayesian Computation (ABC) methods are used to approximate posterior distributions in models with unknown or computationally intractable likelihoods. Both the accuracy and computational efficiency of ABC depend on the choice of summary statistic, but outside of special cases where the optimal summary statis…
Improved computational complexity in statistical models using second-order information.
New computational lower bounds for clustering and related problems.
New method combines score lists using joint CDFs, improving computation.
Study shows computational and statistical gaps in Gaussian Single-Index Models.
A research frontier has emerged in scientific computation, wherein numerical error is regarded as a source of epistemic uncertainty that can be modelled. This raises several statistical challenges, including the design of statistical methods that enable the coherent propagation of probabilities through a (possibly dete…
In these notes we describe heuristics to predict computational-to-statistical gaps in certain statistical problems. These are regimes in which the underlying statistical problem is information-theoretically possible although no efficient algorithm exists, rendering the problem essentially unsolvable for large instances…
A new method uses neural tangent kernel to efficiently compute MMD statistic.
New methods improve statistical accuracy of complex models without high computational cost.
Efficient method for tensor linear form inference with noisy incomplete data.
Statistical query algorithms and low-degree tests are nearly equivalent in high-dimensional hypothesis testing.
Paper explores limits of high-order clustering with planted structures.
Approximate Bayesian computation is an established and popular method for likelihood-free inference with applications in many disciplines. The effectiveness of the method depends critically on the availability of well performing summary statistics. Summary statistic selection relies heavily on domain knowledge and care…
Optimizes ICA performance in high dimensions with computational constraints.
We consider the weakly supervised binary classification problem where the labels are randomly flipped with probability . Although there exist numerous algorithms for this problem, it remains theoretically unexplored how the statistical accuracies and computational efficiency of these algorithms depend on the degr…
Proposes a new method to improve Bayesian computation accuracy using flexible classification.
Big Data bring new opportunities to modern society and challenges to data scientists. On one hand, Big Data hold great promises for discovering subtle population patterns and heterogeneities that are not possible with small-scale data. On the other hand, the massive sample size and high dimensionality of Big Data intro…
We investigate the efficiency of k-means in terms of both statistical and computational requirements. More precisely, we study a Nyström approach to kernel k-means. We analyze the statistical properties of the proposed method and show that it achieves the same accuracy of exact kernel k-means with only a fraction of co…
Sliced Optimal Transport simplifies OT for fast computation.
New insights link diverse statistical problems via secret leakage planted clique.
Paper studies statistical-computational trade-offs in tensor PCA and related problems.
Modern technologies are generating ever-increasing amounts of data. Making use of these data requires methods that are both statistically sound and computationally efficient. Typically, the statistical and computational aspects are treated separately. In this paper, we propose an approach to entangle these two aspects …
How should statistical procedures be designed so as to be scalable computationally to the massive datasets that are increasingly the norm? When coupled with the requirement that an answer to an inferential question be delivered within a certain time budget, this question has significant repercussions for the field of s…
This article is the rejoinder for the paper "Probabilistic Integration: A Role in Statistical Computation?" to appear in Statistical Science with discussion. We would first like to thank the reviewers and many of our colleagues who helped shape this paper, the editor for selecting our paper for discussion, and of cours…
Extends JKO scheme for iterative algorithms with unknown parameters.
Learning representations of data is an important problem in statistics and machine learning. While the origin of learning representations can be traced back to factor analysis and multidimensional scaling in statistics, it has become a central theme in deep learning with important applications in computer vision and co…
Active learning method for ABC statistics selection reduces expert work and improves posterior estimates.
Optimized Franz-Parisi criterion matches SQ lower bounds for various statistical models.
We discuss the relative merits of optimistic and randomized approaches to exploration in reinforcement learning. Optimistic approaches presented in the literature apply an optimistic boost to the value estimate at each state-action pair and select actions that are greedy with respect to the resulting optimistic value f…
Statistical-computational gap found in aligning multiple Gaussian graphs.
Paper introduces a method to assess the statistical reliability of changepoints using selective inference and dynamic programming.
This paper investigates asymptotic behaviors of gradient descent algorithms (particularly accelerated gradient descent and stochastic gradient descent) in the context of stochastic optimization arising in statistics and machine learning where objective functions are estimated from available data. We show that these alg…
The paper tackles statistical and computational challenges in learning correlated reward models.
The scalability of statistical estimators is of increasing importance in modern applications. One approach to implementing scalable algorithms is to compress data into a low dimensional latent space using dimension reduction methods. In this paper we develop an approach for dimension reduction that exploits the assumpt…
Database theory and database practice are typically the domain of computer scientists who adopt what may be termed an algorithmic perspective on their data. This perspective is very different than the more statistical perspective adopted by statisticians, scientific computers, machine learners, and other who work on wh…
The development of cluster computing frameworks has allowed practitioners to scale out various statistical estimation and machine learning algorithms with minimal programming effort. This is especially true for machine learning problems whose objective function is nicely separable across individual data points, such as…
The interplay between computational efficiency and statistical accuracy in high-dimensional inference has drawn increasing attention in the literature. In this paper, we study computational and statistical boundaries for submatrix localization. Given one observation of (one or multiple non-overlapping) signal submatrix…
U-statistics improve gradient estimation in importance-weighted variational inference.
Polynomial-time algorithm finds planted hypercube vectors in Gaussian mixtures.
Lightlike hypersurfaces of a statistical manifold are studied. It is shown that a lightlike hypersurface of a statistical manifold is not a statistical manifold with respect to the induced connections, but the screen distribution has a canonical statistical structure. Some relations between induced geometric objects wi…