Hybrid Random/Deterministic Parallel Algorithms for Convex and Nonconvex Big Data Optimization
Hybrid Random/Deterministic Parallel Algorithms for Convex and Nonconvex Big Data Optimization
复制标题
DOI：
10.1109/tsp.2015.2436357
复制
发表时间：
2014-07
影响因子：
5.4
通讯作者：
Amir Daneshmand;F. Facchinei;V. Kungurtsev;G. Scutari
中科院分区：
文献类型：
--
作者：
Amir Daneshmand;F. Facchinei;V. Kungurtsev;G. Scutari
我们提出了一个分解框架，用于并行优化可微（可能非凸）函数和非光滑（可能不可分）凸函数的和。后一个术语通常用于加强解决方案中的结构，通常是稀疏性。这项工作的主要贡献是一种新的并行、混合随机/确定性分解方案，其中，在每次迭代中，通过最小化原始非凸函数的凸代理来同时更新（块）变量子集。为了解决大规模问题，需要更新的（块）变量是根据随机和确定性混合过程选择的，它同时抓住了纯确定性和随机更新方案的优点。证明了所提方案的收敛性。数值结果表明，在大规模问题上，无论在凸问题还是非凸问题上，所提出的随机/确定性混合算法都优于随机和确定性混合算法。
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 parallel, hybrid random/deterministic decomposition scheme wherein, at each iteration, a subset of (block) variables is updated at the same time by minimizing a convex surrogate of the original nonconvex function. To tackle huge-scale problems, the (block) variables to be updated are chosen according to a 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 compares favorably to random and deterministic schemes on both convex and nonconvex problems.