COS511-LEC-01-27-2026

Summary

Key Points

• —Machine learning theory involves modeling practical problems mathematically to develop efficient algorithms with provable guarantees. 2:01
• —The "prediction from expert advice" paradigm is a fundamental and successful approach for repeated binary decision-making, relevant to various applications including modern LLMs. 2:05
• —The primary goal in this setting is to minimize the number of mistakes made, ideally performing as well as the single best expert in hindsight. 8:03
• —A naive approach of always picking the advice of the expert who has made the fewest mistakes so far (best in hindsight) fails due to adversarial scenarios. 11:04
• —The deterministic Weighted Majority algorithm assigns weights to experts, reduces weights of those who give wrong advice, and makes decisions based on the weighted majority. 16:41
• —The Weighted Majority algorithm guarantees that its total mistakes will be at most twice the mistakes of the best expert in hindsight, plus a term logarithmic in the number of experts. 21:47
• —The Randomized Weighted Majority algorithm improves upon this by making decisions probabilistically based on expert weights, achieving the same mistake bound in expectation without the factor of two. 54:41
• —The factor of two in the deterministic Weighted Majority algorithm's guarantee is proven to be inevitable for any deterministic algorithm in this setting. 62:56
• —The bounds derived for these algorithms, including the logarithmic dependence on the number of experts, are generally considered tight, though more refined analyses can explore specific expert behaviors like variance. 65:44
• —Theoretical research continuously seeks to refine algorithms and bounds by considering more nuanced problem aspects and motivating practical applications. 67:16