Approximated Structured Prediction for Learning Large Scale Graphical Models

This manuscript contains the proofs for "A Primal-Dual Message-Passing Algorithm for Approximated Large Scale Structured Prediction" We derive the Lagrangian by introducing the Lagrange multipliers Anymaa (33") for every marginalization constraint:13an bggfiyfiafija): bawdy"), and Lagrange multipliers 0r for every equality We obtain the dual function by minimizing the beliefs over their compact domain, i.e. Deriving the dual by minimizing over the compact set of beliefs enables us to obtain an unconstrained dual, which corresponds to the approximated structured prediction program. Its final form is derived similarly to Claim. We find the optimal Amyyywoxgv) whenever the gradient vanishes, i.e. A Hx7y7afiv (3912) 'i' Anymaa (go) $957971?