This four day workshop will introduce students to Optimization tools required to handle Big Data problems.

Date: 3 - 6 December 2018

Venue: Wits University

Course & Instructor:

• Large-scale Optimization - Montaz Ali (Wits)

Course Outline:

Large-scale Optimization

1. Optimization problems in big data: Huge datasets can be generated in many practical situations, they can also be generated many social networks and commercial internet sites, or by some experiments. One way to analyse a dataset is to postulate a statistical model (e.g. maximum likelihood) that generates the data, but the model has some parameters in it. The idea is to estimate these parameters that best fit the generated data. This typically leads to large problems in optimization (and also numerical linear algebra, especially in graph theoretical problem). Numerical linear algebra provide an invaluable tool in dealing with many such problems. Examples of such large scale problems will be given.
2. The first order optimality condition e.g. the KKT condition. Algorithm for very large scale continuous optimization problems e.g. conjugate gradient for unconstrained nonlinear problem, alternating direction method of multipliers (ADMM) for very large scale constrained convex optimization.
3. Monte Carlo method, Markov chain, MCMC (Markov chain Monte Carlo), Metropolis Algorithm, Metropolis-Hasting Algorithm, Simulated Annealing for solving large scale and complex optimization problems, and estimation problems.
4. Genetic algorithm for solving discrete, Combinatorial and continuous optimization problems.
5. The LASSO and its various incarnations in compress sensing, Optimization methods involving iterative thresholding (hard thresholding), and matching pursuit.
6. The optimization problems in machine learning e.g. support vector machine specially the linear separation/classification problem, Ridge Regression, the Linear Regression (the least squared problems) and LASSO, the logistic regression models, the normal equation.
7. Very large scale optimization in graph such as optimization problems in maximum clique, and planted clique and their applications.
8. Optimization problem formulations of zero-sum and non-zero games, and Nash Equilibrium, Prisoner’s Dilemma, Battle of Sexes, solutions of some well-known Game theoretical problems.