Figure 1. HODLR structure. All four figures represent the same matrix at different hierarchical levels. The red diagonal blocks represent full rank dense blocks, and the teal off diagonal blocks are low rank.

Computational Methods for Optimization with Rank Structure

Frederik Hagsholm Pedersen: Identifying and exploiting hidden structure for efficient optimization in data science

Mathematical optimization concerns the minimization/maximization of some cost/performance measure subject to a set of constraints. Many core problems in data science are naturally posed as optimization problems. One example in machine learning is the need to solve regression problems for supervised learning algorithms. In recent years, the quantity of data and complexity of data science problems has increased dramatically. Increasingly sophisticated data science models continue to emerge, presenting computational challenges for data scientists, who are often limited by the computational resources available. To handle the increasing complexity, existing methods often rely on crude approximations or simplified models resulting in suboptimal solutions.

In this project, we will develop novel optimization techniques, which can efficiently solve certain classes of problems within data science. The key in developing efficient algorithms is to exploit structure in the data. Sparsity is an example of a structure, which, if properly identified and exploited, often allows for efficient solutions of core optimization problems. However, many core problems in data science are not sparse in the traditional sense but “data-sparse”, which motivates the need to develop more complex methods to handle these cases.

In this project, we will investigate how to identify and exploit complex rank structure in the data. One example of such a rank structure is hierarchical off-diagonal low rank (HODLR) matrices, which have low rank off-diagonal blocks, see Figure 1. These data structures arise naturally in some data science applications, where the off-diagonal blocks represent low-information interactions between variables. The hypothesis is that the rank-structure may be exploited in state-of-the-art optimization methods to efficiently evaluate gradients and Hessians needed to compute search directions.

The successful completion of this project gives valuable theoretical insight within the field of optimization, as well as computational tools ready to be applied to problems within data science.

PhD project

By: Frederik Hagsholm Pedersen

Section: Scientific Computing

Principal supervisor: Martin Skovgaard Andersen

Co-supervisor: Joachim Dahl

Project title: Computational Methods for Optimization with Rank Structure

Term: 15/03/2021 → 14/03/2024

Contact

Martin Skovgaard Andersen
Associate Professor
DTU Compute
+45 45 25 30 36

Contact

Joachim Dahl Thomsen
Postdoc
DTU Physics
+45 45 25 66 25

Contact

Frederik Hagsholm Pedersen
PhD student
DTU Compute