20874 - ALGORITHMS FOR OPTIMIZATION AND INFERENCE
Course taught in English
Go to class group/s: 29
Synchronous Blended: Lezioni erogate in modalità sincrona in aula (max 1 ora per credito online sincrona)
The course will teach the students the fundamentals of designing and analyzing algorithms for optimization and inference problems. The students will be able to estimate the computational complexity and the resource requirements of the algorithms they encounter, and to use them as building blocks in their own work. They will be familiarized with fundamental algorithmic theory and optimization techniques, and their interplay with inference and learning methods.
Basic Notions and Algorithmic Background
Algorithmic efficiency
Complexity classes and reductions
Graph and Combinatorial Optimization
Fundamental graph optimization problems
Matroids and Matroid intersection, Submodularity
Approximation algorithms for hard combinatorial optimization problems
Mathematical Optimization techniques
Linear Programming models and algorithms
Duality and Sensitivity analysis
Integer Programming models and algorithms
Non-linear Programming models and algorithms
Stochastic and Robust Optimization
Large-scale optimization
Inference and Learning
Submodular optimization and its applications in ML and AI
Mathematics of Neural Networks
Optimization algorithms for Deep Learning
- Understand the Recognize the efficiency of algorithms
- Estimate the computational and resource requirements of algorithms
- Classify optimization problems according to their computational complexity
- Formulate optimization problems as Linear/Integer/Non-linear programming models, including stochastic and robust aspects
- Understand the mathematics behind neural networks and inference algorithms
- Design and analyze efficient algorithms
- Estimate the computational and resource requirements of algorithms
- Classify optimization problems according to their computational complexity
- Formulate optimization problems as Linear/Integer/Non-linear programming models
- Solve stochastic, robust, and large-scale optimization problems using the appropriate techniques
- Apply inference algorithms
- Face-to-face lectures
The teaching method is face-to-face lectures. Several lectures will include exercises to be done in class.
Continuous assessment | Partial exams | General exam | |
---|---|---|---|
x | |||
x |
There will be a written exam and two homework assignments. The homework assignments are not mandatory.
The final grade will be calculated by taking for each student the best outcome out of the following two ones:
(a) Final written test contributes 70% of the final grade, and homework assignments contribute 30%.
(b) Final written test contributes 100% of the final grade.
The exam will test the students' ability to explain and reproduce the concepts learned in class, and connect these concepts to specific problem instances. There will be no difference between attending and non-attending students.
- Lecture slides and notes provided by the instructor
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, (The MIT press), 3rd/4th edition
- W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver. Combinatorial Optimization. Wiley-Interscience, 1997
- B. Guenin, J. Könemann, L. Tuncel, A Gentle Introduction to Optimization, Cambridge University Press, 2014
- Computer and Intractability. A Guide to NP-Completeness. M. R. Garey and D. S. Johnson. Publisher W. H. Freeman, 1979
- Information Theory, Inference, and Learning Algorithms, D. J. C. MacKay, Cambridge University Press, 2003