In the online false discovery rate (FDR) problem, one observes apossibly infinite sequence of $p$-values $P_1,P_2,\dots$, each testinga different null hypothesis, and an algorithm must pick a sequence ofrejection thresholds $\alpha_1,\alpha_2,\dots$ in an online fashion,effectively rejecting the $k$-th null hypothesis whenever $P_k \leq\alpha_k$. Importantly, $\alpha_k$ must be a function of the past, andcannot depend on $P_k$ or any of the later unseen $p$-values, and mustbe chosen to guarantee that for any time $t$, the FDR up to time $t$is less than some pre-determined quantity $\alpha \in (0,1)$. In thiswork, we present a powerful new framework for online FDR control thatwe refer to as ``SAFFRON''. Like older alpha-investing algorithms,SAFFRON starts off with an error budget (called alpha-wealth) that itintelligently allocates to different tests over time, earning backsome alpha-wealth whenever it makes a new discovery. However, unlikeolder methods, SAFFRON's threshold sequence is based on a novelestimate of the alpha fraction that it allocates to true nullhypotheses. In the offline setting, algorithms that employ an estimateof the proportion of true nulls are called ``adaptive'', henceSAFFRON can be seen as an online analogue of the offlineStorey-BH adaptive procedure. Just as Storey-BH is typically morepowerful than the Benjamini-Hochberg (BH) procedure underindependence, we demonstrate that SAFFRON is also more powerful thanits non-adaptive counterparts such as LORD.

Open category detection is the problem of detecting "alien" test instances that belong to categories or classes that were not present in the training data. In many applications, reliably detecting such aliens is central to ensuring the safety and accuracy of test set predictions. Unfortunately, there are no algorithms that provide theoretical guarantees on their ability to detect aliens under general assumptions. Further, while there are algorithms for open category detection, there are few empirical results that directly report alien detection rates. Thus, there are significant theoretical and empirical gaps in our understanding of open category detection. In this paper, we take a step toward addressing this gap by studying a simple, but practically-relevant variant of open category detection. In our setting, we are provided with a "clean" training set that contains only the target categories of interest and an unlabeled "contaminated'' training set that contains a fraction alpha of alien examples. Under the assumption that we know an upper bound on alpha we develop an algorithm with PAC-style guarantees on the alien detection rate, while aiming to minimize false alarms. Empirical results on synthetic and standard benchmark datasets demonstrate the regimes in which the algorithm can be effective and provide a baseline for further advancements.

For data-driven decision-making, one promising approach, called predictive optimization, is to solve maximization problems i n which the objective function to be maximized is estimated from data. Predictive optimization, however, suffers from the problem of a calculated optimal solution’s being evaluated too optimistically, i.e., the value of the objective function is overestimated. This paper investigates such optimistic bias and presents two methods for correcting it. The first, which is analogous to cross-validation, successfully corrects the optimistic bias but results in underestimation of the true value. Our second method employs resampling techniques to avoid both overestimation and underestimation. We show that the second method, referred to as the parameter perturbation method, achieves asymptotically unbiased estimation. Empirical results for both artificial and real-world datasets demonstrate that our proposed approach successfully corrects the optimistic bias.

Recent work has combined Stein's method with reproducing kernel Hilbert space theory to develop nonparametric goodness-of-fit tests for un-normalized probability distributions. However, the currently available tests apply exclusively to distributions with smooth density functions. In this work, we introduce a kernelized Stein discrepancy measure for discrete spaces, and develop a nonparametric goodness-of-fit test for discrete distributions with intractable normalization constants. Furthermore, we propose a general characterization of Stein operators that encompasses both discrete and continuous distributions, providing a recipe for constructing new Stein operators. We apply the proposed goodness-of-fit test to three statistical models involving discrete distributions, and our experiments show that the proposed test typically outperforms a two-sample test based on the maximum mean discrepancy.

In this paper, we make an important step towards the black-box machine teaching by considering the cross-space machine teaching, where the teacher and the learner use different feature representations and the teacher can not fully observe the learner's model. In such scenario, we study how the teacher is still able to teach the learner to achieve faster convergence rate than the traditional passive learning. We propose an active teacher model that can actively query the learner (i.e., make the learner take exams) for estimating the learner's status and provably guide the learner to achieve faster convergence. The sample complexities for both teaching and query are provided. In the experiments, we compare the proposed active teacher with the omniscient teacher and verify the effectiveness of the active teacher model.