EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
577. Need to relax - but perhaps later?
Invited abstract in session MB-1: Immanuel M. Bomze, stream Keynotes.
Monday, 10:30-12:00Room: Sportshallen (building: 101)
Authors (first author is the speaker)
1. | Immanuel Bomze
|
Dept. of Statistics and OR, University of Vienna |
Abstract
In some ML communities, researchers claim that obtaining local solutions of optimality criteria is often sufficient to provide a meaningful and accurate data model in real-world analytics. However, this is simply incorrect and sometimes dangerously misleading, particularly when it comes to highly structured problems involving non-convexity such as discrete decisions (binary variables). This talk will advocate the necessity of research efforts in the quest for global solutions and strong rigorous bounds for quality guarantees, showcased on one of the nowadays most popular domains -- cardinality-constrained models. These models try to achieve fairness, transparency and explainability in AI applications, ranging from Math.Finance/Economics to social and life sciences.
From a computational viewpoint, it may be tempting to replace the zero-norm (number of nonzero variables) with surrogates, for the benefit of tractability. We argue that these relaxations come too early. Instead, we propose to incorporate the true zero-norm into the base model and treat this either by MILP relaxations or else by lifting to tractable conic optimization models. Both in practice and in theory, these have proved to achieve much stronger bounds than the usual LP-based ones, and therefore they may, more reliably and based upon exact arguments, assess the quality of proposals coming from other techniques in a more precise way. With some effort invested in the theory (aka later relaxations), the resulting models are still scalable and would guarantee computational performance closer to reality and/or optimality.
Keywords
- Global Optimization
- Machine Learning
- Programming, Mixed-Integer
Status: accepted
Back to the list of papers