Tight analyses for subgradient descent I: Lower bounds

Consider the problem of minimizing functions that are Lipschitz and convex, but not necessarily differentiable. We construct a function from this class for which the Tþ iterate of subgradient descent has error Ω(log(T)/T). This matches a known upper bound of O(log(T)/T). We prove analogous results for functions that are additionally strongly convex. There exists such a function for which the error of the Tþ iterate of subgradient descent has error Ω(log(T)/T), matching a known upper bound of O(log(T)/T). These results resolve a question posed by Shamir (2012).