The paper parallelizes HMM inference for efficient long-term computations.
problem Efficiently computing inference in long-term hidden Markov models.
method Parallelization using associative elements and operators for sum-product and max-product algorithms.
result The proposed parallel algorithms are computationally efficient for long time horizons.
This paper improves parallel belief propagation for scalable machine learning.
problem Efficient parallelization of belief propagation for large-scale machine learning tasks.
method Use of scalable relaxed schedulers to parallelize belief propagation.
result Our approach outperforms previous methods in scalability and convergence time.
PL-NMF improves parallel NMF by optimizing data locality.
problem Data movement costs dominate in parallel NMF applications.
method Developed a parallel NMF algorithm based on HALS with data locality optimizations.
result Significant performance improvement over existing parallel NMF algorithms.
A new parallel MCMC algorithm improves topic modeling without communication.
problem Quasi-ergodicity problem in topic modeling due to multimodal topic distributions.
method Developed an embarrassingly parallel MCMC algorithm for sLDA by switching topic combination and labeling prediction.
result Out-of-sample prediction performance is comparable to non-parallel sLDA but computation time is significantly reduced.
Parallelized bandit algorithms speed up decision-making.
problem Sequential exploration limits decision-making speed.
method Developed parallel contextual bandit algorithms.
result Regret nearly identical to sequential algorithms.
MixML unifies analysis of weakly consistent parallel learning.
problem Lack of insight into how communication structure affects convergence in parallel learning.
method Proposes MixML framework for analyzing convergence of weakly consistent parallel machine learning.
result Shows dependency of convergence on mixing time tmix.
Enhances feature selection speed and quality with parallelized MeLiF.
problem Efficient feature selection in machine learning and data mining.
method Parallelizes MeLiF algorithm using ensembles of ranking filters.
result Significant improvement in algorithm performance and feature selection quality.
We present a generic framework for parallel coordinate descent (CD) algorithms that includes, as special cases, the original sequential algorithms Cyclic CD and Stochastic CD, as well as the recent parallel Shotgun algorithm. We introduce two novel parallel algorithms that are also special cases---Thread-Greedy CD and …
We introduce a new embarrassingly parallel parameter learning algorithm for Markov random fields with untied parameters which is efficient for a large class of practical models. Our algorithm parallelizes naturally over cliques and, for graphs of bounded degree, its complexity is linear in the number of cliques. Unlike…
A new algorithm for parallel transport on shape spaces is presented and compared to existing methods.
problem Statistical analysis of shape data, especially in time series and optimization.
method Pole ladder algorithm for parallel transport on Kendall shape spaces, compared to integration methods.
result The pole ladder algorithm is a more efficient method for parallel transport.
Parallel sampling for smooth distributions with fast convergence.
problem Efficiently sampling from distributions with smooth densities.
method Parallelization of Langevin algorithms under log-Sobolev inequalities.
result Samples close to target distribution with low KL divergence or TV distance.
This paper studies effective parallelization of MCTS for computer games.
problem Computational expense of MCTS due to many rollouts.
method Examined parallel MCTS performance, identified necessary conditions for desirable parallelization, and proposed BU-UCT algorithm.
result Theoretical foundation for effective parallel MCTS, with BU-UCT outperforming baselines.
Parallel algorithm finds sparse solutions for nonconvex problems.
problem Nonconvex sparsity-regularized rank minimization.
method Parallel best-response algorithm with exact line search.
result Guaranteed convergence to a stationary point.
We present a parallel algorithm that computes the ask and bid prices of an American option when proportional transaction costs apply to the trading of the underlying asset. The algorithm computes the prices on recombining binomial trees, and is designed for modern multi-core processors. Although parallel option pricing…
New algorithms improve causal direction inference accuracy using parallel ensemble methods.
problem Stability of causal direction inference results from observational data.
method Parallel ensemble frameworks to map and improve inference accuracy.
result Significant improvement in accuracy of causal direction inference.
A new method for parallelizing neural network training on large computers.
problem Efficiently parallelizing deep neural networks training on large distributed-memory computers.
method Integrates model, batch, and domain parallelism using a matrix-based parallel algorithm.
result Lowest communication costs achieved with an integrated approach, not pure model or data parallelism.
New framework simplifies analysis of asynchronous parallel optimization algorithms.
problem Difficulty in analyzing asynchronous parallel optimization algorithms due to delay and inconsistency.
method Revisit and clarify technical issue in convergence rate proofs, propose simplified 'perturbed iterate' framework.
result Proves linear speedup for ASAGA and KROMAGNON on multi-core systems without sparsity assumptions.
Unified parallel ADMM for high-dimensional regression with combined regularizations.
problem Efficiently solving high-dimensional regression problems with combined regularization terms in parallel.
method Unified constrained optimization formulation based on consensus problem, parallel ADMM algorithms.
result Global convergence and linear convergence rate of the proposed algorithm.
Communication costs, resulting from synchronization requirements during learning, can greatly slow down many parallel machine learning algorithms. In this paper, we present a parallel Markov chain Monte Carlo (MCMC) algorithm in which subsets of data are processed independently, with very little communication. First, w…
WP-SGD optimizes SGD for unevenly distributed data in distributed systems.
problem Inequalities in node performance and data consumption in parallel SGD.
method Combines weighted model parameters from different nodes to compensate for performance inconsistencies.
result WP-SGD significantly outperforms traditional parallel SGD in systems with uneven workloads.
AsyB-ProxSGD parallelizes model updates and stochastic gradient descent for large models and data.
problem Efficiently training large models and handling large datasets in parallel.
method AsyB-ProxSGD: model parallel proximal stochastic gradient algorithm for asynchronous systems.
result Achieves linear speedup with O(K1/4) number of workers for nonconvex problems. Paper presents efficient algorithms for convolutional neural networks using Winograd minimal filtering.
problem Resource-efficient implementation of convolutional neural networks.
method Winograd minimal filtering trick applied to M-tap filters (M=3,5,7,9,11) for parallel hardware implementation.
result Approximately 30% reduction in multipliers for fully parallel hardware implementation.
New parallel algorithms optimize on manifolds, reducing communication costs.
problem Optimization on non-Euclidean spaces like manifolds.
method Generalized parallel inference algorithms for optimization on manifolds.
result Communication-efficient and convergent algorithms for manifold optimization.
Quantum computers can speed up machine learning optimization problems.
problem Long computation times and high resource requirements for classical optimization algorithms in machine learning.
method Developed a mathematical model to leverage quantum parallelism for machine learning.
result Quantum machine learning applied to a 3D time-varying image demonstrated significant speedup.
Optimized parallel algorithms for identifying strong ties in data.
problem Identifying strong ties in data with varying distances and community sizes.
method Design and analysis of sequential and parallel algorithms for partitioned local depths.
result Optimized algorithms achieve up to 19.4x speedup in parallel execution.
Proposes a scalable algorithm for large-scale probabilistic tensor analysis.
problem Leveraging time constraints to capture evolving tensor data.
method Introduces a new tensor data split strategy and an efficient algorithm for stochastic Alternating Direction Method of Multipliers.
result Demonstrates that P2T2F is a highly effective and efficiently scalable algorithm. SySCD improves SCD scalability and speeds up training.
problem Scalability issues in parallel SCD algorithms.
method Developed a system-aware parallel SCD algorithm (SySCD) to avoid bottlenecks.
result Offers up to x42 speedup compared to state-of-the-art GLM solvers.
Optimizes parallel training of linear models, improving convergence.
problem Improving convergence of parallel training of linear models.
method Data partitioning scheme across threads to improve convergence.
result Achieved up to 42x speedup in convergence compared to state of the art implementations.
Asynch-SGBDT speeds up GBDT training on Parameter Server.
problem Training GBDT on Parameter Server is slow due to computational resources and time.
method Developed asynch-SGBDT, an asynchronous parallel method for GBDT training.
result Asynch-SGBDT achieves linear speedup in asynchronous parallel training.
New algorithm speeds up feature selection and experimental design.
problem Designing efficient parallel algorithms for statistical subset selection.
method Differential submodularity and adaptive sampling.
result Logarithmic parallel runtime for feature selection and experimental design.
Parallel Mapper algorithm for efficient topological data analysis.
problem Efficient parallel processing of Mapper for topological data analysis.
method Provable correct parallel algorithm for Mapper execution on multiple processors.
result Demonstrates the efficiency of parallel Mapper compared to sequential implementations.
New algorithm for parallel inference without block partitioning.
problem Slow inference in probabilistic models due to single-variable updates.
method Lower bounds ELBO with forest mixture bound for parallel inference.
result Algorithm converges faster for 'forest-like' models.
New simulation shows trading algorithms' performance varies with parallelism.
problem Validation of trading algorithms' performance in parallel markets.
method Used TBSE, a threaded market simulator, to compare algorithms' performance.
result Trading algorithms' performance differs in parallel vs. sequential markets.
New parallel Bayesian optimization method outperforms existing techniques.
problem Expensive function evaluations in parallel settings.
method Asynchronous Thompson Sampling (TS) for Bayesian optimization.
result Asynchronous TS achieves asymptotically lower regret under time constraints.
New adaptive temperature selection improves parallel tempering efficiency.
problem Enhancing mixing in multi-modal distributions using parallel tempering.
method Adaptive temperature selection using policy gradient approach.
result Lower integrated autocorrelation times achieved compared to traditional methods.
This paper improves thresholding bandit problem algorithms.
problem Identifying arms with rewards above a threshold.
method Asynchronous parallel empirical variance guided algorithms.
result Optimal round complexity improvement for all arms with bounded high order moments.
In many applications of black-box optimization, one can evaluate multiple points simultaneously, e.g. when evaluating the performances of several different neural network architectures in a parallel computing environment. In this paper, we develop a novel batch Bayesian optimization algorithm --- the parallel knowledge…
We consider learning problems over training sets in which both, the number of training examples and the dimension of the feature vectors, are large. To solve these problems we propose the random parallel stochastic algorithm (RAPSA). We call the algorithm random parallel because it utilizes multiple parallel processors…
We consider the problem of maximum a posteriori (MAP) inference in discrete graphical models. We present a parallel MAP inference algorithm called Bethe-ADMM based on two ideas: tree-decomposition of the graph and the alternating direction method of multipliers (ADMM). However, unlike the standard ADMM, we use an inexa…
Parallel optimization limits are tight for non-smooth convex functions.
problem Limiting parallel acceleration in convex optimization.
method Information-theoretic measure of adaptivity, lower bounds for parallel runtime.
result No randomized algorithm can achieve better convergence rates than a one-query-per-round algorithm with adaptivity better than o(n1/3). Proposes a new backpropagation algorithm for deep learning with guaranteed convergence.
problem Backward locking in backpropagation limits parallel updates in deep neural networks.
method Decouples gradients and splits the network into modules for parallel updates, proving convergence for non-convex problems.
result The proposed algorithm achieves significant speedup without accuracy loss in training deep convolutional neural networks.
Parallelizes LARS for high-dimensional data with speedups and accuracy trade-offs.
problem Fitting linear regression models to high-dimensional data efficiently.
method Two parallel and communication avoiding versions of LARS: bLARS and Tournament-bLARS.
result Speedups up to 4x compared to LARS, with trade-offs in solution quality.
New algorithm for collaborative deep learning over fixed networks.
problem Data parallelization and decentralized computation in deep learning.
method Consensus-based distributed SGD (CDSGD) and CDMSGD algorithms for fixed topology networks.
result Demonstrated improved performance over centralized and federated learning algorithms.
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 …
Many machine learning algorithms minimize a regularized risk, and stochastic optimization is widely used for this task. When working with massive data, it is desirable to perform stochastic optimization in parallel. Unfortunately, many existing stochastic optimization algorithms cannot be parallelized efficiently. In t…
Direct parallel algorithm for optimal transport with optimal runtime.
problem Computing the Wasserstein distance between two distributions efficiently.
method Primal-dual extragradient method for first-order iterations.
result Solves optimal transport to additive ε with O(1/ε) parallel depth.
A parallel algorithm learns efficient Kronecker product dictionaries.
problem Sparse representation of 2D signals like images and hyperspectral data.
method Highly parallelizable algorithm for learning separable dictionaries.
result Competitive sparse representations at lower computational cost.
POLO simplifies parallel optimization research with a flexible library.
problem Ease of implementing and evaluating parallel optimization algorithms.
method Uses policies and template programming for algorithm decomposition and code reuse.
result Allows implementation of state-of-the-art algorithms in minimal code.