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.
Algorithm learns polynomials in Gaussian inputs with reduced sample complexity.
A wide range of fundamental machine learning tasks that are addressed by the maximum a posteriori estimation can be reduced to a general minimum conical hull problem. The best-known solution to tackle general minimum conical hull problems is the divide-and-conquer anchoring learning scheme (DCA), whose runtime complexi…
In many recent applications, data is plentiful. By now, we have a rather clear understanding of how more data can be used to improve the accuracy of learning algorithms. Recently, there has been a growing interest in understanding how more data can be leveraged to reduce the required training runtime. In this paper, we…
Paper tackles efficient IRL in offline settings with polynomial samples and runtime.
We show how to efficiently project a vector onto the top principal components of a matrix, without explicitly computing these components. Specifically, we introduce an iterative algorithm that provably computes the projection using few calls to any black-box routine for ridge regression. By avoiding explicit principal …
Algorithm efficiently learns deep ReLU networks with polynomial runtime in depth and parameters.
Algorithm samples from Bingham distribution efficiently.
Neural network learns low-dimensional polynomials with SGD near information-theoretic limit.
Many results in recent years established polynomial time learnability of various models via neural networks algorithms. However, unless the model is linear separable, or the activation is a polynomial, these results require very large networks -- much more than what is needed for the mere existence of a good predictor.…
LDP speeds up causal discovery by partitioning, improving VAS recall and runtime.
Polynomial-time algorithm for near-optimal community detection in graphs.
The vanishing ideal is a set of polynomials that takes zero value on the given data points. Originally proposed in computer algebra, the vanishing ideal has been recently exploited for extracting the nonlinear structures of data in many applications. To avoid overfitting to noisy data, the polynomials are often designe…
We study the computational cost of recovering a unit-norm sparse principal component planted in a random matrix, in either the Wigner or Wishart spiked model (observing either with drawn from the Gaussian orthogonal ensemble, or independent samples from $\mathcal{N}(0, I_n + …
"How much energy is consumed for an inference made by a convolutional neural network (CNN)?" With the increased popularity of CNNs deployed on the wide-spectrum of platforms (from mobile devices to workstations), the answer to this question has drawn significant attention. From lengthening battery life of mobile device…
Near-optimal algorithms for mean estimation and linear regression with Gaussian covariates and Huber contamination.
Support vector machine (SVM) is a particularly powerful and flexible supervised learning model that analyzes data for both classification and regression, whose usual algorithm complexity scales polynomially with the dimension of data space and the number of data points. To tackle the big data challenge, a quantum SVM a…
Study on estimating Gaussian mean with missing data in high dimensions.
Rectified Linear Units (ReLUs) are among the most widely used activation function in a broad variety of tasks in vision. Recent theoretical results suggest that despite their excellent practical performance, in various cases, a substitution with basis expansions (e.g., polynomials) can yield significant benefits from b…
Model predicts counterfactuals under domain shift and inaccessible variables.
New scalable MCMC sampling for nonsymmetric DPPs speeds up computations.
Efficiently plans large MDPs with weak function approximations.
PolyNSD improves Neural Sheaf Diffusion with polynomial operators and spectral rescaling.
Improved robust regression algorithms with faster runtime and better estimation rates.
Algorithm learns halfspaces with Tsybakov noise in polynomial time.
New algorithm speeds up learning of graphical models.
Within the framework of statistical learning theory it is possible to bound the minimum number of samples required by a learner to reach a target accuracy. We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning---for which statistical guarantees are …
New algorithm estimates robust Gaussian covariance in nearly matrix multiplication time.
New algorithm samples from log-concave distributions with high accuracy in polynomial time.
Graph Convolutional Networks (GCNs) have proven to be successful tools for semi-supervised learning on graph-based datasets. For sparse graphs, linear and polynomial filter functions have yielded impressive results. For large non-sparse graphs, however, network training and evaluation becomes prohibitively expensive. B…
Predicts the number of polynomial additions in Buchberger's algorithm using machine learning.
We propose an estimator for the mean of a random vector in that can be computed in time for i.i.d.~samples and that has error bounds matching the sub-Gaussian case. The only assumptions we make about the data distribution are that it has finite mean and covariance; in particular, we mak…
RIn-Close_CVC is an efficient (take polynomial time per bicluster), complete (find all maximal biclusters), correct (all biclusters attend the user-defined level of consistency) and non-redundant (all the obtained biclusters are maximal and the same bicluster is not enumerated more than once) enumerative algorithm for …
The implied volatility is a crucial element of any financial toolbox, since it is used for quoting and the hedging of options as well as for model calibration. In contrast to the Black-Scholes formula its inverse, the implied volatility, is not explicitly available and numerical approximation is required. We propose a …
Vecchia approximations provide the best accuracy-runtime trade-off for Gaussian process approximations.
Stochastic momentum methods trade compute efficiency for serial runtime.
A new bootstrapping method reduces key sizes and runtime in FHE.
Bayesian method predicts runtime metrics for fog manufacturing.
The runtime for Kernel Partial Least Squares (KPLS) to compute the fit is quadratic in the number of examples. However, the necessity of obtaining sensitivity measures as degrees of freedom for model selection or confidence intervals for more detailed analysis requires cubic runtime, and thus constitutes a computationa…
Asynchronous SGD can speed up training with a trade-off of gradient staleness.
The Expectation-Maximization (EM) algorithm is a fundamental tool in unsupervised machine learning. It is often used as an efficient way to solve Maximum Likelihood (ML) estimation problems, especially for models with latent variables. It is also the algorithm of choice to fit mixture models: generative models that rep…
Algorithm decides if two hyperbolic 3-manifolds are homeomorphic.
Computing the permanent of a non-negative matrix is a core problem with practical applications ranging from target tracking to statistical thermodynamics. However, this problem is also #P-complete, which leaves little hope for finding an exact solution that can be computed efficiently. While the problem admits a fully …
Sampling logconcave functions arising in statistics and machine learning has been a subject of intensive study. Recent developments include analyses for Langevin dynamics and Hamiltonian Monte Carlo (HMC). While both approaches have dimension-independent bounds for the underlying processes under s…
New method computes affine normal directions efficiently for sparse polynomials.
New algorithm achieves optimal clustering for sparse centers with high dimensions.
For well over a quarter century, detection systems have been driven by models learned from input features collected from real or simulated environments. An artifact (e.g., network event, potential malware sample, suspicious email) is deemed malicious or non-malicious based on its similarity to the learned model at runt…
Simulating the time-evolution of quantum mechanical systems is BQP-hard and expected to be one of the foremost applications of quantum computers. We consider classical algorithms for the approximation of Hamiltonian dynamics using subsampling methods from randomized numerical linear algebra. We derive a simulation tech…
Separating the short jobs from the long is a known technique to improve scheduling performance. In this paper we describe a method we developed for accurately predicting the runtimes classes of the jobs to enable this separation. Our method uses the fact that the runtimes can be represented as a mixture of overlapping …