In this paper, we present an algorithm for minimizing the difference between\ntwo submodular functions using a variational framework which is based on (an\nextension of) the concave-convex procedure [17]. Because several commonly used\nmetrics in machine learning, like mutual information and conditional mutual\ninformation, are submodular, the problem of minimizing the difference of two\nsubmodular problems arises naturally in many machine learning applications. Two\nsuch applications are learning discriminatively structured graphical models and\nfeature selection under computational complexity constraints. A commonly used\nmetric for measuring discriminative capacity is the EAR measure which is the\ndifference between two conditional mutual information terms. Feature selection\ntaking complexity considerations into account also fall into this framework\nbecause both the information that a set of features provide and the cost of\ncomputing and using the features can be modeled as submodular functions. This\nproblem is NP-hard, and we give a polynomial time heuristic for it. We also\npresent results on synthetic data to show that classifiers based on\ndiscriminative graphical models using this algorithm can significantly\noutperform classifiers based on generative graphical models.\n