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.
Direct proof shows adaptive gradient descent converges near-linearly for convex functions.
Improved Sinkhorn algorithm for UOT with near-linear complexity.
New algorithm trains neural networks in near-linear time, overcoming slow convergence issues.
A clustering algorithm for natural hierarchical clusters with near-linear time complexity.
We propose a stochastic variance reduced optimization algorithm for solving sparse learning problems with cardinality constraints. Sufficient conditions are provided, under which the proposed algorithm enjoys strong linear convergence guarantees and optimal estimation accuracy in high dimensions. We further extend the …
Although distributed computing can significantly reduce the training time of deep neural networks, scaling the training process while maintaining high efficiency and final accuracy is challenging. Distributed asynchronous training enjoys near-linear speedup, but asynchrony causes gradient staleness - the main difficult…
SAIL-RevKL improves SAIL's convergence by regularizing the objective function.
Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in …
CTT compresses samples to test distributions near-linearly, outperforming existing methods.
Adam achieves optimal convergence in deep ReLU networks via novel Kakeya bounds.
Improved efficient robust regression with near-linear time and subquadratic samples.
New algorithm speeds up Gaussian process optimization.
New algorithm approximates distributions with near-linear time and optimal sample efficiency.
Policy gradient converges to globally optimal policy in nearly linear-quadratic systems.
We investigate the theoretical limits of pipeline parallel learning of deep learning architectures, a distributed setup in which the computation is distributed per layer instead of per example. For smooth convex and non-convex objective functions, we provide matching lower and upper complexity bounds and show that a na…
Algorithm finds frequencies, amplitudes, and phases of sinusoids in noisy data.
Compress++ speeds up distribution compression to near-linear time.
We consider the demixing problem of two (or more) high-dimensional vectors from nonlinear observations when the number of such observations is far less than the ambient dimension of the underlying vectors. Specifically, we demonstrate an algorithm that stably estimate the underlying components under general \emph{struc…
Stein's method for measuring convergence to a continuous target distribution relies on an operator characterizing the target and Stein factor bounds on the solutions of an associated differential equation. While such operators and bounds are readily available for a diversity of univariate targets, few multivariate targ…
Computable Stein discrepancies have been deployed for a variety of applications, ranging from sampler selection in posterior inference to approximate Bayesian inference to goodness-of-fit testing. Existing convergence-determining Stein discrepancies admit strong theoretical guarantees but suffer from a computational co…
New algorithm recovers sparse signals from linearly sparse dictionaries efficiently.
A new algorithm estimates mean adaptively to covariance, faster and more flexible than existing methods.
We consider the fundamental learning problem of estimating properties of distributions over large domains. Using a novel piecewise-polynomial approximation technique, we derive the first unified methodology for constructing sample- and time-efficient estimators for all sufficiently smooth, symmetric and non-symmetric, …
New framework for DP-SMO with near-optimal privacy-loss trade-off.
In this work, we propose a robust approach to design distributed controllers for unknown-but-sparse linear and time-invariant systems. By leveraging modern techniques in distributed controller synthesis and structured linear inverse problems as applied to system identification, we show that near-optimal distributed con…
Solving linear programs by using entropic penalization has recently attracted new interest in the optimization community, since this strategy forms the basis for the fastest-known algorithms for the optimal transport problem, with many applications in modern large-scale machine learning. Crucial to these applications h…
We study optimization algorithms based on variance reduction for stochastic gradient descent (SGD). Remarkable recent progress has been made in this direction through development of algorithms like SAG, SVRG, SAGA. These algorithms have been shown to outperform SGD, both theoretically and empirically. However, asynchro…
Quantum algorithms reduce clustering input size, achieving near-linear approximation.
SNS accelerates Sinkhorn algorithm with sparse Newton iterations.
Lapse improves parameter servers by dynamically allocating parameters, achieving near-linear scaling.
This paper develops a fast algorithm for solving nonlinear PDEs using sparse Cholesky factorization.
WildCat efficiently compresses neural network attention mechanisms.
Large models are prevalent in modern machine learning scenarios, including deep learning, recommender systems, etc., which can have millions or even billions of parameters. Parallel algorithms have become an essential solution technique to many large-scale machine learning jobs. In this paper, we propose a model parall…
Paper proposes FedQ-Advantage for federated Q-learning with near-optimal regret and low communication cost.
New insights into variable selection with different model assumptions.
Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art parallel mini-batch algorithms assume synchronous operation or cyclic update orders. When worker nodes are heterogeneous (due to different computational capabilities or different communication delays), s…
New method for robust linear regression in nearly linear time.
Improved sketching for logistic and regression with near-linear dimensions.
CSD improves goodness-of-fit testing for higher-order dependence.
Matrix completion is the problem of recovering a low rank matrix by observing a small fraction of its entries. A series of recent works [KOM12,JNS13,HW14] have proposed fast non-convex optimization based iterative algorithms to solve this problem. However, the sample complexity in all these results is sub-optimal in it…
Local polynomial regression (Fan and Gijbels 1996) is an important class of methods for nonparametric density estimation and regression problems. However, straightforward implementation of local polynomial regression has quadratic time complexity which hinders its applicability in large-scale data analysis. In this pap…
New method computes affine normal directions efficiently for sparse polynomials.
We show how the discovery of robust scalable numerical solvers for arbitrary bounded linear operators can be automated as a Game Theory problem by reformulating the process of computing with partial information and limited resources as that of playing underlying hierarchies of adversarial information games. When the so…
Framework detects changes in causal dependence between variables.
We introduce novel communication strategies in synchronous distributed Deep Learning consisting of decentralized gradient reduction orchestration and computational graph-aware grouping of gradient tensors. These new techniques produce an optimal overlap between computation and communication and result in near-linear sc…
Implicit schemes are popular methods for the integration of time dependent PDEs such as hyperbolic and parabolic PDEs. However the necessity to solve corresponding linear systems at each time step constitutes a complexity bottleneck in their application to PDEs with rough coefficients. We present a generalization of ga…
If learning methods are to scale to the massive sizes of modern datasets, it is essential for the field of machine learning to embrace parallel and distributed computing. Inspired by the recent development of matrix factorization methods with rich theory but poor computational complexity and by the relative ease of map…
In this work we propose R-GPM, a parallel computing framework for graph pattern mining (GPM) through a user-defined subgraph relation. More specifically, we enable the computation of statistics of patterns through their subgraph classes, generalizing traditional GPM methods. R-GPM provides efficient estimators for thes…