Smooth minimization of nonsmooth functions with parallel coordinate descent methods

DOI10.1007/978-3-030-12119-8_4MaRDI QIDQ2325237zbMATH OpenOpenAlexFDO

Authors Olivier Fercoq, Peter Richtárik

Publication date 9 September 2019

Full work available at URL https://arxiv.org/abs/1309.5885

zbMATH Keywords

coordinate descentLipschitz constantparallel computingsmoothing

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Deterministic scheduling theory in operations research (90B35) Nonconvex programming, global optimization (90C26)

Abstract: We study the performance of a family of randomized parallel coordinate descent methods for minimizing the sum of a nonsmooth and separable convex functions. The problem class includes as a special case L1-regularized L1 regression and the minimization of the exponential loss ("AdaBoost problem"). We assume the input data defining the loss function is contained in a sparse $mimesn$ matrix $A$ with at most $omega$ nonzeros in each row. Our methods need $$ iterations to find an approximate solution with high probability, where $au$ is the number of processors and $$ for the fastest variant. The notation hides dependence on quantities such as the required accuracy and confidence levels and the distance of the starting iterate from an optimal point. Since $$ is a decreasing function of $au$, the method needs fewer iterations when more processors are used. Certain variants of our algorithms perform on average only $O(nz(A)/n)$ arithmetic operations during a single iteration per processor and, because $$ decreases when $omega$ does, fewer iterations are needed for sparser problems.

Recommendations

• Parallel coordinate descent methods for big data optimization
• Accelerated, parallel, and proximal coordinate descent
• Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
• Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm

Cited in

(16)

• Synchronous parallel block coordinate descent method for nonsmooth convex function minimization
• Asynchronous Lagrangian scenario decomposition
• Restarting the accelerated coordinate descent method with a rough strong convexity estimate
• Parallel block coordinate minimization with application to group regularized regression
• A parallel line search subspace correction method for composite convex optimization
• Parallel coordinate descent methods for big data optimization
• Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• Stochastic block mirror descent methods for nonsmooth and stochastic optimization
• On optimal probabilities in stochastic coordinate descent methods
• Accelerated, parallel, and proximal coordinate descent
• Distributed block coordinate descent for minimizing partially separable functions
• Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
• On the complexity of parallel coordinate descent
• A generic coordinate descent solver for non-smooth convex optimisation
• Coordinate descent methods beyond smoothness and separability

This page was built for publication: Smooth minimization of nonsmooth functions with parallel coordinate descent methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2325237)