Variance Reduced Random Relaxed Projection Method for Constrained Finite-sum Minimization Problems

西南交通大学

“创源”大讲堂研究生学术讲座

海 报

讲座时间： 2022年12月9日14:30—15:30

讲座地点：腾讯会议号：393 812 857；密码：1209

主讲人简介：

夏福全，四川师范大学数学科学学院教授，博士研究生导师。主要从事最优化理论及应用方面的研究。到现在为止，已在国内外知名学术刊物上发表SCI收录论文30余篇，主持了四川省教育厅基金，四川省科技厅应用基础项目，教育部博士点基金和教育部重点项目。应邀多次访问了台湾的国立中山大学、高雄医学大学和长庚大学，韩国的Gyeongsang大学和Gyungnam大学。

讲座内容简介：

Title: Variance Reduced Random Relaxed Projection Method for Constrained Finite-sum Minimization Problems

(Joint work with Zhichun Yang, Kai Tu and Man-Chung Yue)

Abstract. We consider the problem of minimizing a large sum of smooth convex functions subject to a large number of constraints defined by convex functions that are possibly non-smooth. Such a problem finds a wide range of applications in many areas, such as machine learning and signal processing. In this paper, we devise a new random projection method (RPM) for efficiently solving this problem. Compared with existing RPMs, our proposed algorithm features two useful algorithmic ideas. First, at each iteration, instead of projection onto a subset of the feasible region, our algorithm requires only a relaxed projection in the sense that only the projection onto a half-space approximation of the subset is needed. This significantly reduces the per iteration computational cost as the relaxed projection admits a closed-form formula. Second, to exploit the structure that the objective function is a large sum of convex functions, the variance reduction technique is incorporated into our algorithm to improve the empirical convergence behaviour. As our theoretical contributions, under an error bound-type condition and some other standard conditions, we prove that almost surely the proposed algorithm converges to an optimal solution and that both the optimality and feasibility gaps decrease to zero, with rates and , respectively. As a side contribution, we also show that the said error bound-type condition holds some mild assumptions, which could be of independent interest. Numerical results on synthetic problem instances are also presented to demonstrate the practical effectiveness of the variance reduction technique and the superiority of our proposed RPM as compared with two existing ones.