Breaking the Barrier for Tractable Global Optimization of Continuous Problems in Large Scale Data Science

• Applicant: Professor Dr. Peter Ochs
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 539436611

In many applications of Data Science such as Image Processing,Computer Vision, Machine Learning, or Statistics the tremendous dimensionality (even infinite for some instances), the rapidly growing data size, and the natural need to model these problems as non-smooth and non-convex optimization problems still renders global optimization of them intractable. This desire is significantly amplified by the prospective success of incorporating parametrized classical regularization based models such as (continuous-valued) graphical models or variational methods into Deep Learning models, which already now achieve state-of-the-art performance in several applications. The proposed project TRAGO will achieve tractability by a paradigm shift in the design of optimization algorithms for non-convex and non-smooth continuous optimization problems, which is inspired from discrete optimization perspective. In discrete optimization, many state-of-the-art algorithms are derived via lifting the problem to a linear program (e.g. the basic LP-relaxation). In the continuous setting, a complicated non-convex problems can be lifted to a higher (possibly infinite) dimensional simple convex optimization problem, which unlocks the possibility of computing a global minimizer. Although there has been significant progress in the area of structured non-convex (and non-smooth) optimization in recent years, most algorithms content themselves with finding stationary points instead of (approximating) a global minimizer. In contrast, TRAGO will break the barrier for tractable global optimization of continuous problems in large scale Data Science applications by theoretically and computationally investigating the optimal trade-off between gaining important properties for efficient optimization and paying for a higher dimensionality, which will dramatically change the picture that global minimization in large scale non-convex optimization in Data Science is intractable. TRAGO will target flagship applications in Data Science which are more ambitious and far larger scale than typical settings where these optimization problems are currently used. The work program will develop sound mathematical and computational tools whose power will be demonstrated in several examples in Machine Learning problems such as Graphical Models or Regularized Risk Minimization, Inverse and Variational Problems in Signal/Image Processing and Computer Vision, and Bilevel Optimization in Data Science.

• DFG Programme: Research Grants