Adaptive Proximal Average Approximation for Composite Convex Minimization

Authors

  • Li Shen South China University of Technology
  • Wei Liu Tencent AI Lab
  • Junzhou Huang University of Texas at Arlington
  • Yu-Gang Jiang Fudan University
  • Shiqian Ma The Chinese University of Hong Kong

DOI:

https://doi.org/10.1609/aaai.v31i1.10873

Abstract

We propose a fast first-order method to solve multi-term nonsmooth composite convex minimization problems by employing a recent proximal average approximation technique and a novel adaptive parameter tuning technique. Thanks to this powerful parameter tuning technique, the proximal gradient step can be performed with a much larger stepsize in the algorithm implementation compared with the prior PA-APG method, which is the core to enable significant improvements in practical performance. Moreover, by choosing the approximation parameter adaptively, the proposed method is shown to enjoy the O(1/k) iteration complexity theoretically without needing any extra computational cost, while the PA-APG method incurs much more iterations for convergence. The preliminary experimental results on overlapping group Lasso and graph-guided fused Lasso problems confirm our theoretic claim well, and indicate that the proposed method is almost five times faster than the state-of-the-art PA-APG method and therefore suitable for higher-precision required optimization.

Downloads

Published

2017-02-13

How to Cite

Shen, L., Liu, W., Huang, J., Jiang, Y.-G., & Ma, S. (2017). Adaptive Proximal Average Approximation for Composite Convex Minimization. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10873