Online List Labeling with Predictions

• URL: http://arxiv.org/abs/2305.10536v2
• Date: Tue, 20 Jun 2023 13:45:49 GMT
• Title: Online List Labeling with Predictions
• Abstract summary: We show that predictions can be leveraged in the fundamental online list labeling problem. In the problem, n items arrive over time and must be stored in sorted order in an array of size Theta(n) We design a new list labeling data structure and bound its performance in two models.
• Score: 13.126494821223755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A growing line of work shows how learned predictions can be used to break through worst-case barriers to improve the running time of an algorithm. However, incorporating predictions into data structures with strong theoretical guarantees remains underdeveloped. This paper takes a step in this direction by showing that predictions can be leveraged in the fundamental online list labeling problem. In the problem, n items arrive over time and must be stored in sorted order in an array of size Theta(n). The array slot of an element is its label and the goal is to maintain sorted order while minimizing the total number of elements moved (i.e., relabeled). We design a new list labeling data structure and bound its performance in two models. In the worst-case learning-augmented model, we give guarantees in terms of the error in the predictions. Our data structure provides strong guarantees: it is optimal for any prediction error and guarantees the best-known worst-case bound even when the predictions are entirely erroneous. We also consider a stochastic error model and bound the performance in terms of the expectation and variance of the error. Finally, the theoretical results are demonstrated empirically. In particular, we show that our data structure has strong performance on real temporal data sets where predictions are constructed from elements that arrived in the past, as is typically done in a practical use case.

Related papers

• Conformal Reliability: A New Evaluation Metric for Conditional Generation [62.761166941396844]
  Conditional generative models have recently remarkable success in various applications.<n>We propose a novel evaluation metric called reliability based on prediction set at a pre-specified confidence level.<n>We introduce Conformal ReLiability (CReL), a framework that can (i) construct a prediction set and (ii) accurately optimize the reliability score within the constructed prediction set.
  arXiv  Detail & Related papers  (2026-05-29T03:52:44Z)
• Incremental Strongly Connected Components with Predictions [3.761866694781818]
  We use this framework to design a learned data structure for the incremental strongly connected components problem.<n>Our algorithm receives a possibly erroneous prediction of the edge sequence and uses it to precompute partial solutions.<n>We show that our algorithm achieves nearly optimal bounds with good predictions and its performance smoothly degrades with the prediction error.
  arXiv  Detail & Related papers  (2026-04-28T18:56:28Z)
• Stochastic Online Conformal Prediction with Semi-Bandit Feedback [29.334511328067777]
  We consider the online learning setting, where examples arrive over time, and the goal is to construct prediction sets dynamically. We propose a novel conformal prediction algorithm targeted at this setting, and prove that it obtains sublinear regret compared to the optimal conformal predictor.
  arXiv  Detail & Related papers  (2024-05-22T00:42:49Z)
• PAC Prediction Sets Under Label Shift [52.30074177997787]
  Prediction sets capture uncertainty by predicting sets of labels rather than individual labels. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting. We evaluate our approach on five datasets.
  arXiv  Detail & Related papers  (2023-10-19T17:57:57Z)
• Cross-Prediction-Powered Inference [15.745692520785074]
  Cross-prediction is a method for valid inference powered by machine learning. We show that cross-prediction is consistently more powerful than an adaptation of prediction-powered inference.
  arXiv  Detail & Related papers  (2023-09-28T17:01:58Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  We propose a generalization of conformal prediction to multiple learnable parameters. We show that it achieves approximate valid population coverage and near-optimal efficiency within class. Experiments show that our algorithm is able to learn valid prediction sets and improve the efficiency significantly.
  arXiv  Detail & Related papers  (2022-02-22T18:37:23Z)
• Conformal prediction for the design problem [72.14982816083297]
  In many real-world deployments of machine learning, we use a prediction algorithm to choose what data to test next. In such settings, there is a distinct type of distribution shift between the training and test data. We introduce a method to quantify predictive uncertainty in such settings.
  arXiv  Detail & Related papers  (2022-02-08T02:59:12Z)
• Generalized Adversarial Distances to Efficiently Discover Classifier Errors [0.0]
  High-confidence errors are rare events for which the model is highly confident in its prediction, but is wrong. We propose a generalization to the Adversarial Distance search that leverages concepts from adversarial machine learning. Experimental results show that the generalized method finds errors at rates greater than expected given the confidence of the sampled predictions.
  arXiv  Detail & Related papers  (2021-02-25T13:31:21Z)
• Distribution-Free, Risk-Controlling Prediction Sets [112.9186453405701]
  We show how to generate set-valued predictions from a black-box predictor that control the expected loss on future test points at a user-specified level. Our approach provides explicit finite-sample guarantees for any dataset by using a holdout set to calibrate the size of the prediction sets.
  arXiv  Detail & Related papers  (2021-01-07T18:59:33Z)
• Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing [12.961453245099044]
  We propose a new model for augmenting algorithms with predictions by requiring that they are formally learnable and instance robust. We design online algorithms with predictions for a network flow allocation problem and restricted assignment makespan minimization.
  arXiv  Detail & Related papers  (2020-11-23T21:38:57Z)
• Learning Output Embeddings in Structured Prediction [73.99064151691597]
  A powerful and flexible approach to structured prediction consists in embedding the structured objects to be predicted into a feature space of possibly infinite dimension. A prediction in the original space is computed by solving a pre-image problem. In this work, we propose to jointly learn a finite approximation of the output embedding and the regression function into the new feature space.
  arXiv  Detail & Related papers  (2020-07-29T09:32:53Z)
• Ambiguity in Sequential Data: Predicting Uncertain Futures with Recurrent Models [110.82452096672182]
  We propose an extension of the Multiple Hypothesis Prediction (MHP) model to handle ambiguous predictions with sequential data. We also introduce a novel metric for ambiguous problems, which is better suited to account for uncertainties.
  arXiv  Detail & Related papers  (2020-03-10T09:15:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.