As datasets continue to increase in size and multi-core computer architectures are developed, asynchronous parallel optimization algorithms become more and more essential to the field of Machine Learning. Unfortunately, conducting the theoretical analysis asynchronous methods is difficult, notably due to the introducti…
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,932 papers · 148 categories
Trend · papers per month
48 results for “asynchronous parallelism”
Paper analyzes convergence and speedup of asynchronous parallel SGD.
problem Achieving good convergence and linear speedup in asynchronous parallel SGD.
method Second-order convergence analysis of APSGD with consistent read near strictly saddle points.
result Theoretical guarantee for using at most workers for good convergence and linear speedup.
Stochastic gradient descent~(SGD) and its variants have become more and more popular in machine learning due to their efficiency and effectiveness. To handle large-scale problems, researchers have recently proposed several parallel SGD methods for multicore systems. However, existing parallel SGD methods cannot achieve…
A scalable parallel BO method for asynchronous settings.
problem Expensive-to-evaluate problems in machine learning.
method Simple and scalable Bayesian optimization method for asynchronous parallel settings.
result Demonstrated promising performance on benchmark functions and hyperparameter optimization.
We design and analyse variations of the classical Thompson sampling (TS) procedure for Bayesian optimisation (BO) in settings where function evaluations are expensive, but can be performed in parallel. Our theoretical analysis shows that a direct application of the sequential Thompson sampling algorithm in either synch…
Asynchronous parallel implementations of stochastic gradient (SG) have been broadly used in solving deep neural network and received many successes in practice recently. However, existing theories cannot explain their convergence and speedup properties, mainly due to the nonconvexity of most deep learning formulations …
We show that asymptotically, completely asynchronous stochastic gradient procedures achieve optimal (even to constant factors) convergence rates for the solution of convex optimization problems under nearly the same conditions required for asymptotic optimality of standard stochastic gradient procedures. Roughly, the n…
Batch Bayesian optimisation (BO) has been successfully applied to hyperparameter tuning using parallel computing, but it is wasteful of resources: workers that complete jobs ahead of others are left idle. We address this problem by developing an approach, Penalising Locally for Asynchronous Bayesian Optimisation on …
In AI research and industry, machine learning is the most widely used tool. One of the most important machine learning algorithms is Gradient Boosting Decision Tree, i.e. GBDT whose training process needs considerable computational resources and time. To shorten GBDT training time, many works tried to apply GBDT on Par…
We consider parallel asynchronous Markov Chain Monte Carlo (MCMC) sampling for problems where we can leverage (stochastic) gradients to define continuous dynamics which explore the target distribution. We outline a solution strategy for this setting based on stochastic gradient Hamiltonian Monte Carlo sampling (SGHMC) …
POAP and pySOT improve surrogate optimization of expensive functions.
problem Optimizing expensive functions with concurrent evaluations.
method Event-driven asynchronous framework for optimization strategies.
result Asynchronous computation offers significant speed-up advantages.
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…
Most commonly used distributed machine learning systems are either synchronous or centralized asynchronous. Synchronous algorithms like AllReduce-SGD perform poorly in a heterogeneous environment, while asynchronous algorithms using a parameter server suffer from 1) communication bottleneck at parameter servers when wo…
Advances in asynchronous optimization methods for machine learning.
problem Efficiently solving large-scale optimization problems in machine learning.
method Asynchronous parallel and distributed optimization methods, accounting for information delays.
result Degree of asynchrony impacts convergence rates in stochastic optimization methods.
Markov Chain Monte Carlo (MCMC) methods such as Gibbs sampling are finding widespread use in applied statistics and machine learning. These often lead to difficult computational problems, which are increasingly being solved on parallel and distributed systems such as compute clusters. Recent work has proposed running i…
A new method for efficient optimization of expensive simulations on HPC.
problem Efficiently solving computationally expensive simulation-based optimization problems.
method Asynchronous parallel Bayesian optimization with budgeted computational resource.
result Improved efficiency and handling of constraints in optimization.
PipeMare enables efficient DNN training with minimal memory and pipeline sacrifices.
problem Sacrificing hardware efficiency to maintain statistical efficiency in pipeline parallel DNN training.
method PipeMare is a simple yet robust training method that tolerates asynchronous updates during pipeline parallelism without sacrificing pipeline utilization or memory.
result PipeMare achieves up to 2.7x less memory usage or 4.3x higher pipeline utilization compared to state-of-the-art synchronous PP training techniques.
Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problemstat.ML
This paper considers the multi-armed thresholding bandit problem -- identifying all arms whose expected rewards are above a predefined threshold via as few pulls (or rounds) as possible -- proposed by Locatelli et al. [2016] recently. Although the proposed algorithm in Locatelli et al. [2016] achieves the optimal round…
We present CYCLADES, a general framework for parallelizing stochastic optimization algorithms in a shared memory setting. CYCLADES is asynchronous during shared model updates, and requires no memory locking mechanisms, similar to HOGWILD!-type algorithms. Unlike HOGWILD!, CYCLADES introduces no conflicts during the par…
PARyOpt is a python based implementation of the Bayesian optimization routine designed for remote and asynchronous function evaluations. Bayesian optimization is especially attractive for computational optimization due to its low cost function footprint as well as the ability to account for uncertainties in data. A key…
We introduce and analyze stochastic optimization methods where the input to each gradient update is perturbed by bounded noise. We show that this framework forms the basis of a unified approach to analyze asynchronous implementations of stochastic optimization algorithms.In this framework, asynchronous stochastic optim…
Ringmaster ASGD improves Asynchronous SGD's efficiency under varying worker times.
problem Suboptimal performance of Asynchronous SGD under heterogeneous worker computation times.
method Ringmaster ASGD, a novel Asynchronous SGD method with optimal time complexity.
result Ringmaster ASGD achieves optimal time complexity under arbitrary worker heterogeneity.
Asynchronous parallel optimization algorithms for solving large-scale machine learning problems have drawn significant attention from academia to industry recently. This paper proposes a novel algorithm, decoupled asynchronous proximal stochastic gradient descent (DAP-SGD), to minimize an objective function that is the…
New algorithm reduces distributed optimization time with stochastic delays.
problem Optimizing distributed data with stochastic delays.
method Developed ADSAGA, a variant of SAGA for distributed-data settings with stochastic delays.
result ADSAGA converges in $ ilde{O}\left(\left(n + \sqrt{m}κ
ight)\log(1/ε)
ight)$ iterations under mean delay .
Standard acquisition functions are sufficient for asynchronous Bayesian optimization.
problem Redundant and repeated queries in asynchronous Bayesian optimization.
method Conceptual analysis and theoretical guarantees of standard acquisitions.
result Standard acquisition functions achieve theoretical guarantees equivalent to Thompson sampling in asynchronous settings.
In many distributed learning problems, the heterogeneous loading of computing machines may harm the overall performance of synchronous strategies. In this paper, we propose an effective asynchronous distributed framework for the minimization of a sum of smooth functions, where each machine performs iterations in parall…
LSAM optimizes deep learning training with improved efficiency.
problem Inefficiency in distributed large-batch training with Sharpness-Aware Minimization (SAM).
method Integrates SAM's adversarial steps with an asynchronous distributed sampling strategy.
result Higher final accuracy compared to data-parallel SAM.
This paper accelerates D-PSGD and AD-PSGD for large-scale deep learning tasks.
problem Decreasing spectral gap with increasing number of learners hampers convergence in D-PSGD and AD-PSGD.
method Improves spectral gap while minimizing communication cost through new techniques.
result Demonstrates faster training times and lower error rates on large-scale tasks.
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…
Stochastic variational inference (SVI) employs stochastic optimization to scale up Bayesian computation to massive data. Since SVI is at its core a stochastic gradient-based algorithm, horizontal parallelism can be harnessed to allow larger scale inference. We propose a lock-free parallel implementation for SVI which a…
In this paper we analyze, evaluate, and improve the performance of training generalized linear models on modern CPUs. We start with a state-of-the-art asynchronous parallel training algorithm, identify system-level performance bottlenecks, and apply optimizations that improve data parallelism, cache line locality, and …
New rules found to maintain neural network performance in asynchronous training.
problem Asynchronous training leads to degradation in generalization.
method Examined dynamical stability, derived rules for learning rate adjustment.
result Learning rate should be inversely proportional to delay for high delay values.
The training of Deep Neural Networks usually needs tremendous computing resources. Therefore many deep models are trained in large cluster instead of single machine or GPU. Though major researchs at present try to run whole model on all machines by using asynchronous asynchronous stochastic gradient descent (ASGD), we …
Recent several years have witnessed the surge of asynchronous (async-) parallel computing methods due to the extremely big data involved in many modern applications and also the advancement of multi-core machines and computer clusters. In optimization, most works about async-parallel methods are on unconstrained proble…
Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneitymath.OC
Ringleader ASGD optimizes SGD for diverse edge devices with varying data and computation speeds.
problem Scalable distributed optimization with heterogeneous devices and data.
method Ringleader ASGD, an asynchronous SGD algorithm.
result Achieves optimal time complexity under data heterogeneity and arbitrary computation speeds.
AB dynamically scales gradients to mitigate asynchronous training delays.
problem Gradient delay in asynchronous training reduces model performance.
method Adaptive Braking (AB) dynamically scales gradients based on alignment.
result AB enables training with up to 32 update steps of delay without accuracy loss.
Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we cal…
Freya PAGE optimizes nonconvex optimization with heterogeneous, asynchronous workers.
problem Optimizing nonconvex finite-sum problems with varying worker processing times.
method Freya PAGE, a parallel method robust to stragglers and adaptive to slow computations.
result Freya PAGE offers improved time complexity guarantees compared to previous methods.
A(DP)SGD: Asynchronous Decentralized Parallel Stochastic Gradient Descent with Differential Privacycs.LG
A(DP)SGD improves federated learning privacy and efficiency.
problem Privacy and efficiency in federated learning with asynchronous decentralized parallel SGD.
method Differentially private asynchronous decentralized parallel SGD (A(DP)SGD) using R{é}nyi differential privacy.
result Achieves optimal convergence rate and comparable model accuracy to SSGD but faster.
Asynchronous framework speeds up model-based RL to real-time.
problem Real-time learning on real robots with model-based RL.
method Asynchronous framework for model-based reinforcement learning.
result Reduced run time to data collection time, improved sample complexity.
Distributed computing offers a high degree of flexibility to accommodate modern learning constraints and the ever increasing size of datasets involved in massive data issues. Drawing inspiration from the theory of distributed computation models developed in the context of gradient-type optimization algorithms, we prese…
We study the problem of stochastic optimization for deep learning in the parallel computing environment under communication constraints. A new algorithm is proposed in this setting where the communication and coordination of work among concurrent processes (local workers), is based on an elastic force which links the p…
Scalable3-BO tackles scalability issues in Bayesian optimization for big data and high dimensions.
problem Bayesian optimization scalability issues in big data and high dimensions.
method Sparse Gaussian process, random embedding, asynchronous parallelization.
result Scalable3-BO framework optimizes high-dimensional problems with 1 million data points and 10,000 dimensions.
Enhances SGLD for log-concave posteriors with asynchronous computation.
problem Sampling log-concave posterior distributions efficiently.
method Integrates asynchronous computation into SGLD with delayed gradients.
result Convergence in measure is not significantly affected by delayed gradient information.
ADMMiRNN solves RNN training issues with stable convergence.
problem Training RNN with stable convergence and avoiding gradient issues.
method Built ADMMiRNN framework on unfolded RNN, providing novel update rules and theoretical analysis.
result ADMMiRNN achieves convergent results and outperforms baselines.
Finding a fixed point to a nonexpansive operator, i.e., , abstracts many problems in numerical linear algebra, optimization, and other areas of scientific computing. To solve fixed-point problems, we propose ARock, an algorithmic framework in which multiple agents (machines, processors, or cores) update i…
Due to their simplicity and excellent performance, parallel asynchronous variants of stochastic gradient descent have become popular methods to solve a wide range of large-scale optimization problems on multi-core architectures. Yet, despite their practical success, support for nonsmooth objectives is still lacking, ma…
New types of machine learning hardware in development and entering the market hold the promise of revolutionizing deep learning in a manner as profound as GPUs. However, existing software frameworks and training algorithms for deep learning have yet to evolve to fully leverage the capability of the new wave of silicon.…