We derive inferential procedures for large sample sizes that remain valid under data-dependent significance levels (so-called "post-hoc valid inference"). Classical statistical tools require that the significance level -- the "type-I error" -- is selected prior to seeing or analyzing any data. This restriction leads to some drawbacks. For instance, if an analyst generates an inconclusive confidence interval, repeating the process with a larger significance level is not an option -- the result is final. Recently, e-values have emerged as the solution to this problem, being both necessary and sufficient tools for performing various forms of post-hoc inference. All such results, however, have thus far been nonasymptotic. As a result, they inherit familiar limitations of nonasymptotic inferential procedures such as requiring strong moment assumptions and being conservative in general. This paper develops a theory of post-hoc inference in the asymptotic setting, yielding asymptotic post-hoc confidence sets and asymptotic post-hoc p-values that make weaker assumptions and are sharper than their nonasymptotic counterparts.

Deep equilibrium models (DEQs) have recently emerged as a powerful paradigm for training infinitely deep weight-tied neural networks that achieve state of the art performance across many modern machine learning tasks. Despite their practical success, theoretically understanding the gradient descent dynamics for training DEQs remains an area of active research. In this work, we rigorously study the gradient descent dynamics for DEQs in the simple setting of linear models and single-index models, filling several gaps in the literature. We prove a conservation law for linear DEQs which implies that the parameters remain trapped on spheres during training and use this property to show that gradient flow remains well-conditioned for all time. We then prove linear convergence of gradient descent to a global minimizer for linear DEQs and deep equilibrium single-index models under appropriate initialization and with a sufficiently small step size. Finally, we validate our theoretical findings through experiments.

Shapley values and probabilistic values provide principled ways to assign credit in problems such as data valuation, but their estimation is challenging because the underlying utility function is defined on all (2^n) subsets of (n) items. In this talk, I will describe a causal perspective on this problem. The key idea is to treat the subset-indexed utility (u(S)) as a multi-treatment response surface and to view the target value as a linear functional of that surface. For a fixed player, this leads to a weighted average of marginal treatment effects; for the full value vector, it leads to questions of design, sample reuse, and efficient correction. Using this viewpoint, I will revisit several lines of work in the Shapley literature and connect them to familiar ideas from causal inference, including matched or paired designs, inverse-probability weighting, regression adjustment, and doubly robust style estimators. I will focus on how these methods trade off variance reduction, sample reuse, and structural modeling of the utility function, and on why this perspective may be useful for understanding recent advances in semivalue estimation.

When model predictions inform downstream decision making, a natural question is under what conditions can the decision-makers simply respond to the predictions as if they were the true outcomes. Calibration suffices to guarantee that simple best-response to predictions is optimal. However, calibration for high-dimensional prediction outcome spaces requires exponential computational and statistical complexity. The recent relaxation known as decision calibration ensures the optimality of the simple best-response rule while requiring only polynomial sample complexity in the dimension of outcomes. However, known results on calibration and decision calibration crucially rely on linear loss functions for establishing best-response optimality. A natural approach to handle nonlinear losses is to map outcomes y into a feature space ϕ(y) of dimension m, then approximate losses with linear functions of ϕ(y). Unfortunately, even simple classes of nonlinear functions can demand exponentially large or infinite feature dimensions m. A key open problem is whether it is possible to achieve decision calibration with sample complexity independent of~m. We begin with a negative result: even verifying decision calibration under standard deterministic best response inherently requires sample complexity polynomial in~m. Motivated by this lower bound, we investigate a smooth version of decision calibration in which decision-makers follow a smooth best-response. This smooth relaxation enables dimension-free decision calibration algorithms. We introduce algorithms that, given poly(|A|,1/ϵ) samples and any initial predictor~p, can efficiently post-process it to satisfy decision calibration without worsening accuracy. Our algorithms apply broadly to function classes that can be well-approximated by bounded-norm functions in (possibly infinite-dimensional) separable RKHS.

Private Evolution (PE) is a training-free method for differentially private synthetic data generation that has shown strong empirical performance, but until recently lacked theoretical guarantees. In this talk, I will present the main result of Private Evolution Converges (https://arxiv.org/pdf/2506.08312), which proves that PE can generate an (ε,δ)-differentially private synthetic dataset with expected 1-Wasserstein distance of order (d/(nε))^(1/d) to the sensitive data. This gives the first convergence guarantee for PE and places this practical method on a firmer theoretical foundation. I will also discuss extensions of this paper that I'm currently working on.

We give a gentle introduction to optimal transport theory and Gromov-Wasserstein distances, as well as some of their statistical applications. At the end, we discuss some of our recent progress in this area, described below. The Gromov-Wasserstein distance with inner product cost (IGW distance) quantifies the discrepancy between Borel probability measures on (possibly different) Euclidean spaces which have finite second moment. The IGW distance provides a natural framework for comparing the shapes of heterogeneous datasets, although its exact computation is generally NP-hard. Previous work has studied the metric geometry arising from the IGW distance, but it is generally statistically and computationally difficult to estimate the IGW distance and barycenter from samples. In this work, we rewrite the IGW distance between uncentered Gaussian measures on separable Hilbert spaces as the solution of a quadratic optimization problem on the Stiefel manifold, which we solve numerically in simulations. Moreover, we prove upper and lower bounds on the IGW distance between Gaussians (up to a Cauchy-Schwarz gap), and for centered Gaussians, we recover a natural closed-form expression for the IGW distance and barycenter. Furthermore, we analytically resolve the multi-marginal IGW problem between Gaussians. As an extension, we rewrite the multi-marginal optimal transport problem between Gaussians as the optimal value of a semidefinite program and solve it efficiently using a rank-deficiency constraint. Finally, we apply our results to synthetic experiments, including clustering heterogeneous user profiles. Collaborators: Sasha Podkopaev, Shiva Kasiviswanathan, Aaditya Ramdas, and Ziv Goldfeld

Data Shapley is an important tool for data valuation, which quantifies the contribution of individual data points to machine learning models. In practice, group-level data valuation is desirable when data providers contribute data in batch. However, we identify that existing group-level extensions of Data Shapley are vulnerable to shell company attacks, where strategic group splitting can unfairly inflate valuations. We propose Faithful Group Shapley Value (FGSV) that uniquely defends against such attacks. Building on original mathematical insights, we develop a provably fast and accurate approximation algorithm for computing FGSV. This is the joint work with Kiljae Lee, Weijing Tang, and Yuan Zhang.

The paper studies the problem of uncertainty quantification for time series prediction, with the goal of providing easy-to-use algorithms with formal guarantees. The algorithms we present build upon ideas from conformal prediction and control theory, are able to prospectively model conformal scores in an online setting, and adapt to the presence of systematic errors due to seasonality, trends, and general distribution shifts. This theory both simplifies and strengthens existing analyses in online conformal prediction.

Like students facing hard exam questions, large language models sometimes guess when uncertain, producing plausible yet incorrect statements instead of admitting uncertainty. Such “hallucinations” persist even in state-of-the-art systems and undermine trust. We argue that language models hallucinate because the training and evaluation procedures reward guessing over acknowledging uncertainty, and we analyze the statistical causes of hallucinations in the modern training pipeline. Hallucinations need not be mysterious—they originate simply as errors in binary classification. If incorrect statements cannot be distinguished from facts, then hallucinations in pretrained language models will arise through natural statistical pressures. We then argue that hallucinations persist due to the way most evaluations are graded—language models are optimized to be good test-takers, and guessing when uncertain improves test performance. This “epidemic” of penalizing uncertain responses can only be addressed through a socio-technical mitigation: modifying the scoring of existing benchmarks that are misaligned but dominate leaderboards, rather than introducing additional hallucination evaluations. This change may steer the field toward more trustworthy AI systems. https://arxiv.org/pdf/2509.04664

Representation learning has shown great success at learning low-dimensional, empirically useful representations of high-dimensional data in an unsupervised manner. Despite this success, standard approaches are limited to association-level insights and are inadequate for strong generalization. As a key step toward more principled representation learning, causal representation learning (CRL) has emerged as a cutting-edge field that merges the strengths of statistical inference, machine learning, and causal inference. Its objective is to estimate the ground truth, identifiable latent representations and rich structures that model the interactions among the variables in the latent space. In this talk, we will mainly show how to learn causal representations from unstructured, high-dimensional data observed under multiple (interventional) environments. To that end, we establish connections between score functions and CRL. First, we address CRL in the nonparametric setting under relatively rich interventional information. Then, we consider a linear transformation from latent to observed variables, discussing crucial aspects for algorithm design including intervention types (perfect vs. imperfect), intervention size (single vs. multi-node), and sample complexity guarantees. https://www.jmlr.org/papers/volume26/24-0194/24-0194.pdf

We will consider decision-making processes that involve evaluating and then selecting items (e.g., scientific peer review, hiring, admissions). Traditionally, the eventual selection is performed by first obtaining expert evaluations, followed by rules or deliberations, and eventually deterministically selecting a subset of applications. More recently, citing drawbacks of the traditional approach, a number of funding agencies worldwide have moved towards a different decision model. These agencies have incorporated “partial lotteries” into their decision-making: the review process remains similar to that of the traditional process (sometimes omitting deliberations), but the final decisions introduce a randomized component that still respects experts’ evaluations. We will first identify several problems in current implementations of such partial lotteries. We will then present a principled approach to designing improved partial lotteries with strong theoretical guarantees and empirical performance. Based on joint work with Alexander Goldberg and Giulia Fanti. Blog post: https://researchonresearch.blog/2025/07/12/randomizing-selection-under-uncertainty-designing-principled-partial-lotteries-for-grant-funding-and-beyond/

We will discuss the foundational ideas behind Automatic Debiased Machine Learning (AutoDML), a framework to costruct of efficient estimators for causal and semiparametric parameters. Standard machine learning methods often yield biased estimates of causal quantities in high-dimensional settings, while traditional debiasing techniques rely on the Efficient Influence Function (EIF), which can be challenging to derive and may involve unstable components such as inverse probability weights. AutoDML provides a principled alternative: it builds double-robust, root-n consistent estimators without requiring an explicit EIF expression. Instead, it leverages the Riesz representation theorem to directly learn the EIF’s key component by minimizing a Riesz loss function, offering an “automatic” and stable approach to debiased estimation that unifies ideas from semiparametric theory and modern machine learning.

Large pre-trained models trained on internet-scale data are often not ready for deployment out-of-the-box. They are heavily fine-tuned and aligned using large quantities of human preference data, usually elicited using pairwise comparisons. While aligning an AI/ML model to human preferences or values, it is important to ask whose preference and values we are aligning it to? The prominent approaches of preference alignment are severely limited due to inherent assumption of uniformity by the preference models. We aim to overcome this limitation by building mathematical foundations for learning heterogeneous human preferences. In this talk, I will present PAL, a personalize-able reward modelling framework for pluralistic alignment. PAL has modular design that leverages commonalities across users while catering to individual personalization, enabling efficient few-shot generalization. PAL is versatile to be applied to various domains and matches or outperforms state-of-the-art methods on both text-to-text and text-to-image tasks with 100x fewer parameters in practice. I will also present theoretical results on per user sample complexity for generalization and fundamental limitations when there are limited pairwise comparisons.

During this talk, I will briefly discuss some modern methods for ensuring valid inference after model selection including: data splitting, data fission, simultanaeous inference, and conditional selective inference. I will then discuss some recent work that comment on the relative efficiency of each of these frameworks. Recent papers: Infer-and-widen, or not? (https://arxiv.org/abs/2408.06323) On Selecting and Conditioning in Multiple Testing and Selective Inference (https://arxiv.org/abs/2207.13480) Background papers: https://arxiv.org/abs/2112.11079 https://arxiv.org/abs/1611.05401 https://arxiv.org/abs/1306.1059 https://arxiv.org/abs/1311.6238

I will present a few interesting results on quantitative central limit theorems in terms of integral probability metrics and the implications for the study of bagging. In particular, the results provide a finite-sample smoothing phenomenon of bagging. The first part of the talk will be based on https://arxiv.org/abs/2306.14382.

We study the problem of finding the index of the minimum value of a vector from noisy observations. This problem is relevant in population/policy comparison, discrete maximum likelihood, and model selection. By integrating concepts and tools from cross-validation and differential privacy, we develop a test statistic that is asymptotically normal even in high-dimensional settings, and allows for arbitrarily many ties in the population mean vector. The key technical ingredient is a central limit theorem for globally dependent data characterized by stability. We also propose a practical method for selecting the tuning parameter that adapts to the signal landscape.

Off-Policy Evaluation of a Linear Functional is a fundamental problem in both causal inference and reinforcement learning, encompassing key challenges such as average treatment effect estimation and off-policy evaluation. Prior work has explored the asymptotic difficulty of this problem by deriving the semiparametric efficiency bound and showing that the Augmented Inverse Propensity Weighted (AIPW) estimator achieves it. More recent research has extended these ideas to the nonasymptotic setting with adaptive sampling, leading to locally minimax-optimal procedures for data collected adaptively. In this talk, I will present a comprehensive overview of these results, beginning with the semiparametric efficiency framework and then demonstrating how these insights can be leveraged to develop algorithms with strong finite-sample guarantees in adaptive settings. The talk will be based on the following papers: https://www.jstor.org/stable/2998560 https://arxiv.org/abs/2209.13075 https://arxiv.org/abs/2411.12786

Stochastic Convex Optimization (SCO) and Stochastic Saddle Point (SSP) problems are important in ML. At the same time, protecting users’ privacy has emerged as a critical concern in ML applications, and Differential Privacy (DP) has become the gold standard to ensure formal privacy guarantees. Existing lower bounds for SCO under DP indicate that the excess of risk is polynomial-in-the-dimension in the worst case. However, it has been shown that under some extra geometric assumptions it is possible to achieve polylogarithmic-in-the-dimension excess of risk. We generalize the polylogarithmic-in-the-dimension error rates to the more general problem of SSP under DP, by using very different techniques from the ones used for the SCO case. Talk based on: https://arxiv.org/pdf/2403.02912

When data is collected in an adaptive manner, even simple methods like ordinary least squares can exhibit non-normal asymptotic behavior. We consider settings with adaptively collected data, such as multi-armed bandit problems, and demonstrate how martingale CLTs can be used to provide accurate inference in linear regression problems. The talk will be based on the following papers: https://projecteuclid.org/journals/annals-of-statistics/volume-10/issue-1/Least-Squares-Estimates-in-Stochastic-Regression-Models-with-Applications-to/10.1214/aos/1176345697.full, https://arxiv.org/abs/1712.06695, https://arxiv.org/abs/2002.03217, https://arxiv.org/pdf/2107.02266

Image segmentation algorithms can be understood as a collection of pixel classifiers, for which the outcomes of nearby pixels are correlated. Classifier models can be calibrated using Inductive Conformal Prediction, but this requires holding back a sufficiently large calibration dataset for computing the distribution of non-conformity scores of the model's predictions. If one only requires only marginal calibration on the image level, this calibration set consists of all individual pixels in the images available for calibration. However, if the goal is to attain proper calibration for each individual pixel classifier, the calibration set consists of individual images. In a scenario where data are scarce (such as the medical domain), it may not always be possible to set aside sufficiently many images for this pixel-level calibration. The method we propose, dubbed ``Kandinsky calibration'', makes use of the spatial structure present in the distribution of natural images to simultaneously calibrate the classifiers of ``similar'' pixels. This can be seen as an intermediate approach between marginal (imagewise) and conditional (pixelwise) calibration, where non-conformity scores are aggregated over similar image regions, thereby making more efficient use of the images available for calibration. We run experiments on segmentation algorithms trained and calibrated on subsets of the public MS-COCO and Medical Decathlon datasets, demonstrating that Kandinsky calibration method can significantly improve the coverage. When compared to both pixelwise and imagewise calibration on little data, the Kandinsky method achieves much lower coverage errors, indicating the data efficiency of the Kandinsky calibration.

Full abstract (with Latex rendering) here: https://arxiv.org/abs/2502.06188

We introduce a framework called causal geodesy for studying the landscape of stochastic interventions that lie between the two extremes of performing no intervention and performing a sharp intervention that sets an exposure equal to a specific value. We do this by constructing paths of distributions that interpolate between the treatment density and a point mass at the target intervention. Of particular interest are paths corresponding to geodesics in some metric. We then consider the interpreting and estimation of the corresponding causal effects.

In the Graph Matching (also known as Network Alignment) problem, the goal is to find a shared vertex labeling (matching) between two observed, unlabelled graphs, focusing on maximizing the alignment of their edges. This problem can be framed as a random instance of the well-known quadratic assignment problem. We explore two versions of graph matching: the seeded version, where partial matching is provided as side information, and the seedless version, where only the input graphs are given. For the seeded case, we introduce a statistically guaranteed algorithm based on the projected power method and demonstrate its effectiveness in the correlated Gaussian Wigner model, a widely used generative framework for jointly generated graphs. For the seedless case, we propose a novel convex relaxation approach combined with a Mirror Descent algorithm, demonstrating its capability to recover the ground truth matching in the case of isomorphic input graphs. References: https://www.jmlr.org/papers/volume25/22-0402/22-0402.pdf https://arxiv.org/abs/2310.20609

Joint work with Arun Kuchibhotla (soon to be on arXiv): Inference for online algorithms is a difficult problem because estimation of asymptotic variance can inflate the computational cost. Previous works have proposed online estimation of the covariance matrix as well as batching methods to construct confidence intervals. In this work, we propose the use of the recently developed HulC procedure for uncertainty quantification in the online setting. The highlights of this procedure include: no inflation in the computational cost; no estimation of the asymptotic variance; and asymptotically exact coverage. We compare the performance of this procedure with those of previous works in the context of linear and logistic regression over a wide range of covariance settings and dimension-aspect ratios. Our main finding is that we get comparable or better coverage properties compared to the methods that estimate the asymptotic variance.

Co-training is a semi-supervised learning technique that leverages two distinct views (i.e., sets of features) of the data to iteratively expand a labeled set using unlabeled examples. In this talk, I will introduce the classical co-training framework and algorithm based on Combining Labeled and Unlabeled Data with Co-Training. I will then reformulate the co-training setting as a missing data problem, characterized by non-monotone missingness. This perspective allows us to connect with the rich literature on missing data mechanisms and offers tools to potentially improve the co-training estimator.

Group data valuation is increasingly important in real-world applications, where data comes from different contributors—such as copyright owners, data providers, or institutions—and benefits such as model revenue need to be fairly allocated. Existing methods often adopt a “group-as-individual” approach, treating each group as a single unit, but we find this leads to systematic biases, especially under unequal or strategic partitioning. In this talk, I’ll present a new formulation of group Shapley value that defines a group’s value as the sum of individual contributions, preserving key axioms—including a new partition invariance axiom that ensures consistency across groupings. We also develop a computationally efficient approximation algorithm that achieves a nearly linear runtime in dataset size. Through synthetic experiments and real-world applications such as copyright attribution in generative AI, we demonstrate that our method achieves both improved fairness and computational efficiency compared to existing approaches. This is joint work with Kiljae Lee, Yuan Zhang, and Weijing Tang.

This talk starts from a vision of establishing a field of "Generative Data Science," which aims to elucidates the underlying principles behind generative AI. This vision is supported by the recent observation that "creating something out of nothing" is possible and beneficial through synthetic data generation. The rest of talks focus on the initial steps towards this goal by showcasing our recent progresses in measuring fidelity (of generated image data), watermarking (on generated tabular data) and privacy auditing (of synthetic data).

Approximate message passing is a powerful machinery that has found a wide array of applications in areas like high dimensional statistics, signal processing, machine learning, etc. We will give a gentle introduction to this topic starting with some motivation in statistical estimation, followed by some basic analysis of the algorithm. We will also briefly review some recent progress in the literature and discuss some potential future problems of the topic.

Adaptive experiments such as multi-arm bandits adapt the treatment-allocation policy and/or the decision to stop the experiment to the data observed so far. This has the potential to improve outcomes for study participants within the experiment, to improve the chance of identifying best treatments after the experiment, and to avoid wasting data. Seen as an experiment (rather than just a continually optimizing system) it is still desirable to draw statistical inferences with frequentist guarantees. The concentration inequalities and union bounds that generally underlie adaptive experimentation algorithms can yield overly conservative inferences, but at the same time the asymptotic normality we would usually appeal to in non-adaptive settings can be imperiled by adaptivity. In this article we aim to explain why, how, and when adaptivity is in fact an issue for inference and, when it is, understand the various ways to fix it: reweighting to stabilize variances and recover asymptotic normality, always-valid inference based on joint normality of an asymptotic limiting sequence, and characterizing and inverting the non-normal distributions induced by adaptivity.

Motivated by work with Jeff Schneider (Robotics Insitute), I will first give a basic intro to bootstrapping -- can it be done anytime anywhere? What's the use? Then, I'll discuss the paper by Yixin Fang, Jinfeng Xu, Lei Yang (https://arxiv.org/abs/2306.02205): In many applications involving large dataset or online learning, stochastic gradient descent (SGD) is a scalable algorithm to compute parameter estimates and has gained increasing popularity due to its numerical convenience and memory efficiency. While the asymptotic properties of SGD-based estimators have been well established, statistical inference such as interval estimation remains much unexplored. The classical bootstrap is not directly applicable if the data are not stored in memory. The plug-in method is not applicable when there is no explicit formula for the covariance matrix of the estimator. In this paper, we propose an online bootstrap procedure for the estimation of confidence intervals, which, upon the arrival of each observation, updates the SGD estimate as well as a number of randomly perturbed SGD estimates. The proposed method is easy to implement in practice. We establish its theoretical properties for a general class of models that includes linear regressions, generalized linear models, M-estimators and quantile regressions as special cases. The finite-sample performance and numerical utility is evaluated by simulation studies and real data applications.

Accurate estimates of causal effects play a key role in decision-making across applications such as healthcare, economics, and operations. In the absence of randomized experiments, a common approach to identifying causal effects uses covariate adjustment on a set of random variables. In this talk, I will discuss causal effect estimation via covariate adjustment in discrete distributions, focusing on finite-sample guarantees and the interplay between structure learning and causal effect estimation. To begin, I will present a new PAC bound on the worst case estimation error of covariate adjustment, which is exponential in the size of the adjustment set. Motivated by this result, I will present two constraint-based algorithms to search for smaller adjustment sets, PAC guarantees on these algorithms, and bounds on the misspecification error from violations of these constraints, which are combined into a full sample complexity analysis of the algorithms.

We study the problem of distribution-free dependence detection and modeling through the new framework of binary expansion statistics (BEStat). The binary expansion testing (BET) avoids the problem of non-uniform consistency and improves upon a wide class of commonly used methods (a) by achieving the minimax rate in sample size requirement for reliable power and (b) by providing clear interpretations of global relationships upon rejection of independence. The binary expansion approach also connects the symmetry statistics with the current computing system to facilitate efficient bitwise implementation. Modeling with the binary expansion linear effect (BELIEF) is motivated by the fact that two linearly uncorrelated binary variables must be also independent. Inferences from BELIEF are easily interpretable because they describe the association of binary variables in the language of linear models, yielding convenient theoretical insight and striking parallels with the Gaussian world. With BELIEF, one may study generalized linear models (GLM) through transparent linear models, providing insight into how modeling is affected by the choice of link. We explore these phenomena and provide a host of related theoretical results. This is joint work with Benjamin Brown and Xiao-Li Meng.

We introduce a framework for testing conditional independence relationships between time series that are possibly high-dimensional, nonstationary, and nonlinear. As far as we know, this is the first conditional independence test that can be used with a single realization of a nonstationary nonlinear time series (X, Y, Z). Consider the setting in which X and Y are univariate time series, and Z is a multivariate time series. Our test has two key steps. First, regress X on Z, and Y on Z using black-box time-varying nonlinear regression estimators. Notably, we allow the error processes to be temporally dependent and nonstationary. Second, estimate the time-varying variances of the process of error products based on the process of residual products. Using these estimates of the time-varying variances, we can approximate the desired quantile of our test statistic using a bootstrap procedure based on a distribution-uniform version of the strong Gaussian approximation for nonstationary nonlinear time series from Mies and Steland [MS22]. We extend this testing procedure to the high-dimensional setting, where the dimensions of the processes are allowed to grow with the sample size. We conduct a real data analysis with nonstationary nonlinear epidemiological time series. Specifically, we determine whether a population’s level of infectivity contains auxiliary information about future case growth rates of COVID-19. We discuss how to gain power with our ?2-type test statistic by using high-resolution data from groups of time series, such as sensor networks in neuroscience and physics, nearby cities in epidemiology and economics, or related price series in finance and e-commerce. Our testing framework opens the door to many downstream statistical applications which utilize conditional independence tests. In our companion paper [WHR24], we use our test as the basis of a causal discovery algorithm for nonstationary nonlinear time series, which we use to study epidemiological dynamics.

We consider the problem of estimating the asymptotic variance of a function defined on a Markov chain, an important step for statistical inference of the stationary mean. We design a novel recursive estimator that requires O(1) computation at each step, does not require storing any historical samples or any prior knowledge of run-length, and has optimal O(1n) rate of convergence for the mean-squared error (MSE) with provable finite sample guarantees. Here, n refers to the total number of samples generated. Our estimator is based on linear stochastic approximation of an equivalent formulation of the asymptotic variance in terms of the solution of the Poisson equation. We generalize our estimator in several directions, including estimating the covariance matrix for vector-valued functions, estimating the stationary variance of a Markov chain, and approximately estimating the asymptotic variance in settings where the state space of the underlying Markov chain is large. We also show applications of our estimator in average reward reinforcement learning (RL), where we work with asymptotic variance as a risk measure to model safety-critical applications. We design a temporal-difference type algorithm tailored for policy evaluation in this context. We consider both the tabular and linear function approximation settings. Our work paves the way for developing actor-critic style algorithms for variance-constrained RL.

We present a sequential version of the kernelized Stein discrepancy, which allows for conducting goodness-of-fit tests for unnormalized densities that are continuously monitored and adaptively stopped. That is, the sample size need not be fixed prior to data collection; the practitioner can choose whether to stop the test or continue to gather evidence at any time while controlling the false discovery rate. In stark contrast to related literature, we do not impose uniform boundedness on the Stein kernel. Instead, we exploit the potential boundedness of the Stein kernel at arbitrary point evaluations to define test martingales, that give way to the subsequent novel sequential tests. We prove the validity of the test, as well as an asymptotic lower bound for the logarithmic growth of the wealth process under the alternative. We further illustrate the empirical performance of the test with a variety of distributions, including restricted Boltzmann machines.

Many statistical applications can be framed as the solution of stochastic optimizations whose objective function is estimated from data. This framework, widely known as M-estimation, includes maximum likelihood estimation, functional estimation, regression, and classification. Classical inferential methodologies for M-estimation often rely on strong assumptions about the underlying distribution as well as the asymptotic properties of the estimator. As a result, there is a severe shortage of inferential tools for high-dimensional settings. A simple method is proposed for constructing a confidence set for M-estimation, which remains valid without assumptions about the dimension of data. The proposed confidence set is based on a sample-splitting procedure, and conditions are provided under which its diameter converges at an optimal rate. Furthermore, the proposed method is applicable to non-standard problems where the inference has been notoriously difficult.

I'll review and discuss Hoeffding, Bennett, Bernstein, bounded difference/Efron-Stein inequalities for scalars and matrices, empirical Bernstein inequalities for scalars, and present two matrix empirical Bernstein inequalities.

Transport maps are important statistical objects, chief among them the optimal transport map. A nice nonparametric theory on estimation of optimal transport maps have recently been developed, showing that estimation can be performed stlightly faster than the usual non-parametric rate, as a consequence of the smoothness property of the optimal transport. However, computational challenges prevent us from computing the optimal transport efficiently, and people have suggested the rectified flow as a cheaper surrogate. This estimator can be estimated via non-parametric regression. In this talk I will introduce the rectified transport framework and discuss its smoothness properties in bounded and unbounded domains. Based on that I will comment on a bias and variance analysis of the associated non-parametric estimator. This also enjoys benefits over the usual kernel regression estimator

Given K uncertainty sets that are arbitrarily dependent --- for example, confidence intervals for an unknown parameter obtained with K different estimators, or prediction sets obtained via conformal prediction based on K different algorithms --- we address the question of how to efficiently combine them in a black-box manner to produce a single uncertainty set. We present a simple and broadly applicable majority vote procedure that produces a merged set with (nearly) the same error guarantee as the input sets. We then extend this core idea in a few ways: we show that weighted averaging can be a powerful way to incorporate prior information, and a simple randomization trick produces strictly smaller merged sets (without altering the coverage guarantee). Finally, when deployed in online settings, we show how the exponential weighted majority algorithm can be employed in order to learn a good weighting over time.

Empirical risk minimization may lead to poor prediction performance when the target distribution differs from the source populations. This talk discusses leveraging data from multiple sources and constructing more generalizable and transportable prediction models. We introduce an adversarially robust prediction model to optimize a worst-case reward concerning a class of target distributions and show that our introduced model is a weighted average of the source populations' conditional outcome models. We leverage this identification result to robustify arbitrary machine learning algorithms, including, for example, high-dimensional regression, random forests, and neural networks. In our adversarial learning framework, we propose a novel sampling method to quantify the uncertainty of the adversarial robust prediction model. Moreover, we introduce guided adversarially robust transfer learning (GART) that uses a small amount of target domain data to guide adversarial learning. We show that GART achieves a faster convergence rate than the model fitted with the target data. Our comprehensive simulation studies suggest that GART can substantially outperform existing transfer learning methods, attaining higher robustness and accuracy.

The main paper by Chen et al (2021) is here: https://arxiv.org/abs/1610.08637 Usually when we think of gradient descent algorithms, we seek an estimator for the "true parameter theta" that minimizes the loss function for the population. Often (especially for maching learning applications) we are satisfied with a point estimate with convergence guarantees. But can we use SGD to produce a confidence interval for theta? Yes. The idea is the following: "Averaged SGD" (ASGD), also known as Polyak-Ruppert averaging, is known to have desirable asymptotic properties (Polyak-Juditsky1992): not only does it converge to the population minimizing parameter under a convex objective function (with some key assumptions), it also has an asymptotic normal distribution. However, this result isn't useful for inference unless we can also estimate the asymptotic variance in an online fashion. Chen et al (2021) come up with 2 methods to do so. I will cover the following background: (1) GD vs SGD vs ASGD (2) martingales and the martingale CLT (3) the main proof (sketch) of the Polyak-Juditsky 1992 asymptotic normality result for ASGD (4) Chen et al's (2021) estimators for conducting inference via ASGD (5) If we have time, other useful notes on finite sample inference via ASGD

Confidence intervals (and hypothesis tests) are fundamental components of statistical analysis, integral to any rigorous scientific study. The traditional framework for constructing confidence intervals for a functional/parameter $\theta_0$ starts with an estimator, denoted as $\widehat{\theta}_n$, possessing a known rate of convergence and an estimable limiting distribution. Resampling techniques, such as bootstrap and subsampling, have been introduced to relax the assumption of a known convergence rate and to provide estimates of limiting distributions. However, there are still scenarios that elude analysis through resampling techniques. In this presentation, I propose a robust framework for statistical inference, with 'robust' being interpreted as resilient to distributional assumptions. The recently introduced HulC methodology can be viewed as a special case within this framework. Despite a slight loss in efficiency, this proposed framework can offer elegant solutions to a variety of complex inference problems, including confidence intervals for online algorithms, cube-root estimators, shape-constrained estimators, non-/semi-parametric estimators, and non-standard regression problems. The foundation of this talk rests on concepts developed in my recent works, namely, 'The HulC: Confidence Regions from Convex Hulls (2023+, JRSS-B)' and 'Median Regularity and Honest Inference (2023, Biometrika).'

In the past decade major advances have been made in machine learning and statistics by explicitly modeling the feedback loop between a model or algorithm and its outcome. Despite this growing body of work (variously called ‘performative prediction’ or ‘strategic classification’), these ideas have been slow to reach applied social science. Yet, paradoxically, social scientists and philosophers of science have been grappling with the same ideas for over a century. This talk aims to give an overview of performative prediction from the perspective of the social sciences and philosophy of science. The goals of this talk are twofold. First, to summarize the developments of neighboring scientific disciplines for statisticians and computer scientists so they can better understand the historical importance of these questions. Second, to argue that while there are two distinct approaches to performative prediction, only one represents a revolutionary new paradigm in modeling social phenomena. No prior knowledge of the social sciences or philosophy of science is assumed. Two major works in this area--"Performative Prediction" (Perdomo et al. 2020) and "Strategic Classification" (Hardt et al. 2016)--will loosely serve as the technical foundation for the talk.

Consider the problem of approximating the distribution of a polynomial of $n$ independent data points in $\R^d$, where $d$ may grow as an arbitrary function of $n$. The first part of the talk focuses on a COLT’23 paper (https://arxiv.org/abs/2302.05686), where we consider the special case of degree-two U-statistics in the context of kernel-based distribution tests. We prove that the limiting distribution of the U-statistics undergoes a phase transition from the non-degenerate Gaussian limit to the degenerate limit, regardless of its degeneracy and depending only on a moment ratio. A surprising consequence is that a non-degenerate U-statistic in high dimensions can have a non-Gaussian limit with a larger variance and asymmetric distribution. In a simple empirical setting, our results correctly predict how the test power of MMD and KSD scales with dimension d and kernel bandwidth. In the second part of the talk, I will briefly discuss results in an unpublished work, where we generalise such findings to degree-$m$ polynomials with $m=o(log n)$. We prove a general Gaussian universality result for such polynomials by Lindeberg’s principle, which extends the invariance principle of Mossel et al. (AoM, 2010). We also prove that the bounds obtained are near-optimal.

We study what dataset assumption permits solving offline multi-agent games. In stark contrast to the offline single-agent Markov decision process, we show that the single strategy concentration assumption is insufficient for learning the Nash equilibrium (NE) strategy in offline two-player zero-sum Markov games. On the other hand, we propose a new assumption named unilateral concentration and design a pessimism-type algorithm that is provably efficient under this assumption. We further show that the unilateral concentration assumption is necessary for learning an NE strategy and can be generalized to multi-agent general-sum games. Lastly, we consider offline congestion games and show different feedback types require qualitatively different dataset coverage conditions.

Why do passive inference when you can do active inference?! I'll discuss a recent framework for active statistical inference proposed by Zrnic and Candes, which leverages predictions by a black-box model to help decide which observations should be labelled. If time allows, I'll relate this work to prediction-powered inference. Main paper: https://arxiv.org/pdf/2403.03208.pdf.

We revisit the question of whether the strong law of large numbers (SLLN) holds uniformly in a rich family of distributions, culminating in a distribution-uniform generalization of the Marcinkiewicz-Zygmund SLLN. These results can be viewed as extensions of Chung's distribution-uniform SLLN to random variables with uniformly integrable $q^\text{th}$ absolute central moments for $0 < q < 2;\ q \neq 1$. Furthermore, we show that uniform integrability of the $q^\text{th}$ moment is both sufficient and necessary for the SLLN to hold uniformly at the Marcinkiewicz-Zygmund rate of $n^{1/q - 1}$. These proofs centrally rely on novel distribution-uniform analogues of some familiar almost sure convergence results including the Khintchine-Kolmogorov convergence theorem, Kolmogorov's three-series theorem, a stochastic generalization of Kronecker's lemma, and the Borel-Cantelli lemmas. We also consider the non-identically distributed case and an application to strongly consistent variance estimation.

A classical question in statistics and in online learning, is that of model selection: given a collection of predictors, produce one which is as good as the best predictor (upto a small additive error). Variants of this basic primitive have many "applications" in theory, often yielding surprising results in new contexts. I will discuss, at a high-level, some old ideas and results in model selection aggregation, and work towards an analysis of Q-aggregation. Most of the ideas of the analysis follow from old papers -- https://arxiv.org/abs/1203.2507 and https://arxiv.org/pdf/1301.6080.pdf Some newer papers (which I won't cover) provide a new perspective and some fresh motivation -- https://arxiv.org/pdf/1803.09349.pdf and https://arxiv.org/pdf/2102.12919.pdf

Sign and rank statistics have been widely studied because they enable flexible and powerful non-parametric testing on a number of problems. I will focus on testing for symmetry. In the one-dimensional case, the null hypothesis is H0: X=-X, for which the so-called sign test and Wilcoxon's absolute sum-rank tests are known to enjoy distribution-freeness under the null and remarkable asymptotic efficiency properties, regardless of their non-parametric nature. Unfortunately, it is not fully clear how the notion of rank and sign can be extended to the multidimensional case. In this discussion, I will present the work by Huang and Sen (2023). I will comment on different notions of symmetry that appear in the multidimensional case and how the mathematical framework of optimal transportation can be leveraged to develop natural extensions of the sign and rank statistics, which, in turn, are used as natural statistics for testing for symmetry in the multidimensional case. Remarkably, the nice asymptotic properties of such tests are retained in the multidimensional case, suggesting that the proposed framework adds up to a natural extension. The discussion will consist of an introductory commentary on the efficiency of sign-rank tests in the one-dimensional case (mostly from Van der Vaart's book) and elementary results on optimal transportation, followed by an exposition of the main results in Huang and Sen. Huang, Zhen, and Bodhisattva Sen. "Multivariate symmetry: Distribution-free testing via optimal transport." arXiv preprint arXiv:2305.01839 (2023). https://arxiv.org/pdf/2305.01839.pdf

We study batched bandit experiments and consider the problem of inference conditional on the realized stopping time, assignment probabilities, and target parameter, where all of these may be chosen adaptively using information up to the last batch of the experiment. Absent further restrictions on the experiment, we show that inference using only the results of the last batch is optimal. When the adaptive aspects of the experiment are known to be location-invariant, in the sense that they are unchanged when we shift all batch-arm means by a constant, we show that there is additional information in the data, captured by one additional linear function of the batch-arm means. In the more restrictive case where the stopping time, assignment probabilities, and target parameter are known to depend on the data only through a collection of polyhedral events, we derive computationally tractable and optimal conditional inference procedures. Talk will be based on: https://arxiv.org/pdf/2309.12162.pdf.

The sliced Wasserstein metric (SW) compares probability measures on Rd by taking averages of the Wasserstein distances between projections of the measures to lines. The distance has found a range of applications in statistics and machine learning, as it is easier to approximate and compute than the Wasserstein distance in high dimensions. This talk will focus on analytic properties of the sliced Wasserstein distance related to its statistical properties. Namely, when the measures considered are ``nice'' then the SW metric is comparable to the (homogeneous) negative Sobolev norm H˙−(d+1)/2. In particular, this is connected to the parametric finite sample approximation rate noted by Manole, Balakrishnan, and Wasserman '22. This allows us to view SW as a `curved' version of Maximum Mean Discrepancy. This talk is based on a joint work with Dejan Slepcev. https://arxiv.org/abs/2311.05134

The MLE is perhaps the most common estimator for fitting finite mixture models, but it presents significant computational challenges due to the lack of convexity of the space of mixing measures with a bounded number of components. An appealing alternative is the nonparametric maximum likelihood estimator (NPMLE), which maximizes the likelihood over the convex set of all mixing measures, including those which are not finite. Beyond its computational tractability, the mixture NPMLE is appealing in that is a completely tuning-parameter free estimator, unlike other tractable estimators like the method of moments. In this talk, I will present a few recent results on the mixture NPMLE. I will spend most of my time discussing paper [1], which proves (very surprisingly) that this estimator performs a form of automatic model selection: with high probability, the NPMLE is supported on a set which is finite, and whose cardinality grows logarithmically with the sample size. I will then explain how this result can be used to re-derive known convergence rates for the NPMLE in Hellinger distance. If time permits, I will close with a broader discussion on open questions about the minimax rate for estimating a mixture density in Hellinger distance, in particular making references to paper [2]. [1] https://arxiv.org/pdf/2008.08244.pdf [2] https://proceedings.mlr.press/v195/jia23a/jia23a.pdf

A dynamical model consists of a continuous self-map of a compact state space and a continuous observation function. In this talk, I will start by surveying some interesting general problems of statistical inference for dynamical systems (cf. [1]). My focus will be on translating some central concepts in the study of real-valued dynamical systems to familiar statistical settings. Then I will highlight some results on the consistency of parameter estimation under dynamical models (cf. [2]). [1] https://projecteuclid.org/journals/statistics-surveys/volume-9/issue-none/Statistical-inference-for-dynamical-systems-A-review/10.1214/15-SS111.full [2] https://projecteuclid.org/journals/annals-of-statistics/volume-48/issue-4/Empirical-risk-minimization-and-complexity-of-dynamical-models/10.1214/19-AOS1876.full

Consider the relationship between a regulator (the principal) and a pharmaceutical company (the agent). The pharmaceutical company wishes to sell a drug for profit, whereas the regulator wishes to allow only efficacious drugs to be marketed. The efficacy of the drug is not known to the regulator, so the pharmaceutical company must run a costly trial to prove efficacy to the regulator. Critically, the statistical protocol used to establish efficacy affects the behavior of a strategic, self-interested pharmaceutical company; a lower standard of statistical evidence incentivizes the pharmaceutical company to run more trials for drugs that are less likely to be effective, since the drug may pass the trial by chance, resulting in large profits. The interaction between the statistical protocol and the incentives of the pharmaceutical company is crucial for understanding this system and designing protocols with high social utility. In this work, we discuss how the principal and agent can enter into a contract with payoffs based on statistical evidence. When there is stronger evidence for the quality of the product, the principal allows the agent to make a larger profit. We show how to design contracts that are robust to an agent’s strategic actions, and derive the optimal contract in the presence of strategic behavior.

The sequential probability ratio test (SPRT), also known as the likelihood ratio test (LRT), was first developed by Wald in the 40s. In its modern incarnation it says that the probability ratio process dQ/dP(X1, ..., Xn) under the null P is a non-negative martingale, hence an e-process, which satisfies Ville's inequality. I will chiefly focus on the case when P and Q are both Gaussian, and cover the following very interconnected topics: (1) Growth and shrinkage (2) mixtures (proper and improper, which leads to interesting "non-integrable" martingales and maximal inequalities) (3) Confidence sequences (4) large, nonparametric, non-iid nulls. In particular, results from the following two papers will be mentioned: [1] Section 3.2 of https://arxiv.org/abs/2203.04485 [2] Sections 5-6 of https://arxiv.org/abs/2304.01163

Understanding the relationship between training data and model outputs is a key challenge for model interpretability. I will start with a brief overview of training data influence analysis methods as categorized by [1], commenting on the challenges particular to deep neural network (and other black box) models. I will then share a proposed method [2] for estimating the influence of particular training points on the prediction of a new test point for neural network models. This approach draws on the famous representer theorem and a clever partitioning of the layers of the neural network. [1] https://arxiv.org/pdf/2212.04612.pdf [2] https://arxiv.org/pdf/1811.09720.pdf

Conformal inference has played a pivotal role in providing uncertainty quantification for black-box ML prediction algorithms with finite sample guarantees. Traditionally, conformal prediction inference requires a data-independent specification of miscoverage level. In practical applications, one might want to update the miscoverage level after computing the prediction set. For example, in the context of binary classification, the analyst might start with a 95% prediction sets and see that most prediction sets contain all outcome classes. Prediction sets with both classes being undesirable, the analyst might desire to consider, say 80% prediction set. Construction of prediction sets that guarantee coverage with data-dependent miscoverage level can be considered as a post-selection inference problem. In this work, we develop simultaneous conformal inference to account for data-dependent miscoverage levels. Under the assumption of independent and identically distributed observations, our proposed methods have a finite sample simultaneous guarantee over all miscoverage levels. This allows practitioners to trade freely coverage probability for the quality of the prediction set by any criterion of their choice (say size of prediction set) while maintaining the finite sample guarantees similar to traditional conformal inference. I shall explain the background topics briefly (conformal inference and confidence bands for CDF) and arrive at the proposed method. [1] https://arxiv.org/abs/2304.06158

Conformal inference has played a pivotal role in providing uncertainty quantification for black-box ML prediction algorithms with finite sample guarantees. Traditionally, conformal prediction inference requires a data-independent specification of miscoverage level. In practical applications, one might want to update the miscoverage level after computing the prediction set. For example, in the context of binary classification, the analyst might start with a 95% prediction sets and see that most prediction sets contain all outcome classes. Prediction sets with both classes being undesirable, the analyst might desire to consider, say 80% prediction set. Construction of prediction sets that guarantee coverage with data-dependent miscoverage level can be considered as a post-selection inference problem. In this work, we develop simultaneous conformal inference to account for data-dependent miscoverage levels. Under the assumption of independent and identically distributed observations, our proposed methods have a finite sample simultaneous guarantee over all miscoverage levels. This allows practitioners to trade freely coverage probability for the quality of the prediction set by any criterion of their choice (say size of prediction set) while maintaining the finite sample guarantees similar to traditional conformal inference. I shall explain the background topics briefly (conformal inference and confidence bands for CDF) and arrive at the proposed method. [1] https://arxiv.org/abs/2304.06158

Isotonic distributional regression (IDR) is a nonparametric technique for the estimation of conditional distributions under order restrictions within the covariate space. It is a natural generalization of estimating single-valued functional such as isotonic regression/isotonic quantile regression. I will start with defining IDR in terms of its uniqueness and optimality with respect to the continuous ranked probability score (CRPS). Then I will talk about its universality in the sense that it is also optimal with respect to a broader class of proper scoring rules. Finally, I will discuss its uniform consistency if time permits. The results are mainly based on the following papers: [1] https://arxiv.org/abs/1909.03725 and [2] https://link.springer.com/article/10.1007/s10463-021-00808-0

A standard practice in statistical hypothesis testing is to mention the p-value alongside the accept/reject decision. We show the advantages of mentioning an e-value instead. With p-values, we cannot use an extreme observation (e.g. p≪α) for getting better frequentist decisions. With e-values it is straightforward, since they provide Type-I risk control in a generalized Neyman-Pearson setting with the decision task (a general loss function) determined post-hoc, after observation of the data -- thereby providing a handle on `roving α's'. When Type-II risks are taken into consideration, the only admissible decision rules in the post-hoc setting turn out to be e-value-based. Similarly, if the loss incurred when specifying a faulty confidence interval is not fixed in advance, standard confidence intervals and distributions may fail whereas e-confidence sets and e-posteriors still provide valid risk guarantees. Relevant papers: https://arxiv.org/abs/2205.00901 , https://arxiv.org/abs/2301.01335

Over the last decade, an approach that has gained a lot of popularity to tackle non-parametric testing problems on general (i.e., non-Euclidean) domains is based on the notion of reproducing kernel Hilbert space (RKHS) embedding of probability distributions. The main goal of our work is to understand the optimality of two-sample tests constructed based on this approach. First, we show that the popular MMD (maximum mean discrepancy) two-sample test is not optimal in terms of the separation boundary measured in Hellinger distance. Second, we propose a modification to the MMD test based on spectral regularization by taking into account the covariance information (which is not captured by the MMD test) and prove the proposed test to be minimax optimal with a smaller separation boundary than that achieved by the MMD test. Third, we propose an adaptive version of the above test which involves a data-driven strategy to choose the regularization parameter and show the adaptive test to be almost minimax optimal up to a logarithmic factor. Moreover, our results hold for the permutation variant of the test where the test threshold is chosen elegantly through the permutation of the samples. Through numerical experiments on synthetic and real-world data, we demonstrate the superior performance of the proposed test in comparison to the MMD test. Relevant paper: https://arxiv.org/abs/2212.09201

We consider the problem of inference for projection parameters in linear regression with increasing dimensions. This problem has been studied under a variety of assumptions in the literature. The classical asymptotic normality result for the least squares estimator of the projection parameter only holds when the dimension $d$ of the covariates is of smaller order than $n^{1/2}$, where $n$ is the sample size. Traditional sandwich estimator-based Wald intervals are asymptotically valid in this regime. In this work, we propose a bias correction for the least squares estimator and prove the asymptotic normality of the resulting debiased estimator as long as $d = o(n^{2/3})$, with an explicit bound on the rate of convergence to normality. We leverage recent methods of statistical inference that do not require an estimator of the variance to perform asymptotically valid statistical inference. https://arxiv.org/abs/2007.09751 https://arxiv.org/abs/2307.00795

We will introduce the minimax framework for hypothesis testing, some basic tricks of the trade, and discuss the paper "Minimax optimal testing by classification" by Gerber, Han, and Polyanskiy [1]. In this work, the authors study the effectiveness of learned classifiers for deciding if two distributions are equal or far apart in the total variation distance. We aim to make the presentation self-contained; hence, no previous knowledge about minimax hypothesis testing will be assumed. [1] https://proceedings.mlr.press/v195/gerber23a.html

The theory of optimal transport (OT) offers versatile tools for the comparison of probability measures in a geometrically faithful way. In statistical contexts, transport based methodology often relies on estimation of the optimal transport cost through an empirical plug-in approach, which raises questions about its accuracy. The convergence behavior of the empirical OT cost for increasing sample size is dictated by various aspects. These include the intrinsic dimension of the population measures, their concentration, as well as the regularity of the ground cost function. Remarkably, under distinct population measures with different intrinsic dimensions, the convergence rate for the empirical optimal transport cost adapts in the most favorable way, being determined by the lower dimensional measure. This phenomenon represents a hallmark feature of empirical optimal transport and is termed "lower complexity adaptation“. The talk is based on joint work with Thomas Staudt and Axel Munk.

Prediction with experts’ advice is one of the most fundamental problems in online learning and captures many of its technical challenges. A recent line of work has looked at online learning through the lens of differential equations and continuous-time analysis. This viewpoint has yielded optimal results for several problems in online learning. In this paper, we employ continuous-time stochastic calculus in order to study the discrete-time experts’ problem. We use these tools to design a continuous-time, parameter free algorithm with improved guarantees on the quantile regret. We then develop an analogous discrete-time algorithm with a very similar analysis and identical quantile regret bounds. Finally, we design an anytime continuous-time algorithm with regret matching the optimal fixed-time rate when the gains are independent Brownian motions; in many settings, this is the most difficult case. This gives some evidence that, even with adversarial gains, the optimal anytime and fixed-time regrets may coincide. https://arxiv.org/pdf/2206.00236.pdf

Stochastic processes are random variables with values in some space of paths. However, reducing a stochastic process to a path-valued random variable ignores its filtration, i.e. the flow of information carried by the process through time. By conditioning the process on its filtration, we introduce a family of higher order kernel mean embeddings (KMEs) that generalizes the notion of KME and captures additional information related to the filtration. We derive empirical estimators for the associated higher order maximum mean discrepancies (MMDs) and prove consistency. We then construct a filtration-sensitive kernel two-sample test able to pick up information that gets missed by the standard MMD test. In addition, leveraging our higher order MMDs we construct a family of universal kernels on stochastic processes that allows to solve real-world calibration and optimal stopping problems in quantitative finance (such as the pricing of American options) via classical kernel-based regression methods. Finally, adapting existing tests for conditional independence to the case of stochastic processes, we design a causal- discovery algorithm to recover the causal graph of structural dependencies among interacting bodies solely from observations of their multidimensional trajectories. https://arxiv.org/abs/2109.03582

I will recall the median-of-means (MoM) principle for estimating mean and risk minimizers (cf. [1,2]). The estimators based on MoM provide robustness under heavy-tailed distributions and adversarial contamination. These estimators achieve an optimal rate of convergence in certain models with weak assumptions. We'll discuss applications of the MoM principle and compare them with alternative approaches such as trimming. https://doi.org/10.1007/s10208-019-09427-x ; https://doi.org/10.1214/19-AOS1828

I will begin the talk with an overview of selective inference, which is the problem of giving valid answers to statistical questions chosen in a data-driven manner. I will describe a standard solution to selective inference called simultaneous inference, which delivers valid answers to the set of all questions that could possibly have been asked. Then, I will describe a less conservative solution that we call locally simultaneous inference, which only answers those questions that could plausibly have been asked in light of the observed data, all the while preserving rigorous type I error guarantees. For example, if the objective is to construct a confidence interval for the “winning” treatment effect in a clinical trial with multiple treatments, and it is obvious in hindsight that only one treatment had a chance to win, then locally simultaneous inference will return an interval that is nearly the same as the uncorrected, standard interval. Based on joint work with Will Fithian. No prior knowledge of selective inference will be assumed. Link to paper: https://arxiv.org/pdf/2212.09009.pdf

What does it mean for a vector of random variables to be "negatively dependent"? We'll look at various definitions from the literature, and examples of when they arise (multinomials, permutations, sampling without replacement, tournaments). This will be based on some recent work with Ziyu Chi and Ruodu Wang https://arxiv.org/pdf/2212.09706.pdf, which proves the first known (and possibly surprising) results for multiple testing under negative dependence. We'll end with a few ripe open problems.

We look at a couple ways to test for conditional independence, whether X is independent of Y conditional on a variable Z, using permutations. We first consider the case under the model X framework where the conditional distribution of X given Z is known. In this case, by putting a distribution over possible permutations, we can form exchangeable test statistics for a valid finite sample test. In the case where the distribution of X given Z is unknown, we will look at local permutation tests which involves binning the variable Z and shuffling within the bins. This procedure relies on the condition that the distribution of X and y conditioned on Z cannot change much with respect to small perturbations in Z. This is characterized through smoothness assumptions. We will discuss the validity of this procedure under these smoothness assumptions. https://arxiv.org/pdf/1807.05405.pdf, https://arxiv.org/pdf/2112.11666.pdf

Independence testing is a fundamental and classical statistical problem that has been extensively studied in the batch setting when one fixes the sample size before collecting data. Instead of sticking to a prespecified sample size, well-designed sequential tests (a) allow stopping earlier on easy tasks (and later on harder tasks), hence making better use of available resources, and (b) continuously monitor the data and efficiently incorporate statistical evidence after collecting new data, while controlling the false alarm rate. In this talk, I will talk about our recent work on using the principle of testing by betting and kernel methods for consistent sequential nonparametric independence testing. After discussing the necessary background on batch independence testing and highlighting the respective limitations, I will present our new test and interpret the results. Lastly, I will briefly discuss extensions to those settings, where batch independence tests fail, such as testing under non-i.i.d. time-varying settings. Link: https://arxiv.org/abs/2212.07383

An agnostic learning algorithm finds a predictor that is competitive with the best predictor in a benchmark hypothesis class. However, the predictor might be quite sub-optimal for structured subgroups of individuals, such as protected demographic groups. The goal of multi-group agnostic learning is as follows: fixing some loss, a benchmark class H, and a collection of (potentially overlapping) subgroups G, learn a predictor such that the loss experienced by every group g ∈ G is not much larger than the best possible loss (within H) for g. The phrase "multi-group agnostic PAC" was conceived by Rothblum and Yona (2021), and my description above is almost directly from their abstract. Blum and Lykouris (2020) studied multi-group agnostic online learning for bounded decomposable losses. Their (surprising) finding is a single randomized strategy that controls regret on each group g simultaneously, at almost the same level that one would achieve by running separate strategies for each g. They do this via a reduction to the problem of 'sleeping' experts, which in turn can be solved using adaptive versions of the well-known Hedge algorithm. I will present the multi-group learning goal, make the reduction to sleeping experts, and (time permitting) discuss details of a specific adaptive hedging algorithm by Luo and Schapire (2015). Relevant papers: - Rothblum and Yona (2021) https://arxiv.org/abs/2105.09989 - Blum and Lykouris (2020) https://arxiv.org/abs/1909.08375 - Luo and Schapire (2015) https://arxiv.org/abs/1502.05934

In this work, we provide a (n/m)−1/2-rate finite sample Berry-Esseen bound for m-dependent high-dimensional random vectors over the class of hyper-rectangles. This bound imposes minimal assumptions on the random vectors such as nondegenerate covariances and finite third moments. The proof uses inductive relationships between anti-concentration inequalities and Berry--Esseen bounds, which are inspired by the telescoping method of Chen and Shao (2004) and the recursion method of Kuchibhotla and Rinaldo (2020). Performing a dual induction based on the relationships, we obtain tight Berry-Esseen bounds for dependent samples. https://arxiv.org/abs/2212.05355

This work introduces a new goodness-of-fit tests and corresponding confidence bands for distribution functions. The tests are inspired by multi-scale methods of testing and based on refined laws of the iterated logarithm for the normalized uniform empirical process. The goodness-of-fit tests perform well in signal detection problems involving sparsity, which they demonstrate under certain classical hypothesis testing frameworks. The confidence bands provided are also an improvement over Berk-Jones statistic and the DKW inequality confidence bands in the tail regions. I will be discussing an earlier version of the paper (version 2: https://arxiv.org/abs/1402.2918v2) and connect it to the generalisations the current draft proposes. I will cover a brief outline of prior work, the proposed statistic and confidence band method and it's optimality properties. If time permits, I will present a brief outline of the proof for the theorems related to confidence bands.

We present a simple reduction from sequential estimation to sequential changepoint detection (SCD). In short, suppose we are interested in detecting changepoints in some parameter or functional θ of the underlying distribution. We demonstrate that if we can construct a confidence sequence (CS) for θ, then we can also successfully perform SCD for θ. This is accomplished by checking if two CSs -- one forwards and the other backwards -- ever fail to intersect. Since the literature on CSs has been rapidly evolving recently, the reduction provided in this paper immediately solves several old and new change detection problems. Further, our "backward CS", constructed by reversing time, is new and potentially of independent interest. We provide strong nonasymptotic guarantees on the frequency of false alarms and detection delay, and demonstrate numerical effectiveness on several problems.

In recent years, conformal prediction has exploded in popularity as a means for quantifying the uncertainty in black-box machine learning model predictions without making idealized distributional assumptions. I will discuss a different optimization-based approach that relies on minimal distributional assumptions to guarantee appropriate coverage. In particular, I will focus on a recent paper entitled “Universal prediction band via semi-definite programming” by Tengyuan Liang. Constructing the proposed prediction band requires solving a convex optimization program which simultaneously learns the conditional mean and variance functions while trading off their complexities. This optimization program has connections to many others in the literature, including sum-of-squares optimization, phase retrieval, min-norm interpolation, kernel ridge regression, and support vector regression. Tools from empirical process theory are used to show that the resulting prediction band has the correct coverage – this differs from the analysis of conformal prediction intervals which relies on an exchangeability argument. I will discuss pros and cons of this optimization-based approach compared to conformal prediction. Time permitting, I will briefly mention some new work with Arun on the related problem of constructing distribution-free prediction sets with valid coverage when the sample size is not known/fixed in advance and may depend on the observed data.

Consider the problem of binary hypothesis testing Z ∼ P vs Z ∼ Q from m samples. Achieving a small error rate when P and Q are completely known is possible using the Neyman-Pearson test, for example. We consider a variation of the problem, which the authors call likelihood-free hypothesis testing, where access to P and Q (which are a priori only known to belong to a large non-parametric family) is given through iid samples from each. We discuss the minimax sample complexity of such a test, the proof of which borrows on the L^2 distance statistic of Ingster and the "Ingster trick." We discuss a fundamental trade-off between the size of the observed dataset Z and the size of the simulated datasets X ~ P and Y ~ Q.

In the recent Basel Accords, the Expected Shortfall (ES) replaces the Value-at-Risk (VaR) as the standard risk measure for market risk in the banking sector, making it the most important risk measure in financial regulation. One of the most challenging tasks in risk modeling practice is to backtest ES forecasts provided by financial institutions. Ideally, backtesting should be done based only on daily realized portfolio losses without imposing specific models. We discuss how to use e-values and e-processes to backtest risk forecasts of VaR and ES, which can be naturally generalized to many other risk measures and statistical quantities. https://arxiv.org/abs/2209.00991

I will recall some classical ideas (https://link.springer.com/content/pdf/10.1007/s004409970006.pdf) for deriving minimax estimation rates for nonsmooth functionals, via polynomial approximation and moment matching. My emphasis will be on the problem of estimating the L^1 distance between discrete distributions (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8379458). We'll then see how these ideas can be used to derive minimax lower bounds for estimating the Wasserstein distance between arbitrary distributions (https://projecteuclid.org/journals/bernoulli/volume-28/issue-4/Estimation-of-Wasserstein-distances-in-the-Spiked-Transport-Model/10.3150/21-BEJ1433.short).

The multiplicative weights algorithm (https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) is a classic algorithm for prediction with expert advice, and has been applied in machine learning, economics, game theory etc. I will discuss a recent result that leverages multiplicative weights to derive a variance-adaptive regret bound (https://arxiv.org/abs/2206.02656).

I will discuss and prove a CLT for V-fold cross-validated risk using stability conditions with Stein’s method and Slepian interpolation. Focus will be put on the CLT with a fixed center mentioned in Theorem 3 of Asymptotics of Cross-Validation with some slight modifications. Lastly, I'll comment on how this work can be extended into high-dimensions. https://arxiv.org/abs/2001.11111

I will share a classical result on the minimax rate for testing qualitative hypotheses associated with a nonparametric regression function: if the function satisfies certain shape constraints such as monotonicity. The proposed test involves the estimation of the Lr distance between the regression function and the convex cone. The main technical focus will be on the derivation of lower bound, which resembles the classical method for nonsmooth functionals by Lepski et al. Although this is a spiritual follow-up to Tudor’s talk on nonsmooth functionals, the attendance to his talk is not required.

Inference for the parameters indexing generalised linear models is routinely based on the assumption that the model is correct and a priori specified. This is unsatisfactory because the chosen model is usually the result of a data-adaptive model selection process, which may induce excess uncertainty that is not usually acknowledged. Moreover, the assumptions encoded in the chosen model rarely represent some a priori known, ground truth, making standard inferences prone to bias, but also failing to give a pure reflection of the information that is contained in the data. Inspired by developments on assumption-free inference for so-called projection parameters, we here propose novel nonparametric definitions of main effect estimands and effect modification estimands. These reduce to standard main effect and effect modification parameters in generalised linear models when these models are correctly specified, but have the advantage that they continue to capture respectively the primary (conditional) association between two variables, or the degree to which two variables interact (in a statistical sense) in their effect on outcome, even when these models are misspecified. We achieve an assumption-lean inference for these estimands (and thus for the underlying regression parameters) by deriving their influence curve under the nonparametric model and invoking flexible data-adaptive (e.g., machine learning) procedures.

Sieve estimators, or estimation using orthogonal function series, is a classical nonparametric statistical learning strategy (starting from the 80s). It is believed to be a nice idea when the covariates/ predictors are of very low dimension. However, in multivariate cases (say covariate dimension = 5), the direct extension of sieve estimators is usually thought to be not fruitful due to its high computational burden. In this talk, I will discuss how to effectively apply sieve estimators under multivariate tensor product models (including the relationship between these nonparametric spaces and classical Sobolev spaces). The proposed estimators can partially avoid the curse of dimensionality (statistically and computationally) under the more restrictive but still "interesting" nonparametric models. Check https://arxiv.org/abs/2206.02994 for more details.

In this talk, I will review a selection of results from two recent papers on designing incentive-compatible forecasting competitions. I will first follow Witkowski et al. (2022)'s discussion on how deterministic (e.g., winner-take-all) forecasting competitions do not incentivize forecasters to report their predictions truthfully. I will then introduce their proposed stochastic alternative, called the Event Lotteries Forecasting Competition Mechanism (ELF), that is incentive-compatible. After that, I will go over Frongillo et al. (2021)'s proof that shows how ELF requires Θ(n log n) test events to select a near-optimal forecaster, where n is the number of forecasters in the competition. Time permitting, I will also briefly describe some of their other results, including an approximately incentive-compatible mechanism that can select an ε-optimal forecaster with just O(log n/ε^2) events and how it leads to the first no-regret algorithm for online prediction with non-myopic strategic experts.

Suppose that there are K parameters of potential interest, and that one can construct a valid (1-\delta)-CI for each of them separately. A data analyst uses an arbitrary data-dependent criterion to select some subset S of them for reporting, or highlighting. The confidence intervals for the selected parameters are no longer valid, due to the selection bias, so the question is how one must adjust these in order to account for selection. We focus on the popular notion of false coverage rate (FCR), which is the expected ratio of the number of selected intervals that miscover, to the number of selected intervals |S|. The main established method is the ``BY procedure'' from a seminal work by Benjamini and Yekutieli (JASA, 2005), that was inspired by the Benjamini-Hochberg (BH) procedure. Unfortunately, the BY procedure involves restrictions on the dependence between CIs and the selection criterion. We propose a natural and much simpler method---both in implementation, and in proof---which is valid under any dependence structure between the original CIs, and any (unknown) selection criterion, but which only applies to a special, yet broad, class of CIs. Our procedure reports (1-\delta|S|/K)-CIs for the selected parameters, and we prove that it controls the FCR at \delta for confidence intervals that implicitly invert e-values; examples include those constructed via self-normalized supermartingale methods, or via universal inference, or via Chernoff-style bounds on the moment generating function, among others. We call it the *e-BY procedure*, since it is inspired by the aforementioned BY procedure, and strongly borrows intuition from the recent e-BH procedure of Wang and Ramdas (JRSSB, 2022). This work has strong implications for multiple testing in sequential settings, since it applies at stopping times, to continuously-monitored confidence sequences along with multi-armed bandit sampling. https://arxiv.org/abs/2203.12572

Suppose we observe a random vector X from some distribution P in a known family with unknown parameters. We ask the following question: when is it possible to split X into two parts f(X) and g(X) such that neither part is sufficient to reconstruct X by itself, but both together can recover X fully, and the joint distribution of (f(X),g(X)) is tractable? As one example, if X=(X1,…,Xn) and P is a product distribution, then for any m less than n, we can split the sample to define f(X)=(X1,…,Xm) and g(X)=(Xm+1,…,Xn). Rasines and Young (2021) offers an alternative route of accomplishing this task through randomization of X with additive Gaussian noise which enables post-selection inference in finite samples for Gaussian distributed data and asymptotically for non-Gaussian additive models. In this paper, we offer a more general methodology for achieving such a split in finite samples by borrowing ideas from Bayesian inference to yield a (frequentist) solution that can be viewed as a continuous analog of data splitting. We call our method data blurring, as an alternative to data splitting, data carving and p-value masking. We exemplify the method on a few prototypical applications, such as post-selection inference for trend filtering and other regression problems. https://arxiv.org/abs/2112.11079

Functions of bounded variation (BV) arise in diverse settings such as image recovery (where the 2D function to be modeled is BV) and locally adaptive regression splines/trend filtering (where the kth weak derivative of the estimator is BV). In this talk I will discuss the problem of estimating a BV function in R^d using scattered data, and along the way discuss various continuous & discrete notions of total variation and how they relate to each other. Based on work in-progress with Alden Green and Ryan Tibshirani.

We apply computational methods to study epistemic success of the data collection strategies that have been proposed by philosophers of science or executed by scientists themselves. We develop a multi-agent model of the scientific process that jointly formalizes its core aspects: data collection, data explanation, and social learning. We find that agents who choose new experiments at random develop the most accurate accounts of the world. On the other hand, the agents following the confirmation, falsification, crucial experimentation (theoretical disagreement), or novelty-motivated strategies end up with an illusion of epistemic success: they develop promising accounts for the data they collected, while completely misrepresenting the ground truth that they intended to learn about. These results, while being methodologically surprising, reflect basic principles of statistical learning and adaptive sampling.

We consider the the problem of sequentially optimizing a black-box function f based on noisy samples and bandit feedback. We assume that f is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yielding a commonly-considered non-Bayesian form of Gaussian process bandit optimization. We will discuss algorithm-independent lower bounds with a focus on the cumulative regret, measuring the sum of regrets over the T chosen points. We will discuss results pertaining to two commonly-used stationary kernels: squared exponential (SE) and Matérn. https://arxiv.org/abs/1706.00090

A fundamental challenge in interactive learning and decision making, ranging from bandit problems to reinforcement learning, is to provide sample-efficient, adaptive learning algorithms that achieve near-optimal regret. This question is analogous to the classical problem of optimal (supervised) statistical learning, where there are well-known complexity measures (e.g., VC dimension and Rademacher complexity) that govern the statistical complexity of learning. However, characterizing the statistical complexity of interactive learning is substantially more challenging due to the adaptive nature of the problem. The main result of this work provides a complexity measure, the Decision-Estimation Coefficient, that is proven to be both necessary and sufficient for sample-efficient interactive learning. In particular, we provide: 1. a lower bound on the optimal regret for any interactive decision making problem, establishing the Decision-Estimation Coefficient as a fundamental limit. 2. a unified algorithm design principle, Estimation-to-Decisions (E2D), which transforms any algorithm for supervised estimation into an online algorithm for decision making. E2D attains a regret bound matching our lower bound, thereby achieving optimal sample-efficient learning as characterized by the Decision-Estimation Coefficient. Taken together, these results constitute a theory of learnability for interactive decision making. When applied to reinforcement learning settings, the Decision-Estimation Coefficient recovers essentially all existing hardness results and lower bounds. More broadly, the approach can be viewed as a decision-theoretic analogue of the classical Le Cam theory of statistical estimation; it also unifies a number of existing approaches -- both Bayesian and frequentist. https://arxiv.org/abs/2112.13487

I'll review a class of univariate piecewise polynomial functions known as discrete splines, which share properties analogous to the better-known class of spline functions, but where continuity in derivatives is replaced by (a suitable notion of) continuity in divided differences. As it happens, discrete splines bear connections to a wide array of developments in applied mathematics and statistics, from divided differences and Newton interpolation (dating back to over 300 years ago) to trend filtering (from the last 15 years). I'll survey these connections, and contribute some new perspectives and new results along the way. Paper: https://www.stat.cmu.edu/~ryantibs/papers/dspline.pdf

In frequentist statistics, we typically evaluate the performance of a procedure through the lens of minimax optimality. However, for many problems, these notions of minimax optimality turn out to be overly pessimistic. As such, over the past decade, there has been a rising interest in studying so-called local minimax optimality, which provides a more fine grained characterization of the fundamental limits of various statistical procedures. In this talk, we will focus on the problem of adaptively sampling in order to learn a convex function in the ell-infinity norm. We will discuss both local minimax lower bounds and matching upper-bounds for the aforementioned problem, as well as the advantages offered by adaptive sampling over passive designs. https://arxiv.org/abs/1808.04523

The problem of sequential prediction with log loss arises in several practical applications such as compression, portfolio optimization and density estimation. The measure of performance in the prediction game is the regret, that is, the suboptimality of the predicted distributions with respect to the best constant distribution selected from a reference (or hypothesis) class in hindsight. Prior work in this area has focused on two settings: the well-specified case, in which the data is generated from a distribution within the reference class, and the individual-sequence setting, in which there are no probabilistic assumptions on the data source. In both these settings, the minimax regret has been characterized exactly in terms of properties of the reference class. In this paper, the authors consider an intermediate setting, called the PAC setting, where the observations are assumed to be drawn from an arbitrary i.i.d. source. https://arxiv.org/abs/2102.00050

I'll review a class of univariate piecewise polynomial functions known as discrete splines, which share properties analogous to the better-known class of spline functions, but where continuity in derivatives is replaced by (a suitable notion of) continuity in divided differences. As it happens, discrete splines bear connections to a wide array of developments in applied mathematics and statistics, from divided differences and Newton interpolation (dating back to over 300 years ago) to trend filtering (from the last 15 years). I'll survey these connections, and contribute some new perspectives and new results along the way. Paper: https://www.stat.cmu.edu/~ryantibs/papers/dspline.pdf

This work derives confidence intervals (CI) and time-uniform confidence sequences (CS) for the classical problem of estimating an unknown mean from bounded observations. We present a general approach for deriving concentration bounds, that can be seen as a generalization (and improvement) of the celebrated Chernoff method. At its heart, it is based on deriving a new class of composite nonnegative martingales, with strong connections to testing by betting and the method of mixtures. We show how to extend these ideas to sampling without replacement, another heavily studied problem. In all cases, our bounds are adaptive to the unknown variance, and empirically vastly outperform competing approaches based on Hoeffding or empirical Bernstein inequalities and their recent supermartingale generalizations. In short, we establish a new state-of-the-art for four fundamental problems: CSs and CIs for bounded means, with and without replacement.” https://arxiv.org/abs/2010.09686

We consider two or more forecasters each making a sequence of predictions over time and tackle the problem of how to compare them -- either online or post-hoc. In fields ranging from meteorology to sports, forecasters make predictions on different events or quantities over time, and this work describes how to compare them in a statistically rigorous manner. Specifically, we design a nonasymptotic sequential inference procedure for estimating the time-varying difference in forecast quality when using a relatively large class of scoring rules (bounded scores with a linear equivalent). The resulting confidence intervals can be continuously monitored and yield statistically valid comparisons at arbitrary data-dependent stopping times ("anytime-valid"); this is enabled by adapting recent variance-adaptive confidence sequences (CS) to our setting. In the spirit of Shafer and Vovk's game-theoretic probability, the coverage guarantees for our CSs are also distribution-free, in the sense that they make no distributional assumptions whatsoever on the forecasts or outcomes. Additionally, in contrast to a recent preprint by Henzi and Ziegel, we show how to sequentially test a weak null hypothesis about whether one forecaster outperforms another on average over time, by designing different e-processes that quantify the evidence at any stopping time. We examine the validity of our methods over their fixed-time and asymptotic counterparts in synthetic experiments and demonstrate their effectiveness in real-data settings, including comparing probability forecasts on Major League Baseball (MLB) games and comparing statistical postprocessing methods for ensemble weather forecasts. https://arxiv.org/abs/2110.00115

A number of recent calibration or uncertainty quantification techniques in machine learning rely on the assumption that the data is i.i.d. I will briefly summarize some of my contributions in this area. However, the majority of this talk will break away from this suspicious assumption. First, I will present Foster and Vohra's controversial 1998 result from the paper Asymptotic calibration (https://www.jstor.org/stable/2337364?seq=1#metadata_info_tab_contents), where they show that there exist forecasting strategies that are calibrated for every possible data sequence. I will sketch a proof using Blackwell's approachability theorem (https://msp.org/pjm/1956/6-1/pjm-v6-n1-p01-s.pdf). Foster and Vohra's result has developed into the broader field of 'strategic hypothesis testing'. In standard hypothesis testing, we implicitly assume that the hypothesis is borne out of 'thin air', without any hidden incentives for the hypothesis-generating-entity. The statistician's goal is to design testing algorithms that verify if the observations are coherent with the proposed hypothesis. However, the hypothesis-generating-entity in an ML/prediction setting is a probabilistic forecaster; such a forecaster naturally has strong incentives to pass tests. In strategic hypothesis testing, we give the forecaster access to the test, and ask if they can 'strategically' pass it no matter how the data is distributed. I will present a number of results (without proof) by Olszewski and Sandroni (2003–2011) showing that a large class of tests can be passed for every possible data sequence. The talk will closely follow Chapter 18 of the Handbook of Game Theory, Volume 4 (https://www.elsevier.com/books/handbook-of-game-theory/young/978-0-444-53766-9). A publicly available version is here (https://faculty.wcas.northwestern.edu/~wol737/Hand.pdf).

This paper is concerned with the problem of variable selection and forecasting in the presence of parameter instability. There are a number of approaches proposed for forecasting in the presence of time-varying parameters, including the use of rolling windows and exponential down-weighting. However, these studies start with a given model specification and do not consider the problem of variable selection, which is complicated by time variations in the effects of signals on target variables. In this study we investigate whether or not we should use weighted observations at the vari- able selection stage in the presence of parameter instability, particularly when the number of potential covariates is large. Amongst the extant variable selection ap- proaches we focus on the recently developed One Covariate at a time Multiple Testing (OCMT) method. This procedure allows a natural distinction between the selection and forecasting stages. We establish three main theorems on selection, estimation post selection, and in-sample fit. These theorems provide justification for using the full (not down-weighted) sample at the selection stage of OCMT and down-weighting of observations only at the forecasting stage (if needed). The benefits of the proposed method are illustrated by empirical applications to forecasting monthly stock market returns and quarterly output growths. The public version of the paper is available here (https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3671261).

Dynamic pricing with unknown demand has been extensively studied and often formulated as a bandit problem. While well-understood theoretically, bandit-based policies are rarely deployed in the real world, since many of them overlooked practical constraints. For example, the price may oscillate, which is unfavorable in practice. We consider markdown policies, i.e. policies with non-increasing prices, and show tight regret bounds under various assumptions. Further, our results separates markdown pricing and unonstrained pricing, highlighting the extra complexity incurred by this monotonicity constraint.

Tree-form, sequential decision making (TFSDM) captures tree-form decision processes where the decision maker faces multiple decisions interleaved with observations about the way previous decisions affected the (potentially adversarial) environment. TFSDM provides a powerful and general formalism which captures the decision problem faced by a player of an adversarial imperfect-information extensive-form game (such as poker and other non-recreational strategic interactions), as well as partially-observable Markov decision processes for which the agent conditions its policy on the entire history of observations and actions. By allowing interleaved decisions and observations, TFSDM is significantly more sophisticated than non-sequential decision making, where only one action is planned `in a vacuum' prescinding from any observation about the state of the system. This sophistication is reflected in the underlying mathematical and computational details. Our understanding of TFSDM making lacks decisively behind that of non-sequential decision making. In this talk, I will try to shed some light on the theoretical and algorithmic foundations of tree-form sequential decision making, as well as the richness of connections between TFSDM and game theory.

Graceful composition is one of the most important properties of differential privacy. Well-known advanced composition theorems allow one to query a private database approximately quadratically more times than naive, basic privacy composition would permit. However, there is a major caveat — although the algorithms being composed can be selected adaptively, existing results require the privacy parameters of all algorithms to be fixed before interacting with the private database. A recent line of work started by Rogers et al. has studied fully-adaptive composition, wherein both algorithms and their privacy parameters can be selected adaptively. The authors introduce two probabilistic objects to measure privacy in adaptive composition: privacy filters, objects providing differential privacy guarantees for composed interactions, and privacy odometers, time-uniform bounds on privacy loss. However, there are substantial gaps between the composition results proved about these objects and the aforementioned advanced composition theorems. First, existing filters place stronger assumptions on the algorithms being composed. Second, the odometers and filters often suffer from large constants, making them impractical. This work greatly improves the state-of-the-art for fully-adaptive composition. In particular, we construct privacy filters that exactly match the tightness of advanced composition, including constants, despite allowing for adaptively chosen privacy parameters. In addition, we construct several general families of privacy odometers that have improved empirical tightness. These odometers can be optimized to match the tightness of advanced composition exactly at an arbitrary, preselected point in time, or at all points in time simultaneously, up to a small, doubly-logarithmic factor. We obtain our results by leveraging recent advances by Howard et al. on time-uniform martingale inequalities. In sum, our results show that fully-adaptive privacy is obtainable at no loss, giving practitioners added flexibility when working with sensitive data. https://arxiv.org/abs/2203.05481

We discuss a class of sampling algorithms/generative models motivated by the Schrödinger bridge problem, a classical problem in probability theory closely connected to stochastic control and entropy-regularized optimal transport. The talk will be expository. Primary reference is the following article of Tzen & Raginsky from COLT 2019: http://proceedings.mlr.press/v99/tzen19a/tzen19a.pdf

We propose a general method for constructing hypothesis tests and confidence sets that have finite sample guarantees without regularity conditions. We refer to such procedures as “universal.” The method is very simple and is based on a modified version of the usual likelihood ratio statistic, that we call “the split likelihood ratio test” (split LRT). The method is especially appealing for irregular statistical models. Canonical examples include mixture models and models that arise in shape-constrained inference. Constructing tests and confidence sets for such models is notoriously difficult. Typical inference methods, like the likelihood ratio test, are not useful in these cases because they have intractable limiting distributions. In contrast, the method we suggest works for any parametric model and also for some nonparametric models. Examples of problems for which valid tests were not known before our work: (a) testing for number of components in a mixture model, (b) testing for whether a density is log-concave, (c) testing for whether a distribution is totally positive, (d) testing number of hidden states in an HMM, (e) testing sparsity level in a high-dimensional linear model. The split LRT can also be used with profile likelihoods to deal with nuisance parameters, and it can also be run sequentially to yield anytime-valid p-values and confidence sequences.

Reference: Larry Wasserman, Aaditya Ramdas, Sivaraman Balakrishnan, 2019 (http://arxiv.org/abs/1912.11436)

Abstract: In high energy physics, an important problem is to detect if there is any significant difference between the distribution of just background events (generated from an assumed Monte Carlo model) and the distribution of the actual observations, which could be a mixture of background and signal events. We propose a test based on the performance of a classifier in differentiating between the two distributions.

When data analysts train a classifier and check if its accuracy is significantly different from chance, they are implicitly performing a two-sample test. We investigate the statistical properties of this flexible approach in the high-dimensional setting. We first present general conditions under which a classifier-based test is consistent, meaning that its power converges to one. To get a finer understanding of the rates of consistency, we study a specialized setting of distinguishing two Gaussians with different means and a common covariance. By focusing on Fisher's linear discriminant analysis (LDA) and its high-dimensional variants, we provide asymptotic but explicit power expressions of classifier-based tests and contrast them with corresponding Hotelling-type tests. Surprisingly, the expressions for their power match exactly in terms of the parameters of interest, and the LDA approach is only worse by a constant factor. This is joint work with Aaditya Ramdas, Aarti Singh, and Larry Wasserman.

Reference

The asymptotic distribution of the MLE in logistic models based on the classical ML theory does not account for the bias and variance inflation, thus yields the incorrect inference if one uses LRT. Sur and Candes [SC19] proposed a theory to handle this issue in the high dimensional setting. Recently, the redux [ZSC20] came out to resolve the arbitrary (Gaussian) feature covariance. I'll more focus on the recent paper based on the stochastic representation but will also try to cover the overlapping ideas that arise in both papers.

We develop Causal Clustering, a new framework for the analysis of treatment effect heterogeneity by leveraging tools in clustering analysis. We pursue an efficient way of ascertaining subgroups with similar treatment effects - viewing each of them as a separate cluster - by harnessing widely-used clustering methods. We show that k-means, density-based, hierarchical clustering algorithms can be successfully adopted into our framework, almost only at an additional cost of estimating nuisance regression functions for the outcome process. Particularly for k-means causal clustering, we develop an efficient nonparametric estimator that attains fast convergence rates under weak nonparametric conditions on the nuisance function estimation, and find the conditions that assure asymptotic normality of the cluster centers. Our framework can be extended to outcome-wide studies where we assess treatment effects over numerous outcomes.

This is joint work with Edward, Jisu and Larry. In this talk, I will focus more on the idea (i.e. how the two different concepts - clustering and causal inference - can be harmonized together), and how the semi-parametric and SML theories can help to develop more appealing estimators.

We consider the problem of designing minimax estimators for estimating the parameters of a probability distribution. Unlike classical approaches such as MLE, M-estimators, we consider an algorithmic approach for constructing such estimators.

We view the problem of designing minimax estimators as finding a mixed strategy Nash equilibrium of a zero-sum game. By leveraging recent results in online learning with non-convex losses, we provide a general algorithm for finding a Nash equilibrium of the statistical game. Our algorithm requires access to two subroutines, namely, a Bayes estimator subroutine which outputs a Bayes estimator corresponding to a given prior probability distribution, and a subroutine which computes the worst-case risk of any given estimator. Given access to these two subroutines, we show that our algorithm outputs both a minimax estimator and a least favorable prior. To demonstrate the power of this technique, we use it to construct provably minimax estimators for classical problems such as estimation in finite Gaussian sequence model, linear regression.

For this week in SMLRG, I will be presenting entry-wise perturbation bounds for eigenvectors as proven in recent work by Eldridge, Belkin, and Wang. While this work is not my own, I am invoking their results quite a bit for my own research and have found these results worthwhile to keep in mind. Specifically, I will first briefly review the stochastic block model (SBM), where the goal is to estimate the clustering of nodes in a random graph, and the classical Davis-Kahan bound (following the logic in Jing and Ale's AoS paper) as a baseline analysis to compare against. Then, I present the intuition/results/rate on how Eldridge et. al deploy their entrywise perturbation bounds in the SBM setting. These rates can immediately conclude that spectral clustering can obtain exact clustering consistency with only a few extra (mild) assumptions compared to previous work. With the remaining time, I will close the talk with open questions/discussion/ramblings related to incoherence, delocalization in random matrix theory, and possibly extensions to broader classes of random graphs beyond SBMs. For those interested in using these rates in their own work, please be aware that minor clarifications/typos in Eldridge et. al's work have been fixed in a work by Li, Levina, and Zhu, which I will be using in my talk.

This is joint work with Edward, Jisu and Larry. In this talk, I will focus more on the idea (i.e. how the two different concepts - clustering and causal inference - can be harmonized together), and how the semi-parametric and SML theories can help to develop more appealing estimators.

The Lasso estimator is a commonly used estimator for high-dimensional regression models which allows the number of covariates p to be larger than the number of observations n. It is known that in the regime where the ratio n/p is a constant, the Lasso estimator has a non-trivial distribution that involves an extra noise term due to the under-sampling effect. In this talk, I will first discuss the results by Miolane and Montanari'18 which characterizes the exact distribution of the Lasso estimator under standard Gaussian design. Establishing this result uses the Gordon's minimax Theorem developed by Tampoulidis, Oymak, and Hassibiâ'16 which finds its root in the Gaussian comparison inequalities. Understanding the distribution of Lasso provides many interesting consequences including but not limited to characterizing the prediction and estimation risk, noise level estimation, model selection etc. If time permits, I will also talk about our recent work generalizing this result to cases beyond the standard Gaussian design and its use in hypothesis testing.

One of the themes we explored last semester was understanding generalization in overfitted models (i.e., models trained with zero regression loss), even for noisy data. We examined several flavors of this phenomenon for local nonparametric methods (nearest neighbor simplicial interpolation, singular kernel smoothing), high-dimensional linear regression (asymptotic analysis), kernel regression (polynomial and Laplace kernels) in various capacities. This week, we will discuss recent work by Barlett et al. that characterizes conditions (involving two special notions of effective rank of the data covariance operator) under which the minimum-norm interpolator has nearly optimal excess risk for Gaussian linear regression problems. The key punchline of the work is that overparametrization may help provide many unimportant (low-variance) directions in the parameter space to effectively hide the noise that gets injected in an overfitted solution enabling good generalization. We’ll conclude by briefly discussing its relevance to recent progress on understanding generalization and optimization in deep neural networks (that are well approximated by certain linear functions assuming small-step gradient descent training on sufficiently wide networks) and high sensitivity of such models to small (careful) perturbations.

This work is motivated by the computation of the Fantope projection and selection model (FPS, Vu et al., 2013), a convex formulation of the sparse principal component analysis (SPCA). Most existing SPCA algorithms are based on nonconvex objective functions, which are computationally fast but have little global optimum guarantee. FPS, on the other hand, is convex, but requires solving a highly constrained optimization problem. The existing ADMM-based algorithm for FPS includes a projection step in each iteration, which requires a full eigen decomposition of a large matrix. Inspired by Kundu et al. (2018) and Mahdavi et al. (2012), we first develop a general projection-free algorithm for solving constrained convex optimization problems, where the constraint set is the intersection of several simple sets. Each of the simple sets can either be trivially projected onto, or has a simple boundary function. Under certain conditions, we prove that the original constrained problem is equivalent to a new unconstrained one, where fast iteration methods such as subgradient descent can be applied. In the final part, we go back to the FPS problem, and prove that it satisfies the sufficient conditions imposed in the algorithm above. New computational methods are then developed for solving FPS.

References:

Fantope projection and selection: https://papers.nips.cc/paper/5136-fantope-projection-and-selection-a-near-optimal-convex-relaxation-of-sparse-pca.pdf

Convex optimization over intersection of simple sets: https://arxiv.org/pdf/1710.06465.pdf

SGD with only one projection: https://papers.nips.cc/paper/4797-stochastic-gradient-descent-with-only-one-projection.pdf

Finding planted "signals" in random "noise" is a theme that captures problems arising in several different areas such as machine learning (compressed sensing, matrix completion, sparse principal component analysis, regression, recovering planted clusters), average-case complexity (stochastic block model, planted clique, random constraint satisfaction), and cryptography (attacking security of pseudorandom generators). For some of these problems (e.g. variants of compressed sensing and matrix completion), influential works in the past two decades identified the right convex relaxation and techniques for analyzing it that guarantee nearly optimal (w.r.t. to the information theoretic threshold) recovery guarantees. However these methods are problem specific and do not immediately generalize to other problems/variants. This talk is about a principled approach via the sum-of-squares method, to design and analyze a "right" convex relaxation that offers optimal recovery guarantees for a broad class of average case problems including all those listed above. I will illustrate this approach by focusing on the example of a recent work on outlier-robust linear regression. I will explain how the process of coming up with the convex relaxation and its analysis in this paradigm can be black-boxed into showing a "simple" proof of unique identifiability (i.e., a statement that the signal (such as mixture components/added clique/regression-hypothesis) is information-theoretically uniquely identified by the observed data.

A key task in Bayesian approaches in machine learning is sampling from distributions of the form p(x) = e^{-f(x)}/Z where Z is a normalizing constant, for some function f whose values and gradients we can query. One prevalent example of this is sampling posteriors in parametric distributions, such as latent-variable generative models -- which is the natural Bayesian analogue of clustering. However sampling (even very approximately) can be #P-hard. Classical results on sampling focus on log-concave distributions (i.e. f is convex), and show a natural Markov process called Langevin diffusion mixes in polynomial time. However, log-concavity is quite restrictive in practice: in particular such distributions are uni-modal. I will address in this talk some ways to move beyond this setup.

We will consider a problem of testing for fairness of human decisions in application to conference peer review. Specifically, we are interested in testing for biases in single-blind setup, where reviewers observe identities of authors. We will show that various idiosyncrasies of peer review (including non-random assignment, noise and miscalibration of reviewers) do not allow to perform fully randomized controlled trials and may undermine Type-I error guarantees of popular parametric approaches to testing. To overcome this negative result, we will consider a general framework for performing such tests and show that a simple non-parametric procedure leads to a more reliable test, requiring weaker assumptions to control for the Type-I error and having non-trivial power. This is a joint work with Nihar and Aarti.

Draft: http://www.cs.cmu.edu/afs/cs.cmu.edu/user/istelmak/www/papers/bias.pdf

High-dimensional variable selection is a notoriously difficult problem that statisticians have been grappling with for decades. A recently proposed and increasingly popular methodology in this realm is knockoffs, which can be viewed as a wrapper around any variable selection methodology (like the lasso) that endows it with rigorous Type-I error guarantees. It is based on the idea that a feature statistic like a lasso coefficient can be calibrated with the help of negative control variables (knockoffs), carefully constructed to be pairwise exchangeable with the original variables. The validity of the resulting Type-I error guarantees hinges on the model-X assumption---that the joint distribution of the covariates is known. This assumption is particularly well-suited to the application of genome-wide association studies. I will present the knockoffs framework, the model-X assumption, and the application to genome-wide association studies. If time permits, I will also discuss more recent works on constructing knockoffs for general classes of covariate distributions.

Nonparametric goodness-of-fit testing is a classical statistical problem, in which we observe data y_i = f(x_i) + epsilon for x_i in R^d and wish to test the null hypothesis f = 0 against the alternative that f lies in some smooth function class. For instance, we may assume f lies in a Sobolev ball. Often, in order to derive standard minimax rates for this problem, the assumption will be made -- either explicitly or implicitly -- that the Sobolev ball exhibits a certain degree of regularity, measured by the number of derivatives k relative to the dimension d. In particular, the assumption is often made that 2k > d. We will begin by reviewing facts about Sobolev spaces, to establish why the threshold 2k = d is special, why the assumption 2k > d is made, and what properties we retain / lose when we don’t want to make this assumption. We will then move on to reviewing a paper of Ingster’s, which shows that a very classical projection-based test statistic can achieve minimax optimal rates as long as 4k > d. (As we will see from the preceding discussion, this will include functions which are qualitatively quite different from those for which 2k > d.) Finally, if time permits, I will detail some recent work which shows that analogous test statistics, defined over graphs, can also achieve minimax optimal rates without requiring 2k > d.

Random forests remain among the most popular off-the-shelf supervised machine learning tools with a well-established track record of predictive accuracy in both regression and classification settings. Despite their empirical success as well as a bevy of recent work investigating their important statistical properties, a full and satisfying explanation for their success has yet to be put forth. In this talk, I’ll go through the most popular explanations offered to date and discuss what I feel are the shortcomings of each. I’ll then offer a new (old?) explanation for their success building on fundamental ideas in model selection and show that the intuition offered by this alternative explanation holds with remarkable consistency on both real and synthetic data. Specifically, I’ll offer a precise explanation for the actual role being played by the additional randomness and we’ll see that this idea, when injected into existing model selection procedures, can lead to surprisingly large improvements in performance.

In this talk I will discuss The Simulator, which is a mechanism which can be used to prove lower bounds for Best-Arm Identification (BAI) in Multi Armed Bandits (MAB). Traditionally, lower bounds for this problem have been proved using so called change-of-measure arguments. However, these lower bounds only paint an accurate picture of the problem difficulty in traditional BAI problem, and can paint a misleading picture when there is some additional structure (i.e when the means of the arms lie in a simplex). The Simulator is an alternative mechanism which can be used to prove these lower bounds as well as a broader range of instance-dependent properties describing the difficulty of a BAI problem. In this talk, I will be going over the ideas from The Simulator paper and showing how it can be used to prove some lower bounds for BAI as well as some other interesting properties.

Paper: https://arxiv.org/abs/1702.05186

A recent avenue of work in the study of highly overparametrized neural networks is to investigate the limit where the number of hidden nodes goes to infinity. In the limit where the number of layers is fixed, but the width is sent to infinity, training a neural net using (stochastic) gradient descent approximates a continuum problem corresponding to the gradient flow of a special functional on the space of probability distributions. This type of problem is an object of intensive study in the optimal transport community. In this talk, we will give an overview of some recent results studying the convergence behavior and loss landscape of wide neural nets from a continuum limit perspective. In the second half of the talk, we will see that a nonlocal relaxation of the continuum problem suggests a novel regularization procedure for neural nets, somewhat like dropout, that significantly accelerates training dynamics.

References: https://www.pnas.org/content/115/33/E7665; https://arxiv.org/pdf/1805.09545.pdf; https://arxiv.org/pdf/1902.01843.pdf

There is growing concern in various medical and life sciences that many of the published results are irreproducible in the sense that the promised error control guarantees for such results might be violated. To alleviate such reproducibility crisis, a class methods called "safe testing" has been proposed recently to control Type-1 error for a (potentially infinite) number of tests. Such methods construct a (super)martingale to combine evidence from each test, but as opposed to measuring the evidence via a p-value as is usually done, safe tests use an "S-value". Unlike the p-value, which is designed to control Type-1 error for a single test, the S-value is designed to control Type-1 error for an (infinite) sequence of tests. As with p-values, there can be various designs of S-values for a given test, however for the parametric tests, there is an "optimal" S-value, which takes the form of a Bayes factor with non-standard priors. Bayes factors are known to control Type-1 error for an online experiment, but the error guarantee is only proved for a simple null whereas the S-value works for composite nulls. As an example, I will present the S-value for the t-test, which has better performance in terms of statistical power compared with Jeffreys' Bayesian t-test. If time permits, I will also discuss a special case where the S-value itself is a (super)martingale which allows for Type-1 error control without combining the S-values.

Reference: https://arxiv.org/abs/1906.07801

In a wide variety of applications in science and technology, data arrives sequentially (think one subject at a time in a psychology study, or one user at a time on a website) and the data is often frequently monitored to estimate certain quantities of interest or test hypotheses about them. Unfortunately, p-values and confidence intervals developed in the batch setting (to be constructed once when the number of data points is specified in advance) are incorrect and invalid when they are constructed and peeked at repeatedly. The sub-field of anytime-valid inference tries to construct p-values or confidence intervals that are valid simultaneously at all times, including data-dependent stopping times. I will give examples of such constructions for various functionals of distributions, like means and quantiles, that are valid under nonparametric conditions and are optimal in certain senses. The main theoretical quantities of interest are some very interesting nonnegative (super)martingales. There are a host of fascinating open research questions surrounding adaptivity to parametric assumptions or “simpler” distributions, efficiency relative to an oracle fixed-sample batch method, and expanding the types of functionals for which we can construct tight (including constants) and practical intervals or p-values that are not too conservative. I’ll try to cover a bit of everything: applications, theory, methods, software. This topic forms one central aspect of the SAVI workshop next summer http://stat.cmu.edu/~aramdas/SAVI/savi20.html.

References: Main publications along this theme are: 1. Sequential estimation of quantiles with applications to A/B-testing and best-arm identification (S. Howard, A. Ramdas); 2. Uniform, nonparametric, nonasymptotic confidence sequences (S. Howard, A. Ramdas, J. Sekhon, J. McAuliffe); 3. Exponential line-crossing inequalities (S. Howard, A. Ramdas, J. Sekhon, J. McAuliffe)

Since Wald's pioneering work in 1947, the sequential testing problem has been thoroughly studied in which a single hypothesis is sequentially tested based on the streaming of data. Various testing methods based on the likelihood ratio technique have been proposed and analyzed since they are well-suited in the sequential setting and often have some optimalities. However, most of previous works have focused on asymptotic properties of the sequential procedures. In this talk, a recent advance in the non-asymptotic analysis of the sequential testing will be discussed. In particular, we will discuss the advantages of using overlapping hypotheses in the sequential setting and present lower bounds of the sample complexity for sequential tests with fixed confidence. In the end, a simple modification of the generalized likelihood ratio test is introduced which has a non-asymptotic upper bound of the sample complexity matching the lower bound.

Reference: Garivier and Kaufmann 2019 (https://arxiv.org/abs/1905.03495)

Consider an infinite sequence of independent, uniformly chosen points from [0,1]^d. After looking at each point in the sequence, an overseer is allowed to either keep it or reject it, and this choice may depend on the locations of all previously kept points. However, the overseer must keep at least one of every two consecutive points. We call a sequence generated in this fashion a two-thinning sequence. Here, the purpose of the overseer is to control the discrepancy of the empirical distribution of points, that is, after selecting n points, to reduce the maximal deviation of the number of points inside any axis-parallel hyper-rectangle of volume A from nA. Our main result is an explicit low complexity two-thinning strategy which guarantees discrepancy of O(log^{2d+1}(n)) for all n with high probability [compare with \Theta(\sqrt{n log log n}) without thinning]. The case d=1 of this result answers a question of Benjamini.

Paper: https://link.springer.com/article/10.1007/s00440-018-0860-y?wt_mc=Internal.Event.1.SEM.ArticleAuthorOnlineFirst

In this talk, we discuss the inference problem of quantile regression for a large sample size n but under a limited memory constraint, where the memory can only store a small batch of data of size m. A popular approach, the naive divide-and-conquer method, only works when n=o(m^2) and is computationally expensive. This talk proposes a novel inference approach and establishes the asymptotic normality result that achieves the same efficiency as the quantile regression estimator computed on all the data. Essentially, our method can allow arbitrarily large sample size n as compared to the memory size m. Our method can also be applied to address the quantile regression under distributed computing environment (e.g., in a large-scale sensor network) or for real-time streaming data. This is a joint work with Weidong Liu and Yichen Zhang.

Robust estimation is much more challenging in high dimensions than it is in one dimension: Most techniques either lead to intractable optimization problems or estimators that can tolerate only a tiny fraction of errors. Recent work in theoretical computer science has shown that, in appropriate distributional models, it is possible to robustly estimate the mean and covariance with polynomial time algorithms that can tolerate a constant fraction of corruptions, independent of the dimension. However, the sample and time complexity of these algorithms is prohibitively large for high-dimensional applications. In this work, we address both of these issues by establishing sample complexity bounds that are optimal, up to logarithmic factors, as well as giving various refinements that allow the algorithms to tolerate a much larger fraction of corruptions. Finally, we show on both synthetic and real data that our algorithms have state-of-the-art performance and suddenly make high-dimensional robust estimation a realistic possibility.

Paper: https://arxiv.org/abs/1703.00893

This will be a combination of a paper by Liu and Gao on robust density estimation under pointwise L_2 loss (at a fixed point), along with some ongoing work on density estimation under L_p loss. Please see the paper for abstract of the first work (easier to parse the mathematical expressions in pdf). A rough summary of the of the second work is as follows. We revisit the classical non-parametric density estimation under Huber's contamination model and consider various L_p losses. We carefully study the effect of contamination on the rate-optimal estimation over a scale of the anisotropic Nikolskii classes. We also develop new adaptive procedures and derive the corresponding L_p risk oracle inequalities. Our technical analysis in adaptive procedures relies on some uniform bounds under the L_p norm of empirical processes developed by Goldenshluger and Lepski.

Ensemble methods are popular models for making predictions using many observations on predictors which may interact in complex ways. The regression function fit by ensemble methods is an average of many nonparametric base models, and is thus difficult to analyze. We propose a permutation test approach to feature significance in random forests (which can be extended easily to other bagged learners), which exploits the averaging nature of ensemble methods. In particular, we permute the individual trees of two random forests - one trained with a reduced dataset, and one trained with the full dataset. This method can be used to analyze predictions made by models at high numbers of test points at minimal extra cost. Moreover, the testing framework works with many existing implementation of random forests. We prove the asymptotic validity of the hypothesis test by exploring the connection between exchangeable random variables and ensemble methods. Further, we establish asymptotic normality for a wide variety of random forest metrics. Convergence of the permutation distribution to the null distribution, we avoid the difficulty of estimating the variance of random forests, which has inhibited the practical implementation of many distributional random forest results. Numerical results demonstrate that the test maintains Type I error validity and attains good power in practical random forest implementations.

Related paper: https://arxiv.org/pdf/1304.5939.pdf

I will lead the discussion of the paper on high-dimensional bootstrap by El Karoui and Purdom. The paper studies two variants of the bootstrap in linear regression models with 0 < p/n < 1 using ERM estimators with convex loss functions. I will mostly cover the first variant: the residual bootstrap. The key technical component is a dual leave-one-out analysis that characterizes the behavior of the fitted residuals and the estimation error, which is the main contribution of the earlier work by El Karoui and Co.

Random forests remain among the most popular off-the-shelf supervised learning algorithms. Despite their well-documented empirical success, however, until recently, few theoretical results were available to describe their performance and behavior. In this work we push beyond recent work on consistency and asymptotic normality by establishing rates of convergence for random forests and other supervised learning ensembles. We develop the notion of generalized U-statistics and show that within this framework, random forest predictions remain asymptotically normal for larger subsample sizes than previously established. We also provide a Berry-Esseen bound in order to quantify the rate at which this convergence occurs, making explicit the roles of the subsample size and the number of trees in determining the distribution of random forest predictions.

I will talk about some new results exposing surprising phenomena in min-norm least squares interpolation in high dimensions. The setting is very simple: given n observations from a linear model in p dimensions, run a linear regression, and take the minimum L2 norm solution when p > n. Now examine asymptotic prediction risk, when p/n converges to a positive constant \gamma. How does this behave with \gamma (and other problem aspects)? Random matrix theory provides a precise answer to this; despite the simplicity of this problem, there are several surprises, and several similarities to what is observed for more complex interpolators like kernels and neural networks.

Given data (x_i,y_i), i=1..n, an interpolating estimator f fits f(x_i) = y_i. Until recently it has been folklore knowledge that such interpolators do not have good prediction risk properties in the presence of label/response noise. But recent empirical findings are surprising -- test error goes down with training error in some high-dimensional settings such as neural networks. A natural question arises -- can we show that interpolating methods have good prediction risk in theory as well? In the first paper above, a kernel smoothing interpolator is shown to have minimax optimal prediction risk when the true regression function is in a Holder class. In the second paper, two nearest-neighbor-like interpolators are shown to have near optimal prediction risk.

Papers: 1. Does data interpolation contradict statistical optimality?; 2. Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate

Recall that we've been exploring the phenomenon of good out-of-sample error for estimators that achieve (nearly) zero in-sample error (even with noisy data); Ryan considered the minimum-norm interpolator in high-dimensional linear regression setting, while Veeru considered local smoothing methods with singular kernels and simplicial interpolation. This week, we'll consider minimum-norm interpolators in reproducing kernel Hilbert spaces. Empirical results in [Belkin et al., 2018] that indicate parallels in terms of good generalization in spite of overfitting between shallow architectures of kernel methods and deep architectures provide motivation for such discussion. Following [Liang and Rakhlin, 2018], we'll see how a combination of geometric properties of data and the kernel function, along with high dimensionality, lead to implicit regularization. We'll conclude with a converse from [Rakhlin and Zhai, 2018] that show inconsistency for the minimum-norm estimator using the Laplace kernel for any choice of bandwidth, even when selected using the data, if the input dimensional is constant, indicating the necessity of high dimensionality for good generalization in certain cases.

Classical study of linear regression required many assumptions like linearity, homoscedasticity and normality which can be unrealistic. I will start with some results on linear regression that do not require any model assumptions and further do not require any randomness assumptions on the data. I will then briefly discuss extension of this result to other M-estimation problems (including logistic and Poisson regression). Implications such as uniform-in-submodel result of these results follow. The problem of post-selection inference (PoSI) in linear regression will be discussed based on these results. Finally some results on computation for PoSI will be announced.

Prediction sets aim to trap a future observation with some guaranteed coverage. We'll visit different ways of constructing such sets, including using ideas from conformal prediction that endow such sets with nice properties. Then, we'll motivate the problem of robust prediction set estimation, in which the data generating process differs from the process generating future observation that we wish to trap. We'll see ways of adapting prediction sets to guarantee robust coverage, along with certain efficiency results for such constructions.

Relevant papers: Conformal prediction papers from Vovk's group [Shafer08, Vovk05]; use of conformal prediction ideas for (both unsupervised and supervised) prediction sets from all-star team here [Lei13, Lei15, Lei17]; robust prediction set part ongoing.

Conditional independence testing (i.e. testing whether X is independent of Y given Z) is an important topic in several fields in statistics such as graphical models and causal inference. It was recently shown that conditional independence testing is “hard” in the continuous Z case. In this paper, we demonstrate that by narrowing down the sets of distributions under the null and alternative hypothesis, conditional independence testing becomes possible. We obtain minimax lower bounds, and develop tests that match the lower bounds under the simplifying assumption of Poissonization. This is joint work with Siva and Larry.

We will consider a certain problem in fairness, write it down as an ML problem, use social choice theory to solve it, and end with some statistical open problems. What "certain problem" you ask? It's a problem on making decisions in the presence of subjective opinions of multiple evaluators (e.g., choosing papers in conference peer review or hiring candidates in a company). What is "social choice theory" you ask? It is a very cool field of research on voting and decision making. Tools from this area can be useful for problems we study, and I'll attempt to at least briefly introduce this area. Do I have a draft with more details, you ask? Yes I do https://arxiv.org/pdf/1808.09057

I will informally discuss some new, old and (very) partial results on robust mean estimation. Particularly, I will discuss my thoughts on model-misspecification versus robustness, some results on Hellinger robustness and on adapting to unknown parameters and unknown perturbation models in robust estimation. This is based on joint work/discussions with Adarsh.

Momentum based Stochastic Gradient Descent (SGD) algorithms are the workhorse for deep learning, and central premise for adding momentum based techniques is to accelerate SGD. However, it is not clear if such methods really accelerate vanilla SGD (with batch-size=1) or require the batch-size to be large to provide acceleration. In this talk, we will present a surprising result which shows that such methods *cannot* improve over SGD in standard stochastic approximation setting. However, by modifying the algorithm, we can show that one can indeed accelerate SGD but this requires very careful parametrization of the problem. Based on joint works with Rahul Kidambi, Praneeth Netrapalli, Sham Kakade, and Aaron Sidford.

This paper develops a class of exponential bounds for the probability that a martingale sequence crosses a time-dependent linear threshold. Our key insight is that it is both natural and fruitful to formulate exponential concentration inequalities in this way. We illustrate this point by recovering and improving many tail bounds for martingales, including classical inequalities (1960-80) by Bernstein, Bennett, Hoeffding, and Freedman; contemporary inequalities (1980-2000) by Shorack and Wellner, Pinelis, Blackwell, van de Geer, and de la Pena; and several modern inequalities (post-2000) by Khan, Tropp, Bercu and Touati, Delyon, and others. In each of these cases, we give the strongest and most general statements to date, quantifying the time-uniform concentration of scalar, matrix, and Banach-space-valued martingales, under a variety of nonparametric assumptions in discrete and continuous time. By choosing the optimal linear bound for a given time, we bridge the gap between existing line-crossing inequalities, the sequential probability ratio test, the Cramer-Chernoff method, self-normalized processes, and other parts of the literature.

From scientific experiments to online A/B testing, the previously observed data often affects how future experiments are performed, which in turn affects which data will be collected. Such adaptivity introduces complex correlations between the data and the collection procedure. In this paper, we prove that when the data collection procedure satisfies natural conditions, then sample means of the data have systematic negative biases. As an example, consider an adaptive clinical trial where additional data points are more likely to be tested for treatments that show initial promise. Our surprising result implies that the average observed treatment effects would underestimate the true effects of each treatment. We quantitatively analyze the magnitude and behavior of this negative bias in a variety of settings. We also propose a novel debiasing algorithm based on selective inference techniques. In experiments, our method can effectively reduce bias and estimation error.

A confidence sequence is a sequence of confidence intervals that is uniformly valid over an unbounded time horizon. In this paper, we develop non-asymptotic confidence sequences under nonparametric conditions that achieve arbitrary precision. Our technique draws a connection between the classical Cramer-Chernoff method, the law of the iterated logarithm (LIL), and the sequential probability ratio test (SPRT)—our confidence sequences extend the first to produce time-uniform concentration bounds, provide tight non-asymptotic characterizations of the second, and generalize the third to nonparametric settings, including sub-Gaussian and Bernstein conditions, self-normalized processes, and matrix martin- gales. We strengthen and generalize existing constructions of finite-time iterated logarithm (“finite LIL”) bounds. We illustrate the generality of our proof techniques by deriving an empirical-Bernstein finite LIL bound as well as a novel upper LIL bound for the maximum eigenvalue of a sum of random matrices. Finally, we demonstrate the utility of our approach with applications to covariance matrix estimation and to estimation of sample average treatment effect under the Neyman-Rubin potential outcomes model.

At first glance, online learning and martingale inequalities may not appear to be intrinically linked. We will showcase a recently discovered equivalence between existence of algorithms for online learning, martingale inequalities, and special "Burkholder" functions. Using this equivalence as a starting point, we define a notion of a sufficient statistic for online learning and use the Burkholder method---originally used to certify probabilistic martingale inequalities---to develop algorithms that only keep these sufficient statistics in memory. To demonstrate the power of the Burkholder method we introduce new efficient and adaptive algorithms for online learning, including an algorithm for matrix prediction that attains a regret bound corresponding to the variance term found in matrix concentration inequalities.

Suppose that you have a copy of a single issue of a medical journal whose policy is to publish 100 findings with p-values<0.05. You take a look at the first article and see a reported p-value of 0.03. What do you make out of this information, being aware of the selection effect and remembering that you only have access to the published articles? A reasonable correction would be to estimate the fraction of nulls among reported findings with p-value<0.03. We discuss ideas for estimating this quantity from only the reported (truncated) p-values. Focusing attention on estimation rather than testing, we propose an empirical Bayes estimator for the mean effect size for the published findings. This can be considered an analogue of Efron’s (2012) methods for the case where only the selected are observed. This is joint work with Amit Meir.

I'll give a high-level intro to some basic in random matrix theory, primarily surrounding the Marchenko-Pastur law. Then I'll talk about how this and other more recent results in random matrix theory can be leveraged to understand the asymptotics of ridge regression in a very general and interesting way, due to Dobriban and Wager (2018) https://arxiv.org/pdf/1507.03003.pdf. Time permitting, I'll also mention some recent work by Alnur Ali, Zico Kolter, and myself, where we use similar techniques to develop an understanding of gradient flow (continuous-time gradient descent) and its relationship to ridge.

We study the statistical properties of the iterates generated by gradient descent, applied to the fundamental problem of least squares regression. We take a continuous-time view, i.e., consider infinitesimal step sizes in gradient descent, in which case the iterates form a trajectory called gradient flow. In a random matrix theory setup, which allows the number of samples $n$ and features $p$ to diverge in such a way that $p/n \to \gamma \in (0,\infty)$, we derive and analyze an asymptotic risk expression for gradient flow. In particular, we compare the asymptotic risk profile of gradient flow to that of ridge regression. When the feature covariance is spherical, we show that the optimal asymptotic gradient flow risk is between 1 and 1.25 times the optimal asymptotic ridge risk. Further, we derive a calibration between the two risk curves under which the asymptotic gradient flow risk no more than 2.25 times the asymptotic ridge risk, at all points along the path. We present a number of other results illustrating the connections between gradient flow and $\ell_2$ regularization, and numerical experiments that support our theory.

Papers: http://www.stat.cmu.edu/~ryantibs/papers/tvdfs.pdf; http://www.stat.cmu.edu/~ryantibs/papers/trendfilter.pdf

The goal of active learning is to learn a classifier in a setting where data comes unlabeled, and any labels must be explicitly requested and paid for. The hope is that an accurate classifier can be found by buying just a few labels. This problem is also known as the optimal decision tree problem in the field of approximation algorithms. In this talk I will introduce some classical results in both these two fields, and present some representative techniques for analyzing the related greedy algorithms.

Three challenges which attract a great deal of attention in the current mixture model literature include (1) understanding the behaviour of parameter estimation in mixtures with a misspecified number of components, (2) estimating the number of components of a mixture, and (3) constructing estimators which are robust to misspecification of the component density functions. I will start by discussing some recent results regarding (1), to motivate a new method of Ho, Nguyen and Ritov which addresses (2) and (3). In the first part of the talk, the focus will be on a recent line of work by the first two authors, which characterizes the complicated behaviour of optimal rates of convergence for various classes of mixing measures. For instance, I will explain why the results of this theory warn against the use of maximum likelihood estimation for Gaussian mixture models with an incorrect number of components. In the second part of the talk, I will present the authors' proposed estimator of mixing measures, inspired by minimum Hellinger distance estimation. I will discuss its robustness properties, and show that it satisfies similar asymptotic properties as comparable likelihood-based approaches, under weaker assumptions.

The main paper is: https://arxiv.org/pdf/1709.08094.pdf The first part of the talk will mainly be based on the following two papers: http://www-personal.umich.edu/~minhnhat/AoS_2016.pdf and http://www-personal.umich.edu/~minhnhat/Ejs_2016.pdf

In this talk, we investigate the problem of statistical inference of the true model parameters based on stochastic gradient descent (SGD). To this end, we propose two consistent estimators of the asymptotic covariance of the average iterate from SGD: (1) an intuitive plug-in estimator and (2) a computationally more efficient batch-means estimator, which only uses the iterates from SGD. As the SGD process forms a time-inhomogeneous Markov chain, our batch-means estimator with carefully chosen increasing batch sizes generalizes the classical batch-means estimator designed for time-homogenous Markov chains. Both proposed estimators allow us to construct asymptotically exact confidence intervals and hypothesis tests. We further discuss an extension to conducting inference based on SGD for high-dimensional linear regression.

In this paper we consider the question of global optimization of unknown non-convex smooth functions. The algorithm is allowed to adaptively query the underlying func- tion at different locations and receive noisy evaluations function values at queried points. Optimization performance is evaluated by the expected difference of function values at the estimated optimum and the true optimum. Unlike classical optimization problems, first-order information like gradients are not accessible. We propose a local minimax theoretical framework to characterize the fundamental difficulty of optimizing smooth functions with adaptive function evaluations. We show that for functions with fast level set growth around the global minimum, adaptive algorithms converge faster. For the special case of strongly convex and smooth functions, our implied convergence rates match the one developed solely for zeroth-order convex optimization problems [1, 27]. On the other hand, for worst-case smooth functions no algorithm can converge faster than the minimax rate of estimation the entire unknown function in sup norm. We also explicitly give an intuitive and efficient algorithm that attains the derived upper error bounds.

In supervised learning, we leverage a labeled dataset to design methods for function estimation. In many practical situations, we are able to obtain alternative feedback, possibly at a low cost. A broad goal is to understand the usefulness of, and to design algorithms to exploit, this alternative feedback. We consider a semi-supervised setting where we obtain additional ordinal (or comparison) information for potentially unlabeled samples. We consider ordinal feedback of varying qualities where we have either a perfect ordering of the samples, a noisy ordering of the samples or noisy pairwise comparisons between the samples. We provide a precise quantification of the usefulness of these types of ordinal feedback in non-parametric regression, showing that in many cases it is possible to accurately estimate an underlying function with a very small labeled set, effectively escaping the curse of dimensionality. We develop an algorithm called Ranking-Regression(R^2) and analyze its accuracy as a function of size of the labeled and unlabeled datasets and various noise parameters. We also present lower bounds that establish fundamental limits for the task and show that R^2 is optimal in a variety of settings. This is joint work with Hariank Muthakana, Sivaraman Balakrishnan, Artur Dubrawski and Aarti Singh.

GAN tutorial: https://arxiv.org/abs/1701.00160

Two papers: https://arxiv.org/pdf/1703.00573.pdf; https://arxiv.org/abs/1706.08224.pdf

We propose a generalization of the lasso that allows the model coefficients to vary as a function of a general set of modifying variables. These modifiers might be variables such as gender, age or time. The paradigm is quite general, with each lasso coefficient modified by a sparse linear function of the modifying variables Z. The model is estimated in a hierarchical fashion to control the degrees of freedom and avoid overfitting. The modifying variables may be observed, observed only in the training set, or unobserved overall. There are connections of our proposal to varying coefficient models and high-dimensional interaction models. We present a computationally efficient algorithm for its optimization, with exact screening rules to facilitate application to large numbers of predictors. The method is illustrated on a number of different simulated and real examples.

In this talk I'll discuss the cost-sensitive classification problem and a new active learning algorithm for this setting. The talk has something for everyone: (1) algorithmic challenges, (2) statistical analysis, and (3) fun experiments. There are also many open problems for future work.

In this work we study some tests for the homogeneity between two independent samples of functional data. The null hypothesis of "homogeneity" here means that the latent stochastic processes which generated the two samples have the same distribution. Most instances of functional data are so complex that it seems natural to opt for nonparametric procedures in this setting. Making use of recent developments on functional depths, we adapt some Kolmogorov-Smirnov- and Cramer-von-Mises-type of criteria to the functional context. Exact p-values for the test can be obtained via permutations, or, in case of too large samples, a bootstrap algorithm is easily implemented. Some real data examples are analyzed.

We will discuss the information-theoretic limitations of graph property testing in zero-field Ising models. Instead of learning the entire graph structure, sometimes testing a basic graph property such as connectivity, cycle presence or maximum clique size is a more relevant and attainable objective. Since property testing is more fundamental than graph recovery, any necessary conditions for property testing imply corresponding conditions for graph recovery, while custom property tests can be statistically and/or computationally more efficient than graph recovery based algorithms. Understanding the statistical complexity of property testing requires the distinction of ferromagnetic (i.e., positive interactions only) and general Ising models. Using combinatorial constructs such as graph packing and strong monotonicity, we characterize how target properties affect the corresponding minimax upper and lower bounds within the realm of ferromagnets. On the other hand, by studying the detection of an antiferromagnetic (i.e., negative interactions only) Curie-Weiss model burried in Rademacher noise, we show that property testing is strictly more challenging over general Ising models. We will also briefly discuss two types of correlation based tests: computationally efficient screening for ferromagnets, and "score type" tests for general models.

I will discuss the question of locating the minimum of an unknown function from noisy adaptive queries. I will discuss why the problem does not make much sense for general non-parametric families like Holder classes, and why the problem becomes interesting with certain shape constraints such as convexity. I will review some results in both the machine learning and the statistics literature on convex regression and zeroth order optimization, and mention open questions.

We consider a regression problem of semi-supervised learning: given real-valued labels on a small subset of data recover the function on the whole data set while taking into account the information provided by a large number of unlabeled data points. Objective functionals modeling this regression problem involve terms rewarding the regularity of the function estimate while enforcing agreement with the labels provided. We will discuss regularizations motivated by p-Laplace equation. We will discuss and prove which of these functionals make sense when the number of data points goes to infinity. The talk is based on joint work with Matthew Thorpe (arXiv:1707.06213).

Statistical reasoning and statistical inference have strong historical connections with philosophy of science. In this talk, the new paradigm of data-driven science is examined through comparison with principled statistical approaches. I will review the merits and shortcomings of principled statistical inference. The talk will feature a case study of post-selection inference, recent progress regarding inference for black box algorithms, and a survey of future challenges.

Noisy matrix non-negative matrix completion involves reconstructing a structured matrix whose entries are partially observed in noise. Standard approaches to this problem are based on assuming that the underlying matrix has a low (non-negative) rank. We first describe how this classical non-negative rank model enforces restrictions that may be quite undesirable in practice. We propose a richer model based on what we term the "permutation-rank" of a matrix, and show how these restrictions can be avoided by using this richer model. Second, we establish the minimax rates of estimation under the new permutation-based model, and prove that surprisingly, the minimax rates are equivalent up to logarithmic factors to those for estimation under the typical low rank model. We also analyze a computationally efficient singular-value-thresholding algorithm, known to be optimal for the low-rank setting, and show that it also simultaneously yields a consistent estimator for the low-permutation rank setting.

In this talk, I will review some of basic concepts in the random closed set theory. Specifically, I will give a brief review of two intuitive definitions of expectations of random closed sets – the Vorob’ev expectation and the ODF expectation. The former minimizes the expected measure of the symmetric difference between the random set and its expectation. I will discuss how one might possibly use this property to construct a representative, non-random predictive region from observed random predictive regions. The latter has some attractive properties for shape and boundary estimation problem. These properties include inclusion relations, convexity preservation, and equivariance with respect to rigid motions.

References: 1. Molchanov, Ilya. Theory of random sets. Springer Science & Business Media, 2006; 2. Jankowski, Hanna K., and Larissa I. Stanberry. "Expectations of random sets and their boundaries using oriented distance functions." Journal of Mathematical Imaging and Vision 36.3 (2010): 291-303.

The dynamic Bayesian regression tree is a flexible regression model for sequential data that permits the relationship between the response and explanatory variables to evolve smoothly over time through a latent process. As such it is suited to tasks involving concept drift and active learning. This paper shows that exact sequential inference can be performed via implementation of the intermittent Kalman filter, permitting fast computation. Inference on the tree structure is done through an ensemble approach and an exact expression for the posterior weight of each tree in the ensemble can be derived. Extensions of this work will be discussed.

Huber's \epsilon contamination model is a half-century-old problem in statistics. Classical approaches based on Tukey's give optimal statistical rate but is computationally infeasible. In this talk, I'll first describe polynomial time robust estimators for Gaussian mean proposed last year by theoretical computer science researchers. Next, I'll talk about our work on how to generalize the estimators to the high-dimensional setting. Last, I'll list several open problems.

References: https://arxiv.org/abs/1604.06443; https://arxiv.org/abs/1604.06968; https://arxiv.org/abs/1702.07709; https://arxiv.org/abs/1703.00893

Traditionally, network data is embedded to Euclidean space, such as multidimensional scaling. However, embedding network data into Euclidean space is inappropriate if the degree distribution is heterogeneous. Considering the volume of a ball with increasing radius, then the volume grows polynomially in Euclidean space, while the volume grows exponentially in tree network data, and hence embedding tree network data into Euclidean space distort the distance structure in the data. Embedding network data in hyperbolic space has been vastly tried in visualizing internet network, where the degree of a network is believed to follow a power-law distribution. In this talk, we will review basic concepts in hyperbolic geometry, and see how network data can be embedded into hyperbolic space, or how to model network data using hyperbolic space.

I will talk about the problem of “sequential adaptive estimation”, where we want to come up with estimators that can accurately estimate a sequence of sequentially chosen parameters. This is related to the problem of Adaptive Data Analysis by Dwork et. al., 2015 (appeared in FOCS’14, NIPS’15 and then a Science article), but differs in that we consider the Gaussian sequence model that is more relevant to statistical literature. I will talk about upper bound through a simple mutual information argument due to Russo and Zou (AISTATS’16), highlighting the difficulties in generalizing beyond joint-Gaussianity; and talk about a matching lower bound that Jing, Steve and I worked out. I will try to go over the high level arguments of the rather challenging proof, and mention a few open problems. Lastly, I will highlight a surprising connection to “linear bandits”, which has been studied extensively over the past few years and discuss the intriguing implication of the interplay between the two fields.

References: - Dwork et. al. : FOCS, https://arxiv.org/abs/1411.2664, NIPS https://papers.nips.cc/paper/5993-generalization-in-adaptive-data-analysis-and-holdout-reuse.pdf - Russo and Zou paper: http://proceedings.mlr.press/v51/russo16.html - Hugely out-dated version our paper: https://arxiv.org/abs/1602.04287. The more recent reference is Chapter 10 of my thesis: https://www.dropbox.com/s/v4t7nf9ytqlu1hv/yuxiang-thesis-draft.pdf?dl=0, and the connection to bandits are partially written down on Page 293 onwards. - Stochastic linear bandits: http://banditalgs.com/2016/10/19/stochastic-linear-bandits/) - Adversarial linear bandits: http://banditalgs.com/2016/11/25/adversarial-linear-bandits-and-the-curious-case-of-the-unit-ball/

In exciting new work, Bertsimas et al. (2016) showed that the classical best subset selection problem in regression modeling can be formulated as a mixed integer optimization (MIO) problem. Using recent advances in MIO algorithms, they demonstrated that best subset selection can now be solved at much larger problem sizes that what was thought possible in the statistics community. They presented empirical comparisons of best subset selection with other popular variable selection procedures, in particular, the lasso and forward stepwise selection. Surprisingly (to us), their simulations suggested that best subset selection consistently outperformed both methods in terms of prediction accuracy. Here we present an expanded set of simulations to shed more light on these comparisons. The summary is roughly as follows: (a) neither best subset selection nor the lasso uniformly dominate the other, with best subset selection generally performing better in high signal-to-noise (SNR) ratio regimes, and the lasso better in low SNR regimes; (b) best subset selection and forward stepwise perform quite similarly throughout; (c) the relaxed lasso (actually, a simplified version of the original relaxed estimator defined in Meinshausen, 2007) is the overall winner, performing just about as well as the lasso in low SNR scenarios, and as well as best subset selection in high SNR scenarios.

Papers: Hastie et al. discussion; Bertsimas et al. original paper

We consider the problem of estimating a function defined over n locations on a d-dimensional grid (having all side lengths equal to n^1/d). When the function is constrained to have discrete total variation bounded by Cn, we derive the minimax optimal (squared) \ell_2 estimation error rate, parametrized by n and Cn. Total variation denoising, also known as the fused lasso, is seen to be rate optimal. Several simpler estimators exist, such as Laplacian smoothing and Laplacian eigenmaps. A natural question is: can these simpler estimators perform just as well? We prove that these estimators, and more broadly all estimators given by linear transformations of the input data, are suboptimal over the class of functions with bounded variation. This extends fundamental findings of Donoho and Johnstone [1998] on 1-dimensional total variation spaces to higher dimensions. The implication is that the computationally simpler methods cannot be used for such sophisticated denoising tasks, without sacrificing statistical accuracy. We also derive minimax rates for discrete Sobolev spaces over d-dimensional grids, which are, in some sense, smaller than the total variation function spaces. Indeed, these are small enough spaces that linear estimators can be optimal—and a few well-known ones are, such as Laplacian smoothing and Laplacian eigenmaps, as we show. Relevant paper.

Phylogenetic trees, which is inferring evolutionary histories, has important applications in biology, criminology and public health. This talk presents a continuous space which models the set of all phylogenetic trees having a fixed set of leaves. This space has a natural metric of non-positive curvature, allowing a valid procedure for averaging or combining several trees whose leaves are identical. This talk also presents limiting behavior of such averaged trees. Relevant paper.

Machine learning (ML) has become one of the most powerful classes of tools for artificial intelligence, personalized web services and data science problems across fields. However, the use of ML on sensitive data sets involving medical, financial and behavioral data are greatly limited due to privacy concern. In this talk, we consider the problem of statistical learning with privacy constraints. Under Vapnik's general learning setting and the formalism of differential privacy (DP), we establish simple conditions that characterizes the private learnability, which reveals a mixture of positive and negative insight. We then identify generic methods that reuse existing randomness to effectively solve private learning in practice; and discuss a weaker notion of privacy — on-avg KL-privacy — that allows for orders-of-magnitude more favorable privacy-utility tradeoff, while preserving key properties of differential privacy. Moreover, we show that On-Average KL-Privacy is **equivalent** to generalization for a large class of commonly-used tools in statistics and machine learning that sample from Gibbs distributions---a class of distributions that arises naturally from the maximum entropy principle. Finally, I will describe a few exciting future directions that use statistics/machine learning tools to advance he state-of-the-art for privacy, and use privacy (and privacy inspired techniques) to formally address the problem of p-hacking in scientific discovery. References:

1. Yu-Xiang Wang, Jing Lei, and Stephen E. Fienberg. "Learning with differential privacy: Stability, learnability and the sufficiency and necessity of ERM principle." *Journal of Machine Learning Research* 17.183 (2016): 1-40.
2. Yu-Xiang Wang, Stephen E. Fienberg, and Alexander J. Smola. "Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo." *ICML*. 2015.
3. Yu-Xiang Wang, Jing Lei, and Stephen E. Fienberg. "On-Average KL-Privacy and Its Equivalence to Generalization for Max-Entropy Mechanisms." *International Conference on Privacy in Statistical Databases*. Springer International Publishing, 2016.

I will discuss the problem of estimating structural equation models from high-dimensional Gaussian data with p ≫ n. The main difficulty in establishing statistical guarantees in this setting arises from the nonidentifiability, nonsmoothness, and nonconvexity of the underlying M-estimator (aka score-based estimator). I will discuss how to establish nonasymptotic deviation bounds on the estimation error, sparsity bounds, and model selection consistency for a penalized least squares estimator. The proofs rely on interpreting the graphical model as a recursive linear structural equation model, which reduces the estimation problem to a series of tractable neighbourhood regressions, allowing us to avoid making any assumptions regarding identifiability, irrepresentability, or faithfulness. The techniques employed here provide insight into and can be used more broadly for general nonidentifiable and nonconvex problems. Reference: Mostly based on this preprint.

I'll present about tools for statistical inference conditioned on model selection events that are defined by the generalized lasso regularization path in Tibshirani & Taylor (2011) [1], using recent advances in post-selection inference from Lee et al. (2016) [2], Tibshirani et al. (2016) [3]. These tools allow for exact hypothesis tests and confidence intervals for linear contrasts of the underlying mean vector, conditioned on any model selection event along the generalized lasso path (assuming Gaussian errors in the observations). Models covered by the generalized lasso included such as the fused lasso, trend filtering, and the graph fused lasso. In the fused lasso case, the underlying coordinates of the mean are assigned a linear ordering, and our framework allows us to test selectively chosen breakpoints or changepoints in these mean coordinates. This idea extends to changepoint models recovered by segmentation algorithms, and beyond Gaussian errors, and also to goodness-of-fit tests instead of targeted tests of linear contrasts as described above -- I'll describe these if time permits. This is work by me and my advisors Ryan Tibshirani and Max G'sell [4].

1. https://arxiv.org/pdf/1005.1971.pdf
2. https://arxiv.org/pdf/1311.6238.pdf
3. https://arxiv.org/pdf/1401.3889.pdf
4. https://arxiv.org/pdf/1606.03552.pdf

Most modern supervised statistical/machine learning (ML) methods are explicitly designed to solve prediction problems very well. Achieving this goal does not imply that these methods automatically deliver good estimators of causal parameters. Examples of such parameters include individual regression coefficients, average treatment effects, average lifts, and demand or supply elasticities. In fact, estimates of such causal parameters obtained via naively plugging ML estimators into estimating equations for such parameters can behave very poorly due to the regularization bias. Fortunately, this regularization bias can be removed by solving auxiliary prediction problems via ML tools. Specifically, we can form an orthogonal score for the target low-dimensional parameter by combining auxiliary and main ML predictions. The score is then used to build a de-biased estimator of the target parameter which typically will converge at the fastest possible 1/root(n) rate and be approximately unbiased and normal, and from which valid confidence intervals for these parameters of interest may be constructed. The resulting method thus could be called a "double/de-biased ML" method because it relies on estimating primary and auxiliary predictive models to overcome regularization biases. In order to avoid overfitting, our construction also makes use of the K-fold sample splitting, which we call cross-fitting. This allows us to use a very broad set of ML predictive methods in solving the auxiliary and main prediction problems, such as random forest, lasso, ridge, deep neural nets, boosted trees, as well as various hybrids and aggregators of these methods.

We show that given an estimate $\widehat{A}$ that is close to a general high-rank positive semi-definite (PSD) matrix $\widehat{A}$ in spectral norm, the simple truncated SVD of Ab produces a multiplicative approximation of A in Frobenius norm. This observation leads to many interesting results on general high rank matrix estimation problems, including high rank matrix completion, high rank matrix denoising and low-rank estimation of high-dimensional covariance. Link: https://arxiv.org/abs/1702.06861

Every day Stanford hospital (SHC) orders some number of units of platelets from the Stanford Blood Center (SBC). Although SBC collects these units daily from donors, the units are held in testing for first 2 days, after which they can be released and can only be used for the next 3 days, before they expire. Currently the number of units ordered by SHC is based on historical daily averages. While there is rarely a shortage, many units are wasted over the year. Using information that is available about the patients and planned procedures in the hospital, we have constructed a supervised learning model and an ordering scheme that on backtesting reduces the number of units wasted by two-thirds without any shortages. This will potentially allow for optimized SBC donor collection strategy and SHC ordering strategy to drastically reduce the cost of wastage without compromising patient care.

Cross-validation is one of the most popular model selection methods in statistics and machine learning. Despite its wide applicability, traditional cross-validation methods tend to select overfitting models, unless the ratio between the training and testing sample sizes is much smaller than conventional choices. We argue that such an overfitting tendency of cross-validation is due to the ignorance of the uncertainty in the testing sample. Starting from this observation, we develop a new, statistically principled inference tool based on cross-validation that takes into account the uncertainty in the testing sample. This new method outputs a small set of highly competitive candidate models containing the best one with guaranteed probability. As a consequence, our method can achieve consistent variable selection in a classical linear regression setting, for which existing cross-validation methods require unconventional split ratios. We demonstrate the performance of the proposed method in several simulated and real data examples. Link: https://arxiv.org/abs/1703.07904

j In this talk, I will review some of the well known and less well known statistical results on neural networks. Specifically, I will present minimax rates and generalization error bounds for shallow neural networks, which appear to break the curse of dimensionality that other nonparametric estimators are known to suffer. In the first part of the talk, I will give a brief review of neural networks and present their universal approximation property as well as their minimax rates of convergence [1]. In the second part of the talk, I will introduce convex neural networks and their connections to RKHS to show how shallow neural networks with the popular rectified linear units (ReLUs) can achieve a sparsity-adaptive generalization error bound [2]. Time permitting, I will also mention some recent work that explains the effect of depth in deep learning.

1. Yang, Y., Barron, A. (1999). Information-theoretic determination of minimax rates of convergence. Annals of Statistics, 1564-1599.
2. Bach, F. (2014). Breaking the curse of dimensionality with convex neural networks. Research Report, INRIA Paris.

I will discuss some recent theoretical results on Thompson sampling for Multi-armed Bandits. The discussion will be based on the following line of work,

1. http://www.jmlr.org/papers/volume17/14-087/14-087.pdf
2. http://djrusso.github.io/docs/Learning_to_Optimize.pdf
3. https://arxiv.org/abs/1403.5556

A number of statistical estimation problems can be addressed by semidefinite programs (SDP). While SDPs are solvable in polynomial time using interior point methods, in practice generic SDP solvers do not scale well to high-dimensional problems. In order to cope with this problem, Burer and Monteiro proposed a non-convex rank-constrained formulation, which has good performance in practice but is still poorly understood theoretically. In this paper we study the rank-constrained version of SDPs arising in MaxCut and in synchronization problems. We establish a Grothendieck-type inequality that proves that all the local maxima and dangerous saddle points are within a small multiplicative gap from the global maximum. We use this structural information to prove that SDPs can be solved within a known accuracy, by applying the Riemannian trust-region method to this non-convex problem, while constraining the rank to be of order one. For the MaxCut problem, our inequality implies that any local maximizer of the rank-constrained SDP provides a (1−1/(k−1))×0.878 approximation of the MaxCut, when the rank is fixed to k. We then apply our results to data matrices generated according to the Gaussian ℤ2 synchronization problem, and the two-groups stochastic block model with large bounded degree. We prove that the error achieved by local maximizers undergoes a phase transition at the same threshold as for information-theoretically optimal methods. Link to paper: https://arxiv.org/abs/1703.08729

Modern learning algorithms are often seen as prediction-only tools, meaning that the interpretability and intuition provided by a more traditional modeling approach are sacrificed in order to achieve superior predictions. In this talk, we argue that this black-box perspective need not always be the case and develop formal statistical inference procedures for predictions generated by supervised learning ensembles. Ensemble methods based on bootstrapping, such as bagging and random forests, usually improve the predictive accuracy of individual trees, but fail to provide a framework in which distributional results can be easily determined. Instead of aggregating full bootstrap samples, we consider predicting by averaging over trees built on subsamples of the training set and demonstrate that the resulting estimator takes the form of a U-statistic. As such, predictions for individual feature vectors are asymptotically normal, allowing for confidence intervals to accompany predictions. In practice, a subset of subsamples is used for computational speed; here our estimators take the form of incomplete U-statistics and equivalent results are derived. We further demonstrate that this setup provides a framework for testing the significance of features. Moreover, the internal estimation method we develop allows us to estimate the variance parameters and perform these inference procedures at no additional computational cost. Demonstrations are provided using data from the ebird project hosted at Cornell University. Here is the link to the relevant paper: http://jmlr.org/papers/v17/14-168.html

In this talk I will introduce a framework for constructing goodness of fit tests in both low and high-dimensional linear models. The idea involves applying regression methods to the scaled residuals following either an ordinary least squares or Lasso fit to the data, and using some proxy for prediction error as the final test statistic. We call this family Residual Prediction (RP) tests. We show that simulation can be used to obtain the critical values for such tests in the low-dimensional setting, and demonstrate that some form of the parametric bootstrap can do the same when the high-dimensional linear model is under consideration. We show that RP tests can be used to test for significance of groups or individual variables as special cases, and here they compare favourably with state of the art methods, but we also argue that they can be designed to test for as diverse model misspecifications as heteroscedasticity and different types of nonlinearity. This is joint work with Peter Bühlmann. Preprint: http://www.statslab.cam.ac.uk/~rds37/papers/RPtests

Continuous treatments (e.g., doses) arise often in practice, but many available causal effect estimators are limited by either requiring parametric models for the effect curve, or by not allowing doubly robust covariate adjustment. We develop a novel kernel smoothing approach that requires only mild smoothness assumptions on the effect curve, and still allows for misspecification of either the treatment density or outcome regression. We derive asymptotic properties and give a procedure for data-driven bandwidth selection. The methods are illustrated via simulation and in a study of the effect of nurse staffing on hospital readmissions penalties. Preprint: http://arxiv.org/abs/1507.00747

n many real world problems such as online advertisement, web search, movie recommendations, personalized medical treatment. One can only observe outcomes of the actions (be it ads, search results, movies or treatments) that were taken. Let the algorithm used to generate these actions be a “policy”, we consider the problem of **off-policy** evaluation, where we collect data using a policy and then we try to evaluate the performance of a different policy. In other word, this is to answer the “What-If” question: what if the other policy was deployed, what would the outcomes be? In this talk, I will do the following:

1. Formulate the problem as a minimax-estimation problem and states its minimax risk. The result suggests that the simplest possible approach: “Importance Sampling” a.k.a “Inverse Propensity Scoring” in some sense cannot be improved, if no model assumptions are made.
2. Illustrate that the state-of-the-art “Doubly Robust” estimator that incorporates model-based approaches is strictly suboptimal.
3. Describe a new adaptive estimator that overcomes the issues with “Doubly Robust”.

Relevant slides: http://www.cs.cmu.edu/~yuxiangw/docs/minimax_eval_talk.pdf

It is commonplace to encounter nonstationary data, of which the underlying generating process may change over time or across domains. The nonstationarity presents both challenges and opportunities for causal discovery. In this paper we propose a principled framework to handle nonstationarity, and develop methods to address three important questions. First, we propose an enhanced constraint-based method to detect variables whose local mechanisms are nonstationary and recover the skeleton of the causal structure over observed variables. Second, we present a way to determine some causal directions by taking advantage of information carried by changing distributions. Third, we develop a method for visualizing the nonstationarity of local mechanisms. Experimental results on various synthetic and real-world datasets are presented to demonstrate the efficacy of our methods. Relevant paper: https://arxiv.org/abs/1509.08056

ketching techniques have become popular for scaling up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, while still maintaining the statistical power of big data. We study sketching from an optimization point of view. We first show that the iterative Hessian sketch is an optimization process with preconditioning, and develop accelerated iterative Hessian sketch via the searching the conjugate direction; we then establish primal-dual connections between the Hessian sketch and dual random projection, and apply the preconditioned conjugate gradient approach on the dual problem, which leads to the acclerated iterative dual random projection methods. Finally to tackle the challenges from both large sample size and high-dimensionality, we propose the primal-dual sketch, which iteratively sketches the primal and dual formulations. Joint work with Jialei Wang, Jason D. Lee, Mehrdad Mahdavi and Nati Srebro

I’ll be presenting some of my recent work on statistical matching - the problem of estimating a joint distribution or properties of it when many pairs of random variables are never sampled simultaneously. It is well established that statistical matching encounters problems of non-identifiability unless certain assumptions, such as conditional independence of any pair of variables never sampled together, hold. In this work, we reexamine the conditions under which models can be identified in the statistical matching scenario. We show that latent variable models, such as factor analysis and latent trait models, while violating the typical conditional independence assumptions appealed to in statistical matching, are nonetheless, generically identifiable. Intuitively, generic identifiability establishes identifiability for sets of randomly generated parameters, and we present conditions establishing when latent variable models are generically identifiable and unidentifiable in the statistical matching scenario. I’ll also spend some time describing real neuroscience analyses which motivate the use of statistical matching. This is joint work with Byron Yu and Geoff Gordon that we are currently writing up (so no paper yet), and we would love to get your feedback.

This paper studies how to capture dependency graph structures from real data which may not be multivariate Gaussian. Starting from marginal loss functions not necessarily derived from probability distributions, we use an additive over-parametrization with shrinkage to incorporate variable dependencies into the criterion. An iterative Gaussian graph learning algorithm is proposed with ease in implementation. Statistical analysis shows that with the error measured in terms of a proper Bregman divergence, the estimators have fast rate of convergence. Real-life examples in different settings are given to demonstrate the efficacy of the proposed methodology.

I present a theory of point and interval estimation for nonlinear functionals in parametric, semi-, and non-parametric models based on higher order influence functions. The theory reproduces many previous results, produces new non-root n results, and opens up the ability to perform optimal non-root n inference in complex high dimensional models. We present novel rate-optimal point and intervals estimators for various functionals of central importance to statistics and biostatistics in settings in which estimation at the expected root n rate is not possible, owing to the curse of dimensionality.

The availability of high-dimensional data in statistical applications has created an urgent need for methodologies to pursue sparse and/or low rank models. To provide a proper amount of shrinkage, most statistical approaches use a grid search with a model comparison criterion to locate proper values of the regularization parameters. We study cross-validation for multivariate models where relevant features may lie in a low dimensional subspace. By cross-validating candidate projection-selection patterns instead of regularization parameters, we are able to link cross-validation to a class of information criteria. A scale-free rate calibration helps cross-validation achieve non-asymptotic optimality in prediction.

I will continue the topic that I introduced last semester on computationally efficient experiment selection in regression models, with additional results and analysis. I will analyze a sampling based method and a greedy method, both of which attain provable near-optimal statistical performance in polynomial time while enjoy different finite sample performance.

The estimation of time-varying networks for functional Magnetic Resonance Imaging (fMRI) data sets is of increasing importance and interest. In this work, we formulate the problem in a high-dimensional time series framework and introduce a data-driven method, namely Network Change Points Detection (NCPD), which detects change points in the network structure of a multivariate time series, with each component of the time series represented by a node in the network. NCPD is applied to various simulated data and a resting-state fMRI data set. This new methodology also allows us to identify common functional states within and across subjects. Finally, NCPD promises to offer a deep insight into the large-scale characterisations and dynamics of the brain. This is joint work with Ivor Cribben (Alberta School of Business)

A number of machine learning tasks relies on spectral properties of the graph laplacian associated to the data. I will consider data points obtained as random samples of a measure on a manifold in $R^d$. I will discuss conditions under which the spectrum of the graph Laplacians on a neighborhood graph spanned by the samples converges almost surely to the spectrum of appropriate weighted Laplace-Beltrami operators on the manifold, as the sample size increases and the neighborhood size shrinks to zero. I will present error estimates for the convergence that explicitly depend on the geometry of the manifold, the number of data points available and the size of the neighborhood used in the graph construction. This is based on work that is in preparation.

Nearly all estimators in statistical prediction come with an associated tuning parameter, in one way or another. Common practice, given data, is to choose the tuning parameter value that minimizes a constructed estimate of the prediction error of the estimator. Of course, estimating prediction error has a long history in statistics, and many methods have been proposed for this problem; we focus on Stein’s unbiased risk estimator, or SURE (Stein, 1981; Efron, 1986), which forms an unbiased estimate of the prediction error by augmenting the observed training error with an estimate of the degrees of freedom of our estimator. Parameter tuning via SURE minimization has been advocated by many authors, in a wide variety of problem settings. In general, it is natural to ask: what is the prediction error of the SURE-tuned estimator? The most obvious estimate for this quantity is the value of the SURE criterion at its minimum. However, this is no longer itself unbiased; in fact, we would expect the minimum of SURE to be systematically biased downwards as an estimate of the prediction error of the SURE-tuned estimator. We formally describe and study this bias. This is based on work that is in progress, with Saharon Rosset.

I will continue the topic that Larry started two months ago on "Adaptive Data Analysis" and "Reuseable Holdout". Specifically, I will talk about ideas in:

- "Algorithmic Stability for Adaptive Data Analysis" by Bassily, Nissim, SMith, Steinke, Stemmer and Ullman.
- "Controlling Bias in Adaptive Data Analysis Using Information Theory" by Russo and Zou.

I will not be following the exact sequence of presentation in these papers, but rather use a top-down approach to first give a precise formulation of the problem in terms of a sequence of expectations, then provide an upper bound by explicitly working out the adversarial case, which nicely matches the results in Russo and Zou that uses mutual information. Hopefully, this new presentation will make the concept much clearer. This approach leads to several directions how one can relax the assumptions in existing TCS approaches of adaptive data analysis that often relies on uniform boundedness of the query's sensitivity.

I will present a subset of results from the following two papers:

- "Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence" by Shah, Balakrishnan, radley, Parekh, Ramchandran and Wainwright.
- "Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues" by Shah, Balakrishnan, Guntuboyina and Wainwright.

I discuss the problem of ``internal inference'': how to compare internally derived (trained) predictors to external predictors, based on the same data used for training. The methods that I will discuss for this problem include sample splitting, pre-validation and post-selectiion inference. This work is joint with Sam Gross and Jon Taylor.

Many statistical models are singular, because they are nonidentifiable or their Fisher information matrices are singular. One way to tackle this is to apply resolution of singularities from the field of algebraic geometry. I will introduce how resolution of singularities can be applied, and I will discuss some examples. This talk is based on following book: Sumio Watanabe. Algebraic Geometry and Statistical Learning Theory.

Many real-world applications require searching for sparse signals on a large search domain, looking for needles in a haystack. Motivated by unmanned aerial vehicle surveillance for gas leaks or human survivors of disasters, we study optimal search designs when the observations are limited to taking average values in physically contiguous regions. In contrast to the popular argument that in unconstrained domains, an active design may not be necessary to achieve the optimal sampling complexity (up to logarithmic factors), we find compressive sensing infeasible in our constrained problem. Therefore, we use an information theoretic approach and demonstrate its optimality in 1d domains despite its greedy nature. Simulation studies and demonstrations of our method on real satellite images are provided.

One central task in machine learning (ML) is to extract underlying patterns, structure and knowledge from data. Latent variable models (LVMs) are principled and effective tools to achieve this goal. Due to the dramatic growth of volume and complexity of big data, several new challenges have emerged and cannot be effectively addressed by existing LVMs: (1) How to capture long-tail patterns that carry crucial information when the popularity of patterns is distributed in a power-law fashion? (2) How to reduce model complexity and computational cost without compromising the modeling power of LVMs? (3) How to improve the interpretability and reduce the redundancy of discovered patterns? To addresses the three challenges, we develop a novel regularization technique for LVMs, which controls the geometry of the latent space during learning to enable the learned latent components of LVMs to be diverse, to accomplish long-tail coverage, low redundancy, and better interpretability. In this talk, I will introduce: 1) how the diversity-inducing mutual angular regularizer (MAR) is defined; 2) how to optimize the MAR which is non-convex and non-smooth; 3) a theoretical analysis of why MAR is effective; 4) the applications of MAR in representation learning and distance metric learning.

We study a variant of the classical stochastic K-armed bandit problem where observing the outcome of each arm is expensive, but cheap approximations to this outcome are available. For example, when finding the optimal control policy of a robot, its expensive behaviour can be approximated by cheap computer simulations. Similarly, when minimising cross validation error to tune hyper-parameters of machine learning algorithms, cheaper training routines involving subsets of the data or early stopping can be used to approximate the cross validation curve of the entire dataset. We formalise this task as a multi-fidelity bandit problem, where at each time step the forecaster may choose to play an arm at one of M fidelities. A play at fidelity M, i.e. the desired outcome, expends λ(M) of a resource whereas a play at fidelity m> λ(m) for all m. We develop MF-UCB, a novel upper confidence bound procedure for this setting and prove that it naturally adapts to the sequence of available approximations. For instance, in the above robot control example, MF-UCB would use the cheap computer simulations to quickly eliminate suboptimal policies, while reserving real world trials for a small set of promising candidates. We derive lower bounds for this problem and show that MF-UCB is optimal on a wide range of settings.

I will talk about my recent work on subsampled linear regression. The goal is to randomly subsample a small portion of data (design points) for regression with reduced sample complexity. Our algorithms apply to both problems of estimation of the underlying linear model β and predicting the real-valued response y of a new data point x. The derived subsampling strategies are minimax optimal under the fixed design setting, up to a small (1 + eps) relative factor. We also give interpretable subsampling probabilities for the random design setting and demonstrate explicit gaps in statistical rates between optimal and baseline (e.g., uniform) subsampling methods.

Reference papers:
1. A statistical perspective on algorithmic leveraging. JMLR'15
2. Minimax Subsampling for estimation and prediction in low-dimensional linear regression. arXiv:1601.02068
3. Convergence rates of active learning for maximum likelihood estimation. NIPS'15

We propose a novel class of dynamic nonparanormal graphical models, which allows us to model high dimensional heavy-tailed systems and the evolution of their latent network structures. Under this model we develop statistical tests for presence of edges both locally at a fixed index value and globally over a range of values. The tests are developed for a high-dimensional regime, are robust to model selection mistakes and do not require commonly assumed minimum signal strength. The testing procedures are based on a high dimensional, debiasing-free moment estimator, which uses a novel kernel smoothed Kendall's tau correlation matrix as an input statistic. The estimator consistently estimates the latent inverse Pearson correlation matrix uniformly in both index variable and kernel bandwidth. Its rate of convergence is shown to be minimax optimal. Thorough numerical simulations and an application to a neural imaging dataset support the usefulness of our method.

Reinforcement learning is one of the most prominent frameworks for sequential decision making under uncertainty with a wide range of applications. These include tasks in robotics, health care, education and advertisement. In this talk, I will first give a brief overview of the landscape of reinforcement learning problems and important open research questions. I will then focus on reinforcement learning in episodic Markov decision processes and discuss model-based algorithms using optimism under uncertainty. Finally, I will present the key insights of recent analyses which show that these methods achieve near-optimal sample complexity. The last part of the talk is based on our NIPS'15 paper available at: http://arxiv.org/abs/1510.08906 .

We proposed a doubly stochastic primal-dual coordinate optimization algorithm for regularized empirical risk minimization that can be formulated as a bilinear saddle-point problem using convex conjugate functions. Our method randomly samples a block of primal and dual coordinates to update in each iteration. The convergence of our method is established in both the solution's distance to optimality and the primal-dual objective gap. We show that the proposed method has a lower overall complexity than existing coordinate methods when the data matrix has a factorized structure or the proximal mapping on each block of coordinates is computationally expensive, e.g., involves an eigenvalue decomposition. Furthermore, we prove a theoretical lower bound on the iteration complexity of a family of primal-dual (block) coordinate methods, including our method, for bilinear saddle-point problems.
A draft of the work can be found in http://arxiv.org/abs/1508.03390.

Given a statistical estimation problem where regularization is performed according to the structure of a large, dense graph G, we consider fitting the statistical estimate using a sparsified surrogate graph \tilde{G}, which shares the vertices of G but has far fewer edges, and is thus more tractable to work with computationally. We examine three types of sparsification: spectral sparsification, which can be seen as the result of sampling edges from the graph with probabilities proportional to their effective resistances, and two simpler sparsifiers, which sample edges uniformly from the graph, either globally or locally. We provide strong theoretical and experimental results, demonstrating that sparsification before estimation gives statistically sensible solutions, with potential computational savings.

In large-scale data settings, randomized 'sketching' has become an increasingly popular tool. In the numerical linear algebra literature, randomized sketching based on either random projections or sub-sampling has been shown to achieve optimal worst-case error. In particular the sketched ordinary least-squares (OLS) solution and the CUR decomposition have been shown to achieve optimal approximation error bounds in a worst-case setting. However, until recently there has been limited work on consider the performance of the OLS estimator under a statistical model using statistical metrics. In this talk I present some recent results which address both the performance of sketching in the statistical setting, where we assume an underlying statistical model and show that many of the existing intuitions and results are quite different from the worst-case algorithmic setting.

This is based on joint work with Michael Mahoney. Reference: http://arxiv.org/abs/1505.06659.

A large number of problems in optimization, machine learning, signal processing can be effectively addressed by suitable semidefinite programming (SDP) relaxations. Unfortunately, generic SDP solvers hardly scale beyond instances with a few hundreds variables (in the underlying combinatorial problem). On the other hand, it has been observed empirically that an effective strategy amounts to introducing a (non-convex) rank constraint, and solving the resulting smooth optimization problem by ascent methods. This non-convex problem has --generically-- a large number of local maxima, and the reason for this success is therefore unclear. This paper provides rigorous support for this approach. For the problem of maximizing a linear functional over the elliptope, we prove that all local maxima are within a small gap from the SDP optimum. In several problems of interest, arbitrarily small relative error can be achieved by taking the rank constraint k to be of order one, independently of the problem size.

PS: I might also mention little bits from this paper, just to motivate the other one:
Reference: "Community detection in sparse networks via Grothendieck's inequality", Olivier Guédon and Roman Vershynin,http://arxiv.org/abs/1411.4686.

This is based on joint work with Michael Mahoney. Reference: http://arxiv.org/abs/1505.06659.

We introduce a very general method for high-dimensional classification, based on careful combination of the results of applying an arbitrary base classifier to random projections of the feature vectors into a lower-dimensional space. In one special case that we study in detail, the random projections are divided into non-overlapping blocks, and within each block we select the projection yielding the smallest estimate of the test error. Our random projection ensemble classifier then aggregates the results of applying the base classifier on the selected projections, with a data-driven voting threshold to determine the final assignment. Our theoretical results elucidate the effect on performance of increasing the number of projections. Moreover, under a boundary condition implied by the sufficient dimension reduction assumption, we show that the test excess risk of the random projection ensemble classifier can be controlled by terms that do not depend on the original data dimension. The classifier is also compared empirically with several other popular high-dimensional classifiers via an extensive simulation study, which reveals its excellent finite-sample performance.
http://arxiv.org/pdf/1506.03486v1.pdf

We look at the problem of manifold reconstruction in a semi-asymptotic framework. Under geometrical regularity constraints, we propose a computable estimator M̂ of the support M of an unknown measure from which we observe a i.i.d. n-sample. M has the same topology as M and we give a rate of convergence for the Hausdorff distance. The method is based on a tangential Delaunay complex. After having reduced the question to estimating the tangent spaces of M, the problem is handled with local PCA. A denoising technique with local PCA in a mixture model will be presented as well.

Medial axis has many applications in image analysis, shape recognition, or mathematical morphology. The reach is defined as distance from the set to its medial axis, and it plays key condition in many theorems and algorithms related to geometry reconstruction. In this talk, I will go through definition of medial axis and reach, several properties of medial axis and reach, and I will show stability result in medial axis. I will follow F. Chazal, A. Lieutier. The λ-medial axis, but I will also combine materials from other papers as well.

This will be a mix of work in the following papers:

• A statistical perspective on algorithmic leveraging ( arxiv:1306.5362)
• Constrained adaptive sensing (arxiv:1506.05889)
• A statistical perspective of sampling scores for linear regression (arxiv:1507.05870)
• Optimal subsampling approaches for large-sample linear regression (arxiv:1509.05111)

I will present the paper "A subsampled double bootstrap for massive data" by Srijan Sengupta, Stanislav Volgushev and Xiaofeng Shao. The motivation is to make bootstrap more computationally efficient for massive data with constraints on computation time, communication between distributed nodes, and storage. I will also cover related works in a unified framework, including the more classical "m out of n" bootstrap, the double bootstrap, and the more recent "bag of little bootstrap" . Although it would be a non-trivial achievement to just get the notation clear, I will also try to talk a little bit about the technical proofs if time permits.

We describe several connections between exchangeable random networks and graphical models. We show that exchangeable finite networks extendable to larger networks can be approximated by mixtures of curved exponential families. In turn, these models correspond to a distinguished class of graphical models of marginal independence for binary data. We further consider extendability to infinite exchangeable networks. We obtain a simple derivation of de-Finetti theorem for exchangeable arrays, and we link it to the theory of graphons. Unlike previous results, our analysis yields a canonical parametric model for finite exchangeable arrays. Using this characterization, we discuss the challenges and intrinsic difficulties of fitting exchangeable network models.

Joint work with Steffen Lauritzen and Kayvan Sadeghi.

A previous presentation can be found here .

Reliable estimation of the covariance matrix is notoriously difficult in high dimensions. Numerous methods assume that the population covariance (or inverse covariance) matrix is sparse while making no particular structural assumptions on the desired sparsity pattern. A highly-related, yet complementary, literature studies the setting in which the measured variables have a known ordering, in which case a banded (or near-banded) population matrix is assumed. This work focuses on the broad middle ground that lies between the former approach of complete neutrality to the sparsity pattern and the latter highly restrictive assumption of having a known ordering. We develop a class of convex regularizers that is in the spirit of banding and yet attains sparsity structures that can be customized to a wide variety of applications.

Overfitting is the bane of data analysts, even when data are plentiful. Formal approaches to understanding this problem focus on statistical inference and generalization of individual analysis procedures. Yet the practice of data analysis is an inherently interactive and adaptive process: new analyses and hypotheses are proposed after seeing the results of previous ones, parameters are tuned on the basis of obtained results, and datasets are shared and reused. An investigation of this gap has recently been initiated by the authors in (Dwork et al., 2014), where we focused on the problem of estimating expectations of adaptively chosen functions.

Density ridges are curve-like structures characterizing high density regions. In cosmology, density ridges are excellent models for tracing structures of the Universe. We study asymptotic theory for density ridges and propose a procedure for constructing confidence sets using the bootstrap. Moreover, we generalize the integrated distance to assess the risk for estimating ridges, and choose smooth bandwidth via minimizing the risk.

References:
Yen-Chi Chen, Christopher Genovese, Larry Wasserman. "Asymptotic theory for density ridges", 2014
Yen-Chi Chen, Christopher Genovese, Shirley Ho, Larry Wasserman. "Optimal Ridge Detection using Coverage Risk", 2015

Learning covariance matrices from high-dimensional data is an important problem that has received a lot of attention recently. In many applications of interest, it could be expensive or physically infeasible to obtain samples from all the underlying variates. Fortunately, the target covariance matrix is often structured. As a means of leveraging this structure, we initiated the study of a framework for recovering a covariance matrix from compressed samples which we call covariance sketching. In this presentation, I will introduce this framework and demonstrate how one can consistently estimate a sparse covariance matrix from compressed samples. Furthermore, I will show that the estimator achieves near optimal compression rates and is computationally efficient. This is based on work I did during my PhD with Pari Shah, Badri Bhaskar, and Rob Nowak. If you have time, you can skim through the following: - (journal version) - (slightly older arxiv version) I will next discuss some interesting open problems that I am currently thinking about with Pari Shah and Aarti Singh. In particular, I will discuss some main roadblocks to understanding the precise statistical performance and the tradeoffs between compression ratio and sample complexity of such algorithms.

Multiple hypotheses testing is a core problem in statistical inference and arises in almost every scientific field. Given a sequence of null hypotheses (H1,...,Hn), Benjamini and Hochberg \cite{benjamini1995controlling} introduced the false discovery rate (FDR) criterion, which is the expected proportion of false positives among rejected null hypotheses, and proposed a testing procedure that controls FDR below a pre-assigned significance level. They also proposed a different criterion, called mFDR, which does not control a property of the realized set of tests; rather it controls the ratio of expected number of false discoveries to the expected number of discoveries. In this paper, we propose two procedures for multiple hypotheses testing that we will call "LOND" and "LORD". These procedures control FDR and mFDR in an \emph{online manner}. Concretely, we consider an ordered --possibly infinite-- sequence of null hypotheses (H1,H2,H3,...) where, at each step i, the statistician must decide whether to reject hypothesis Hi having access only to the previous decisions. To the best of our knowledge, our work is the first that controls FDR in this setting. This model was introduced by Foster and Stine \cite{alpha-investing} whose alpha-investing rule only controls mFDR in online manner. In order to compare different procedures, we develop lower bounds on the total discovery rate under the mixture model and prove that both LOND and LORD have nearly linear number of discoveries. We further propose adjustment to LOND to address arbitrary correlation among the p-values. Finally, we evaluate the performance of our procedures on both synthetic and real data comparing them with alpha-investing rule, Benjamin-Hochberg method and a Bonferroni procedure.

This is work in progress. Most of non-parametric conditional independence tests, if not all of them, require some assumptions on random variables being tested (e.g. smooth density or being able to estimate density). This is in contrast to non-parametric two sample tests or independence tests, which are consistent regardless of underlying distributions. Is conditional independence testing more difficult then those two other problems or have we just not found the right test yet? I'll show that there is no U-statistic based test for conditional independence and then I'll discuss a following general conjecture: If a test for conditional independence controls type one error on level alpha, then its power is less or equal to alpha. If time permits we will discuss a specific, U-statistic based test, which requires weak assumptions on random variables (by weak I mean: relaxing them further might enlarge space of distribution so much that it's impossible to conduct a U-statistics based test).

Kernel methods represent one of the most powerful tools in machine learning to tackle problems expressed in terms of function values and derivatives. While these methods show good versatility, they are computationally intensive and have poor scalability to large data as they require operations on Gram matrices. In order to mitigate this serious computational limitation, recently randomized methods have been proposed in the literature, which allow the application of fast linear algorithms. Random Fourier features (RFF) are among the most popular and widely applied constructions: they provide an easily computable, low-dimensional feature representation for shift-invariant kernels. Despite the popularity of RFFs, very little is understood theoretically about their approximation quality. In this talk, I am going to present the main ideas and results of a detailed finite-sample theoretical analysis about the approximation quality of RFFs by (i) establishing optimal (in terms of the RFF dimension, and growing set size) performance guarantees in uniform norm, and (ii) providing guarantees in L^r (1 ≤ r < ∞) norms. I will also propose an RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality. [Joint work with Bharath K. Sriperumbudur; equal contribution]

I will introduce differential privacy in the machine learning setting with an illustrative example. Convince you why it is useful. I mostly talk about the following two papers:
``Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo''
``Fast Differentially Private Matrix Factorization''

Though if time permits, I will also mention some theoretical understanding from ``Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of the ERM principle'' and draw connections to the recent buzz of ``Reuseable Holdout'' by Dwork et. al.

Stochastic blockmodels and graphons are models for network data that are studied in both statistics and mathematics. A stochastic blockmodel is like a mixture model for networks, while a graphon is a fully nonparametric model. In this talk, I'll show a connection between stochastic blockmodels and K-means clustering. Using this connection, I'll apply existing bounds for K-means clustering to show an oracle inequality, stating that the excess clustering risk for stochastic blockmodeling decays as O(1/sqrt(n)) if the data is generated from a graphon.

Modal regression estimates the local modes of the distribution of Y given X = x, instead of the mean, as in the usual regression sense, and can hence reveal important structure missed by usual regression methods. We study a simple nonparametric method for modal regression, based on a kernel density estimate (KDE) of the joint distribution of Y and X. We derive asymptotic error bounds for this method, and propose techniques for constructing confidence sets and prediction sets. The latter is used to select the smoothing bandwidth of the underlying KDE. The idea behind modal regression is connected to many others, such as mixture regression and density ridge estimation, and we discuss these ties as well.
Link: http://arxiv.org/abs/1412.1716

We thank Microsoft Research for their gracious support

The discussion will be based on the following paper:
http://arxiv.org/pdf/0912.3995v4.pdf

"I haven't decided the order or how much detail yet, but the following projects are at varying stages of completion (some will end up in my thesis).
(1) QQ Plots and Distribution-Free Wasserstein TST (with Nicolas Garcia, Marco Cuturi - evolved from last sem's SMLRG talk and a Japan trip)
(2) Martingale LIL and Sequential TST (with Akshay Balasubramani - evolved from staying with him for a week and having enough beer)
(3) Adaptivity and Computation-Statistics Tradeoffs in TST (with Sashank Reddi, Larry Wasserman, Aarti Singh, Barnabas Poczos - evolved from random walks through idea/proof/experiment space)
(4) TST vs Classification, Independence Testing vs Regression (with Larry Wasserman, Aarti Singh - evolved from chatting with Leila Wehbe about neuroscience problems)
(5) Distributed and Private TST (with Yuxiang Wang, Aarti Singh - evolved from thinking about privacy concerns with clinical data held at different hospitals)
(6) Fast TST with Smoothed Characteristic Functions (with Kacper Chwialkowski, Arthur Gretton, Dino Sejdinovic)
I guess I'll mostly talk about the second one so I can go into details and spare time for ideas - it also has the most scope for extensions at the moment, which I would be extremely interested in pursuing with some of you (since most of these projects just started off as conversations with people smarter than me). "

Forward stagewise regression follows a very simple strategy for constructing a sequence of sparse regression estimates: it starts with all coefficients equal to zero, and iteratively updates the coefficient (by a small amount ε) of the variable that achieves the maximal absolute inner product with the current residual. This procedure has an interesting connection to the lasso: under some conditions, it can be shown that the sequence of forward stagewise estimates exactly coincides with the lasso path, as the step size ε goes to zero. Furthermore, essentially the same equivalence holds outside of least squares regression, with the minimization of a differentiable convex loss function subject to an l1 norm constraint (the stagewise algorithm now updates the coefficient corresponding to the maximal absolute component of the gradient).
Even when they do not match their l1-constrained analogues, stagewise estimates provide a useful approximation, and are computationally appealing. Their success in sparse modeling motivates the question: can a simple, effective strategy like forward stagewise be applied more broadly in other regularization settings, beyond the l1 norm and sparsity? The current talk shares an attempt to do just this. I present a general framework for stagewise estimation, which yields fast algorithms for problems such as group-structured learning, matrix completion, image denoising, and more.
This talk will be based on: http://www.stat.cmu.edu/~ryantibs/papers/stagewise.pdf

In topological data analysis, stability theorem plays essential role for analyzing statistical properties of persistent homology. I will present the statement of stability theorem, brief idea of the proof, and applications of stability theorem.

Following the talks that Aaditya gave during the fall and spring, in this talk I will revisit the two sample test problem. In fact, my goal is to present a two sample test with the following properties: - It is transportation based in the sense that the quantity to be computed to construct the test is the Wasserstein distance between two measures. -It is distribution free, in the sense that under the null hypothesis, the asymptotic distribution of the quantity used to construct the test does not depend on the distribution the random points were drawn from. I will present results and give a sketch of their proofs. This is a joint work with Aaditya Ramdas and Marco Cuturi.

A population clustering can be understood as an essential partition of the support of a probability distribution. Different notions of cluster lead to different concepts of ideal population clusters, but no matter what approach is taken, eventually the researcher needs to evaluate the performance of a clustering methodology by measuring the distance between a data-driven clustering and the ideal population goal. In this talk, two new distances are proposed for this aim, by extending well-known distances between sets to distances between clusterings.
http://arxiv.org/abs/1408.1381

We propose a general framework for regularization based on group-induced majorization. In this framework, a group is defined to act on the parameter space and an orbit is fixed; to control complexity, the model parameters are confined to the convex hull of this orbit (the orbitope). We recover several well-known regularizers as particular cases, and reveal a connection between the hyperoctahedral group and the recently proposed sorted l1-norm. We derive the properties a group must satisfy for being amenable to optimization with conditional and projected gradient algorithms. Finally, we suggest a continuation strategy for orbit exploration, presenting simulation results for the symmetric and hyperoctahedral groups.

Topological Data Analysis (TDA) is an emerging area of research at the intersection of algebraic topology and computational geometry, aimed at describing, summarizing and analyzing possibly high-dimensional data using low-dimensional algebraic representations. Recent advances in computational topology have made it possible to actually compute topological invariants from data. These novel types of data summaries have been used successfully in a variety of applied problems, and their potential for high-dimensional statistical inference appears to be significant. Nonetheless, the statistical properties of the data summaries produced in TDA and, more generally, of the usually heuristic data-analytic methods they are part of, have remained largely unexplored by statisticians. Our analysis involves the tools of persistent homology, the main method of TDA for measuring the topological features of shapes and functions at different resolutions. A major part of our research also focuses on cluster trees, which provide a simple yet meaningful abstraction of the input domain of a function by means of the topological changes in its level sets. The main goal of this thesis is to contribute to the development of a statistical theory for TDA and to propose new and statistically principled methodologies to improve and extend the applicability of the algorithms of TDA. In particular, we (1) construct confidence sets to separate topological signal from topological noise; (2) explore new methods for topological dimensional reduction; (3) determine how our methods contribute to reduce computational costs, which currently represent an obstacle in TDA.

I will cover some of my recent progress on the structured normal means problem. In this problem, there is a finite collection of vectors available to the learner, nature chooses one of them and shows the learner a gaussian centered at the chosen vector. The goal of the learner is to identify which vector was chosen with low minimax probability of error. In the first part of the talk, I will focus on the issue of minimax optimality, where I will show nearly-matching upper and lower bounds on the minimax risk, generically for any structured normal means problem. I will also mention an algorithm to precisely characterize the minimax risk and identify a minimax estimator. In the second part of the talk, I will discuss issues of passive and adaptive sampling in the structured normal means problem. I will present a number of well-studied examples throughout.

Consider the problem of nonparametric two-sample mean testing, where we have access to i.i.d. samples from two multivariate distributions and wish to test whether they have the same mean. We propose a sequential test for this problem suitable for data-rich, memory-constrained situations. It is novel in several ways: it takes linear time and constant space to compute on the fly, and has robust high-dimensional statistical performance, including basically the same power guarantee (for a given false positive rate) as a batch/offline version of the test with the same computational constraints. Most notably, it has a distinct computational advantage over the batch test, because it accesses only as many samples as are required -- its stopping time is adaptive to the unknown difficulty of the problem! We analyze the test and prove these properties in a rigorously finite-sample fashion, using a novel uniform empirical Bernstein version of the law of the iterated logarithm (LIL), which may be of independent interest and allows analysis of sequential tests in a general framework. We demonstrate how to extend our ideas to nonparametric homogeneity and independence testing, and make a case for their even broader applicability.
http://arxiv.org/pdf/1506.03486v1.pdf