Accelerated dual-averaging primal–dual method for composite convex minimization

ABSTRACT

Dual averaging-type methods are widely used in industrial machine learning applications due to their ability to promoting solution structure (e.g. sparsity) efficiently. In this paper, we propose a novel accelerated dual-averaging primal–dual algorithm for minimizing a composite convex function. We also derive a stochastic version of the proposed method that solves empirical risk minimization, and its advantages on handling sparse data are demonstrated both theoretically and empirically.

KEYWORDS:

• Dual averaging algorithm
• primal–dual
• empirical risk minimization
• acceleration
• sparse data

2010 MATHEMATICS SUBJECT CLASSIFICATION:

• 90c25

Acknowledgements

The authors are grateful to two anonymous referees for providing insightful and constructive comments that greatly improved the presentation of this paper. The research of S. Ma was supported in part by a startup package in the Department of Mathematics at University of California, Davis.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Notes on contributors

Conghui Tan

Conghui Tan obtained his PhD degree in Systems Engineering and Engineering Management from the Chinese University of Hong Kong in 2019. He is currently an AI researcher in WeBank Co., Ltd., Shenzhen, China.

Yuqiu Qian

Yuqiu Qian received her PhD degree in Computer Science from the University of Hong Kong in 2019. She is currently an applied researcher in Tencent, Shenzhen, China.

Shiqian Ma

Shiqian Ma received his PhD degree in Industrial Engineering and Operations Research from Columbia University in 2011. He is currently an associate professor in the Department of Mathematics at University of California, Davis.

Tong Zhang

Tong Zhang obtained his PhD in Computer Science from Stanford University in 1999. He is a chair professor of Computer Science and Mathematics at the Hong Kong University of Science and Technology.