1. A system for optimizing parameters of a structured prediction model, the system comprising: a computer-readable medium; a parameter optimization processor coupled to the computer-readable medium; and a communication interface coupled to the parameter optimization processor and adapted to receive and transmit electronic representations of structured prediction models to and from the parameter optimization processor, respectively, the computer-readable medium having stored thereon software instructions that, when executed by the parameter optimization processor, cause the parameter optimization processor to perform operations including: initializing a group of parameters to respective values corresponding to a state within a set of allowable structured prediction models; bounding a partition function across a number of variable pairs to generate a plurality of bounds each being a quadratic upper bound on a partition function; determining new values for the group of parameters that minimize a sum of the plurality of bounds; setting the group of parameters to the new values; optimizing the parameters by iteratively performing the bounding, determining and setting; and stopping the optimizing when a termination condition is reached.