optimal subgradient method – Optimization Online

Exact convergence rate of the last iterate in subgradient methods

Published: 2023/07/23

Convex Optimization, Nonsmooth Optimization constant step length, constant step size, convergence rate, convex optimization, last iterate, nonsmooth optimization, optimal subgradient method, subgradient method

We study the convergence of the last iterate in subgradient methods applied to the minimization of a nonsmooth convex function with bounded subgradients. We first introduce a proof technique that generalizes the standard analysis of subgradient methods. It is based on tracking the distance between the current iterate and a different reference point at each … Read more

OSGA: A fast subgradient algorithm with optimal complexity

Published: 2014/02/05

Arnold Neumaier

Convex Optimization, Nonsmooth Optimization complexity, convex optimization, large-scale optimization, nesterov's optimal method, nonsmooth optimization, optimal first-order methods, optimal subgradient method, smooth optimization, strongly convex

This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst … Read more