Midterm Exam 1 ISYE 4301 | Answered Latest 2025-26 Total points: 95 points + 15 bonus. - GT. - ISYE 4301 (ISYE4301) - Stuvia US
ISYE 4301: Midterm 1 Name: ........................................................... Total points: 95 points + 15 bonus. Please justify your answers and show complete steps so that we can assign partial credit when needed. Note the scrap paper space at the end if you need additional space Remark (Exam timing). Questions 1 to 5 are should be relatively fast; questions 6 to 10 require computing weights, losses, regrets, and will take more time and contribute more points in your final grade. Make sure to manage your time! Note that there are two bonus problems at the end. Remark on grading: we will try to avoid double-counting mistakes. So, for example, if you run an algorithm for several days and make a mistake on day 1, but your answer for subsequent days is consistent with your answer for day 1, we will only count day 1 as wrong. You will get full points if you have the right answer, and the ”partial credit” part of the grading grid will be used in case your answer is wrong. Q1 (5 points) Imagine that you have a binary online prediction setting in which you know there is at least one perfect expert. Based on the worst-case mistake and/or regret bounds seen in class, which algorithm should you use? Justify your answer. Answer: You should use the Halving algorithm that makes at most O(log2 n) mistakes if there exists at least one perfect expert. This is the best you can get, as it does not even depend on T ! Grading: 3 points for the right algorithm, 2 for the justification Q2 (5 points) You are using the Halving algorithm with 513 experts. What is the best upper bound on the number of mistakes the Halving Algorithm can make, under the traditional assumption of the Halving algorithm? Answer: 9 ≤ log2 (513) ≤ 10—you can guarantee no more than 9 mistakes. Alternatively, you can note that there will be at most 256 experts left after mistake 1 (this requires 257 experts at least being wrong to get a majority that leads to a mistake), 128 after mistake 2, 64 after mistakes 3, 32 after mistake 4, 16 after mistake 5, 8 after mistake 6, 4 after mistake 7, 2 after mistake 8, and finally only the perfect expert remaining after mistake 9. Grading: 4 points if you said 10 instead of 9. 3 points if the reasoning or formula is right, but the final result is wrong. 0 if both result and reasoning/formula are wrong. Q3 (5 points) The Multiplicative Weight Update Algorithm enjoys the following properties when the