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.
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,742 papers · 148 categories
Trend · papers per month
48 results for “Polynomial speedup”
Quantum machine learning can't achieve polylogarithmic runtimes, even with quantum data access.
problem Bounding the minimum number of samples required for supervised quantum learning.
method Statistical learning theory and quantum machine learning algorithms.
result Quantum machine learning algorithms for supervised learning have at most polynomial speedups over classical algorithms.
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.
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.
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.
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…
We develop the first quantum algorithm for the constrained portfolio optimization problem. The algorithm has running time , where is the number of positivity and budget constraints, is the number of assets in the portfolio, the des…
Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU() Symmetryquant-ph
Enhances quantum computing for symmetrical systems, proving a new class of problems.
problem Proving the efficiency of a new quantum computing model for symmetrical systems.
method Introducing equivariant convolutional quantum algorithms tailored for SU(d) symmetries.
result Demonstrates a problem that can be solved efficiently on a new quantum model, suggesting it's not classically simulatable.
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.
Simple gradient descent algorithm escapes saddle points efficiently.
problem Escaping saddle points in nonconvex optimization.
method Gradient-based algorithm with polynomial iterations.
result Outputs ε-approximate second-order stationary points efficiently.
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.
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.
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 …
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.
New method speeds up generative modeling without requiring diffusion steps.
problem Improving the speed and efficiency of generative modeling techniques.
method Probability flow ODE with a corrector step, achieving better dimension dependence.
result Better dimension dependence ( vs. , assuming smoothness of the data distribution).
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.
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³/²).
Bayesian methods in machine learning, such as Gaussian processes, have great advantages com-pared to other techniques. In particular, they provide estimates of the uncertainty associated with a prediction. Extending the Bayesian approach to deep architectures has remained a major challenge. Recent results connected dee…
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…
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.
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.
FedLCB-Q learns optimal policies from federated offline data with linear speedup.
problem Learning optimal policies from offline data with federated learning.
method Federated offline RL algorithm tailored for Q-learning, using local Q-function updates and central aggregation.
result Achieves linear speedup in sample complexity with collaboration among agents.
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…
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.
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…
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.
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.
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.
Distributed Non-Convex Optimization with Sublinear Speedup under Intermittent Client Availabilitystat.ML
Federated learning algorithm improves with intermittent client availability.
problem Performance degradation in Federated Averaging due to client availability changes.
method Federated Latest Averaging (FedLaAvg) uses latest gradients from all clients, even when unavailable.
result FedLaAvg achieves sublinear speedup compared to classical Federated Averaging.
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 …
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.
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…
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.
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.
Neural networks offer high-accuracy solutions to a range of problems, but are costly to run in production systems because of computational and memory requirements during a forward pass. Given a trained network, we propose a techique called Deep Learning Approximation to build a faster network in a tiny fraction of the …
Improved K-Means++ and K-Means with faster run-time.
problem Efficiently selecting initial seeds for K-means clustering.
method Triangle inequality pruning and dynamic priority queue.
result Up to 17x speedup for K-Means++ and 551x for K-Means$\$.
We describe ASAGA, an asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. Through a novel perspective, we revisit and clarify a subtle but important technical issue present in a large fraction of the recent convergence rate proofs for asynchronous parallel…
State-of-the-art implementations of boosting, such as XGBoost and LightGBM, can process large training sets extremely fast. However, this performance requires that the memory size is sufficient to hold a 2-3 multiple of the training set size. This paper presents an alternative approach to implementing the boosted trees…
DASA speeds up SA with delayed agents, achieving N-fold speedup.
problem Speeding up Stochastic Approximation with asynchronous delays.
method DASA: Delay-Adaptive Multi-Agent Stochastic Approximation algorithm.
result First algorithm with convergence rate dependent on mixing time and average delay.