Exponentiated gradient algorithms for log-linear structured prediction

Citations Over TimeTop 10% of 2007 papers

Abstract

Conditional log-linear models are a commonly used method for structured prediction. Efficient learning of parameters in these models is therefore an important problem. This paper describes an exponentiated gradient (EG) algorithm for training such models. EG is applied to the convex dual of the maximum likelihood objective; this results in both sequential and parallel update algorithms, where in the sequential algorithm parameters are updated in an online fashion. We provide a convergence proof for both algorithms. Our analysis also simplifies previous results on EG for max-margin models, and leads to a tighter bound on convergence rates. Experiments on a large-scale parsing task show that the proposed algorithm converges much faster than conjugate-gradient and L-BFGS approaches both in terms of optimization objective and test error.

Related Papers

• → Scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization(2006)79 cited
• → A modified scaled memoryless BFGS preconditioned conjugate gradient method for unconstrained optimization(2013)27 cited
• → A modified conjugate gradient method based on the self-scaling memoryless BFGS update(2021)5 cited
• → Enhanced conjugate gradient methods for training MLP-networks(2010)4 cited
• → New adaptive conjugate gradient methods choices for unconstrained optimization(2018)