Midterm Exam 1 ISYE 4301 | Answered Latest 2025-26 Total points: 95 points + 15 bonus. - GT. - ISYE 4301 (ISYE4301) - Stuvia US
- The term inside the square root will be negative, which makes the calculation of ε∗ infeasible. False,
there is no way to make that term negative. (1 point) Q5 (10 points) Consider an online learning framework with 5 experts, with decisions {0, 1}, and T = 500 time periods. We would like to use the deterministic weighted majority algorithm and use this side information in fine-tuning the learning parameter. Answer the following two questions:
- If we do not know the number of mistakes made by the same expert, what ε should we use as seen in
class? Please provide a numerical value.
- Suppose we have magical powers and, before running the online learning algorithm, we know that the
best expert will make mistakes M ∗ = T /2 time periods. Is it possible to guarantee always sublinear regret using WMA?
- What if we know that M ∗ = 0?
Answer:
q q
- In this case we use εalt = ln n
T ln 5 ∼ 0.0567. (2 point) = 500 √
- Now, the best regret you can guarantee is M ∗ + O( T ln), which is at least T /2 and is linear, not
sub-linear. (2 points) √ √
- Yes, because the regret of M ∗ + O( T ln) becomes O( T ln). (1 point)
Q6, Q7, and Q8 will use the following weather prediction setup that you should read carefully In Q6, Q7, and Q8, we will explore the performance of various online algorithms on the problem of predicting Atlanta’s weather (sunny or rainy) at 7 pm every day. We will do this prediction on the advice of 3 weather forecasters: AccuWeather, weather.com and NOAA. The following table shows the forecasts of the 3 experts
as well as the actual weather each day:
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