A central task in the field of quantum computing is to find applications where quantum computer could provide exponential speedup over any classical computer. Machine learning represents an important field with broad applications where quantum computer may offer significant speedup. Several quantum algorithms for discr…
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.
168,657 papers · 148 categories
Trend · papers per month
48 results for “exponential speedup”
Quantum algorithm speeds up learning from big data exponentially.
problem Scalable learning from big data with optimized random features.
method Quantum algorithm for sampling optimized random features.
result Exponential speedup in runtime compared to classical algorithms.
ECD algorithm speeds up non-convex optimization, offering quantum and stochastic enhancements.
problem Non-convex optimization challenges in machine learning.
method Energy Conserving Descent (ECD) algorithm, stochastic ECD dynamics (sECD), quantum ECD Hamiltonian (qECD).
result ECD and its quantum version achieve exponential speedup over gradient descent.
Efficiently approximates Sparse PCA with significant speedups and minor error.
problem Sparse Principal Component Analysis (Sparse PCA) is NP-hard and computationally expensive.
method Approximates the covariance matrix with block-diagonal form, solves sub-problems in each block, and reconstructs the solution.
result Significant computational speedups with minor additive error.
Weight normalization speeds up matrix sensing problems.
problem Matrix sensing with overparameterization.
method Generalized weight normalization with Riemannian optimization.
result WN achieves linear convergence, improving speed and complexity.
Sparse attention model reduces long-context inference time with exponential accuracy guarantees.
problem Efficiently processing long-context queries in large language models.
method Formalizes attention as a projection onto key vectors, analyzes entropic relaxation, and introduces Vashista Sparse Attention.
result Sparse attention concentrates on a constant-size active face, leading to exponential decay of inactive tokens' mass and linear scaling of active face error.
GPA improves LLM training speed by 8.71% for Llama-160M models.
problem Training Large Language Models (LLMs) with high memory overhead and slow convergence.
method Generalized Primal Averaging (GPA) extends Nesterov's method to eliminate memory-intensive two-loop structure.
result GPA achieves up to 10.13% speedup over AdamW in training Llama-1B model.
We design a randomised parallel version of Adaboost based on previous studies on parallel coordinate descent. The algorithm uses the fact that the logarithm of the exponential loss is a function with coordinate-wise Lipschitz continuous gradient, in order to define the step lengths. We provide the proof of convergence …
New method speeds up model selection for complex scientific tasks.
problem Exhaustive model selection is computationally infeasible for large model spaces.
method Branch-and-bound algorithm with non-monotonic criteria.
result Guaranteed identification of optimal models with significant computational speedups.
STRIDE improves explainable AI by efficiently decomposing feature interactions without subset enumeration.
problem Lack of expressive power and high computational cost in existing XAI frameworks.
method STRIDE uses a functional decomposition approach in RKHS, avoiding subset enumeration and focusing on orthogonal components.
result STRIDE achieves a 3.0 times speedup over TreeSHAP and a high R^2 of 0.93 for feature reconstruction.
ProxSkip achieves linear speedup in distributed non-convex optimization.
problem Achieving linear speedup in distributed non-convex optimization.
method Unified convergence analysis for stochastic non-convex, convex, and strongly convex problems.
result ProxSkip achieves linear speedup in the number of nodes under stochastic gradients.
SiD distills pretrained diffusion models into a fast one-step generator.
problem Efficiently distilling pretrained diffusion models into a fast generator.
method Reformulates forward diffusion processes as semi-implicit distributions and uses three score-related identities to create a loss mechanism.
result Achieves high FID performance and significantly reduces generation time.
Quantum computing promises faster finance algorithms.
problem Solving finance problems faster than classical methods.
method Quantum computing applications to finance, including Monte Carlo, portfolio optimization, and machine learning.
result Quantum speedups for finance problems, especially Monte Carlo and portfolio optimization.
A fast method for Lasso and Logistic Lasso problems.
problem Solving Lasso and Logistic Lasso regression problems efficiently.
method Iterative active set approach using solver updates.
result 31.41 times faster on average for compressed sensing.
Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updatescs.LG
New insights explain speedup saturation in distributed learning with large batches and delays.
problem Understanding and optimizing speedup in distributed learning with large batches and delays.
method Theoretical analysis of strongly convex, convex, and non-convex settings, considering data sparsity.
result Identification of a data-dependent parameter explaining speedup saturation in both batch size and gradient staleness.
Quantum computing offers a quadratic speedup for estimating non-linear functionals.
problem Estimating non-linear functionals of probability distributions.
method Proposes a quantum-inside-quantum Monte Carlo algorithm for a broad class of non-linear estimation problems.
result Achieves a quadratic speedup for non-linear estimation problems, including nested conditional expectations and stochastic optimization.
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…
Predicting structured outputs can be computationally onerous due to the combinatorially large output spaces. In this paper, we focus on reducing the prediction time of a trained black-box structured classifier without losing accuracy. To do so, we train a speedup classifier that learns to mimic a black-box classifier u…
Quantum algorithm speeds up nested expectation estimation by nearly quadratically.
problem Estimating repeatedly nested expectations with quantum computing.
method Proposes a quantum algorithm achieving nearly quadratic speedup over classical methods.
result Achieves nearly quadratic speedup for RNEs, up to logarithmic factors.
Federated Q-Learning achieves linear regret speedup with low communication cost.
problem Achieving linear regret speedup in federated reinforcement learning without high communication costs.
method Proposed two federated Q-Learning algorithms: FedQ-Hoeffding and FedQ-Bernstein, using event-triggered synchronization, novel step size selection, and concentration inequalities.
result Total regrets achieve linear speedup compared to single-agent counterparts with logarithmic communication cost.
GPU optimization speeds up large-scale classification tasks.
problem Efficiently training large-scale classification models on GPUs.
method Judecious GPU-optimization principles applied to TRON algorithm.
result Significant speedups for logistic regression and SVM classification.
Quantum computing speeds up pricing multi-asset derivatives.
problem Exponential growth in complexity for multi-asset derivatives pricing.
method Quantum algorithm based on quantum linear system algorithms for FDM.
result Exponential speedup in derivative pricing compared to classical methods.
Two new algorithms speed up TreeSHAP computation for tree-based models.
problem Slow computation of SHAP values on tree-based models.
method Two new algorithms, Fast TreeSHAP v1 and v2, designed to improve computational efficiency.
result Fast TreeSHAP v2 is 2.5x faster than TreeSHAP, with slightly higher memory usage.
A new parallel algorithm speeds up Hawkes process estimation.
problem Slow maximum likelihood estimation for Hawkes processes.
method Parallel prefix scan for sparse transition matrices.
result Massive speedup with complexity.
New algorithm achieves linear speedup in non-i.i.d. federated bilevel learning.
problem Linear speedup in convergence for non-i.i.d. datasets in federated bilevel optimization.
method Proposes FedMBO with a novel client sampling scheme for non-i.i.d. datasets.
result Achieves a convergence rate of O(1/√(nK) + 1/K + √n/K³/²).
Under appropriate cooperation protocols and parameter choices, fully decentralized solutions for stochastic optimization have been shown to match the performance of centralized solutions and result in linear speedup (in the number of agents) relative to non-cooperative approaches in the strongly-convex setting. More re…
System learns optimizer hyperparameters to generalize across tasks.
problem Lack of generalization in learning optimizers for neural networks.
method Generalization-first approach, learning optimizer hyperparameters.
result System outperforms Adam on various tasks, including unseen modalities.
The impact of the maximally possible batch size (for the better runtime) on performance of graphic processing units (GPU) and tensor processing units (TPU) during training and inference phases is investigated. The numerous runs of the selected deep neural network (DNN) were performed on the standard MNIST and Fashion-M…
With the increase in the amount of data and the expansion of model scale, distributed parallel training becomes an important and successful technique to address the optimization challenges. Nevertheless, although distributed stochastic gradient descent (SGD) algorithms can achieve a linear iteration speedup, they are l…
Quantum algorithms speed up derivative pricing beyond Black-Scholes models.
problem Quantum speedups for derivative pricing beyond Black-Scholes models.
method Utilizing fast-forwardability and quantum Milstein sampler for non-GBM models, and improved numerical integration for GBM and CIR models.
result Quadratic speedups for derivative pricing in practical models like CIR and Heston's model.
ForestPrune optimizes tree ensemble pruning for compactness and speed.
problem Large tree ensembles in predictive models consume excessive memory and reduce interpretability.
method Developed a specialized optimization algorithm to efficiently prune tree ensembles by depth layers.
result ForestPrune produces compact, high-performing models that outperform existing post-processing methods.
Unified analysis of Federated Averaging and Nesterov FedAvg for linear speedup.
problem Understanding convergence of FL algorithms under non-i.i.d. data and partial participation.
method Systematic study of convergence guarantees for FedAvg and Nesterov FedAvg under different conditions.
result Unified analysis of linear speedup for FedAvg and Nesterov FedAvg in various settings.
ML-EM method speeds up diffusion model sampling.
problem Efficiently sampling from complex diffusion models.
method Multilevel Euler-Maruyama method with UNet approximations.
result Polynomial speedup in sampling from diffusion models.
We develop parallel and distributed Frank-Wolfe algorithms; the former on shared memory machines with mini-batching, and the latter in a delayed update framework. Whenever possible, we perform computations asynchronously, which helps attain speedups on multicore machines as well as in distributed environments. Moreover…
Novel periodic momentum SGD method for decentralized training with linear speedup.
problem Lack of effective momentum schema in decentralized training methods.
method Proposes a novel periodic decentralized momentum SGD method.
result Achieves linear speedup in decentralized training.
Orders-of-magnitude speedup in atmospheric chemistry modeling through neural network-based emulationphysics.ao-ph
Chemical transport models (CTMs), which simulate air pollution transport, transformation, and removal, are computationally expensive, largely because of the computational intensity of the chemical mechanisms: systems of coupled differential equations representing atmospheric chemistry. Here we investigate the potential…
Latent DiTs improve data distribution recovery and inference efficiency under low-dimensional latent space.
problem Improving data distribution recovery and inference efficiency in latent DiTs.
method Investigates statistical and computational limits of latent DiTs under low-dimensional latent space assumption, deriving approximation error bounds, sample complexity, and efficient inference and training algorithms.
result Latent DiTs can bypass high dimensionality challenges and achieve almost-linear time inference and training.
Quantum algorithm speeds up MIP solving by a near-quadratic factor.
problem Solving Mixed Integer Programs (MIPs) efficiently.
method Incremental-Quantum-Branch-and-Bound algorithm combining quantum speedup with classical search heuristics.
result Universal near-quadratic speedup over classical Branch-and-Bound algorithms.
Speeds up deep neural networks training by 10x using GPU concurrency.
problem Training deep residual neural networks efficiently.
method Layer-wise parallel training with GPU concurrency and Nonlinear Multigrid.
result 10.2x speedup over traditional techniques.
Machine Learning as a Service (MLaaS) is enabling a wide range of smart applications on end devices. However, such convenience comes with a cost of privacy because users have to upload their private data to the cloud. This research aims to provide effective and efficient MLaaS such that the cloud server learns nothing …
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…
Markov logic networks (MLNs) reconcile two opposing schools in machine learning and artificial intelligence: causal networks, which account for uncertainty extremely well, and first-order logic, which allows for formal deduction. An MLN is essentially a first-order logic template to generate Markov networks. Inference …
DPM-Solver speeds up DPM sampling to 10-20 function evaluations.
problem Slow sampling from Diffusion Probabilistic Models (DPMs).
method Exact formulation of diffusion ODE solutions, using change-of-variable and exponentially weighted integral.
result Generates high-quality samples in 10-20 function evaluations.
New GPU kernels boost deep learning speed and memory efficiency.
problem Sparse deep learning matrices are not well-suited for existing sparse kernels.
method Identified favorable properties of sparse matrices from deep learning, developed high-performance GPU kernels for sparse matrix operations.
result 27% of single-precision peak performance on Nvidia V100 GPUs achieved with new kernels.
Asynchronous SGD can speed up training with a trade-off of gradient staleness.
problem Asynchronous SGD suffers from gradient staleness, affecting convergence error.
method Theoretical analysis of the error-runtime trade-off considering random straggling delays.
result A method of gradually varying synchronicity in distributed SGD is proposed and demonstrated.
New algorithm speeds up polynomial kernel approximations.
problem Efficiently approximating polynomial kernels of high degree.
method Oblivious sketching combined with novel sampling.
result Polynomial factor slowdown removed in running time.
SliceOut speeds up deep learning training without sacrificing accuracy.
problem Frequent model re-training and large model training workloads in deep learning.
method SliceOut uses dropout-inspired scheme to drop contiguous sets of units at random, leveraging GPU memory layout.
result 10-40% speedups and memory reduction with minimal accuracy loss.
Quantum algorithm speeds up Lasso regression by quadratically faster per iteration.
problem Efficiently solving high-dimensional linear regression with L1-penalty.
method Pathwise LARS algorithm adapted for quantum computing, using minimum-finding subroutines.
result Quadratic speedup in computation time for both number of features and observations.