The CUR matrix decomposition is an important extension of Nyström approximation to a general matrix. It approximates any data matrix in terms of a small number of its columns and rows. In this paper we propose a novel randomized CUR algorithm with an expected relative-error bound. The proposed algorithm has the advanta…
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,291 papers · 148 categories
Trend · papers per month
48 results for “relative-error bounds”
Rank-One NMF-Based Initialization for NMF and Relative Error Bounds under a Geometric Assumptionstat.ML
The paper proposes an efficient NMF algorithm using geometric assumptions and rank-one NMFs.
problem Nonnegative matrix factorization (NMF) for clustering and factorization.
method Geometric assumption on data matrices, rank-one NMF initialization, and clustering.
result The proposed algorithm provides faster speeds and comparable relative errors to classical NMF algorithms.
In this paper, we develop a relative error bound for nuclear norm regularized matrix completion, with the focus on the completion of full-rank matrices. Under the assumption that the top eigenspaces of the target matrix are incoherent, we derive a relative upper bound for recovering the best low-rank approximation of t…
A new framework evaluates HTE estimators using relative error.
problem Lack of robust evaluation methods for HTE estimators.
method Proposes a relative error-based evaluation framework and neural network architecture to estimate nuisance parameters and robustly compare HTE estimators.
result Demonstrates reliable comparisons and improved HTE estimation through the proposed framework and learning algorithm.
New GaussianSketch approximates kernel distances with almost relative error and small additive term.
problem Approximating kernel distances between point sets efficiently.
method Truncating Gaussian kernel expansions and using RecursiveTensorSketch.
result Approximates kernel distance with almost -relative error and small additive term.
Develops a method to estimate rare-event probabilities under distributional uncertainty.
problem Distributional uncertainty limits the effectiveness of rare-event simulation techniques.
method Wasserstein distributionally robust rare-event simulation (DRIS) framework.
result DRIS achieves vanishing relative error in estimating rare-event probabilities.
Kernel density estimation (KDE) is a popular statistical technique for estimating the underlying density distribution with minimal assumptions. Although they can be shown to achieve asymptotic estimation optimality for any input distribution, cross-validating for an optimal parameter requires significant computation do…
Improved kernel k-means clustering for large datasets with reduced computational cost.
problem High computational cost of kernel k-means clustering for large datasets.
method Applying linear k-means clustering to a subset of features constructed using rank-restricted Nyström approximation.
result Achieves a 1+ε approximation ratio for kernel k-means cost function.
Paper develops robust neural network sensors for fuel injection quantities.
problem Adversarial noise increases error in standard neural network models for fuel injection measurements.
method Apply provable robust network learning and verification methods to fuel injection measurements.
result Provable robust model reduces mean relative error to 16.5% under sensor noise.
We consider the question of efficient estimation in the tails of Gaussian copulas. Our special focus is estimating expectations over multi-dimensional constrained sets that have a small implied measure under the Gaussian copula. We propose three estimators, all of which rely on a simple idea: identify certain \emph{dom…
Algorithm learns item qualities from noisy comparisons, scaling with graph resistance.
problem Learning item qualities from noisy comparisons.
method Minimax optimal algorithm using comparison graph resistance.
result Algorithm's performance scales with the square root of graph resistance.
Given a real matrix A with n columns, the problem is to approximate the Gram product AA^T by c << n weighted outer products of columns of A. Necessary and sufficient conditions for the exact computation of AA^T (in exact arithmetic) from c >= rank(A) columns depend on the right singular vector matrix of A. For a Monte-…
Let X be a data matrix of rank ρ, whose rows represent n points in d-dimensional space. The linear support vector machine constructs a hyperplane separator that maximizes the 1-norm soft margin. We develop a new oblivious dimension reduction technique which is precomputed and can be applied to any input matrix X. We pr…
Efficiently estimates graphlet statistics in large networks.
problem Limited ability to compute graphlets in massive networks.
method Unbiased estimation framework for graphlets, parallel and scalable.
result Accurate and fast estimation of graphlet statistics in billions of edges networks.
Novel approach for SEM in small samples with .
problem Small sample size and issues in factor-based SEM.
method Reformulates covariance structure into self-covariance and cross-covariance, defines a feasible set with relative error constraint.
result Improved stability and directional information in small-sample settings.
New method preserves unitarity for Schrödinger equation learning, reducing errors and improving time generalization.
problem Learning the evolution operator for time-dependent Schrödinger equation with varying Hamiltonians.
method Linear estimator preserving weak unitarity, with theoretical error bounds and time generalization.
result Achieves up to two orders of magnitude smaller relative errors than existing methods.
We develop embeddings for nonlinear subspaces preserving vector norms.
problem Preserving vector norms in nonlinear subspaces.
method Low-distortion embeddings for subspaces under nonlinear transformations.
result First low-distortion embeddings for a wide class of nonlinear functions.
In recent years, stochastic gradient descent (SGD) methods and randomized linear algebra (RLA) algorithms have been applied to many large-scale problems in machine learning and data analysis. We aim to bridge the gap between these two methods in solving constrained overdetermined linear regression problems---e.g., $\el…
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.
Optimal sampling bounds for various classification losses under different regularization terms.
problem Achieving optimal sampling complexity for classification losses under different regularization terms.
method Proved optimal sampling bounds for a broad class of Lipschitz continuous classification loss functions under various regularization terms.
result Proved upper and lower bounds for regularization, and upper and lower bounds for regularization.
SS-GEN simulates rare events in heavy and light-tailed data.
problem Estimating probabilities of extreme events in multivariate data.
method Self-Similar Generative Estimation (SS-GEN) decomposes tail distribution into radial and angular components.
result SS-GEN generates representative extreme scenarios and estimates rare-event probabilities beyond observed data.
This handbook translates lead time analysis into R code.
problem Tracking divergence in booking lead times over time.
method Translated original article's methodology into R code.
result Demonstrated reproducibility and error bounds in lead time forecasts.
Risks of Large Portfoliosstat.AP
Estimating and assessing the risk of a large portfolio is an important topic in financial econometrics and risk management. The risk is often estimated by a substitution of a good estimator of the volatility matrix. However, the accuracy of such a risk estimator for large portfolios is largely unknown, and a simple ine…
Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimizationcs.LG
The paper studies estimating the normalizing constant using queries to a black-box function in RKHS.
problem Estimating the normalizing constant of a function in a reproducing kernel Hilbert space.
method Combines Bayesian quadrature and Bayesian optimization approaches, considering different levels of difficulty based on the parameter λ.
result The difficulty of estimating the normalizing constant varies between Bayesian quadrature and Bayesian optimization, even with noisy function evaluations.
The paper constructs upper bounds for cost minimization in shallow neural networks.
problem Cost minimization in underparametrized shallow ReLU networks.
method Explicit construction of upper bounds based on the geometric structure of classification data.
result An upper bound on the minimum of the cost function of order , with exact degenerate local minimum in the special case .
New algorithm for weighted low rank approximation with provable guarantees.
problem Weighted low rank approximation (WLRA) is computationally hard.
method Reweights the low rank solution using the weight matrix itself.
result Provably optimal approximation guarantees for WLRA.
Paper proposes machine learning models for more accurate road inspection.
problem Traditional road inspection systems have safety, energy, and cost issues.
method Hybrid machine learning models using surface deflection data from FWD tests.
result CMIS model outperforms other models with APRE=2.3303, AAPRE=11.6768, RMSE=12.0056, and SD=0.0210.
Statistical and Algorithmic Perspectives on Randomized Sketching for Ordinary Least-Squares -- ICMLstat.ML
We consider statistical and algorithmic aspects of solving large-scale least-squares (LS) problems using randomized sketching algorithms. Prior results show that, from an \emph{algorithmic perspective}, when using sketching matrices constructed from random projections and leverage-score sampling, if the number of sampl…
AGMMNs improve learning of copula models by adaptively selecting kernels.
problem Learning dependence structures in copula models.
method Adaptive bandwidth selection for MMD in GMMNs, increasing kernels based on validation loss.
result AGMMNs significantly improve training performance over GMMNs and parametric models.
AGCA approximates angular variation on the unit sphere, reducing extremal dependence problems to eigenanalysis.
problem Approximating angular variation in multivariate extremes.
method Anchored geodesic component analysis (AGCA) approximates angular variation by great subspheres constrained to pass through a chosen reference direction.
result AGCA finds concentrated tail directions in daily equity-portfolio losses, explaining about 91% of anchored variation.
New algorithm reduces ERM problem size while maintaining accuracy.
problem Empirical risk minimization problem size reduction.
method Adaptive Deterministic Uniform-Weight Trimming (ADUWT) algorithm.
result Uniform relative-error approximation for ERM objective.
New method estimates model and uncertainty for efficient control design.
problem Optimal control of systems with unknown dynamics.
method Coarse-ID control procedure using random matrix theory and convex optimization.
result End-to-end bounds on control cost relative error, nearly optimal.
The paper develops a convergence framework for inexact nonconvex and nonsmooth algorithms.
problem Tackles convergence of inexact nonconvex and nonsmooth algorithms.
method Promises pseudo sufficient descent and relative error conditions, and assumes continuity and Kurdyka-Lojasiewicz property.
result Proves the convergence of algorithms to critical points under specific conditions.
Investigation of the Estimation Accuracy of 5 Different Numerical ODE Solvers on 3 Case Studiesmath.NA
Study compares 5 ODE solvers on 3 case studies, finding varying accuracy.
problem Comparing estimation accuracy of 5 ODE solvers on 3 case studies.
method Used 5 different numerical ODE solvers (Euler's, Heun's, Midpoint, Runge-Kutta 4th order, ODE45) on 3 case studies and compared their results.
result Different solvers have varying accuracy depending on the case study.
The dominant language models (LMs) such as n-gram and neural network (NN) models represent sentence probabilities in terms of conditionals. In contrast, a new trans-dimensional random field (TRF) LM has been recently introduced to show superior performances, where the whole sentence is modeled as a random field. In thi…
Study improves sample complexity for finding influential seed nodes in networks.
problem Determining the most influential set of nodes in a network with limited simulations.
method Upper bounds on reachability variance and data-adaptive simulation method.
result Significantly improved upper bound on sample complexity for IM.
We consider radial solutions to the fast diffusion equation on the hyperbolic space for , , . By radial we mean solutions depending only on the geodesic distance from a given point . We investigate their fine asymptotics near…
The article models illiquid stocks using quantum calculus with asymptotic methods.
problem Modeling illiquid financial markets.
method Application of quantum stochastic calculus and asymptotic methods.
result Power series solutions can approximate quantum stochastic processes for longer time frames.
Optimal sketching bounds for sparse linear regression under various loss functions are established.
problem Sparse linear regression under different loss functions.
method Distribution over oblivious sketches for sparse norm regression and hinge-like loss functions.
result Optimal sketching bounds with rows for sparse norm regression and rows for hinge-like loss functions.
Fast ML framework for derivative valuation from volatility surfaces.
problem Derivative valuation from complex volatility surfaces.
method Parameterized SVI model, synthetic market scenarios, Gaussian Process Regressor.
result Very accurate and fast (3-4 orders of magnitude) derivative valuations.
New polynomial-time solutions found for training ReLU networks, mirroring Max-Cut complexity.
problem Training two-layer ReLU neural networks with weight decay regularization.
method Developed a convex formulation and randomized algorithm to find approximate global optimizers.
result First polynomial-time approximation guarantees and hardness of approximation results for regularized ReLU networks.
New estimator for covariance of heavy-tailed data with affine-invariant bound.
problem Estimating covariance of heavy-tailed multivariate distributions.
method Affine-invariant bound for covariance estimation with fourth-order moment requirement.
result Proposed estimator has an affine-invariant bound of in high probability.
This paper shows that one cannot learn the probability of rare events without imposing further structural assumptions. The event of interest is that of obtaining an outcome outside the coverage of an i.i.d. sample from a discrete distribution. The probability of this event is referred to as the "missing mass". The impo…
Portfolio credit risk with Archimedean copulas: asymptotic analysis and efficient simulationq-fin.RM
The paper analyzes portfolio credit risk using Archimedean copulas and introduces efficient simulation methods.
problem Analyzing large losses from credit portfolio defaults with Archimedean copulas.
method Derives asymptotic results and develops variance reduction algorithms for Monte Carlo simulations.
result Proposed algorithms significantly enhance classical Monte Carlo methods for estimating portfolio credit risk.
This work proposes a method to price American basket options using a Markovian projection.
problem Pricing American basket options in high dimensions is computationally expensive.
method Use a stopping rule based on a low-dimensional Markovian projection of the basket's dynamics.
result Approximate the optimal early-exercise boundary in a lower-dimensional space, providing bounds for the option price.
Bitcoin volatility analysis shows decreasing HE with longer sampling periods.
problem Understanding volatility patterns in Bitcoin using different sample sizes.
method Examined Bitcoin data to analyze Hurst exponent (HE) and multifractality.
result HE decreases as sampling period increases, indicating rough volatility.
A fast sketching algorithm solves regularized least squares problems efficiently.
problem Solving large-scale optimization problems with convex or nonconvex regularization.
method Sketching for Regularized Optimization (SRO) algorithm that generates a sketch of the original data matrix and solves the sketched problem.
result General theoretical results for the approximation error between the original and sketched problems, including minimax rates for sparse signal estimation.
Deep learning the Hurst parameter of linear fractional processes and assessing its reliabilitystat.ML
Deep learning improves Hurst parameter estimation for fractional processes.
problem Estimating the Hurst parameter in fractional stochastic processes.
method Training Long Short-Term Memory (LSTM) networks on extensive datasets of fBm, fOU, and lfsm processes.
result LSTM outperforms traditional methods in fBm and fOU processes but has limited accuracy on lfsm.