Goal
The course concerns theory and algorithms for dealing with optimization and decision making problems arising in Artificial Intelligence. The theoretical foundations of algorithms for global and approximate optimization are established, with a focus on theoretical performance guarantees, which find application in machine learning and optimum decision making. Models for online decision making are also investigated, with a separate focus on exploiting statistical prior information.
Upon successful completion of the course, the students will be in position to:
- develop formal mathematical representation models for optimization and decision making problems
- choose appropriate methods for global or approximate solving methods, for a given mathematical problem model
- evaluate the solution to a mathematical optimization model and the performance of a solving method
- design and apply algorithmic techniques for online decision making, using available statistical information or online machine learning
Also, the course targets to the following general competencies:
- Search for, analysis and synthesis of data and information by the use of appropriate technologies
- Adapting to new situations
- Decision-making
- Individual/Independent work
- Group/Team work
- Critical thinking
- Introduction of innovative research
- Development of free, creative and inductive thinking
Contents
- Elements of Convex Optimization
- Algorithms for Minimizing Convex Functions Gradient Descent, Newton-Raphson, Conjugate Gradient, Applications in Machine Learning
- Linear Programming Linear Programming Theory, Simplex, Duality, Examples
- Integer Programming Modeling Examples, Linear Relaxations, Global Optimization Algorithms.
- Elements of Approximation Algorithms NP-hard Problems, Approximation via Linear Programming, Rounding, Primal-Dual and Dual-Fitting Approximations
- Online Decision Making Algorithms with Statistical Information Online Algorithms, Secretary Problem, Prophet Inequalities, other related models.
- Online Machine Learning Algorithms No-Regret Learning, Experts Learning, Bandits Learning
Bibliography
- S. Boyd, L. Vanderberghe. Convex Optimization. Cambridge University Press, 2004.
- M. Mohri, A. Rostamizadeh, A. Talwalkar. Foundations of Machine Learning. MIT Press, 2018.
- D. Bertsimas, J. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997.
- D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
- C. H. Papadimitriou, K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.
- N. Cesa-Bianchi, G. Lugosi, Prediction, Learning, and Games. Cambridge University Press, 2006.
- T. Lattimore, C. Szepesvari. Bandit Algorithms. Cambridge University Press, 2020.
Relevant scientific journals:
- SIAM Journal on Computing, SIAM
- Journal of the ACM, ACM
- Theory of Computing
- Journal of Machine Learning Research
- Journal of Artificial Intelligence Research
- Theoretical Computer Science, Elsevier
