Numerical solution of a PDE arising from prediction with expert advice

• URL: http://arxiv.org/abs/2406.05754v1
• Date: Sun, 9 Jun 2024 12:17:05 GMT
• Title: Numerical solution of a PDE arising from prediction with expert advice
• Authors: Jeff Calder, Nadejda Drenska, Drisana Mosaphir,
• Abstract summary: This work investigates the online machine learning problem of prediction with expert advice in an adversarial setting. The continuum limit of this game over a large number of steps is a degenerate elliptic equation whose solution encodes the optimal strategies for both players.
• Score: 2.048226951354646
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work investigates the online machine learning problem of prediction with expert advice in an adversarial setting through numerical analysis of, and experiments with, a related partial differential equation. The problem is a repeated two-person game involving decision-making at each step informed by $n$ experts in an adversarial environment. The continuum limit of this game over a large number of steps is a degenerate elliptic equation whose solution encodes the optimal strategies for both players. We develop numerical methods for approximating the solution of this equation in relatively high dimensions ($n\leq 10$) by exploiting symmetries in the equation and the solution to drastically reduce the size of the computational domain. Based on our numerical results we make a number of conjectures about the optimality of various adversarial strategies, in particular about the non-optimality of the COMB strategy.

Related papers

• Online Convex Optimization with Memory and Limited Predictions [19.7248150754102]
  We study the problem of online convex optimization with memory and predictions over a horizon $T$. We propose an algorithm to solve this problem and show that the dynamic regret of the algorithm decays exponentially with the prediction window length.
  arXiv  Detail & Related papers  (2024-10-31T02:33:47Z)
• DNA-SE: Towards Deep Neural-Nets Assisted Semiparametric Estimation [39.48526221316346]
  Semiparametric statistics play a pivotal role in a wide range of domains, including but not limited to missing data, causal inference, and transfer learning. We develop a scalable algorithm called Deep Neural-Nets Assisted Semiparametric Estimation (DNA-SE) by leveraging the universal approximation property of Deep Neural-Nets (DNN) to streamline semiparametric procedures.
  arXiv  Detail & Related papers  (2024-08-04T14:45:26Z)
• Constrained or Unconstrained? Neural-Network-Based Equation Discovery from Data [0.0]
  We represent the PDE as a neural network and use an intermediate state representation similar to a Physics-Informed Neural Network (PINN) We present a penalty method and a widely used trust-region barrier method to solve this constrained optimization problem. Our results on the Burgers' and the Korteweg-De Vreis equations demonstrate that the latter constrained method outperforms the penalty method.
  arXiv  Detail & Related papers  (2024-05-30T01:55:44Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Efficient PDE-Constrained optimization under high-dimensional uncertainty using derivative-informed neural operators [6.296120102486062]
  We propose a novel framework for solving large-scale partial differential equations (PDEs) with high-dimensional random parameters. We refer to such neural operators as multi-input reduced basis derivative informed neural operators (MR-DINOs) We show that MR-DINOs offer $103$--$107 times$ reductions in execution time, and are able to produce OUU solutions of comparable accuracies to those from standard PDE based solutions.
  arXiv  Detail & Related papers  (2023-05-31T17:26:20Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  We focus on optimisation programming (SP), Optimal Control (SOC) and Decision Processes (MDP) Recent progress in solving convex multistage Markov problems is based on cutting planes approximations of the cost-to-go functions of dynamic programming equations. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables.
  arXiv  Detail & Related papers  (2023-03-28T01:30:40Z)
• Automated differential equation solver based on the parametric approximation optimization [77.34726150561087]
  The article presents a method that uses an optimization algorithm to obtain a solution using the parameterized approximation. It allows solving the wide class of equations in an automated manner without the algorithm's parameters change.
  arXiv  Detail & Related papers  (2022-05-11T10:06:47Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)
• Comparison of Distal Teacher Learning with Numerical and Analytical Methods to Solve Inverse Kinematics for Rigid-Body Mechanisms [67.80123919697971]
  We argue that one of the first proposed machine learning (ML) solutions to inverse kinematics -- distal teaching (DT) -- is actually good enough when combined with differentiable programming libraries. We analyze solve rate, accuracy, sample efficiency and scalability. With enough training data and relaxed precision requirements, DT has a better solve rate and is faster than state-of-the-art numerical solvers for a 15-DoF mechanism.
  arXiv  Detail & Related papers  (2020-02-29T09:55:45Z)

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.