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 …

$$\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 …