Random Coordinate Descent Methods for Nonseparable Composite Optimization
From MaRDI portal
Abstract: In this paper we consider large-scale composite optimization problems having the objective function formed as a sum of two terms (possibly nonconvex), one has block coordinate-wise Lipschitz continuous gradient and the other is differentiable but nonseparable. Under these general settings we derive and analyze two new random coordinate descent methods. The first algorithm, referred to as random coordinate proximal gradient method, considers the composite form of the objective function, while the other algorithm disregards the composite form of the objective and uses the partial gradient of the full objective, yielding a random coordinate gradient descent scheme with novel adaptive stepsize rules. We prove that these new stepsize rules make the random coordinate gradient scheme a descent method, provided that additional assumptions hold for the second term in the objective function. We also present a complete worst-case complexity analysis for these two new methods in both, convex and nonconvex settings. Preliminary numerical results also confirm the efficiency of our two algorithms on practical problems.
Recommendations
- An accelerated coordinate gradient descent algorithm for non-separable composite optimization
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions
- A flexible coordinate descent method
Cites work
- Accelerated, parallel, and proximal coordinate descent
- Accelerating the cubic regularization of Newton's method on convex problems
- An accelerated coordinate gradient descent algorithm for non-separable composite optimization
- Block Bregman majorization minimization with extrapolation
- Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
- Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
- Coordinate descent algorithms
- Cubic regularization of Newton method and its global performance
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Efficiency of the accelerated coordinate descent method on structured optimization problems
- Gradient descent finds the cubic-regularized nonconvex Newton step
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 1179314 (Why is no real title available?)
- scientific article; zbMATH DE number 2171466 (Why is no real title available?)
- scientific article; zbMATH DE number 3449561 (Why is no real title available?)
- Inexact basic tensor methods for some classes of convex optimization problems
- Inexact block coordinate descent methods with application to non-negative matrix factorization
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Minimization of functions having Lipschitz continuous first partial derivatives
- Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
- On search directions for minimization algorithms
- On the complexity analysis of randomized block-coordinate descent methods
- On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes
- On the convergence of block coordinate descent type methods
- On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Pathwise coordinate optimization
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Proximal gradient methods with adaptive subspace sampling
- Random Coordinate Descent Algorithms for Multi-Agent Convex Optimization Over Networks
- Random Coordinate Descent Methods for Nonseparable Composite Optimization
- Randomized sketch descent methods for non-separable linearly constrained optimization
- Relatively smooth convex optimization by first-order methods, and applications
- The University of Florida sparse matrix collection
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
Cited in
(20)- A flexible coordinate descent method
- An accelerated coordinate gradient descent algorithm for non-separable composite optimization
- Oracle complexity separation in convex optimization
- Accelerated randomized mirror descent algorithms for composite non-strongly convex optimization
- Efficiency of coordinate descent methods on huge-scale optimization problems
- A coordinate gradient descent method for nonsmooth nonseparable minimization
- Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- Dual randomized coordinate descent method for solving a class of nonconvex problems
- Block coordinate type methods for optimization and learning
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Random Coordinate Descent Methods for Nonseparable Composite Optimization
- Local linear convergence of proximal coordinate descent algorithm
- Coordinate descent methods beyond smoothness and separability
- On convergence of a \(q\)-random coordinate constrained algorithm for non-convex problems
- Randomized block coordinate DC algorithm
- A partially derivative-free cyclic block coordinate descent method for nonseparable composite optimization
- Randomized subspace correction methods for convex optimization
This page was built for publication: Random Coordinate Descent Methods for Nonseparable Composite Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6176428)
