1. From ADMM to Proximal Gradient Descent

    Sat 26 July 2014

    At first blush, ADMM and Proximal Gradient Descent (ProxGrad) appear to have very little in common. The convergence analyses for these two methods are unrelated, and the former operates on an Augmented Lagrangian while the latter directly minimizes the primal objective. In this post, we'll show that after a slight …

  2. Accelerated Proximal Gradient Descent

    Thu 25 April 2013

    \(\def\prox{\text{prox}}\) In a previous post, I presented Proximal Gradient, a method for bypassing the \(O(1 / \epsilon^2)\) convergence rate of Subgradient Descent. This method relied on assuming that the objective function could be expressed as the sum of 2 functions, \(g(x)\) and \(h(x)\), with …

  3. Proximal Gradient Descent

    Fri 19 April 2013

    \( \def\prox{\text{prox}} $ In a [previous post][subgradient_descent_usage], I mentioned that one cannot hope to asymptotically outperform the $O(\frac{1}{\epsilon^2})\) convergence rate of Subgradient Descent when dealing with a non-differentiable objective function. This is in fact only half-true; Subgradient Descent cannot be beat using only first-order …