More Like this

1. Conformal Frequency Estimation with Sketched Data

   Sesia, Matteo; Favaro, Stefano (July 2022, Advances in neural information processing systems)

   A flexible conformal inference method is developed to construct confidence intervals for the frequencies of queried objects in very large data sets, based on a much smaller sketch of those data. The approach is data-adaptive and requires no knowledge of the data distribution or of the details of the sketching algorithm; instead, it constructs provably valid frequentist confidence intervals under the sole assumption of data exchangeability. Although our solution is broadly applicable, this paper focuses on applications involving the count-min sketch algorithm and a non-linear variation thereof. The performance is compared to that of frequentist and Bayesian alternatives through simulations and experiments with data sets of SARS-CoV-2 DNA sequences and classic English literature. 

   more » « less
2. Putting the “Learning” into Learning-Augmented Algorithms for Frequency Estimation

   Du, Elbert; Wang, Franklyn; Mitzenmacher, Michael (January 2021, International Conference on Machine Learning)

   null (Ed.)

   In learning-augmented algorithms, algorithms are enhanced using information from a machine learning algorithm. In turn, this suggests that we should tailor our machine-learning approach for the target algorithm. We here consider this synergy in the context of the learned count-min sketch from (Hsu et al., 2019). Learning here is used to predict heavy hitters from a data stream, which are counted explicitly outside the sketch. We show that an approximately sufficient statistic for the performance of the underlying count-min sketch is given by the coverage of the predictor, or the normalized L1 norm of keys that are filtered by the predictor to be explicitly counted. We show that machine learning models which are trained to optimize for coverage lead to large improvements in performance over prior approaches according to the average absolute frequency error. Our source code can be found at https://github.com/franklynwang/putting-the-learning-in-LAA. 

   more » « less
3. Interactive Graph Stream Analytics in Arkouda

   https://doi.org/10.3390/a14080221  

   Du, Zhihui; Rodriguez, Oliver Alvarado; Patchett, Joseph; Bader, David A. (August 2021, Algorithms)

   Data from emerging applications, such as cybersecurity and social networking, can be abstracted as graphs whose edges are updated sequentially in the form of a stream. The challenging problem of interactive graph stream analytics is the quick response of the queries on terabyte and beyond graph stream data from end users. In this paper, a succinct and efficient double index data structure is designed to build the sketch of a graph stream to meet general queries. A single pass stream model, which includes general sketch building, distributed sketch based analysis algorithms and regression based approximation solution generation, is developed, and a typical graph algorithm—triangle counting—is implemented to evaluate the proposed method. Experimental results on power law and normal distribution graph streams show that our method can generate accurate results (mean relative error less than 4%) with a high performance. All our methods and code have been implemented in an open source framework, Arkouda, and are available from our GitHub repository, Bader-Research. This work provides the large and rapidly growing Python community with a powerful way to handle terabyte and beyond graph stream data using their laptops. 

   more » « less
4. Adaptive conformal classification with noisy labels

   https://doi.org/10.1093/jrsssb/qkae114  

   Sesia, Matteo; Wang, Y_X_Rachel; Tong, Xin (December 2024, Journal of the Royal Statistical Society Series B: Statistical Methodology)

   Abstract This article develops a conformal prediction method for classification tasks that can adapt to random label contamination in the calibration sample, often leading to more informative prediction sets with stronger coverage guarantees compared to existing approaches. This is obtained through a precise characterization of the coverage inflation (or deflation) suffered by standard conformal inferences in the presence of label contamination, which is then made actionable through a new calibration algorithm. Our solution can leverage different modelling assumptions about the contamination process, while requiring no knowledge of the underlying data distribution or of the inner workings of the classification model. The empirical performance of the proposed method is demonstrated through simulations and an application to object classification with the CIFAR-10H image data set. 

   more » « less
5. Bayesian Optimization with Conformal Prediction Sets

   Stanton, S.; Maddox, W.; Wilson, A.G. (January 2023, Artificial Intelligence and Statistics)

   Bayesian optimization is a coherent, ubiquitous approach to decision-making under uncertainty, with applications including multi-arm bandits, active learning, and black-box optimization. Bayesian optimization selects decisions (i.e. objective function queries) with maximal expected utility with respect to the posterior distribution of a Bayesian model, which quantifies reducible, epistemic uncertainty about query outcomes. In practice, subjectively implausible outcomes can occur regularly for two reasons: 1) model misspecification and 2) covariate shift. Conformal prediction is an uncertainty quantification method with coverage guarantees even for misspecified models and a simple mechanism to correct for covariate shift. We propose conformal Bayesian optimization, which directs queries towards regions of search space where the model predictions have guaranteed validity, and investigate its behavior on a suite of black-box optimization tasks and tabular ranking tasks. In many cases we find that query coverage can be significantly improved without harming sample-efficiency. 

   more » « less