ML for discrete optimization: Theoretical foundations

on YouTube ↗01h 01m

" summary

Presents two concrete methods with proofs and experiments: a GNN pipeline called MAGNOLIA trains on exponential-time marginal value-to-go labels from tiny graphs (uses GENConv, predicts each offline+skip marginal value-to-go and matches the highest) and outperforms greedy, thresholded greedy, and LP-rounding; theory shows value-to-go is nearly local on random geometric graphs so GNNs with O(log n) layers approximate it. Separately, leverages calibrated predictions and sharpness to give rent-or-buy and online scheduling algorithms whose competitive ratio or regret provably improves with calibration and predictor variance, validated on real data.

AI-written summary · about

" chapters (4)

1. 0:00Introduction to ML and Opt
2. 9:39GNNs for online matching
3. 30:10Algorithms with predictions
4. 55:33Future directions and conclusion

" related talks

• 45mAGT and Machine LearningChristos Papadimitriou · Algorithmic Game Theory and Practice 2015
• 29mGraph Neural Networks + LLM onBrian Shi, Rishi Puri · NODES 2025
• 47mIs Minimax Optimization the Right Framework to Understand Learning in Minimax Games?Gauthier Gidel · Adversarial Approaches in Machine Learning 2022
• 32mLearning Ill-Conditioned Gaussian Graphical ModelsRaghu Meka · Algorithmic Aspects of Causal Inference 2022
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 15mImproved Machine Learning Algorithm for Predicting Ground State PropertiesLaura Lewis · Quantum Summer Cluster Workshop 2023
• 23mGraph ML – The Next Level Of Machine Learning; Learn How To Use It And When Not ToJörg Schad · Big Data LDN 2022
• 33mProvably Efficient Algorithms for Training Deep NetworksShai Shalev-Shwartz · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)