We consider the problem of estimating the parameter of interest of a discrete exponential family model under the presence of nuisance parameters. Maximum conditional likelihood estimation in this situation is often intractable owing to the computational cost of the normalizing constant. To overcome this problem, we construct a composite local Bregman divergence for probability distributions on the conditional sample space. The corresponding estimator does not require a normalizing constant, which enables us to estimate the parameter of interest efficiently. Our construction of divergence is based on the graph structure on a conditional sample space. The graph structure is derived using a Markov basis of the nuisance part of the model and some related results from algebraic statistics.