NeurExCo · Synergizing Neural Network Theory and Combinatorial Optimization via Extension Complexity
Horizon Europe — Marie Skłodowska-Curie Actions
- Duration
- 2024-04-01 → 2026-03-31
- EU contribution
- €175,920
- Participants
- 1
- Scheme
- HORIZON-TMA-MSCA-PF-EF
Lines connect the coordinator with its partners.
Results in brief
Synergizing Neural Network Theory and Combinatorial Optimization via Extension Complexity
Artificial intelligence is changing our lives. Artificial neural networks are present and entering various fields of modern technology such as medicine, engineering, education and many more. Even a small-scale theoretical understanding of why and how neural networks succeed in practice can have a considerable impact on the future development of such technologies. In contrast, combinatorial optimization is a well-established discipline at the intersection of mathematics and computer science, dealing with classical algorithmic questions like the Shortest Path or Traveling Salesperson Problems. A powerful tool to study structural and algorithmic properties of combinatorial optimization problems is polyhedral geometry. For example, the geometric notion of extension complexity classifies how well a specific problem can be expressed and solved via an extremely successful general-purpose technique called linear programming. Recent developments show that polyhedral theory can also be a powerful tool to achieve a better mathematical understanding of neural networks. The overall goal of this project is to significantly intensify the connection between neural networks and polyhedral theory, using the concept of extension complexity. This new symbiosis has the potential to advance both, the theoretical understanding of neural networks as well as the fundamental understanding of classical combinatorial optimization problems. On the side of neural networks, the goal is to obtain new bounds on the required size and depth to solve a given problem, serving as an explanation of why large and deep neural networks are more successful in practice. On the side of combinatorial optimization, generalized notions of extension complexity inspired by neural networks will lead to new structural and algorithmic insights to classical problems like the matching problem.
Data: CORDIS, © European Union
Project objective
Artificial intelligence is changing our lives. Artificial neural networks are present and entering various fields of modern technology such as medicine, engineering, education and many more. Even a small-scale theoretical understanding of why and how neural networks succeed in practice can have a considerable impact on the future development of such technologies.In contrast, combinatorial optimization is a well-established discipline at the intersection of mathematics and computer science, dealing with classical algorithmic questions like the Shortest Path or Traveling Salesperson Problems. A powerful tool to study structural and algorithmic properties of combinatorial optimization problems is polyhedral geometry. For example, the geometric notion of extension complexity classifies how well a specific problem can be expressed and solved via an extremely successful general-purpose technique called linear programming.Recent developments show that polyhedral theory can also be a powerful tool to achieve a better mathematical understanding of neural networks. The overall goal of this project is to significantly intensify the connection between neural networks and polyhedral theory, using the concept of extension complexity. This new symbiosis will advance both, the theoretical understanding of neural networks as well as the fundamental understanding of classical combinatorial optimization problems. On the side of neural networks, we expect to obtain new bounds on the required size and depth to solve a given problem, serving as an explanation of why large and deep neural networks are more successful in practice. Furthermore, we expect contributions to a more refined understanding of the computational complexity to train a neural network. On the side of combinatorial optimization, we expect that generalized notions of extension complexity inspired by neural networks lead to new structural and algorithmic insights to classical problems like the matching problem.
Original text from CORDIS.
Participants
- UNIVERSITE LIBRE DE BRUXELLES · Bruxelles / BrusselCoordinatorBelgium
Links
- View on CORDIS
- DOI: 10.3030/101153187
- https://ec.europa.eu/research/participants/documents/downloadPublic?documentIds=080166e51797d7a2&appId=PPGMS
Data: CORDIS, © European Union