When solving problems, particularly constrained optimization in the field of reinforcement learning, I have noticed the use of dual gradient descent. An example of this is in model-based reinforcement learning, where we constrain the KL-divergence between 2 policies.

When would dual gradient descent be preferred over methods like interior-point methods? A example of paper for which the authors go with dual gradient descent, is here - Learning Contact-Rich Manipulation Skills with Guided Policy Search


Daul gradient descent is a "first order method" in that it depends only on the gradient and not second order derivatives. Interior point methods depend on second derivatives and are thus "second order methods."

Second order methods are generally preferred for small to medium size problems because they require fewer iterations to converge and are often faster overall, even when the computational work per iteration may be higher.

However, for very large sized problems it eventually becomes impossible to store and factor the $n$ by $n$ matrices that arise in second-order methods. For example, if your problem has one million variables, then you'll end up having to deal with matrices of size one million rows by one million columns. The storage requirements for such a matrix and its factorization may be impractical, even though the matrix is typically sparse.

For very large scale problems, first-order methods, which require only $O(n)$ storage, are often preferable, even though the theoretical convergence rate may be slower. First-order methods have become the focus of much of the research in optimization in the last decade as researchers have focused on very large scale optimization problems, particularly those arising in machine learning on sets of "big data" and in the training of deep neural networks.

  • 3
    $\begingroup$ I'll add that many researchers are naively using first-order methods in situations where second-order methods would actually be more efficient and not require excessive storage. $\endgroup$ – Brian Borchers Jan 29 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.