Benjamin Grimmer

Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity

  • Benjamin Grimmer
    • Categories Convex Optimization Tags , ,

    We generalize the classic convergence rate theory for subgradient methods to apply to non-Lipschitz functions via a new measure of steepness. For the deterministic projected subgradient method, we derive a global $O(1/\sqrt{T})$ convergence rate for any function with at most exponential growth. Our approach implies generalizations of the standard convergence rates for gradient descent on … Read more

    Radial Subgradient Descent

  • Benjamin Grimmer
    • Categories Convex Optimization Tags ,

    We present a subgradient method for minimizing non-smooth, non-Lipschitz convex optimization problems. The only structure assumed is that a strictly feasible point is known. We extend the work of Renegar [1] by taking a different perspective, leading to an algorithm which is conceptually more natural, has notably improved convergence rates, and for which the analysis … Read more