NN-Baker: A Neural-Network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs
Dez 6, 2021
Sprecher:innen
Evan McCarty
Sprecher:in · 0 Follower:innen
Anastasios Sidiropoulos
Sprecher:in · 0 Follower:innen
Über
Recent years have witnessed a surge of approaches to use neural networks to help tackle combinatorial optimization problems, including graph optimization problems. However, theoretical understanding of such approaches remains limited. In this paper, we consider the geometric setting, where graphs are induced by points in a fixed dimensional Euclidean space. We show that several graph optimization problems can be approximated by an algorithm that is polynomial in graph size n via a framework we propose, call the Baker-paradigm. More importantly, a key advantage of the Baker-paradigm is that it decomposes the input problem into (at most linear number of) small sub-problems of fixed sizes (independent of the size of the input). For the family of such fixed-size sub-problems, we can now design neural networks with universal approximation guarantees to solve them. This leads to a mixed algorithmic-ML framework, which we call NN-Baker that has the capacity to approximately solve a family of graph optimization problems (e.g, maximum independent set and minimum vertex cover) in time linear to input graph size, and only polynomial to approximation parameter. We instantiate our NN-Baker by a CNN version and GNN version, and demonstrate the effectiveness and efficiency of our approach via a range of experiments.Recent years have witnessed a surge of approaches to use neural networks to help tackle combinatorial optimization problems, including graph optimization problems. However, theoretical understanding of such approaches remains limited. In this paper, we consider the geometric setting, where graphs are induced by points in a fixed dimensional Euclidean space. We show that several graph optimization problems can be approximated by an algorithm that is polynomial in graph size n via a framework we p…
Organisator
NeurIPS 2021
Konto · 1,9k Follower:innen
Über NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Gefällt euch das Format? Vertraut auf SlidesLive, um euer nächstes Event festzuhalten!
Professionelle Aufzeichnung und Livestreaming – weltweit.
Freigeben
Empfohlene Videos
Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind
The Banality of Scale: A Theory on the Limits of Modeling Bias and Fairness Frameworks for Social Justice (and other lessons from the Pandemic)
Später ansehen
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Approximate Inference in Bayesian DL
Später ansehen
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Cockpit: A Practical Debugging Tool for the Training of Deep Neural Networks
Später ansehen
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Meta-learning from sparse recovery
Später ansehen
Beicheng Lou, …
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Risk Monotonicity in Statistical Learning
Später ansehen
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Taxonomizing local versus global structure in neural network loss landscapes
Später ansehen
Yaoqing Yang, …
Ewigspeicher-Fortschrittswert: 0 = 0.0%