Smoothed Online Combinatorial Optimization Using Imperfect Predictions

• URL: http://arxiv.org/abs/2204.10979v1
• Date: Sat, 23 Apr 2022 02:30:39 GMT
• Title: Smoothed Online Combinatorial Optimization Using Imperfect Predictions
• Authors: Kai Wang, Zhao Song, Georgios Theocharous, Sridhar Mahadevan
• Abstract summary: We study smoothed online optimization problems when an imperfect predictive model is available. We show that using predictions to plan for a finite time horizon leads to regret dependent on the total predictive uncertainty and an additional switching cost. Our algorithm shows a significant improvement in cumulative regret compared to other baselines in synthetic online distributed streaming problems.
• Score: 27.201074566335222
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Smoothed online combinatorial optimization considers a learner who repeatedly chooses a combinatorial decision to minimize an unknown changing cost function with a penalty on switching decisions in consecutive rounds. We study smoothed online combinatorial optimization problems when an imperfect predictive model is available, where the model can forecast the future cost functions with uncertainty. We show that using predictions to plan for a finite time horizon leads to regret dependent on the total predictive uncertainty and an additional switching cost. This observation suggests choosing a suitable planning window to balance between uncertainty and switching cost, which leads to an online algorithm with guarantees on the upper and lower bounds of the cumulative regret. Lastly, we provide an iterative algorithm to approximately solve the planning problem in real-time. Empirically, our algorithm shows a significant improvement in cumulative regret compared to other baselines in synthetic online distributed streaming problems.

Related papers

• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives. It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
  arXiv  Detail & Related papers  (2024-02-12T16:33:35Z)
• Online Joint Assortment-Inventory Optimization under MNL Choices [14.530542487845732]
  We study an online joint assortment-inventory optimization problem, in which we assume that the choice behavior of each customer follows the Multinomial Logit (MNL) choice model. We propose a novel algorithm that can effectively balance the exploration and exploitation in the online decision-making of assortment and inventory.
  arXiv  Detail & Related papers  (2023-04-04T09:25:34Z)
• Improved Online Conformal Prediction via Strongly Adaptive Online Learning [86.4346936885507]
  We develop new online conformal prediction methods that minimize the strongly adaptive regret. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks.
  arXiv  Detail & Related papers  (2023-02-15T18:59:30Z)
• A Note on Task-Aware Loss via Reweighing Prediction Loss by Decision-Regret [11.57423546614283]
  We propose a decision-aware version of predict-then-optimize. We reweigh the prediction error by the decision regret incurred by an (unweighted) pilot estimator of costs. We show that this approach can lead to improvements over a "predict-then-optimize" framework.
  arXiv  Detail & Related papers  (2022-11-09T18:59:35Z)
• Online Convex Optimization with Long Term Constraints for Predictable Sequences [5.964436882344728]
  We study a specific framework of OCO called it OCO with long term constraints. Long term constraints are introduced as an alternative to reduce the complexity of the projection at every update step in online optimization. We show that, with a predictor that can supply the information of the next function in the sequence, our algorithm can achieve an overall regret and constraint violation rate that is strictly less than the rate that is achievable without prediction.
  arXiv  Detail & Related papers  (2022-10-30T03:50:53Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  We focus on a class of nonsubmodular functions with special structure, and prove regret guarantees for several variants of the online and approximate online bandit gradient descent algorithms. We derive bounds for the agent's regret in the full information and bandit feedback setting, even if the delay between choosing a decision and receiving the incurred cost is unbounded.
  arXiv  Detail & Related papers  (2022-05-15T08:27:12Z)
• Optimal Parameter-free Online Learning with Switching Cost [47.415099037249085]
  -freeness in online learning refers to the adaptivity of an algorithm with respect to the optimal decision in hindsight. In this paper, we design such algorithms in the presence of switching cost - the latter penalizes the optimistic updates required by parameter-freeness. We propose a simple yet powerful algorithm for Online Linear Optimization (OLO) with switching cost, which improves the existing suboptimal regret bound [ZCP22a] to the optimal rate.
  arXiv  Detail & Related papers  (2022-05-13T18:44:27Z)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  We investigate an online prediction strategy named as Discounted-Normal-Predictor (Kapralov and Panigrahy, 2010) for smoothed online convex optimization (SOCO) We show that the proposed algorithm can minimize the adaptive regret with switching cost in every interval.
  arXiv  Detail & Related papers  (2022-05-02T08:48:22Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)
• DJEnsemble: On the Selection of a Disjoint Ensemble of Deep Learning Black-Box Spatio-Temporal Models [0.8347559086129669]
  We present a cost-based approach for the automatic selection and allocation of a disjoint ensemble of black-box predictors. We show that our model produces plans with performance close to the actual best plan.
  arXiv  Detail & Related papers  (2020-05-22T10:37:16Z)

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.