Investigates multifractal scaling in critical dynamics of random surfaces.
problem Analyzing multifractal scaling in critical dynamics of random surfaces.
method Examined multifractal scaling in various conformal field theories on random surfaces.
result Higher moments of time variations of the order parameter exhibit multifractal scaling.
Study reveals a universal formula for knotting in random equilateral polygons.
problem Probability of knotting in equilateral random polygons.
method Extensive Monte Carlo simulations with improved algorithms and knot invariants.
result A universal scaling formula for knotting probability with number of edges, involving exponential and power law factors.
Study reveals neural scaling laws in random graphs and natural language models.
problem Understanding the origin of neural scaling laws in complex systems.
method Examined scaling laws in transformers trained on random walks and simplified natural language models.
result Neural scaling laws emerge in the absence of power law structure in data correlations.
Continuous time random walks impose a random waiting time before each particle jump. Scaling limits of heavy tailed continuous time random walks are governed by fractional evolution equations. Space-fractional derivatives describe heavy tailed jumps, and the time-fractional version codes heavy tailed waiting times. Thi…
The Random Parameters model was proposed to explain the structure of the covariance matrix in problems where most, but not all, of the eigenvalues of the covariance matrix can be explained by Random Matrix Theory. In this article, we explore other properties of the model, like the scaling of its PDF as one take larger …
A new algorithm speeds up CP decomposition for large tensors.
problem Efficiently processing large-scale tensors in real-time.
method Randomized online CP decomposition (ROCP) algorithm.
result ROCP reduces computing time and memory usage significantly.
Randomized spectral co-clustering speeds up large-scale directed networks.
problem Co-clustering directed networks efficiently for large-scale data.
method Randomized spectral co-clustering algorithms using random-projection and random-sampling techniques.
result Theoretical and numerical validation of approximation and misclustering error rates.
Optimizer choice affects neural scaling laws, changing the exponent α.
problem The exponent α in neural scaling laws L(N)∝N−α varies with the optimizer used. method Controlled random-feature regression experiments with five optimizer variants and six spectral conditions.
result Preconditioned optimizers yield steeper scaling (larger α), with the α-shift increasing across most of the tested spectral range. Kernel methods are powerful and flexible approach to solve many problems in machine learning. Due to the pairwise evaluations in kernel methods, the complexity of kernel computation grows as the data size increases; thus the applicability of kernel methods is limited for large scale datasets. Random Fourier Features (R…
Efficiently applies NTK to large-scale datasets using random features.
problem Computational limitations of kernel methods for large-scale datasets.
method Proposes a sketching-based algorithm combining random features of arc-cosine kernels to construct an efficient feature map of the NTK.
result Achieves comparable error bounds to exact kernel methods but with significantly reduced feature dimensionality.
Efficiently resolves entities via scaled Ewens--Pitman model.
problem Entity resolution in large datasets.
method Microclustering Ewens--Pitman model with variational inference.
result Significant speed-up in entity resolution with competitive performance.
We develop a new statistical test for comparing variables with varying scales.
problem Comparing variables with different scales in multidimensional spaces.
method Order based on expectations of random variables, generalized stochastic dominance (GSD) order, regularized statistical test, linear optimization, imprecise probability models.
result Validated through multidimensional data from various fields.
New method for online inference using SGD with random scaling.
problem Efficient online inference for SGD parameters.
method Asymptotic pivotal statistics via random scaling.
result Robust and efficient online inference without resampling.
Study reveals an equivalence principle for the spectrum of random inner-product kernel matrices in polynomial scaling.
problem Understanding the spectrum of random kernel matrices in polynomial scaling regimes.
method Investigates random matrices with nonlinear kernel functions applied to inner products of uniformly distributed vectors.
result The spectrum of the random kernel matrix is asymptotically equivalent to a simpler matrix model through free additive convolution.
Ensembles of random-feature models can't outperform a single large model.
problem Finding the optimal balance between model size and ensemble size.
method Deterministic equivalent risk estimates and scaling laws analysis.
result Ensembles of random-feature models achieve near-optimal performance only under specific conditions.
We prove a central limit theorem for the components of the largest eigenvectors of the adjacency matrix of a finite-dimensional random dot product graph whose true latent positions are unknown. In particular, we follow the methodology outlined in \citet{sussman2012universally} to construct consistent estimates for the …
We propose a new method for input variable selection in nonlinear regression. The method is embedded into a kernel regression machine that can model general nonlinear functions, not being a priori limited to additive models. This is the first kernel-based variable selection method applicable to large datasets. It sides…
Ridge regression reveals surprising high-dimensional behaviors via random matrix theory.
problem Understanding power-law scalings in high-dimensional regression models.
method Random matrix theory and free probability.
result Analytic formulas for training and generalization errors derived from S-transform. Training very deep networks is an important open problem in machine learning. One of many difficulties is that the norm of the back-propagated error gradient can grow or decay exponentially. Here we show that training very deep feed-forward networks (FFNs) is not as difficult as previously thought. Unlike when back-pro…
This paper compresses large datasets for efficient machine learning.
problem Efficiently processing large datasets for machine learning.
method Constructing a sketch of the dataset using random features and averaging, then learning from the sketch.
result The approach can perform machine learning tasks without full dataset access, preserving both information and privacy.
Random matrix theory predicts neural representations generalize well.
problem Understanding why neural representations generalize well in practice.
method Applied random matrix theory to kernel regression and neural networks.
result GCV estimator accurately predicts generalization risk in overparameterized settings.
Divide-and-conquer is a general strategy to deal with large scale problems. It is typically applied to generate ensemble instances, which potentially limits the problem size it can handle. Additionally, the data are often divided by random sampling which may be suboptimal. To address these concerns, we propose the $DC^…
In this paper, we study randomized reduction methods, which reduce high-dimensional features into low-dimensional space by randomized methods (e.g., random projection, random hashing), for large-scale high-dimensional classification. Previous theoretical results on randomized reduction methods hinge on strong assumptio…
New method improves robustness of large models without sacrificing accuracy.
problem Improving robustness of large pre-trained models without accuracy loss.
method Multi-scale diffusion denoised smoothing, selectively applying smoothing at multiple noise scales.
result Strong certified robustness at high noise levels with accuracy close to non-smoothed classifiers.
The nowadays massive amounts of generated and communicated data present major challenges in their processing. While capable of successfully classifying nonlinearly separable objects in various settings, subspace clustering (SC) methods incur prohibitively high computational complexity when processing large-scale data. …
RFFNet scales kernel methods to large datasets by learning kernel relevance.
problem Scaling kernel methods to large datasets while maintaining interpretability.
method Designs random Fourier features for ARD kernels and uses first-order stochastic optimization for learning kernel relevances.
result RFFNet achieves low prediction error and identifies relevant features, leading to more interpretable solutions.
Improved kernel ridge regression for large datasets using weighted random binning.
problem Efficiently approximating kernel matrices for large-scale datasets.
method Introduced weighted random binning features for locality sensitive hashing.
result Weighted random binning features generate Gaussian processes of any desired smoothness.
Random projections help in representing sparse graphs efficiently.
problem Efficiently representing sparse graphs of varying sizes and vertex sets.
method Random projection of adjacency matrices to retain graph functionality and properties.
result Random projections can accurately represent graphs of different sizes and vertex sets in the same space.
Two new scalable K-means initialization methods proposed for large-scale clustering.
problem Efficient initialization for large-scale clustering problems.
method Divide-and-conquer approach and random projection method for multiple lower-dimensional subspaces.
result The proposed methods outperform state-of-the-art in large-scale clustering tasks.
We study the use of "sign α-stable random projections" (where 0<α≤2) for building basic data processing tools in the context of large-scale machine learning applications (e.g., classification, regression, clustering, and near-neighbor search). After the processing by sign stable random projections, the inner pr…
We introduce the C++ application and R package ranger. The software is a fast implementation of random forests for high dimensional data. Ensembles of classification, regression and survival trees are supported. We describe the implementation, provide examples, validate the package with a reference implementation, and …
Quantum machine learning tackles large datasets with randomized measurements.
problem Efficiently process large, high-dimensional datasets on quantum computers.
method Randomized measurements to scale linearly with dataset size and quadratic for post-processing.
result Substantial speed-up for noisy quantum computers, enabling image classification.
Survey on random features for kernel approximation, focusing on algorithms, theory, and practical applications.
problem Efficiently approximating kernel methods for large-scale problems.
method Random features techniques to speed up kernel methods.
result Need for a high number of random features for good approximation quality.
New method scales inference for deep discrete models to thousands of states.
problem Traditional inference limits model capacity for deep discrete models.
method Randomized Dynamic Programming (RDP) algorithms for scaling inference.
result RDP achieves low bias and variance while reducing computation.
Researchers use quantum chaos and RMT to analyze turbulence, revealing unique scaling laws.
problem Understanding the statistical structure and scaling laws of turbulence.
method Applied tools from quantum chaos and Random Matrix Theory to analyze turbulence datasets.
result Turbulence Gram matrices exhibit power-law scalings distinct from classical chaos and random data.
A new method for estimating large-scale linear models with improved precision.
problem Estimating large-scale linear statistical models efficiently.
method Sequential Least-Squares Estimators with Fast Randomized Sketching (SLSE-FRS), integrating Sketch-and-Solve and Iterative-Sketching methods.
result SLSE-FRS produces high-precision estimators, outperforming state-of-the-art methods.
Large-scale kernel approximation is an important problem in machine learning research. Approaches using random Fourier features have become increasingly popular [Rahimi and Recht, 2007], where kernel approximation is treated as empirical mean estimation via Monte Carlo (MC) or Quasi-Monte Carlo (QMC) integration [Yang …
We propose a novel method designed for large-scale regression problems, namely the two-stage best-scored random forest (TBRF). "Best-scored" means to select one regression tree with the best empirical performance out of a certain number of purely random regression tree candidates, and "two-stage" means to divide the or…
Spectral clustering has been one of the widely used methods for community detection in networks. However, large-scale networks bring computational challenges to the eigenvalue decomposition therein. In this paper, we study the spectral clustering using randomized sketching algorithms from a statistical perspective, whe…
Improved ridge regression with Frequent Directions for large-scale tasks.
problem Improving performance of ridge regression for large-scale data.
method Combines Frequent Directions with iterative optimization schemes.
result Achieves high accuracy in estimating bias and variance for sketched ridge regression.
We uncover scaling laws and statistical structure in complex datasets.
problem Understanding universal traits in complex datasets.
method Analogizing data to physical systems, using statistical physics and RMT.
result Real-world datasets and Gaussian data with long-range correlations share the same RMT universality class.
New tuning rules for Metropolis algorithms derived from Bayesian large-sample asymptotics.
problem Optimal scaling in random-walk Metropolis algorithms under realistic assumptions.
method Large-sample asymptotics to derive weak convergence results and tuning guidelines.
result Tuning guidelines consistent with previous ones when target density is product form, accounting for correlation structure.
Study assesses data-driven and physics-based SGS models for transcritical combustion.
problem Challenges in simulating high-pressure combustion systems due to complex fluid behaviors.
method Comparison of physics-based and random forest machine learning models in turbulent transcritical non-premixed flames.
result Random forest models can effectively model subgrid stresses, providing insight into their formation.
New method trains shallow neural networks with subquadratic width scaling.
problem Training shallow neural networks with optimal width scaling.
method Polyak-Lojasiewicz condition, smoothness, standard data assumptions, random matrix theory.
result Subquadratic scaling on network width with standard initialization strategies.
We study the behavior of untrained neural networks whose weights and biases are randomly distributed using mean field theory. We show the existence of depth scales that naturally limit the maximum depth of signal propagation through these random networks. Our main practical result is to show that random networks may be…
New method for online inference of constrained optimization problems.
problem Online inference of constrained stochastic optimization problems.
method Random scaling of Sketched Stochastic Sequential Quadratic Programming (SSQP).
result Asymptotically valid confidence intervals and matrix-free computation.
ParK efficiently solves kernel ridge regression for large datasets.
problem Large-scale kernel ridge regression efficiency and accuracy.
method Partitioning feature space with random projections and iterative optimization.
result Provably maintains statistical accuracy with reduced space and time complexity.
Network embedding, which learns low-dimensional vector representation for nodes in the network, has attracted considerable research attention recently. However, the existing methods are incapable of handling billion-scale networks, because they are computationally expensive and, at the same time, difficult to be accele…