Variable Metric Proximal Gradient Method with Diagonal Barzilai-Borwein Stepsize

Youngsuk Park, Sauptik Dhar, Stephen P. Boyd, Mohak Shah

Abstract

Variable metric proximal gradient (VM-PG) is a widely used class of convex optimization method. Lately, there has been a lot of research on the theoretical guarantees of VM-PG with different metric selections. However, most such metric selections are dependent on (an expensive) Hessian, or limited to scalar stepsizes like the Barzilai-Borwein (BB) stepsize with lots of safeguarding. Instead, in this paper we propose an adaptive metric selection strategy called the diagonal Barzilai-Borwein (BB) stepsize. The proposed diagonal selection better captures the local geometry of the problem while keeping per-step computation cost similar to the scalar BB stepsize i.e. $O(n)$. Under this metric selection for VM-PG, the theoretical convergence is analyzed. Our empirical studies illustrate the improved convergence results under the proposed diagonal BB stepsize, specifically for ill-conditioned machine learning problems for both synthetic and real-world datasets.
BibTeX
@inproceedings{park2019variable,
  author = {Youngsuk Park and Sauptik Dhar and Stephen P. Boyd and Mohak Shah},
  title = {{Variable Metric Proximal Gradient Method with Diagonal Barzilai-Borwein Stepsize}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2019},
  doi = {10.1109/icassp40776.2020.9054193},
}
Figure