We show a connection between sampling and optimization on discrete domains. For a family of distributions μ defined on size k subsets of a ground set of elements that is closed under external fields, we show that rapid mixing of natural local random walks implies the existence of simple approximation algorithms to find maxμ(·). More precisely we show that if t-step down-up random walks have spectral gap at least inverse polynomially large, then t-step local search can find maxμ(·) within a factor of k^O(k). As the main application of our result, we show that 2-step local search achieves a nearly-optimal k^O(k)-factor approximation for MAP inference on nonsymmetric k-DPPs. This is the first nontrivial multiplicative approximation algorithm for this problem. We establish the connection between sampling and optimization by showing that an exchange inequality, a concept rooted in discrete convex analysis, can be derived from fast mixing of local random walks. We further advance the state-of-the-art on the mixing of random walks for nonsymmetric DPPs and more generally sector-stable distributions, by obtaining the tightest possible bound on the step size needed for polynomial-time mixing of random walks. Our improvement brings the step size down by a factor of 2 compared to prior works, and is potentially of independent interest in sampling applications. The improvement on step size directly translates to quadratically faster local search steps for MAP inference.