Numerical solution of a PDE arising from prediction with expert advice
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913782055305216 |
|---|---|
| author | Calder, Jeff Drenska, Nadejda Mosaphir, Drisana |
| author_facet | Calder, Jeff Drenska, Nadejda Mosaphir, Drisana |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05754 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Numerical solution of a PDE arising from prediction with expert advice Calder, Jeff Drenska, Nadejda Mosaphir, Drisana Numerical Analysis Artificial Intelligence Machine Learning Analysis of PDEs 35D40, 65N12, 65N06, 35Q68, 35J60 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. |
| title | Numerical solution of a PDE arising from prediction with expert advice |
| topic | Numerical Analysis Artificial Intelligence Machine Learning Analysis of PDEs 35D40, 65N12, 65N06, 35Q68, 35J60 |
| url | https://arxiv.org/abs/2406.05754 |