  This paper considers an inexact primal-dual algorithm for semi-infinite
programming (SIP) for which it provides general error bounds. To implement the
dual variable update, we create a new prox function for nonnegative measures
which turns out to be a generalization of the Kullback-Leibler divergence for
probability distributions. We show that under suitable conditions on the error,
this algorithm achieves an $\mathcal{O}(1/\sqrt{K})$ rate of convergence in
terms of the optimality gap and constraint violation. We then use our general
error bounds to analyze the convergence and sample complexity of a specific
primal-dual SIP algorithm based on Monte Carlo integration. Finally, we provide
numerical experiments to demonstrate the performance of our algorithm.
