A Tutorial on Analyzing Machine Learning Algorithms
吳沛遠副教授臺灣大學電機工程學系 3:30 p.m.–5:00 p.m. Hongjing Hall M107
Abstract:
This talk explores several foundational and emerging concepts at the intersection of machine learning theory, optimization, and reinforcement learning. We begin by presenting a novel perspective that frames self-taught reasoning in large language models (LLMs) through the lens of Markov chains, offering a probabilistic
interpretation of multi-step in-context learning. We then investigate the convergence behavior of gradient descent under adversarial conditions, showing that with carefully controlled step sizes, gradient-based methods can still converge to the optimum even in the presence of perturbations, provided the objective satisfies smoothness and Polyak-Łojasiewicz (PL) conditions. Transitioning to sequential decision-making, we revisit the principle of Optimism in the Face of Uncertainty (OFU) and its implications for exploration strategies. We introduce a regret analysis of the Upper Confidence Bound (UCB) algorithm in the linear bandit setting, highlighting key theoretical guarantees. Finally, we examine the Least-Squares Value Iteration (LSVI) framework and its UCB-augmented variant (LSVI-UCB), which bridges supervised learning and reinforcement learning with provable exploration efficiency. Together, these topics emphasize the importance of structure, robustness, and principled exploration in modern learning systems.