Research Project — Centroid Informed Approximate Nearest Convex Hull Classification

Background and Motivation:

Recent work found that certain convex separable problems are hard to learn for multi-layer perceptrons (MLPs) while being solvable with vanishing generalization error by nearest convex hull classification (NCHC). Applying NCHC to a classification task of nn classes requires to solve nn constrained convex optimization problems and is, hence, computationally intractable for real-world deployment. Instead, an approximate algorithm must be devised. The convex hull can be isolated in space by a set of MMnn planes which touch the hull tangential. Consider one plane defined by its normal vector wii and bias bbii. The plane effectively cuts the space into two half-planes: The positive half-plane in which wii T x + bbii > 0, and the corresponding negative half plane for which wii T x + bbii < 0. Adding more half-planes (MMnn ↑) cuts out more precise areas of the space such that we can asymptotically isolate the convex hull. The distance of a point x to the hull is then estimated by summing the squared euclidean distances of x to the planes {ii}. This approach is referred to as approximate NCHC (ANCHC).

Overall Project Aim:

The project aims to refine the simple ANCHC algorithm. This shall be done by taking the distance of each plane to the centroid of the hull into account. We refer to this approach as centroid informed approximate NCHC (CNCHC). An initial mathematical study of the problem is followed by an implementation phase in which an improved distance estimator shall be developed. The obtained algorithm is then evaluated to NCHC and ANCHC from a performative and computational complexity perspective.

Project Objectives:

The main objectives of this thesis can be summarized as follows:

  • Mathematical study of the underlying problem and the relation of the distance metric to the centroid of a convex hull.
  • Development and Implementation of CNCHC (analytically or by deep-learning methods).
  • Refinement of CNCHC.

Prerequisites:

The following qualifications are required in order to pursue this project:

  • Very Good knowledge of linear algebra.
  • Basic knowledge of (convex) optimization.
  • Good programming skills in Python (JAX, PyTorch or Haiku, numpy).
  • Beneficial: foundational knowledge on random matrices and free probability theory.
  • Beneficial: experience with Git.
  • Beneficial: experience with convex solvers (e.g. cvxpy or jaxopt).
  • Beneficial: experience with bash and slurm.

If you are interested in pursuing this project, please contact Levi Bohnacker (levi.bohnacker@fau.de). The full project description can be found here.