Addendum for paper "D. Sontag, T. Jaakkola. New Outer Bounds on the Marginal Polytope. Neural Information Processing Systems (NIPS) 20, Dec. 2007."
1/21/2014:
In section 5, page 6, first paragraph, we say "We optimize the TRW objective with conditional gradient, using linear programming after each gradient step to project onto OUTER." This should instead read "We optimize the TRW objective with conditional gradient, using linear or semidefinite programming to optimize over OUTER."
Our implementation of the conditional gradient algorithm (also known as the Frank-Wolfe algorithm) used Armijo's rule for (inexact) line search. Note, however, that one could just as easily perform exact line search, and this would improve convergence rates (running times were not reported for these experiments).