====== Assignment: Generalization Bound ======

**📅 Deadline:** 13.11.2025 21:59

**🏦 Points:** 2

<note warning> Update: Note the difference between ULLN and PAC bounds! Which one are you supposed to use here? ;) Jakub </note>
===== Task Description =====
In this assignment, you are tasked with computing a generalization bound for a learning algorithm that operates within a finite hypothesis space. You can find the complete description of the assignment in the {{ :courses:be4m33ssu:homeworks:hw_assignment_generalization_bound_ws2025.pdf | Assignment PDF}}.

You are provided with a {{ :courses:be4m33ssu:homeworks:hw_generalization_bound_template_14_10_2024.zip |template}} containing the following files:

  * **main.py**: This file includes the function **generalization_bound** that you are required to implement. It loads the input, verifies the correctness of the **generalization_bound** output, and writes the results to a file readable by the [[https://cw.felk.cvut.cz/brute/student/course/BE4M33SSU/genbound|BRUTE]] system.
  * **utils.py**: Contains helper functions for loading and saving data. You do not need to modify this file.
  * **test-cases**: A folder containing public test cases to help you verify your implementation before submitting to [[https://cw.felk.cvut.cz/brute/student/course/BE4M33SSU/genbound|BRUTE]].

Your objective is to implement the function **generalization_bound** in **main.py**.

<note important>
All python files must be stored in the root of the .zip sent for submission.
</note>



===== How to Test =====
After completing your implementation, you can test your solution using the following commands before submitting it to BRUTE:

----


== Test Case 1 ==
  python main.py test-cases/public/instances/instance_1.json
Expected output:
  Given that we selected the predictor from a hypothesis space of 216 predictors,
  the true risk of the predictor is smaller than [0.36] with probability at least 0.95
  
  Comparing with reference solution
  Test OK

----

== Test Case 2 ==

  python main.py test-cases/public/instances/instance_2.json
Expected output:
  Given that we selected the predictor from a hypothesis space of 54 predictors,
  the true risk of the predictor is smaller than [0.30] with probability at least 0.98
  
  Comparing with reference solution
  Test OK

----

== Test Case 3 ==

  python main.py test-cases/public/instances/instance_3.json
Expected output:
  Given that we selected the predictor from a hypothesis space of 54 predictors,
  the true risk of the predictor is smaller than [0.28] with probability at least 0.88
  
  Comparing with reference solution
  Test OK


===== Submission Guidelines =====
  * Submit the completed code as a .zip via BRUTE.
  * All python files must be stored in the root of the .zip sent for submission.
  * Make sure your implementation passes the test cases provided above. Good luck! 😊