Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize

• URL: http://arxiv.org/abs/2305.16830v2
• Date: Sun, 18 Feb 2024 20:18:07 GMT
• Title: Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize
• Authors: Sanket Shah, Andrew Perrault, Bryan Wilder, Milind Tambe
• Abstract summary: We show that our method achieves state-of-the-art results in four domains from the literature. Our approach outperforms the best existing method by nearly 200% when the localness assumption is broken.
• Score: 57.22851616806617
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Predict-then-Optimize is a framework for using machine learning to perform decision-making under uncertainty. The central research question it asks is, "How can the structure of a decision-making task be used to tailor ML models for that specific task?" To this end, recent work has proposed learning task-specific loss functions that capture this underlying structure. However, current approaches make restrictive assumptions about the form of these losses and their impact on ML model behavior. These assumptions both lead to approaches with high computational cost, and when they are violated in practice, poor performance. In this paper, we propose solutions to these issues, avoiding the aforementioned assumptions and utilizing the ML model's features to increase the sample efficiency of learning loss functions. We empirically show that our method achieves state-of-the-art results in four domains from the literature, often requiring an order of magnitude fewer samples than comparable methods from past work. Moreover, our approach outperforms the best existing method by nearly 200% when the localness assumption is broken.

Related papers

• On Sampling Strategies for Spectral Model Sharding [7.185534285278903]
  In this work, we present two sampling strategies for such sharding. The first produces unbiased estimators of the original weights, while the second aims to minimize the squared approximation error. We demonstrate that both of these methods can lead to improved performance on various commonly used datasets.
  arXiv  Detail & Related papers  (2024-10-31T16:37:25Z)
• Federated Continual Learning Goes Online: Uncertainty-Aware Memory Management for Vision Tasks and Beyond [13.867793835583463]
  We propose an uncertainty-aware memory-based approach to solve catastrophic forgetting. We retrieve samples with specific characteristics, and - by retraining the model on such samples - we demonstrate the potential of this approach.
  arXiv  Detail & Related papers  (2024-05-29T09:29:39Z)
• Low-rank finetuning for LLMs: A fairness perspective [54.13240282850982]
  Low-rank approximation techniques have become the de facto standard for fine-tuning Large Language Models. This paper investigates the effectiveness of these methods in capturing the shift of fine-tuning datasets from the initial pre-trained data distribution. We show that low-rank fine-tuning inadvertently preserves undesirable biases and toxic behaviors.
  arXiv  Detail & Related papers  (2024-05-28T20:43:53Z)
• Score Function Gradient Estimation to Widen the Applicability of Decision-Focused Learning [17.962860438133312]
  Decision-focused learning (DFL) paradigm overcomes limitation by training to directly minimize a task loss, e.g. regret. We propose an alternative method that makes no such assumptions, it combines smoothing with score function estimation which works on any task loss. Experiments show that it typically requires more epochs, but that it is on par with specialized methods and performs especially well for the difficult case of problems with uncertainty in the constraints, in terms of solution quality, scalability, or both.
  arXiv  Detail & Related papers  (2023-07-11T12:32:13Z)
• Learning (Local) Surrogate Loss Functions for Predict-Then-Optimize Problems [58.954414264760956]
  Decision-Focused Learning (DFL) is a paradigm for tailoring a predictive model to a downstream optimisation task. We present an approach to learn faithful task-specific surrogates which (a) only requires access to a black-box oracle that can solve the optimisation problem and is thus generalizable, and (b) can be convex by gradients and so can be easily optimized over.
  arXiv  Detail & Related papers  (2022-03-30T05:46:54Z)
• Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse [34.39887495671287]
  We propose an objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates. We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance. Experimental evaluation with multiple real world datasets demonstrates the efficacy of the proposed framework.
  arXiv  Detail & Related papers  (2022-03-13T21:39:24Z)
• Few-shot Quality-Diversity Optimization [50.337225556491774]
  Quality-Diversity (QD) optimization has been shown to be effective tools in dealing with deceptive minima and sparse rewards in Reinforcement Learning. We show that, given examples from a task distribution, information about the paths taken by optimization in parameter space can be leveraged to build a prior population, which when used to initialize QD methods in unseen environments, allows for few-shot adaptation. Experiments carried in both sparse and dense reward settings using robotic manipulation and navigation benchmarks show that it considerably reduces the number of generations that are required for QD optimization in these environments.
  arXiv  Detail & Related papers  (2021-09-14T17:12:20Z)
• Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learning [52.74071439183113]
  We study the predict-then-optimize framework in the context of sequential decision problems (formulated as MDPs) solved via reinforcement learning. Two significant computational challenges arise in applying decision-focused learning to MDPs.
  arXiv  Detail & Related papers  (2021-06-06T23:53:31Z)
• Sufficiently Accurate Model Learning for Planning [119.80502738709937]
  This paper introduces the constrained Sufficiently Accurate model learning approach. It provides examples of such problems, and presents a theorem on how close some approximate solutions can be. The approximate solution quality will depend on the function parameterization, loss and constraint function smoothness, and the number of samples in model learning.
  arXiv  Detail & Related papers  (2021-02-11T16:27:31Z)
• Backpropagation-Free Learning Method for Correlated Fuzzy Neural Networks [2.1320960069210475]
  This paper proposes a novel stepwise learning approach based on estimating desired premise parts' outputs. It does not require backpropagating the output error to learn the premise parts' parameters. It is successfully applied to real-world time-series prediction and regression problems.
  arXiv  Detail & Related papers  (2020-11-25T20:56:05Z)

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.