DID solves NMF for large distributed data.
problem Large distributed nonnegative matrix factorization.
method Distributed incremental block coordinate descent.
result Only one communication step per iteration.
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.
169,341 papers · 148 categories
Trend · papers per month
48 results for “block coordinate updates”
In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is …
Accelerated method for solving convex optimization problems with linear constraints.
problem Solving large-scale convex optimization problems with linear constraints.
method Primal-dual proximal block coordinate updating method with accelerated convergence.
result Achieves convergence rate for strongly convex objectives and linear rate for independent blocks.
Paper speeds up tensor factorization algorithms.
problem Improving convergence speed of tensor factorization algorithms.
method Proposes an extrapolation strategy between block updates.
result HER significantly accelerates convergence speed.
Accelerated Block Coordinate Proximal Gradients with Applications in High Dimensional Statisticsmath.OC
New method accelerates optimization for nonconvex problems in statistics.
problem Nonconvex optimization problems in statistics and machine learning.
method Adaptive momentum and block coordinate proximal gradient method with specific update rules.
result The method achieves provable local linear convergence in sparse linear regression problems.
A hybrid method combines Jacobian and Gauss-Seidel updates for linearly constrained convex programming.
problem Solving linearly constrained convex programming problems with nonseparable constraints.
method Hybrid Jacobian and Gauss-Seidel proximal block coordinate update method.
result The hybrid method converges and performs as well as Gauss-Seidel method and better than a randomized primal-dual BCU method.
Efficient method solves large-scale saddle point problems with parallel updates.
problem Large-scale convex-concave saddle point problems with separable structure.
method Stochastic parallel block coordinate descent with adaptive primal-dual updates.
result Significantly better performance than state-of-the-art methods in various applications.
This paper introduces a new method for optimizing large-scale problems using Markov chain block updates.
problem Optimizing large-scale problems with efficient and natural block selection.
method Markov chain block coordinate descent (BCD) for optimization.
result The method converges for minimizing Lipschitz differentiable functions, with sublinear and linear convergence rates for convex and strongly convex functions, respectively.
New algorithm for convex optimization with coupled constraints and linear constraints.
problem General multi-block convex optimization with coupled objective and linear constraints.
method Randomized primal-dual proximal block coordinate updates.
result Established convergence rate for objective value and feasibility measure.
The paper develops efficient algorithms for solving complex problems using coordinate updates.
problem Solving large or high-dimensional datasets with linear and nonlinear mappings.
method Develops coordinate-friendly operators and algorithms for various applications.
result New algorithms for machine learning, image processing, and optimization problems.
Async-parallel method solves convex problems with nonseparable linear constraints.
problem Solving convex problems with nonseparable linear constraints in an asynchronous setting.
method Randomized primal-dual block coordinate update (BCU) method.
result The objective value sequence converges to the optimal value and constraint residual to zero under convexity assumption.
A matrix factorization method detects text outliers using low rank approximations.
problem Challenges in detecting outliers in text data with mostly zero values.
method TONMF based on block coordinate descent (BCD) framework.
result Effective in distinguishing anomalies from natural variations in text data.
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.
We consider a generic convex-concave saddle point problem with separable structure, a form that covers a wide-ranged machine learning applications. Under this problem structure, we follow the framework of primal-dual updates for saddle point problems, and incorporate stochastic block coordinate descent with adaptive st…
New taxonomy and improved solvers for discrete energy minimization.
problem Maximum-a-posteriori inference in discrete graphical models.
method Dual block-coordinate ascent rule, theoretical analysis, new solver variants.
result Improved state-of-the-art solver outperforming existing methods on all test instances.
Fast Convolutive Nonnegative Matrix Factorization Through Coordinate and Block Coordinate Updatescs.LG
New algorithms improve NMF for extracting patterns from time series data.
problem Extracting short-lived temporal motifs from high-dimensional time series data.
method Extended HALS and ANLS algorithms for CNMF model.
result Improved performance on large-scale data compared to multiplicative updates.
BBPL uses block updates to learn Markov random fields without full inference.
problem Training Markov random fields requires inference over all variables, scaling with model size.
method Block-coordinate updates of approximate marginals to compute approximate gradients.
result BBPL converges to the same solution as full inference, despite approximations.
Core-Halo solves large-scale fixed-point problems by decentralizing updates.
problem Large-scale fixed-point equations with block dependencies.
method Core-Halo decomposition separates write ownership from read-only context, aligning with block-dependence structure.
result Core-Halo achieves near-centralized performance while retaining parallelism.
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…
We propose a doubly stochastic primal-dual coordinate optimization algorithm for empirical risk minimization, which can be formulated as a bilinear saddle-point problem. In each iteration, our method randomly samples a block of coordinates of the primal and dual solutions to update. The linear convergence of our method…
The stochastic gradient (SG) method can minimize an objective function composed of a large number of differentiable functions, or solve a stochastic optimization problem, to a moderate accuracy. The block coordinate descent/update (BCD) method, on the other hand, handles problems with multiple blocks of variables by up…
This paper provides a block coordinate descent algorithm to solve unconstrained optimization problems. In our algorithm, computation of function values or gradients is not required. Instead, pairwise comparison of function values is used. Our algorithm consists of two steps; one is the direction estimate step and the o…
LPOM approximates neural nets with proximal operators for efficient training.
problem Training feed-forward neural networks efficiently and avoiding gradient issues.
method Rewriting activation functions as proximal operators, using block coordinate descent.
result LPOM converges and performs well on MNIST and CIFAR-10.
Sequential coordinate ascent is more robust in high-dimensional linear regression.
problem Behavior difference between sequential and parallel coordinate ascent in variational inference.
method Comparison of sequential and parallel coordinate ascent algorithms in high-dimensional linear regression.
result Sequential algorithm converges under more relaxed conditions than parallel algorithm.
Randomized block-diagonal preconditioning improves parallel learning convergence.
problem Improving convergence of gradient-based optimization methods in parallel settings.
method Randomization of coordinates during optimization to repartition tasks.
result Randomization significantly improves convergence of block-diagonal preconditioned methods.
Random scan CAVI converges linearly under log-concave assumptions.
problem Analyzing the convergence rate of random scan Coordinate Ascent Variational Inference (CAVI) under log-concave conditions.
method Building on previous work, we analyze the random scan version of CAVI using optimal transport geometry.
result We obtain tight linear convergence rates for the random scan version of CAVI.
Improved tensor GLM estimation for complex data.
problem Complex tensor data in GLMs leads to high-dimensional, ill-posed estimation.
method Proposed LSRTR-M algorithm using Muon updates for faster convergence and lower errors.
result LSRTR-M converges faster and achieves lower errors than LSRTR.
Two-layer model sparsifies image residuals for CT image reconstruction.
problem Image reconstruction from limited and corrupted data.
method Pre-learning a two-layer sparsifying transform model with block coordinate descent optimization.
result Preliminary experiments show the two-layer model improves CT image reconstruction from low-dose measurements.
Improved CBCD-type methods converge faster for strongly convex minimization problems.
problem Achieving faster convergence for strongly convex minimization problems using CBCD-type methods.
method Proposed an improved convergence analysis for CBCD-type methods, showing a tighter iteration complexity.
result Iteration complexity of matches GD methods up to a factor.
Training large machine learning (ML) models with many variables or parameters can take a long time if one employs sequential procedures even with stochastic updates. A natural solution is to turn to distributed computing on a cluster; however, naive, unstructured parallelization of ML algorithms does not usually lead t…
Distributed block coordinate descent solves large kernel problems.
problem Large scale kernel learning problems.
method Distributed block coordinate descent for kernel regression and classification.
result Nyström method generally achieves better statistical accuracy than random features.
RAPSA is a parallel stochastic algorithm for large-scale learning problems.
problem Large-scale learning problems with many examples and features.
method Random parallel stochastic algorithm (RAPSA) using multiple processors to select randomly chosen blocks and training subsets.
result RAPSA converges to the optimal classifier for convex training objectives.
New algorithms solve nonconvex federated learning problems efficiently.
problem Nonconvex federated composite optimization in federated learning.
method FedDR and asyncFedDR algorithms combining Douglas-Rachford splitting, randomized block-coordinate strategies, and asynchronous implementation.
result Match communication complexity lower bound up to a constant factor.
DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimizationmath.OC
DSCOVR improves distributed optimization for big data with less communication and synchronization.
problem Efficiently optimizing large linear models with convex loss functions over distributed systems.
method Randomized primal-dual block coordinate algorithms with doubly stochastic coordinate optimization and variance reduction.
result DSCOVR algorithms require less overall computation and communication compared to other first-order distributed algorithms.
CD methods tackle nonconvex optimization with three terms, achieving critical points.
problem Minimizing nonconvex functions with specific structure.
method Developed randomized CD, randomly permuted CD, and accelerated CD methods.
result CD methods converge to critical points with sublinear complexity.
Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updatingmath.OC
Paper proves SHB convergence with biased gradients and approximate step sizes.
problem Establishing convergence of SHB with biased gradients and approximate step sizes.
method Generalizes SHB convergence conditions for biased gradients, approximate step sizes, and block updating.
result Proves convergence of SHB with new conditions for biased gradients and approximate step sizes.
Study on distributed coordinate descent with quantized updates for finite precision communication.
problem Finite precision communication limits the accuracy of updates in distributed coordinate descent.
method Introduced a randomized distributed coordinate descent algorithm with quantized updates, derived convergence conditions, and validated with experiments.
result Algorithm with quantized updates converges under certain conditions on the quantization error.
Differentially private random block coordinate descent improves utility in machine learning.
problem Lack of privacy in classical CD methods when handling sensitive information.
method Proposes a differentially private random block coordinate descent method using sketch matrices and importance sampling.
result Demonstrates improved convergence rates and utility guarantees compared to non-private methods.
A new method improves coordinate descent by adaptively selecting coordinates.
problem Coordinate descent's inefficiency due to checking all coordinates.
method Adaptive multi-armed bandit algorithm to select coordinates.
result Improves convergence of coordinate descent methods.
In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring…
Optimizes variational inference for dynamic network models.
problem Estimating pairwise inner products and intercepts in dynamic latent space models.
method Structured mean-field variational inference with block coordinate ascent algorithm.
result Variational risk attains minimax optimal rate with logarithmic factor under certain conditions.
It is shown that, in four dimensions, it is possible to introduce coordinates so that an analytic metric locally takes block diagonal form. i.e. one can find coordinates such that for where . We call a coordinate system in which the metric takes this for…
We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the d…
Paper analyzes ADMM convergence for nonconvex Gaussian phase retrieval.
problem Nonconvex optimization in Gaussian phase retrieval.
method Block coordinate descent as ADMM with dual variable fixed.
result Block coordinate descent converges linearly to global minimizer.
Improves BCFW for SSVM optimization with adaptive sampling and caching.
problem Optimizing SSVM objective using BCFW algorithm.
method Adaptive gap-based sampling, pairwise and away-step Frank-Wolfe, cache-hit criterion for oracle calls, regularization path computation.
result First method to compute approximate SSVM regularization paths.
New adaptive stepsize method for stochastic approximation converges to target point.
problem Finding optimal step sizes for stochastic approximation algorithms.
method Adaptive block-coordinate stepsizes using online estimates of second moment.
result New method converges almost surely to a small neighborhood of the target point.
Study tackles nonlinear factor models with unknown monotone links from incomplete and noisy data.
problem Learning nonlinear factor models with unknown monotone links from incomplete and noisy data.
method Formulated as joint recovery of low-rank factors, loadings, and nonlinear link function; proposed BCD algorithm with regularization.
result Established convergence guarantees and sublinear regret bounds for link-function updates.
New adaptive methods improve deep learning performance.
problem Training deep networks efficiently and effectively.
method Block-diagonal matrix adaptation for gradient updates.
result Block-diagonal methods outperform adaptive diagonal methods and vanilla SGD.