Efficiency of coordinate descent methods on huge-scale optimization problems
From MaRDI portal
For the unconstrained minimization of a differentiable convex function \(f(x_{1},\dots,x_{n})\) (\(x_{i}\in \mathbb{R}^{n_{i}}\), \(i=1,\dots,n\)) with a globally Lipschitz gradient, the random coordinate descent method consists in randomly choosing, at iteration \(k\), some \(i_{k}\in \{1,\dots,n\}\) and then updating the current iterate by making a step in the direction of the negative of the partial gradient with respect to \(x_{i_{k}}\), the step size being equal to the reciprocal of the Lipschitz constant of this partial gradient. The expected objective function value is shown to converge to the infimum of \(f\); for strongly convex functions, the rate of convergence is linear and an accelerated version is presented. A modification of the method for constrained problems is also introduced. Implementation issues are discussed, and some preliminary numerical experiments are reported.
Recommendations
- Subgradient methods for huge-scale optimization problems
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- Efficiency of the accelerated coordinate descent method on structured optimization problems
- Parallel coordinate descent methods for big data optimization
- Random Coordinate Descent Methods for Nonseparable Composite Optimization
Cited in
(only showing first 100 items - show all)- An estimate of the speed of convergence for certain methods of coordinate descent
- Grouped coordinate minimization using Newton's method for inexact minimization in one vector coordinate
- On the convergence of the coordinate descent method for convex differentiable minimization
- Solving norm constrained portfolio optimization via coordinate-wise descent algorithms
- Stochastic accelerated alternating direction method of multipliers with importance sampling
- A flexible coordinate descent method
- Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
- Accelerated parallel and distributed algorithm using limited internal memory for nonnegative matrix factorization
- A globally convergent algorithm for nonconvex optimization based on block coordinate update
- Coordinate-friendly structures, algorithms and applications
- Duality and nonlinear graph Laplacians
- On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
- Generalization of a result of Fabian on the asymptotic normality of stochastic approximation
- Linear convergence of the randomized sparse Kaczmarz method
- Blocks of coordinates, stochastic programming, and markets
- Stochastic block-coordinate gradient projection algorithms for submodular maximization
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping. II: Mean-square and linear convergence
- A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates
- Robust multicategory support vector machines using difference convex algorithm
- Adaptively weighted large-margin angle-based classifiers
- Multi-label Lagrangian support vector machine with random block coordinate descent method
- Matrix completion under interval uncertainty
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- An optimal randomized incremental gradient method
- Rate of convergence analysis of dual-based variables decomposition methods for strongly convex problems
- Inexact variable metric stochastic block-coordinate descent for regularized optimization
- A coordinate descent method for total variation minimization
- A geometric probability randomized Kaczmarz method for large scale linear systems
- Point process estimation with Mirror Prox algorithms
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- An accelerated directional derivative method for smooth stochastic convex optimization
- A stochastic homotopy tracking algorithm for parametric systems of nonlinear equations
- On maximum residual block and two-step Gauss-Seidel algorithms for linear least-squares problems
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences
- Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
- Fastest rates for stochastic mirror descent methods
- A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization
- Sparse group fused Lasso for model segmentation: a hybrid approach
- An integrated stochastic model and algorithm for constrained multi-item newsvendor problems by two-stage decision-making approach
- On the convergence of a randomized block coordinate descent algorithm for a matrix least squares problem
- Asynchronous networked aggregative games
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- Linear support vector regression with linear constraints
- Levenberg-Marquardt method based on probabilistic Jacobian models for nonlinear equations
- Cyclic coordinate descent in the Hölder smooth setting
- On complexity and convergence of high-order coordinate descent algorithms for smooth nonconvex box-constrained minimization
- On the convergence of a block-coordinate incremental gradient method
- Linear convergence of prox-SVRG method for separable non-smooth convex optimization problems under bounded metric subregularity
- Accelerated proximal envelopes: application to componentwise methods
- On the computational efficiency of catalyst accelerated coordinate descent
- On obtaining sparse semantic solutions for inverse problems, control, and neural network training
- Using neural networks to accelerate the solution of the Boltzmann equation
- Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- An accelerated coordinate gradient descent algorithm for non-separable composite optimization
- Oracle complexity separation in convex optimization
- Phase-only transmit beampattern design for large phased array antennas with multi-point nulling
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Classes of linear programs solvable by coordinate-wise minimization
- Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
- Block layer decomposition schemes for training deep neural networks
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- Randomness and permutations in coordinate descent methods
- On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems
- Synchronous parallel block coordinate descent method for nonsmooth convex function minimization
- Lower bounds for finding stationary points I
- Efficient first-order methods for convex minimization: a constructive approach
- Emergence of price-taking behavior
- Optimization for deep learning: an overview
- Primal-dual block-proximal splitting for a class of non-convex problems
- Worst-case complexity of cyclic coordinate descent: O(n^2) gap with randomized version
- Random batch methods (RBM) for interacting particle systems
- On convergence rate of the randomized Gauss-Seidel method
- Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
- Asynchronous Lagrangian scenario decomposition
- Accelerated directional search with non-Euclidean prox-structure
- Markov chain block coordinate descent
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Variant of greedy randomized Kaczmarz for ridge regression
- Randomized primal-dual proximal block coordinate updates
- Randomized and fault-tolerant method of subspace corrections
- Block-proximal methods with spatially adapted acceleration
- Feature selection method based on partial least squares and analysis of traditional Chinese medicine data
- Generalized affine scaling algorithms for linear programming problems
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Coordinate descent algorithms
- On efficient randomized algorithms for finding the PageRank vector
- On the efficiency of a randomized mirror descent algorithm in online optimization problems
- On the convergence of inexact block coordinate descent methods for constrained optimization
- Parallel block coordinate minimization with application to group regularized regression
- Unsupervised learning of pharmacokinetic responses
- On proximal subgradient splitting method for minimizing the sum of two nonsmooth convex functions
- Performance of first- and second-order methods for _1-regularized least squares problems
- Efficient block-coordinate descent algorithms for the group Lasso
- Random gradient-free minimization of convex functions
- Random block coordinate descent methods for linearly constrained optimization over networks
This page was built for publication: Efficiency of coordinate descent methods on huge-scale optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910875)
