Links between learning and optimization: a brief tutorial
Anthony, M.
(2003).
Links between learning and optimization: a brief tutorial.
(CDAM research report series LSE-CDAM-2003-02).
Centre for Discrete and Applicable Mathematics, London School of Economics and Political Science.
(2003).
Links between learning and optimization: a brief tutorial.
(CDAM research report series LSE-CDAM-2003-02).
Centre for Discrete and Applicable Mathematics, London School of Economics and Political Science.
This report is a brief exposition of some of the important links between machine learning and combinatorial optimization. We explain how efficient ‘learnability’ in standard probabilistic models of learning is linked to the existence of efficient randomized algorithms for certain natural combinatorial optimization problems, and we discuss the complexity of some of these optimization problems.