NUMERICAL OPTIMISATION
PROJECT GUIDELINES
Optimisation in classification with Support Vector Machines (SVMs)
MARTA BETCKE, BOLIN PAN
Submission via TurnItIn, in T3 TBC
This is a numerical optimisation and not a machine learning project. The emphasis here is
on optimisation methods and their convergence not on classification performance. Still,
it is important to pose your problem in the best possible way and solve it with appropriate
tools. Always provide reference to sources of any claims, theorems, methods etc. Mathematical
rigour on par with the lecture and clear and succinct writeup (3k words total hard limit,
please include the word count) is expected.
All methods need to be implemented by you (no use of optimisation packages is allowed)
except for codes that were implemented by you or made available by us in the course of tutorials.
For setting up the classification problem you can use dedicated packages, but do not use the
built in optimisation routines.
Include your implementations of the optimisation methods and an excerpt from testing
script showing how they are called at the end of your report. Restrict the latter to the minimum
necessary to validate that you used your own implementations. The codes will not count towards
the word limit.
UCL rules and regulations on late submission and plagiarism apply.
Optimisation problem underlying SVM classification.
Support vector machines (SVMs) are a well established and rigorously funded technique for
solution of classification problems in machine learning.
? Choose a classification problem and the most appropriate SVM formulation for it: pri-
mal/dual, linear/nonlinear, choice of loss etc (justify appropriateness of all choices for
your classification problem).
? Shortly introduce and explain the chosen formulation (no need for comprehensive deriva-
tion just key steps to demonstrate understanding).
? Identify the type of the resulting optimisation problem and any challenges it poses.
Marks: 10 baseline + up to 5 bonus (more complicated problem: nonlinear, non-standard loss
etc). [10 - 15 pt]
Solve the obtained optimisation problem with two appropriate methods.
Application of the method and underlying theory:
Note: Theory will only be given marks if there is a serious attempt on numerical solution.
1
? Propose two appropriate methods for solution of the optimisation problem (justify your
choices e.g. applicability, convergence, efficiency etc).
? Briefly recap known methods or introduce methods if they were not part of the syllabus
and apply them to your optimisation problem.
? Discuss global convergence in the context of your problem (are there any results that are
applicable? provide references in case of either positive or negative statement).
? Discuss theoretical local convergence rates predicted for your problem.
You can paraphrase theorems from the lecture or other respectable sources (books, journals,
trusted lecture notes etc). Always state the result and explain why it applies to your problem.
If you cannot exactly match the problem with the theory, discuss what is the departure from
the theory in your case and what effect on convergence do you expect and why.
Marks: 2 x { 5 (method) + 5 (solution) + 5 (theory) + 5 (application of theory) baseline +
up to 10 bonus (method substantially different to those on the syllabus) } [40 - 60 pt]
Discussion of the results:
? Provide convergence plots and empirical convergence rates.
? Discuss the theoretical versus empirical convergence rates including all relevant checks
e.g. was trust region active or not, was step size 1 attained or not etc.
? Compare the performance of both methods as rigorously as you can (pay attention to how
expensive is each individual iteration etc).
Marks: 2 x { 5 (empirical convergence plots, rates), 5 (theory vs practice) }, 5 (comparison of
the methods) [25 pt]
2