A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion

By Yangyang Xu, Wotao Yin. 2013

1,259 citations recorded by the source corpus.

Subfields: Computational Mathematics, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

GSpartan: a Geospatio-Temporal Multi-task Learning Framework for Multi-location Prediction (2016, methodology): “Here, we will use Prox-linear [27] to solve our optimization problem, with the following update formula:”
Intelligent Resource Slicing for eMBB and URLLC Coexistence in 5G and Beyond: A Deep Reinforcement Learning Based Approach (2020, methodology): “The proof is based on [33] which shows the global convergence condition and the asymptotic convergence rate by using the assumption of the Kurdyka-Lojasiewicz property.”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, background): “If f is differentiable, multi-convex or has separable non-smooth parts, then every limit point of the sequence generated by the proximal BCD is a critical point [21,59,69,70], but again, the nonsmooth terms cannot couple more than one block of variable.”
Efficient Multitask Feature and Relationship Learning (2017, background): “x optimization problem. A multi-convex function is a generalization of a bi-convex function (Gorski et al., 2007) into multiple variables or blocks of variables. Deﬁnition 3.1 (Multi-convex function (Xu and Yin, 2013)). A function g(x 1;:::;x k) is called multi-convex if for each block of variables ”
Mathematics of Deep Learning (2017, background): “…(but certainly not limited to) gradient descent, stochastic gradient descent, alternating minimization, block coordinate descent, back-propagation, and quasi-Newton methods – which are typically only guaranteed to converge to a critical point of the objective function [33], [34], [35], [36].”
Modern regularization methods for inverse problems (2018, background): “It is important to emphasize that even for nonsmooth, nonconvex optimization there is a vast amount of recent publications, ranging from forward-backward, respectively proximaltype, schemes [8, 9, 10, 49, 50], over linearized proximal schemes [365, 47, 366, 298], to inertial methods [299, 309], prim”
RGB-T Object Tracking: Benchmark and Baseline (2018, methodology): “Since each subproblem is convex, we can guarantee that the limit point by our algorithm satisﬁes the Nash equilibrium conditions [59].”
Collaborative Filtering with Graph Information: Consistency and Scalable Methods (2015, methodology): “In [2], it is shown that any local minimizer of (5) is a global minimizer of (5) if k is larger than the true rank of the underlying matrix.3 From [25], the alternating minimization procedure is guaranteed to globally converge to a block coordinate-wise minimum4 of (5).”
A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update (2014, methodology): “in every T consecutive iterations | otherwise in arbitrary orders. If the blocks are selected cyclically from 1 through s, then (1.2) reduces to the cyclic block proximal gradient (Cyc-BPG) method in [49]. If the sblocks are randomly shued at the beginning of each cycle, each block is updated at lea”
A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition (2020, background): “, [3], [4], [10], [42], [44]), we are not aware of previous analyses including projection-free methods for convex sets and smooth non convex objectives.”
Accessing From the Sky: A Tutorial on UAV Communications for 5G and Beyond (2019, methodology): “To tackle this problem efﬁciently, one useful approach to obtain a generally locally optimal solution for it is by alternately updating one block of variables with the other block ﬁxed, which is known as the BCD method [138,139].”
ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates (2015, background): “m assignment ensures load balance and fault tolerance. In addition, it has been observed numerically on certain problems [14] that random coordinate selection accelerates convergence. Furthermore, in [54,55], the algorithms with random coordinate selection keep clear of low-quality local solutions i”
Global Optimality in Tensor Factorization, Deep Learning, and Beyond (2015, background): “…descent, block coordinate descent, back-propagation, and quasi-newton methods – are typically only guaranteed to converge to a critical point or local minimum of the objective function (Mairal et al., 2010; Rumelhart et al., 1988; Ngiam et al., 2011; Wright and Nocedal, 1999; Xu and Yin, 2013).”
Matrix recovery from quantized and corrupted measurements (2014, background): “Therefore, (Q-MC) can be solved approximately via block-coordinate descent [21].”
Weighted Sum-Rate Maximization for Reconfigurable Intelligent Surface Aided Wireless Networks (2019, methodology): “To eliminate the one dimensional search of λ as well as the expensive matrix inverse operation, we apply the prox-linear BCD update rule as follows [46]:”