Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization

Abstract

We propose a decomposition framework for the parallel optimization of the sum of a differentiable {(possibly nonconvex)} function and a nonsmooth (possibly nonseparable), convex one. The latter term is usually employed to enforce structure in the solution, typically sparsity. The main contribution of this work is a novel \emph{parallel, hybrid random/deterministic} decomposition scheme wherein, at each iteration, a subset of (block) variables is updated at the same time by minimizing local convex approximations of the original nonconvex function. To tackle with huge-scale problems, the (block) variables to be updated are chosen according to a \emph{mixed random and deterministic} procedure, which captures the advantages of both pure deterministic and random update-based schemes. Almost sure convergence of the proposed scheme is established. Numerical results show that on huge-scale problems the proposed hybrid random/deterministic algorithm outperforms both random and deterministic schemes.

The order of the authors is alphabetical

References in corpus (5)

• Parallel Selective Algorithms for Big Data Optimization
• Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization
• Feature Clustering for Accelerating Parallel Coordinate Descent
• A Fast Active Set Block Coordinate Descent Algorithm for ${\ell }_1$-regularized least squares
• A Second-Order Method for Compressed Sensing Problems with Coherent and Redundant Dictionaries

Cited by in corpus (10)

• Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
• Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
• A Parallel Stochastic Approximation Method for Nonconvex Multi-Agent Optimization Problems
• Inexact Block Coordinate Descent Algorithms for Nonsmooth Nonconvex Optimization
• Distributed Training of Graph Convolutional Networks
• Distributed Gradient Methods with Variable Number of Working Nodes
• Distributed stochastic optimization with gradient tracking over strongly-connected networks
• NEXT: In-Network Nonconvex Optimization
• Representation of Federated Learning via Worst-Case Robust Optimization Theory
• Decentralized Dictionary Learning Over Time-Varying Digraphs