[Crib-list] SEMINAR: Thursday, NOV. 17th : LEARNING WITH COMBINATORIAL OPTIMIZATION LAYERS: A PROBABILISTIC APPROACH @ 4:00 -5:00 PM in RM 32-G882

[Shirley Entzminger]

         Learning with Combinatorial Optimization Layers: a Probabilistic 
Approach



SPEAKER:  Guillaume Dalle
Host:     Alan Edelman

DATE:      Thursday: November 17, 2022
TIME:      4pm - 5pm
LOCATION:  Building 32, Room G882


ABSTRACT:

Combinatorial optimization (CO) layers in machine learning (ML)
pipelines are a powerful tool to tackle data-driven decision tasks, but
they come with two main challenges. First, the solution of a CO problem
often behaves as a piecewise constant function of its objective
parameters. Given that ML pipelines are typically trained using
stochastic gradient descent, the absence of slope information is very
detrimental. Second, standard ML losses do not work well in
combinatorial settings. A growing body of research addresses these
challenges through diverse methods. Unfortunately, the lack of
well-maintained implementations slows down the adoption of CO layers._

Building upon previous works, we introduce a probabilistic perspective
on CO layers, which lends itself naturally to approximate
differentiation and the construction of structured losses. We recover
many approaches from the literature as special cases, and we also derive
new ones. Based on this unifying perspective, we present InferOpt.jl, an
open-source Julia package that 1) allows turning any CO oracle with a
linear objective into a differentiable layer, and 2) defines adequate
losses to train pipelines containing such layers. Our library works with
arbitrary optimization algorithms, and it is fully compatible with
Julia’s ML ecosystem. We demonstrate its abilities using a pathfinding
problem on video game maps.

===========================

Shirley Entzminger
Administrative Assistant
Massachusetts Institute of Technology
Department of Mathematics
77 Massachusetts Avenue
Building 2, Room 350A
Cambridge, MA  02139
PHONE: 617-253-4994
EMAIL: daisymae at math.mit.edu