Two commonly arising computational tasks in Bayesian learning are Optimization (Maximum A Posteriori estimation) and Sampling (from the posterior distribution). In the convex case these two problems are efficiently reducible to each other. Recent work (Ma et al. 2019) shows that in the non-convex case, sampling can sometimes be provably faster. We present a simpler and stronger separation. We then compare sampling and optimization in more detail and show that they are provably incomparable: there are families of continuous functions for which optimization is easy but sampling is NP-hard, and vice versa. Further, we show function families that exhibit a sharp phase transition in the computational complexity of sampling, as one varies the natural temperature parameter. Our results draw on a connection to analogous separations in the discrete setting which are well-studied.

In this work, we investigate the use of normalizing flows to model conditional distributions. In particular, we use our proposed method to analyze inverse problems with invertible neural networks by maximizing the posterior likelihood. Our method uses only a single loss and is easy to train. This is an improvement on the previous method that solves similar inverse problems with invertible neural networks but which involves a combination of several loss terms with ad-hoc weighting. In addition, our method provides a natural framework to incorporate conditioning in normalizing flows, and therefore, we can train an invertible network to perform conditional generation. We analyze our method and perform a careful comparison with previous approaches. Simple experiments show the effectiveness of our method, and more comprehensive experimental evaluations are undergoing.

We study the problem, introduced by Qiao and Valiant, of learning from untrusted batches. Here, we assume $m$ users, all of whom have samples from some underlying distribution $p$ over $1, \ldots, n$. Each user sends a batch of $k$ i.i.d. samples from this distribution; however an $\epsilon$-fraction of users are untrustworthy and can send adversarially chosen responses. The goal is then to learn $p$ in total variation distance. When $k = 1$ this is the standard robust univariate density estimation setting and it is well-understood that $\Omega (\epsilon)$ error is unavoidable. Suprisingly, Qiao and Valiant gave an estimator which improves upon this rate when $k$ is large. Unfortunately, their algorithms run in time exponential in either $n$ or $k$. We first give a sequence of polynomial time algorithms whose estimation error approaches the information-theoretically optimal bound for this problem. Our approach is based on recent algorithms derived from the sum-of-squares hierarchy, in the context of high-dimensional robust estimation. We show that algorithms for learning from untrusted batches can also be cast in this framework, but by working with a more complicated set of test functions. It turns out this abstraction is quite powerful and can be generalized to incorporate additional problem specific constraints. Our second and main result is to show that this technology can be leveraged to build in prior knowledge about the shape of the distribution. Crucially, this allows us to reduce the sample complexity of learning from untrusted batches to polylogarithmic in $n$ for most natural classes of distributions, which is important in many applications. To do so, we demonstrate that these sum-of-squares algorithms for robust mean estimation can be made to handle complex combinatorial constraints (e.g. those arising from VC theory), which may be of independent technical interest.

Wessel Bruinsma ‡ wpb23@cam.ac.uk 1. Introduction A principled approach to prediction tasks is to choose a statistical model that explains the data. The choice of the model class is crucial and has to observe the bias-variance tradeoff, which motivates the need for principled approaches to selecting the best model class from a set of options. Whilst model selection can be done manually by trial and error, the process tends to consume considerable time and resources and be prone to human biases. Bayesian model selection (MacKay, 1992; Rasmussen and Ghahramani, 2001), treats the model class as a random variable and computes its posterior distribution. It offers a built-in complexity regulariser, commonly known as Bayesian Occams razor, which penalises models whose complexity is excessive or too modest.

In the last years, crowdsourcing is transforming the way classification training sets are obtained. Instead of relying on a single expert annotator, crowdsourcing shares the labelling effort among a large number of collaborators. For instance, this is being applied to the data acquired by the laureate Laser Interferometer Gravitational Waves Observatory (LIGO), in order to detect glitches which might hinder the identification of true gravitational-waves. The crowdsourcing scenario poses new challenging difficulties, as it deals with different opinions from a heterogeneous group of annotators with unknown degrees of expertise. Probabilistic methods, such as Gaussian Processes (GP), have proven successful in modeling this setting. However, GPs do not scale well to large data sets, which hampers their broad adoption in real practice (in particular at LIGO). This has led to the recent introduction of deep learning based crowdsourcing methods, which have become the state-of-the-art. However, the accurate uncertainty quantification of GPs has been partially sacrificed. This is an important aspect for astrophysicists in LIGO, since a glitch detection system should provide very accurate probability distributions of its predictions. In this work, we leverage the most popular sparse GP approximation to develop a novel GP based crowdsourcing method that factorizes into mini-batches. This makes it able to cope with previously-prohibitive data sets. The approach, which we refer to as Scalable Variational Gaussian Processes for Crowdsourcing (SVGPCR), brings back GP-based methods to the state-of-the-art, and excels at uncertainty quantification. SVGPCR is shown to outperform deep learning based methods and previous probabilistic approaches when applied to the LIGO data. Moreover, its behavior and main properties are carefully analyzed in a controlled experiment based on the MNIST data set.

V arious problems in Engineering and Statistics require the computation of the likelihood ratio function of two probability densities. In classical approaches the two densities are assumed known or to belong to some known parametric family. In a data-driven version we replace this requirement with the availability of data sampled from the densities of interest. For most well known problems in Detection and Hypothesis testing we develop solutions by providing neural network based estimates of the likelihood ratio or its transformations. This task necessitates the definition of proper optimizations which can be used for the training of the network. The main purpose of this work is to offer a simple and unified methodology for defining such optimization problems with guarantees that the solution is indeed the desired function. Our results are extended to cover estimates for likelihood ratios of conditional densities and estimates for statistics encountered in local approaches. HE likelihood ratio of two probability densities is a function that appears in a variety of problems in Engineering and Statistics. Characteristic examples [1], [2] constitute Hypothesis testing, Signal detection, Sequential hypothesis testing, Sequential detection of changes, etc. Many of these problems also use the likelihood ratio under a transformed form with the most frequent example being the log-likelihood ratio. In all these problems the main assumption is that the corresponding probability densities are available under some functional form. What we aim in this work is to replace this requirement with the availability of data sampled from each of the densities of interest. As we mentioned, the computation of the likelihood ratio function relies on the knowledge of the probability densities which, for the majority of applications, is an unrealistic assumption. One can instead propose parametric families of densities and, with the help of available data, estimate the parameters and form the likelihood ratio function. However, with the advent of Data Science and Deep Learning there is a phenomenal increase in need for processing data coming from images, videos etc. For most of these cases it is very difficult to propose any meaningful parametric family of densities that could reliably describe their statistical behavior. Therefore, these techniques tend to be unsuitable for most of these datasets. If parametric families cannot be employed one can always resort to nonparametric density estimation [3] and then form the likelihood ratio. These approaches are purely data-driven but require two different approximations, namely one for each density.

We propose a probabilistic framework for modelling and exploring the latent structure of relational data. Given feature information for the nodes in a network, the scalable deep generative relational model (SDREM) builds a deep network architecture that can approximate potential nonlinear mappings between nodes' feature information and the nodes' latent representations. Our contribution is two-fold: (1) We incorporate high-order neighbourhood structure information to generate the latent representations at each node, which vary smoothly over the network. (2) Due to the Dirichlet random variable structure of the latent representations, we introduce a novel data augmentation trick which permits efficient Gibbs sampling. The SDREM can be used for large sparse networks as its computational cost scales with the number of positive links. We demonstrate its competitive performance through improved link prediction performance on a range of real-world datasets.

Gramatyka 10, 30-067 Krak ow, Poland Abstract --While we would like to predict exact values, available incomplete information is rarely sufficient - usually allowing only to predict conditional probability distributions. This article discusses hierarchical correlation reconstruction (HCR) methodology for such prediction on example of usually unavailable bid-ask spreads, predicted from more accessible data like closing price, volume, high/low price, returns. In HCR methodology we first normalize marginal distributions to nearly uniform like in copula theory. Then here we model each moment (separately) of predicted variable as a linear combination of mixed moments of known variables using least squares linear regression - getting accurate description with interpretable coefficients describing linear relations between moments. Combining such predicted moments we get predicted density as a polynomial, for which we can e.g. There were performed 10-fold cross-validation log-likelihood tests for 22 DAX companies, leading to very accurate predictions, especially when using individual models for each company as there were found large differences between their behaviors. Additional advantage of the discussed methodology is being computationally inexpensive, finding and evaluation a model with hundreds of parameters and thousands of data points takes a second on a laptop. I NTRODUCTION While it is more convenient to work on exact values, real life predictions usually have some uncertainty, controlling of which could allow e.g. to distinguish nearly certain predictions from the practically worthless ones. Generally, wanting to predict Y variable from X ( X 1,...,X d) variables, if there is no a strict relation, they often come from some complicated joint probability distribution - knowing X x, we can only predict Pr ( Y X x) conditional probability distribution.

Modern machine learning models are often so complex that they achieve vanishing classification error on the training set. Max-margin linear classifiers are among the simplest classification methods that have zero training error (with linearly separable data). Despite this simplicity, their high-dimensional behavior is not yet completely understood. We assume to be given i.i.d. data $(y_i,{\boldsymbol x}_i)$, $i\le n$ with ${\boldsymbol x}_i\sim {\sf N}({\boldsymbol 0},{\boldsymbol \Sigma})$ a $p$-dimensional Gaussian feature vector, and $y_i \in\{+1,-1\}$ a label whose distribution depends on a linear combination of the covariates $\langle {\boldsymbol \theta}_*,{\boldsymbol x}_i\rangle$. We consider the proportional asymptotics $n,p\to\infty$ with $p/n\to \psi$, and derive exact expressions for the limiting prediction error. Our asymptotic results match simulations already when $n,p$ are of the order of a few hundreds. We explore several choices for the the pair $({\boldsymbol \theta}_*,{\boldsymbol \Sigma})$, and show that the resulting generalization curve (test error error as a function of the overparametrization ratio $\psi=p/n$) is qualitatively different, depending on this choice. In particular we consider a specific structure of $({\boldsymbol \theta}_*,{\boldsymbol \Sigma})$ that captures the behavior of nonlinear random feature models or, equivalently, two-layers neural networks with random first layer weights. In this case, we observe that the test error is monotone decreasing in the number of parameters. This finding agrees with the recently developed `double descent' phenomenology for overparametrized models.

In variational inference, the complicated target is approximated by a closest member relative to the Kullback-Leibler (KL) divergence in a pre-specified family of tractable densities. In many large-scale machine learning applications including clustering problems [11, 32], image classification [25, 27] and topic models [21, 7], variational inference can be orders of magnitude faster than the traditional sampling based approaches such as Markov Chain Monte Carlo (MCMC). In particular, by turning the integration, or sampling, problem into an optimization problem, variational inference can take advantage of modern optimization tools such as stochastic optimization techniques [20, 17] and distributed optimization architecture [1, 8] for further improving its efficiency. Among various approximating schemes, mean-field approximation is the most common type of variational inference that is conceptually simple, implementation-wise easy and particularly suitable for problems involving large numbers of latent variables. The word "mean-field" is originated from the mean-field theory in physics where despite complex interactions among many particles in a many (infinite) body system, all interactions to any one particle can be approximated by a single averaged effect from a "mean-field". In variational inference, by restricting the approximating family of the mean-field to be all density functions that are fully factorized over (blocks of) unknown variables, the associated optimization problem of finding a closest weih2@illinois.edu