0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 0020 0021 0022 0023 0024 0025 0026 0027 0028 0029 0030 0031 0032 0033 0034 0035 0036 0037 0038 0039 0040...

The study material is called "A Modern Introduction to Online Learning(version3)" written by Francesco Orabona.


0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 0020 0021 0022 0023 0024 0025 0026 0027 0028 0029 0030 0031 0032 0033 0034 0035 0036 0037 0038 0039 0040 0041 0042 0043 0044 0045 0046 0047 0048 0049 0050 0051 0052 0053 0054 0055 0056 0057 0058 0059 CHAPTER 5 ASSIGNMENT DANIEL ROY Note that you should not be using aids such as mathexchange to solve these problems. Better to work on them alone, get stuck, and then get help from other students who can provide helpful hints that still allow you to have that “ah ha!” moment, which expands your brain. Start early. Exercise 5.1. From course notes: Fix U > 0. Mimicking the proof of Theorem 5.1 in the course notes, prove that for any OCO algorithm there exists a vector u∗ and a sequence of loss functions such that RegretT (u ∗) ≥ √ 2 2 ‖u ∗‖2 L √ T , where ‖u∗‖2 = U and the loss functions are L-Lipschitz w.r.t. ‖·‖. Exercise 5.2. From course notes:. Extend the proof of Theorem 5.1 to an arbitrary norm ‖·‖ to measure the diameter of V and with ‖gt‖∗ ≤ L. Exercise 5.3. From course notes:. Assume f and g are proper, convex, and closed and satisfy f(x) ≤ g(x) for all x. Prove that f∗(θ) ≥ g∗(θ) for all θ. Exercise 5.4. From course notes:. Assume f is even, i.e., f(x) = f(−x). Prove that f∗ is even. 1 5.1. 5.2. 5.3. 5.4.