Skip to main content

A Regression Approach to Learning-Augmented Online Algorithms

Publication ,  Conference
Anand, K; Ge, R; Kumar, A; Panigrahi, D
Published in: Advances in Neural Information Processing Systems
January 1, 2021

The emerging field of learning-augmented online algorithms uses ML techniques to predict future input parameters and thereby improve the performance of online algorithms. Since these parameters are, in general, real-valued functions, a natural approach is to use regression techniques to make these predictions. We introduce this approach in this paper, and explore it in the context of a general online search framework that captures classic problems like (generalized) ski rental, bin packing, minimum makespan scheduling, etc. We show nearly tight bounds on the sample complexity of this regression problem, and extend our results to the agnostic setting. From a technical standpoint, we show that the key is to incorporate online optimization benchmarks in the design of the loss function for the regression problem, thereby diverging from the use of off-the-shelf regression tools with standard bounds on statistical error.

Duke Scholars

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2021

Volume

36

Start / End Page

30504 / 30517

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Anand, K., Ge, R., Kumar, A., & Panigrahi, D. (2021). A Regression Approach to Learning-Augmented Online Algorithms. In Advances in Neural Information Processing Systems (Vol. 36, pp. 30504–30517).
Anand, K., R. Ge, A. Kumar, and D. Panigrahi. “A Regression Approach to Learning-Augmented Online Algorithms.” In Advances in Neural Information Processing Systems, 36:30504–17, 2021.
Anand K, Ge R, Kumar A, Panigrahi D. A Regression Approach to Learning-Augmented Online Algorithms. In: Advances in Neural Information Processing Systems. 2021. p. 30504–17.
Anand, K., et al. “A Regression Approach to Learning-Augmented Online Algorithms.” Advances in Neural Information Processing Systems, vol. 36, 2021, pp. 30504–17.
Anand K, Ge R, Kumar A, Panigrahi D. A Regression Approach to Learning-Augmented Online Algorithms. Advances in Neural Information Processing Systems. 2021. p. 30504–30517.

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2021

Volume

36

Start / End Page

30504 / 30517

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology