This note gives a simple analysis of a randomized approximation scheme for matrix multiplication proposed by Sarlos (2006) based on a random rotation followed by uniform column sampling. The result follows from a matrix version of Bernstein's inequality and a tail inequality for quadratic forms in subgaussian random ve…
On-device research index
arXiv research
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “Randomization Scheme”
This paper explores how random sampling and coding can speed up approximate matrix multiplication.
problem Efficiently computing large-scale matrix multiplications in distributed systems.
method Proposes two schemes: coding for recovery and random sampling for approximation.
result Investigates tradeoffs between recovery threshold and approximation error.
New method uses randomized sparse neural networks to solve time-dependent PDEs more accurately and efficiently.
problem Numerical challenges in training neural networks sequentially in time to solve time-dependent PDEs.
method Introduces Neural Galerkin schemes that update randomized sparse subsets of network parameters at each time step.
result Up to two orders of magnitude more accurate and two orders of magnitude faster than dense update schemes.
Optimized sampling scheme for compressed sensing combining randomness and determinism.
problem Improving compressed sensing performance with deterministic sampling.
method Optimized sampling scheme combining random and deterministic selection of rows.
result Measurable improvements in image compressed sensing for generative and sparse priors.
New gradient coding schemes reduce decoding error in both random and adversarial straggler settings.
problem Creating efficient approximate gradient coding schemes for distributed optimization.
method Introduced novel approximate gradient codes based on expander graphs, achieving optimal decoding coefficients.
result Achieved nearly optimal error in random setting and nearly half the error in adversarial setting compared to existing codes.
Improved Random Forests detect pure interactions better.
problem Random Forests struggle with certain pure interactions.
method Alternative partitioning schemes during tree construction.
result Improved Random Forests enhance fitting ability in scenarios with pure interactions.
New high-order approximations for CIR process using random grids.
problem Approximating the Cox-Ingersoll-Ross process with high order.
method Combining discretization schemes on different random grids.
result Weak approximations of order for all .
Bilateral Random Projectionsstat.ML
Low-rank structure have been profoundly studied in data mining and machine learning. In this paper, we show a dense matrix 's low-rank approximation can be rapidly built from its left and right random projections and , or bilateral random projection (BRP). We then show power scheme can further…
New schemes improve error estimates for sampling from non-log-concave distributions.
problem Improving sampling from non-log-concave distributions with super-linear drift growth.
method Developed tamed Euler and randomized Euler schemes with error estimates.
result Near-optimal error bounds for sampling and optimization problems.
The method of random projections has become a standard tool for machine learning, data mining, and search with massive data at Web scale. The effective use of random projections requires efficient coding schemes for quantizing (real-valued) projected data into integers. In this paper, we focus on a simple 2-bit coding …
Study different masking schemes for a universal marginaliser.
problem Understand how well a neural approximator learns conditional distributions.
method Compare networks trained with various masking schemes.
result Neural approximators perform differently based on the masking scheme.
Aggregates predictions from multiple regression models using random projections and kernel methods.
problem Combining predictions from multiple regression models to improve accuracy.
method Random projection of high-dimensional feature space, followed by kernel-based consensual aggregation.
result The aggregation scheme performs similarly to using the original high-dimensional features, with high probability.
We consider the binary classification problem when data are large and subject to unknown but bounded uncertainties. We address the problem by formulating the nonlinear support vector machine training problem with robust optimization. To do so, we analyze and propose two bounding schemes for uncertainties associated to …
New sampling scheme improves privacy in DP-SGD without sacrificing utility.
problem Suboptimal privacy amplification due to participation variance in Poisson subsampling.
method Balanced Iteration Subsampling (BIS) with structured randomness.
result BIS achieves stronger privacy amplification than Poisson subsampling and is optimal at both extremes of noise spectrum.
New defense mechanism RS outperforms existing schemes in protecting against adversarial examples.
problem Adversarial examples trick classifiers into misclassification.
method Proposed a new defense mechanism called Random Spiking (RS) and an evaluation framework.
result Random Spiking (RS) delivers better protection against adversarial examples than many existing schemes.
Study shows different initialization schemes for LoRA finetuning impact performance.
problem The impact of initialization schemes on LoRA finetuning performance.
method Compared two initialization schemes: B=0, A=random vs. A=0, B=random.
result First initialization scheme yields better performance on average.
Two new coding schemes improve the efficient communication of noisy data.
problem Efficient communication of noisy data in machine learning.
method Ordered Random Coding (ORC) and Hybrid Coding Scheme.
result Improved coding schemes over existing approaches.
1) We introduce random discrete Morse theory as a computational scheme to measure the complicatedness of a triangulation. The idea is to try to quantify the frequence of discrete Morse matchings with a certain number of critical cells. Our measure will depend on the topology of the space, but also on how nicely the spa…
Hash codes are efficient data representations for coping with the ever growing amounts of data. In this paper, we introduce a random forest semantic hashing scheme that embeds tiny convolutional neural networks (CNN) into shallow random forests, with near-optimal information-theoretic code aggregation among trees. We s…
We develop high-order approximations for the Heston model.
problem Modeling the Heston model with high accuracy and efficiency.
method Combining approximation schemes on different random grids to achieve any order of convergence.
result Achieve any order of convergence for the Heston model.
Recursive nearest agglomeration (ReNA): fast clustering for approximation of structured signalsstat.ML
In this work, we revisit fast dimension reduction approaches, as with random projections and random sampling. Our goal is to summarize the data to decrease computational costs and memory footprint of subsequent analysis. Such dimension reduction can be very efficient when the signals of interest have a strong structure…
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. …
Novel framework improves randomized smoothing for various norms.
problem Developing robust defenses against adversarial attacks.
method Proposed a novel framework for devising and analyzing randomized smoothing schemes.
result Significantly improved certified accuracy in ℓ1 on standard datasets.
This paper develops quantization algorithms for random Fourier features, simplifying the process and improving performance.
problem Efficient quantization of random Fourier features for better performance and storage.
method Developed Lloyd-Max (LM) and LM-RFF quantization schemes for random Fourier features.
result The marginal distribution of RFF is independent of the Gaussian kernel parameter γ, simplifying quantization design.
New method compresses random forest models for efficient storage.
problem Large storage requirements for ensemble models like random forests.
method Probabilistic modeling of trees followed by model clustering.
result High compression rates and perfect reconstruction of original ensembles.
Bayesian optimization uses triangulation candidates for better performance.
problem Non-convex and multi-modal optimization challenges in Bayesian optimization.
method Proposes using Delaunay triangulation candidates for discrete search over continuous optimization.
result Triangulation candidates outperform numerically optimized and random alternatives.
Unified theory and debiasing framework for random oblique projections in high dimensions.
problem Systematic statistical bias in random oblique projections induced by sampling.
method Unified non-asymptotic theory and debiasing framework.
result Sharp bias--variance characterizations and improved approximation accuracy.
Improved statistical computation through efficient matrix sampling.
problem Reducing computational cost in large-scale statistical methods.
method Accumulative sub-sampling method to improve statistical efficiency.
result Effective matrix size control improves computational efficiency.
This paper proposes a framework for certifying neural network defenses against data poisoning attacks.
problem Vulnerability of neural networks to data poisoning attacks.
method Random selection based defenses that average predictions on sub-datasets sampled from the training set.
result The certified radius of bagging derived by the framework is tighter than previous work.
Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatestat.ML
Many modern machine learning models are trained to achieve zero or near-zero training error in order to obtain near-optimal (but non-zero) test error. This phenomenon of strong generalization performance for "overfitted" / interpolated classifiers appears to be ubiquitous in high-dimensional data, having been observed …
Hash codes are a very efficient data representation needed to be able to cope with the ever growing amounts of data. We introduce a random forest semantic hashing scheme with information-theoretic code aggregation, showing for the first time how random forest, a technique that together with deep learning have shown spe…
Boosts change-point detection power with optimal sub-sampling.
problem Power loss in sequential change-point detection from large history data.
method Optimal sub-sampling of history data before kernel-based detection procedures.
result Improved detection performance in extensive experiments.
Hashing is a basic tool for dimensionality reduction employed in several aspects of machine learning. However, the perfomance analysis is often carried out under the abstract assumption that a truly random unit cost hash function is used, without concern for which concrete hash function is employed. The concrete hash f…
We present a new random sampling strategy for k-bandlimited signals defined on graphs, based on determinantal point processes (DPP). For small graphs, ie, in cases where the spectrum of the graph is accessible, we exhibit a DPP sampling scheme that enables perfect recovery of bandlimited signals. For large graphs, ie, …
The paper analyzes the Spectral Method for clustering data points on Union of Subspaces.
problem Clustering data points on Union of Subspaces.
method Constructing a Random Geometry Graph (Subspace Clustering) and analyzing it using spectral methods.
result Established a theory to analyze the Spectral Method's efficiency on Union of Subspaces.
RGBM improves GBM efficiency with randomization.
problem Limited theoretical understanding of Gradient Boosting Machine.
method Randomization scheme to reduce search in weak-learners space.
result RGBM leads to substantial computational gains compared to GBM.
Consider convex optimization problems subject to a large number of constraints. We focus on stochastic problems in which the objective takes the form of expected values and the feasible set is the intersection of a large number of convex sets. We propose a class of algorithms that perform both stochastic gradient desce…
We systematically investigate the problem of representing Markov chains by families of random maps, and which regularity of these maps can be achieved depending on the properties of the probability measures. Our key idea is to use techniques from optimal transport to select optimal such maps. Optimal transport theory a…
SVD-RND detects blurred images better than conventional methods.
problem Blurred images can fool conventional OOD detection schemes.
method Constructs a novel RND-based detector that uses blurred images during training.
result SVD-RND outperforms baseline detectors in various domains.
The problem of using observed correlations to infer causal relations is relevant to a wide variety of scientific disciplines. Yet given correlations between just two classical variables, it is impossible to determine whether they arose from a causal influence of one on the other or a common cause influencing both, unle…
We present algorithms for topic modeling based on the geometry of cross-document word-frequency patterns. This perspective gains significance under the so called separability condition. This is a condition on existence of novel-words that are unique to each topic. We present a suite of highly efficient algorithms based…
Deep learning relies on good initialization schemes and hyperparameter choices prior to training a neural network. Random weight initializations induce random network ensembles, which give rise to the trainability, training speed, and sometimes also generalization ability of an instance. In addition, such ensembles pro…
Simplex Random Featuresstat.ML
A new method for approximating softmax and Gaussian kernels with reduced error.
problem Approximating softmax and Gaussian kernels with low error.
method Simplex Random Features (SimRFs) and SimRFs+.
result SimRFs provide the smallest MSE among weight-independent geometrically-coupled PRF mechanisms.
Sharp asymptotic lower bounds of the expected quadratic variation of discretization error in stochastic integration are given. The theory relies on inequalities for the kurtosis and skewness of a general random variable which are themselves seemingly new. Asymptotically efficient schemes which attain the lower bounds a…
Novel numerical scheme for G-heat equation with uncertainty.
problem Efficiently quantify G-expectation for financial products.
method Proposes a novel numerical scheme for the two-dimensional G-heat equation.
result The scheme is monotonic, stable, and convergent, showing high efficiency.
A new insurance and reinsurance pricing scheme based on realized loss.
problem Determining fair and risk-adjusted insurance premiums.
method Performance-based variable premium scheme with random initial premium adjusted based on realized loss.
result The variable premium scheme reduces reinsurer's total risk exposure compared to expected-value premium.
We introduce an efficient message passing scheme for solving Constraint Satisfaction Problems (CSPs), which uses stochastic perturbation of Belief Propagation (BP) and Survey Propagation (SP) messages to bypass decimation and directly produce a single satisfying assignment. Our first CSP solver, called Perturbed Blief …
A numerical algorithm for fully nonlinear HJB equations: an approach by control randomizationmath.PR
We propose a probabilistic numerical algorithm to solve Backward Stochastic Differential Equations (BSDEs) with nonnegative jumps, a class of BSDEs introduced in [9] for representing fully nonlinear HJB equations. In particular, this allows us to numerically solve stochastic control problems with controlled volatility,…