Certifiably Globally Optimal Unsupervised Machine Learning

Research topic/area

Classification & Semidefinite Relaxations

Type of thesis

Master

Start time

11.05.2024

Application deadline

02.05.2025

Duration of the thesis

6 months

Description

It is known [Jean B. Lasserre, 2001] that for polynomial problems (POPs), i.e., nonconvex optimization problems where objective and constraints are multivariate polynomials, the global optimum can be determined via rank relaxation, adding redundant constraints, ascending Lasserre‘s hierarchy, and solving a semidefinite program (SDP), in polynomial time. While this methology is not yet real-time applicable as of 2024, it is merely a matter of time until increased computational power, more advanced solvers, and optimized problem design strategies render this possible. The potential applications of machine learning with optimality guarantees and certificates are immense. Many supervised machine learning and perception problems have already been formulated as POP and successfully solved with this framework, e.g., point cloud registration, pose and shape estimation, and robust estimation.

Unsupervised ML problems, like clustering and Gaussian mixture estimation, can also be stated as POP. The goal of this work is demonstrating and evaluating globally and certifiably solving these kind of problems with that same framework as well. The state of art closest to this in terms of problem structure is robust perception, which should be reproduced first to get familiar with the required methology and tools.

What to do

• Get familiar with solving POPs via SDP
• Reproduce robust perception
• Attempt Clustering
• Attempt Gaussian Mixture Estimation
• Optimize problem structure, e.g. exploiting sparsity
• Evaluate against state of art

Thesis language: German or English.

Requirement

Requirements for students

• Excellent grades
• Pre-knowledge in Julia, Matlab, or Python are welcome
• Strong self-motivation, perseverance, reliability, mathematical skills, and critical mind

Faculty departments

• Engineering sciences
  Electrical engineering & information technologies
  Informatics
  Mechanical Engineering
• Natural sciences and Technology
  Mathematics
  Physics
  Mathematics in Technology

Supervision

Title, first name, last name

Dr.-Ing. Daniel Frisch

Organizational unit

Intelligent Sensor-Actuator-Systems (ISAS)

Email address

daniel.frisch@kit.edu

Link to personal homepage/personal page

Website

Application via email

Application documents

• Grade transcript

E-Mail Address for application
Senden Sie die oben genannten Bewerbungsunterlagen bitte per Mail an daniel.frisch@kit.edu


Back