We propose that approximate Bayesian algorithms should optimize a new criterion, directly derived from the loss, to calculate their approximate posterior which we refer to as pseudo-posterior. Unlike standard variational inference which optimizes a lower bound on the log marginal likelihood, the new algorithms can be analyzed to provide loss guarantees on the predictions with the pseudo-posterior. Our criterion can be used to derive new sparse Gaussian process algorithms that have error guarantees applicable to various likelihoods. Results in learning theory show that, under some general conditions, minimizing training set loss, also known as empirical risk minimization (ERM), provides good solutions in the sense that the true loss of such procedures is bounded relative to the best loss possible in hindsight. Alternative algorithms such as structural risk minimization or regularized loss minimization (RLM) have similar guarantees under more general conditions. On the other hand, Bayesian approaches are, in a sense, prescriptive. Given prior and data, we calculate a posterior distribution that compactly captures all our knowledge about the problem. Then, given a prediction task with an associated loss for wrong predictions, we pick the best prediction given our posterior. This is optimal when the model is correct and the exact posterior is tractable. However, the algorithmic choices are less clear with misspecified models or, even if the model is correct, when exact inference is not possible and the learning algorithm can only return an approximation to the posterior. Since the choices are often heuristically motivated we call such approximations pseudo-posteriors. The question is how the pseudo-posterior should be calculated. In this paper we propose to use learning theory to guide this process. To motivate our approach consider the variational approximation which is one of the most effective methods for approximate inference in Bayesian models. In lieu of finding the exact posterior, variational inference maximizes the ELBO, a lower bound on the marginal likelihood. It is well known that this can be seen alternatively as performing regularized loss minimization. For example, in a model with parameters w, prior p(w ), and data y where p(y|w, x ) = i p(y i |w, x i ), we have log p(y ) ≥ ELBO E where q(w ) is the variational posterior and we have suppressed the dependence on x for visual clarity. Minimizing the negative ELBO, we have a loss term i E q(w) [− log p(y i |w, x i )] and a regularization term d KL (q(w), p(w)). The RLM viewpoint is attractive from the perspective of statistical learning theory because such algorithms are known to have good generalization guarantees (under some conditions). However, the ELBO objective is not matched to the intended use of Bayesian predictors: given a posterior q(w) and test example x * , the Bayesian predictor first calculates the predictive distribution p(y * |x * ) = E q(w) [p(y * |x * , w)] and then, assuming we are interested in the log loss, suffers the loss − log p(y * |x * ). In other words, seen from the perspective of learning theory, variational inference optimizes for , which is the loss of the Bayesian predictor. These observations immediately raise several questions: Should we design empirical risk minimization (ERM) algorithms minimizing L B that produce pseudo-posteriors? Should a regularization term, e.g., d KL , be added? Can we use standard analysis, that typically handles frequentist models, to provide guarantees for such algorithms? We emphasize that this differs from standard non-Bayesian algorithms that perform ERM or RLM to find the best parameter w. Here, we propose to perform ERM or RLM to find the best pseudoposterior q(w) as given by the parameters that define it. In this paper, we show that such an analysis can indeed be performed, and provide results which are generally applicable to Bayesian predictors optimized using ERM. Then, we focus on sparse Gaussian processes (sGP) for which we develop risk bounds for a smoothed variant of log loss 1 and any observation likelihood (the non-conjugate case). The significance of this is conceptual, in that it points to a different principle for designing approximate inference algorithms where we no longer aim to optimize the marginal likelihood (or ELBO), but instead a criterion that is directly related to the loss -this diverges from current practice in the literature. The paper highlights sparse GP because it is an important model with significant recent interest and work. But the approach and results are more generally applicable. To illustrate this point the appendix shows how the results can be applied to the Correlated Topic Model (CTM) of Blei and Lafferty (2006) . It is important to distinguish this work from two previous lines of work. Our earlier work (Sheth and Khardon, 2017) made similar observations w.r.t. the mismatch between the optimization criterion and the intended objective. However, the goal there was to analyze existing algorithms where possible. More concretely we showed that optimizing a criterion related to L G does have some risk guarantees, though these are weaker than the ones in this paper. Here, we propose to explore new algorithms based on direct loss minimization with stronger associated guarantees. In Alaoui and Mahoney (2015) and Burt et al. (2019) , the goal is to show that the sparse GP approximation can be chosen to be very close to the full GP solution. Conditions on the kernel functions and on the algorithm to select inducing input locations and variational distribution are given for this to be true. This is a very strong result showing that nothing is lost by using the sparse approximation. However, in many cases, the number of inducing inputs required is too large (e.g., for Matern kernels). In contrast, our analysis aims at identifying the best sGP posterior in terms of the resulting prediction performance, whether it is close to the full GP posterior or not. In other words, we seek an "agnostic PAC guarantee" for the sparse GP posterior. The paper points out the potential of DLM to yield a new type of approximate pseudoBayesian algorithm. In this paper we focused on the analysis of ERM and application to sparse GP. There are many important questions for future work including analysis for RLM, analysis for hyperparameter selection, removing the need for bounded or smoothed loss in our theorem, and investigating empirical properties of these algorithmic variants.
This paper utilizes the analysis of Lipschitz loss on a bounded hypothesis space to derive new ERM-type algorithms with strong performance guarantees that can be applied to the non-conjugate sparse GP model.