DS4DM Coffee Talks

Which is the optimal amount of caffeine you need to make good decisions? At DS4DM we transform coffee, tea, and chats into cutting-edge ideas. Join our seminar series either in Montreal or via Zoom with your favorite hot beverage.

Roughly every 2 weeks, we will invite a speaker working in the areas of Optimization, Machine Learning, and Game Theory to give a talk in our lab.

The format: we will host either a single 50 minutes talk from an experienced researchers, or two 30 minutes talks from junior researchers. You can either join the online stream or attend physically (if you are in Montréal) by visiting Pavillon André-Aisenstadt (Université de Montréal), 6th Floor Auditorium.

Adrian Vetta

McGill

Matching Markets: Incentives under the Deferred Acceptance Algorithm


I will give a short overview of several important applications of algorithmic mechanism design and game theory. Then I will focus on one specific problem: what incentives arise in matching markets when the classical deferred acceptance algorithm is used to obtain a stable matching? This talk is based on work with Ndiame Ndiaye and Sergey Norin.
When: 10th of November 2021 - 2.30pm (EST)
More: Adrian's Website


Can Li

DS4DM & Purdue

Algorithms and Software for Two-stage Stochastic Mixed-integer Nonlinear Programs

Two-stage stochastic programming is one of the approaches to model decision-making under uncertainty. Although there have been algorithmic advances in two-stage stochastic mixed-integer linear programs in the past two decades, the algorithms to address the nonlinear counterpart are few. In this talk, I will first give an overview of the recent advances in solving stochastic MINLP problems. The major focus of this talk is a generalized Benders decomposition-based branch and cut algorithm that combines strengthened Benders cuts and Lagrangean cuts for solving two stage stochastic MINLPs with mixed-binary first and second stage variables. The proposed algorithm is applied to a stochastic pooling problem, a crude selection problem, and a storage design problem. The performance of the proposed algorithm is compared with a Lagrangean decomposition-based branch and bound algorithm and solving the corresponding deterministic equivalent with the solvers including BARON, ANTIGONE, and SCIP.

When: 24th of November 2021 - 11am (EST)
More: Can's Website

Guanyi Wang

DS4DM

Solving row-sparse principal component analysis via convex integer programs

For general computational-intensive mixed-integer non-linear optimization problems, a major challenge is to verify/guarantee the quality of any feasible solution within tractable time/computational limits. A natural idea to tackle this challenge is constructing tight relaxations and designing approximation algorithms for relaxed problems. In this talk, we focus on the (row) sparse principal component analysis (rsPCA) problem, i.e., the problem of finding the top-r leading principal components of a covariance matrix such that all these principal components are linear combinations of a subset of k variables. We propose: (a) a convex integer programming relaxation of rsPCA that gives upper (dual) bounds for rsPCA, and; (b) a new local search algorithm for finding primal feasible solutions for rsPCA. We also show that, in the worst-case, the dual bounds provided by the convex IP are within an affine function of the globally optimal value. We demonstrate our techniques applied to large-scale covariance matrices. This is a joint work with Santanu S. Dey, Rahul Mazumder, Macro Molinaro.

When: 24th of November 2021 - 11am (EST)
More: Guanyi's Website


Didier Chételat

DS4DM

Continuous cutting planes algorithms

Standard cutting plane algorithms are iterative, in that cuts are added as rounds, and the resulting linear program grows at every round. Ineffective cuts are sometimes pruned, but the number of cuts must still fundamentally grow for the algorithm to converge. This is problematic for computational stability, as well as memory and time. In this talk, we present an alternative class of algorithms that finds good cuts by deformation: it starts with a fixed number of initial cuts, and continuously deforms them by gradient ascent to tighten the LP relaxation. The number of cuts never changes throughout the process, and interestingly, it frames the problem of computing good cuts as a continuous optimization problem. Computational experiments show that this can be made to work in practice, although the method is not currently time competitive against the more classical cutting plane algorithms.
When: Date TBA
More: Didier's Website


Maxime Gasse

DS4DM

Causal Reinforcement Learning using Observational and Interventional Data


Learning efficiently a causal model of the environment is a key challenge of model-based RL. In this work we consider a POMDP scenario where the learning agent has the ability to collect online experiences through direct interactions with the environment (interventional data), but has also access to a large collection of offline experiences, obtained by observing another agent interacting with the environment (observational data). A key ingredient, that makes this situation non-trivial, is that we allow the observed agent to interact with the environment based on hidden information, which is not observed by the learning agent. We then ask the following questions: can the online and offline experiences be safely combined for learning a causal model ? And can we expect the offline experiences to improve the agent's performances ? To answer these, we import ideas from the well-established causal framework of do-calculus, and we express model-based reinforcement learning as a causal inference problem.
When: Date TBA
More: Maxime's Website


About

We are the Canada Excellence Research Chair in Data Science for Decision Making (DS4DM) from Polytechnique Montréal. We focus on Optimization, Machine Learning and Game Theory, and often do research at the interface of such areas.

This seminar series is organized by Gabriele Dragotto, Federico Bobbio with the support of the DS4DM group.

  • Address

    Pavillon André-Aisenstadt
    2920, Chemin de la Tour,
    Montréal, QC Canada

  • Contacts

    gabriele (dot) dragotto (at) polymtl (dot) ca
    federico (dot) bobbio (at) umontreal (dot) ca