1 — 16:20 — ** MOVED TO FRIDAY AM REMOTE SESSION ** A Monte Carlo Policy Gradient Method with Local Search for Binary Optimization
Binary integer programming problems are ubiquitous in many practical applications, including the MaxCut and cheeger cut problem, the MIMO detection and MaxSAT, etc. They are NP-hard due to the combinatorial structure. In this talk, we present a policy gradient method using deep Monte Carlo local search to ensure sufficient exploration in discrete spaces. The local search method is proved to improve the quality of integer solutions and the policy gradient descent converges to stationary points in expectation. Numerical results show that this framework provides near-optimal solutions efficiently for quite a few binary optimization problems.
2 — 16:50 — ** CANCELLED ** Understanding and Recomposing the Learning and Searching Techniques in ML4CO: An Deep Dive into the TSP Case
Despite the rich works on machine learning (ML) for combinatorial optimization (CO), there lacks a principled framework. We develop a unified modular framework for CO incorporating existing major techniques in both learning and search to understand the effects of techniques, which is embodied on the Travelling Salesman Problem (TSP). We show that principles like joint probability estimation, symmetry accommodation, online optimization are desirable for ML4CO, which also guide the development of new method designs within our framework. By extensive evaluation, we also show the advantages of nonautoregressive methods over autoregressive ones, as well as the superiority of supervised paradigms over unsupervised ones. The strategic decoupling and organic recompositions within the framework yield a factory of new solvers, among which some achieve SOTA performance in learningbased solvers of optimality drops of 0.000\% for TSP-50 and 100, and 0.109\% for TSP-500
3 — 17:20 — ** CANCELLED ** Learning to learn for discrete optimization: some recent developments
It has become popular in recent years to research on learning to optimize due to the advancement of deep learning and the rising of the AI for Science research paradigm. In this talk, I will present some of our recent works on learning to optimize for discrete optimization problems. In the first part, a learning to optimize algorithm for integer programming within the branch and bound framework is illustrated. A learning to optimize algorithm for multi-objective optimization problems is then presented. Finally, I will present an application to the MIMO signal detection problem in wireless communication.