Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Online Metric Algorithms with Untrusted Predictions

Online Metric Algorithms with Untrusted Predictions Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only benefit from good predictions, but should also achieve a decent performance when the predictions are inadequate. In this article, we propose a prediction setup for arbitrary metrical task systems (MTS) (e.g., caching, k-server, and convex body chasing) and online matching on the line. We utilize results from the theory of online algorithms to show how to make the setup robust. Specifically, for caching, we present an algorithm whose performance, as a function of the prediction error, is exponentially better than what is achievable for general MTS. Finally, we present an empirical evaluation of our methods on real-world datasets, which suggests practicality. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Online Metric Algorithms with Untrusted Predictions

Download PDF
34 pages

Loading next page...
 
/lp/association-for-computing-machinery/online-metric-algorithms-with-untrusted-predictions-92PJ09VnLW

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3582689
Publisher site
See Article on Publisher Site

Abstract

Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only benefit from good predictions, but should also achieve a decent performance when the predictions are inadequate. In this article, we propose a prediction setup for arbitrary metrical task systems (MTS) (e.g., caching, k-server, and convex body chasing) and online matching on the line. We utilize results from the theory of online algorithms to show how to make the setup robust. Specifically, for caching, we present an algorithm whose performance, as a function of the prediction error, is exponentially better than what is achievable for general MTS. Finally, we present an empirical evaluation of our methods on real-world datasets, which suggests practicality.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Apr 15, 2023

Keywords: Metrical task systems

References

  • Customizing ML predictions for online algorithms
    [,
  • The dynamics of repeat consumption
    [,
  • Online computation with untrusted advice
    [,
  • Secretary and online matching problems with machine learned advice
    [,
  • A primal-dual randomized algorithm for weighted paging
    [,
  • Learning-augmented weighted paging
    [,
  • A study of replacement algorithms for a virtual-storage computer
    [,
  • Competitively pricing parking in a tree
    [,
  • A poly-log competitive posted-price algorithm for online metrical matching on a spider
    [,
  • On-line learning and the metrical task system problem
    [,
  • Online Computation and Competitive Analysis
    [,
  • An optimal on-line algorithm for metrical task system
    [,
  • Online algorithms with advice: A survey
    [,
  • Metrical task systems on trees via mirror descent and unfair gluing
    [,
  • Parametrized metrical task systems
    [,
  • Robust learning-augmented caching: An experimental study
    [,
  • Friendship and mobility: User movement in location-based social networks
    [,
  • Metrical task systems, the server problem and the work function algorithm
    [,
  • Approximate methods for sequential decision making using expert advice
    [,
  • Citi Bike Trip Histories
    [,
  • The online k-taxi problem
    [,
  • Pure entropic regularization for metrical task systems
    [,
  • Competitive ratio vs regret minimization: Achieving the best of both worlds
    [,
  • Stochastic k-server: How should Uber work? In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP’17), Vol
    [,
  • Online computation with advice
    [,
  • Competitive algorithms for layered graph traversal
    [,
  • Competitive paging algorithms
    [,
  • Competitive k-server algorithms
    [,
  • A decision-theoretic generalization of on-line learning and an application to boosting
    [,
  • Online matching on a line
    [,
  • Online algorithms for rent-or-buy with expert advice
    [,
  • Online strategies for dynamic power management in systems with multiple power-saving states
    [,
  • Back to the future: Leveraging Belady’s algorithm for improved cache replacement
    [,
  • Online algorithms for weighted paging with predictions
    [,
  • Online weighted matching
    [,
  • Lower bounds for randomized k-server and motion-planning algorithms
    [,
  • Learning to run heuristics in tree search
    [,
  • On-line algorithms for weighted bipartite matching and stable marriages
    [,
  • The case for learned index structures
    [,
  • Online scheduling via learned weights
    [,
  • Lower bounds for MTS
    [,
  • Dynamic right-sizing for power-proportional data centers
    [,
  • The weighted majority algorithm
    [,
  • An imitation learning approach for cache replacement
    [,
  • Competitive caching with machine learned advice
    [,
  • Online optimization with uncertain information
    [,
  • Competitive algorithms for server problems
    [,
  • Revenue optimization with approximate bid predictions
    [,
  • Scheduling with predictions and the price of misprediction
    [,
  • Improving online algorithms via ML predictions
    [,
  • Optimal analysis of an online algorithm for the bipartite matching problem on a line
    [,
  • Near-optimal bounds for online caching with machine learned advice
    [,
  • Applying deep learning to the cache replacement problem
    [,
  • Amortized efficiency of list update and paging rules
    [,
  • Better and simpler learning-augmented online caching
    [,
  • Better and Simpler Learning-Augmented Online Caching
    Wei, Alexander