Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.07252 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909229221150720 |
|---|---|
| author | Vituri, Shlomi Feder, Meir |
| author_facet | Vituri, Shlomi Feder, Meir |
| contents | In this paper we consider the problem of universal {\em batch} learning in a misspecification setting with log-loss. In this setting the hypothesis class is a set of models $Θ$. However, the data is generated by an unknown distribution that may not belong to this set but comes from a larger set of models $Φ\supset Θ$. Given a training sample, a universal learner is requested to predict a probability distribution for the next outcome and a log-loss is incurred. The universal learner performance is measured by the regret relative to the best hypothesis matching the data, chosen from $Θ$. Utilizing the minimax theorem and information theoretical tools, we derive the optimal universal learner, a mixture over the set of the data generating distributions, and get a closed form expression for the min-max regret. We show that this regret can be considered as a constrained version of the conditional capacity between the data and its generating distributions set. We present tight bounds for this min-max regret, implying that the complexity of the problem is dominated by the richness of the hypotheses models $Θ$ and not by the data generating distributions set $Φ$. We develop an extension to the Arimoto-Blahut algorithm for numerical evaluation of the regret and its capacity achieving prior distribution. We demonstrate our results for the case where the observations come from a $K$-parameters multinomial distributions while the hypothesis class $Θ$ is only a subset of this family of distributions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_07252 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Universal Batch Learning Under The Misspecification Setting Vituri, Shlomi Feder, Meir Machine Learning Information Theory In this paper we consider the problem of universal {\em batch} learning in a misspecification setting with log-loss. In this setting the hypothesis class is a set of models $Θ$. However, the data is generated by an unknown distribution that may not belong to this set but comes from a larger set of models $Φ\supset Θ$. Given a training sample, a universal learner is requested to predict a probability distribution for the next outcome and a log-loss is incurred. The universal learner performance is measured by the regret relative to the best hypothesis matching the data, chosen from $Θ$. Utilizing the minimax theorem and information theoretical tools, we derive the optimal universal learner, a mixture over the set of the data generating distributions, and get a closed form expression for the min-max regret. We show that this regret can be considered as a constrained version of the conditional capacity between the data and its generating distributions set. We present tight bounds for this min-max regret, implying that the complexity of the problem is dominated by the richness of the hypotheses models $Θ$ and not by the data generating distributions set $Φ$. We develop an extension to the Arimoto-Blahut algorithm for numerical evaluation of the regret and its capacity achieving prior distribution. We demonstrate our results for the case where the observations come from a $K$-parameters multinomial distributions while the hypothesis class $Θ$ is only a subset of this family of distributions. |
| title | Universal Batch Learning Under The Misspecification Setting |
| topic | Machine Learning Information Theory |
| url | https://arxiv.org/abs/2405.07252 |