An adaptive accelerated coordinate descent method with non-uniform sampling

<p style="text-align:center;"> <strong>(Communicated by Guihua Lin)</strong> <p style="text-align:justify;"> We consider the optimization problem of minimizing a smooth and convex function. Based on the accelerated coordinate descent method (ACDM) using probabilities $L_i^{1/2}[\sum_{k=1}^n L_k^{1/2}]^{-1}$ for non-uniform sampling (Nesterov Yu. et al., SIAM J. Optim., 110–123, 2017 [3]), we propose an adaptive accelerated coordinate descent method (AACDM) with the same probability distribution determined by $\{L_i\}$ as in ACDM. <p style="text-align:justify;"> In [1, 3], the step sizes of their algorithms are fixed and determined by the (global) parameters $\{L_i\}$. Note that this may not be preferable for practical applications where the (local) parameter values differ from the global counterparts to some extent. This implies that methods which can be adaptive to the local parameters might improve the performance in practice. Motivated by this, in this paper we study the adaptive ACDM, which still requires (global) Lipschitz constants for non-uniform sampling as a prior, while the (local) coordinate Lipschitz constants are determined by backtracking (not neceessarily monotone) to achieve better performance. Both the strongly and non-strongly cases are discussed in this paper. <p style="text-align:justify;"> The non-monotone backtracking line search is included in our adaptive scheme, which performs better (compared with the monotone one) for applications whose local coordinate Lipschitz constants oscillate along the trajectory or become smaller when approaching the tail. The adaptive ACDM is indeed not a monotone method, meaning that the sequence of function values it produces is not necessarily nonincreasing. Since the monotone approach can be used to improve numerical stability (see monotone FISTA in [2]), we also propose an adaptive ACDM in monotone version. <p style="text-align:justify;"> Numerical results on some classic problems show the efficiency of the adaptive scheme. <br />