Tractable optimization in machine learning∗

Machine Learning (ML) broadly encompasses a variety of adaptive, autonomous, and intelligent tasks where one must “learn ” to predict from observations and feedback. Throughout its evolution, ML has drawn heavily and successfully on optimization algorithms. This relation to optimization is not surprising as “learning ” and “adapting ” usually lead to problems where some quality functio