Adaptive Proximal Average Approximation for Composite Convex Minimization

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 (Yu 2013), 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 stateof-the-art PA-APG method and therefore suitable for higherprecision required optimization.

Authors

• Li Shen Shenzhen Campus of Sun Yat-sen University
• Wei Liu University of Technology Sydney
• Junzhou Huang University of Texas at Arlington
• Yu-Gang Jiang Shanghai Key Lab of Intell. Info. Processing, School of CS, Fudan University Shanghai Collaborative Innovation Center of Intelligent Visual Computing
• Shiqian Ma Rice University

Keywords

No keywords are indexed for this paper.