<p>In the lecture notes titled &quot;Foundations of Reinforcement Learning and Interactive Decision Making&quot; by Foster and Rakhlin, it is mentioned in the Proposition 1 that there exists an algorithm that's excess risk under squared loss, when competing against the function class <span class="math-container">$\mathcal{F}$</span>, given <span class="math-container">$n$</span> samples from the data distribution <span class="math-container">$D$</span>, is upper bounded by <span class="math-container">$\log(\mathcal{F}/\delta)/n$</span> with probability at least <span class="math-container">$1-\delta$</span>. I wanted to know what that algorithm was, and where I can find the source of this result.</p>

CC BY-SA 4.0
2024-08-06T05:38:54.420Z
Is there a proof of Prop 1 given? Presumably the algorithm is empirical risk minimization (ERM). Such proofs generally use a concentration bound to prove that each function in the class has empirical loss close to its true expected loss, then union-bound over the hypothesis class. Any theoretical ML text such as Understanding ML, Foundations of ML will have proofs along these lines.
usul
CC BY-SA 4.0
2024-08-15T04:36:19.987Z
@usul There is a proof given realizability; however there is not one when the assumption is dropped. Yet the proposition states the bound still holds without the assumption.
atul ganju
<machine-learning><lg.learning>
Agnosting Learning Algorithm for Squared Loss Regression and Conditional Density Estimation
atul ganju
# Agnosting Learning Algorithm for Squared Loss Regression and Conditional Density Estimation

(Asked by: username_0 on 2024-08-01)

In the lecture notes titled "Foundations of Reinforcement Learning and Interactive Decision Making" by Foster and Rakhlin, it is mentioned in the Proposition 1 that there exists an algorithm that's excess risk under squared loss, when competing against the function class $\mathcal{F}$, given $n$ samples from the data distribution $D$, is upper bounded by $\log(\mathcal{F}/\delta)/n$ with probability at least $1-\delta$. I wanted to know what that algorithm was, and where I can find the source of this result.

**Tags:** machine-learning, lg.learning

> **Comments:**
> **username_1**: Is there a proof of Prop 1 given? Presumably the algorithm is empirical risk minimization (ERM). Such proofs generally use a concentration bound to prove that each function in the class has empirical loss close to its true expected loss, then union-bound over the hypothesis class. Any theoretical ML text such as Understanding ML, Foundations of ML will have proofs along these lines.  
> **username_0**: @username_1 There is a proof given realizability; however there is not one when the assumption is dropped. Yet the proposition states the bound still holds without the assumption.  

---

## 0 answers

