optimal iteration-complexity

Improved Analysis of Restarted Accelerated Gradient and Augmented Lagrangian Methods via Inexact Proximal Point Frameworks

  • Matthew X. Burns
  • Jiaming Liang
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    This paper studies a class of double-loop (inner-outer) algorithms for convex composite optimization. For unconstrained problems, we develop a restarted accelerated composite gradient method that attains the optimal first-order complexity in both the convex and strongly convex settings. For linearly constrained problems, we introduce inexact augmented Lagrangian methods, including a basic method and an outer-accelerated … Read more

    Unifying restart accelerated gradient and proximal bundle methods

  • Jiaming Liang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    This paper presents a novel restarted version of Nesterov’s accelerated gradient method and establishes its optimal iteration-complexity for solving convex smooth composite optimization problems. The proposed restart accelerated gradient method is shown to be a specific instance of the accelerated inexact proximal point framework introduced in “An accelerated hybrid proximal extragradient method for convex optimization … Read more