We propose a new family of subgradient- and gradient-based methods which converges with optimal complexity for convex optimization problems whose feasible region is simple enough. This includes cases where the objective function is non-smooth, smooth, have composite/saddle structure, or are given by an inexact oracle model. We unified the way of constructing the subproblems which are necessary to be solved at each iteration of these methods. This permitted us to analyze the convergence of these methods in a unified way compared to previous results which required different approaches for each method/algorithm. Our contribution rely on two well-known methods in non-smooth convex optimization: the mirror-descent method by Nemirovski-Yudin and the dual-averaging method by Nesterov. Therefore, our family of methods includes them and many other methods as particular cases. For instance, the proposed family of classical gradient methods and its accelerations generalize Devolder et al.'s, Nesterov's primal/dual gradient methods, and Tseng's accelerated proximal gradient methods. Also our family of methods can partially become special cases of other universal methods, too. As an additional contribution, the novel extended mirror-descent method removes the compactness assumption of the feasible region and the fixation of the total number of iterations which is required by the original mirror-descent method in order to attain the optimal complexity.
Citation
Research Report B-477, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology
Article
View A Family of Subgradient-Based Methods for Convex Optimization Problems in a Unifying Framework