Universal Subgradient and Proximal Bundle Methods for Convex and Strongly Convex Hybrid Composite Optimization

This paper develops two parameter-free methods for solving convex and strongly convex hybrid composite universal problems, namely, a composite subgradient type method and a proximal bundle type method. Functional complexity bounds for the two methods are established in terms of the unknown strong convexity parameter. The two proposed methods are universal with respect to all problem parameters, including the strong convexity one, and require no knowledge of the optimal value. Moreover, in contrast to previous works, they do not restart nor use multiple threads.