Online Convex Optimization Perspective for Learning from Dynamically Revealed Preferences

• URL: http://arxiv.org/abs/2008.10460v3
• Date: Fri, 4 Jun 2021 13:31:11 GMT
• Title: Online Convex Optimization Perspective for Learning from Dynamically Revealed Preferences
• Authors: Violet Xinying Chen, Fatma K{\i}l{\i}n\c{c}-Karzan
• Abstract summary: We study the problem of online learning from revealed preferences. A learner wishes to learn a non-strategic agent's private utility function through observing the agent's utility-maximizing actions in a changing environment. We adopt an online inverse optimization setup, where the learner observes a stream of agent's actions in an online fashion and the learning performance is measured by regret associated with a loss function.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of online learning (OL) from revealed preferences: a learner wishes to learn a non-strategic agent's private utility function through observing the agent's utility-maximizing actions in a changing environment. We adopt an online inverse optimization setup, where the learner observes a stream of agent's actions in an online fashion and the learning performance is measured by regret associated with a loss function. We first characterize a special but broad class of agent's utility functions, then utilize this structure in designing a new convex loss function. We establish that the regret with respect to our new loss function also bounds the regret with respect to all other usual loss functions in the literature. This allows us to design a flexible OL framework that enables a unified treatment of loss functions and supports a variety of online convex optimization algorithms. We demonstrate with theoretical and empirical evidence that our framework based on the new loss function (in particular online Mirror Descent) has significant advantages in terms of regret performance and solution time over other OL algorithms from the literature and bypasses the previous technical assumptions as well.

Related papers

• LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
  An adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown to the learner. We present a robust online rounds optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown.
  arXiv  Detail & Related papers  (2024-08-12T17:08:31Z)
• Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
  offline preference optimization is a key method for enhancing and controlling the quality of Large Language Model (LLM) outputs. We perform objective discovery to automatically discover new state-of-the-art preference optimization algorithms without (expert) human intervention. Experiments demonstrate the state-of-the-art performance of DiscoPOP, a novel algorithm that adaptively blends logistic and exponential losses.
  arXiv  Detail & Related papers  (2024-06-12T16:58:41Z)
• Fast and Efficient Local Search for Genetic Programming Based Loss Function Learning [12.581217671500887]
  We propose a new meta-learning framework for task and model-agnostic loss function learning via a hybrid search approach. Results show that the learned loss functions bring improved convergence, sample efficiency, and inference performance on tabulated, computer vision, and natural language processing problems.
  arXiv  Detail & Related papers  (2024-03-01T02:20:04Z)
• GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
  Graph Influence Function (GIF) is a model-agnostic unlearning method that can efficiently and accurately estimate parameter changes in response to a $epsilon$-mass perturbation in deleted data. We conduct extensive experiments on four representative GNN models and three benchmark datasets to justify GIF's superiority in terms of unlearning efficacy, model utility, and unlearning efficiency.
  arXiv  Detail & Related papers  (2023-04-06T03:02:54Z)
• Online Loss Function Learning [13.744076477599707]
  Loss function learning aims to automate the task of designing a loss function for a machine learning model. We propose a new loss function learning technique for adaptively updating the loss function online after each update to the base model parameters.
  arXiv  Detail & Related papers  (2023-01-30T19:22:46Z)
• Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient [65.08966446962845]
  offline reinforcement learning, which aims at optimizing decision-making strategies with historical data, has been extensively applied in real-life applications. We take a step by considering offline reinforcement learning with differentiable function class approximation (DFA) Most importantly, we show offline differentiable function approximation is provably efficient by analyzing the pessimistic fitted Q-learning algorithm.
  arXiv  Detail & Related papers  (2022-10-03T07:59:42Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism [65.46524775457928]
  offline reinforcement learning seeks to utilize offline/historical data to optimize sequential decision-making strategies. We study the statistical limits of offline reinforcement learning with linear model representations.
  arXiv  Detail & Related papers  (2022-03-11T09:00:12Z)
• Contextual Inverse Optimization: Offline and Online Learning [3.6739949215165164]
  We study the problems of offline and online contextual optimization with feedback information. We aim to minimize regret, which is defined as the difference between our losses and the ones incurred by an all-knowing oracle.
  arXiv  Detail & Related papers  (2021-06-26T13:09:52Z)
• Visualizing the Loss Landscape of Actor Critic Methods with Applications in Inventory Optimization [0.0]
  We show the characteristics of the actor loss function which is the essential part of the optimization. We apply our approach to multi-store dynamic inventory control, a notoriously difficult problem in supply chain operations, and explore the shape of the loss function associated with the optimal policy.
  arXiv  Detail & Related papers  (2020-09-04T20:52: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.