Contextual Learning for Stochastic Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915298746040320 |
|---|---|
| author | Heuser, Anna Kesselheim, Thomas |
| author_facet | Heuser, Anna Kesselheim, Thomas |
| contents | Motivated by stochastic optimization, we introduce the problem of learning from samples of contextual value distributions. A contextual value distribution can be understood as a family of real-valued distributions, where each sample consists of a context $x$ and a random variable drawn from the corresponding real-valued distribution $D_x$. By minimizing a convex surrogate loss, we learn an empirical distribution $D'_x$ for each context, ensuring a small Lévy distance to $D_x$. We apply this result to obtain the sample complexity bounds for the learning of an $ε$-optimal policy for stochastic optimization problems defined on an unknown contextual value distribution. The sample complexity is shown to be polynomial for the general case of strongly monotone and stable optimization problems, including Single-item Revenue Maximization, Pandora's Box and Optimal Stopping. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_16829 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Contextual Learning for Stochastic Optimization Heuser, Anna Kesselheim, Thomas Machine Learning Data Structures and Algorithms Computer Science and Game Theory Motivated by stochastic optimization, we introduce the problem of learning from samples of contextual value distributions. A contextual value distribution can be understood as a family of real-valued distributions, where each sample consists of a context $x$ and a random variable drawn from the corresponding real-valued distribution $D_x$. By minimizing a convex surrogate loss, we learn an empirical distribution $D'_x$ for each context, ensuring a small Lévy distance to $D_x$. We apply this result to obtain the sample complexity bounds for the learning of an $ε$-optimal policy for stochastic optimization problems defined on an unknown contextual value distribution. The sample complexity is shown to be polynomial for the general case of strongly monotone and stable optimization problems, including Single-item Revenue Maximization, Pandora's Box and Optimal Stopping. |
| title | Contextual Learning for Stochastic Optimization |
| topic | Machine Learning Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2505.16829 |