BE-350: Machine Learning and Deep Learning
Assignment – 1: Understanding Hoeffding inequality
Deadline: September 30, 2024
In class I mentioned that hypothesis should be fixed before generating data then only Hoeffding
inequality bound holds true.
If hypothesis h is fixed before generating data, then:
2 𝑁𝑁
𝑃𝑃[|𝐸𝐸𝑖𝑖𝑖𝑖 (ℎ) − 𝐸𝐸𝑜𝑜𝑜𝑜𝑜𝑜 (ℎ)| > 𝜖𝜖 ] ≤ 2𝑒𝑒 −2𝜖𝜖 for any 𝜖𝜖 > 0
If the hypothesis h is chosen after generating data or looking at the data, then the bound doesn’t
hold true.
Let’s understand this with a simulation:
Run a computer simulation for flipping 1,000 fair coins. Flip each coin independently 10 times.
Let’s focus on 3 coins as follows:
1. C1 is the first coin flipped
2. Crandom is a coin you choose at random
3. Cmin is the coin that had the minimum frequency of heads (pick the earlier one in case of
a tie)
Let V1, Vrandom and Vmin be the fraction of heads you obtain for the respective three coins.
a. What is μ for the three coins selected?
b. Repeat this entire experiment a large number of times (e.g., 100,000 runs of the entire
experiment) to get several instances of V1, Vrandom and Vmin and plot the histograms of the
distributions of V1, Vrandom and Vmin. Notice that which coins end up being Crandom and Cmin
may differ from one run to another.
c. Using values in part (b), plot estimates for P[|v−μ| ≥ ε] as a function of ε, together with the
Hoeffding bound 2e−2ε²N on the same graph.
d. Which coins obey the Hoeffding bound, and which ones do not? Explain why.
You have to create a 1–2-page report answering all the parts above and submit as a pdf file. Also
submit a jupyter notebook as a separate file.
Naming conventions for files:
<enrolmentNo>_<name>.pdf
<enrolmentNo>_<name>.ipynb
Form Link: [Link]
