In this talk, we explore differentiable extensions of combinatorial optimization problems and their applications in unsupervised learning. Combinatorial problems over discrete domains are inherently incompatible with gradient-based optimization and deep learning architectures. We address these challenges for two broad classes of problems: those over permutations (e.g., TSP, CutWidth) and set functions (e.g., Coverage, Facility Location).

We introduce differentiable extensions that are polynomial-time computable and come with rounding guarantees. Our extensions integrate naturally with the gradient backpropagation framework, allowing them to serve as loss functions in data-driven, unsupervised learning pipelines.