Skip to main content

Piecewise linear optimization in machine learning

Dr. Joey Huchette,  Assistant Professor

Department of Computational and Applied Mathematics

Rice University

Date: Friday, Oct 2, 2020

Time: 1 - 2pm

Zoom Meeting ID: 970 7656 5407

Password: 477211


Abstract: Piecewise linear functions arise in numerous contexts throughout machine learning (ML), such as the 0-1 classification loss and the ReLU nonlinear activation function used throughout deep learning. This talk focuses on two specific settings in ML where piecewise linear optimization problems can be fruitfully modeled and solved using linear programming (LP) and mixed-integer programming (MIP). First, we study optimization over trained neural neural networks, which arises naturally in verification and settings where data can be used to learn a proxy for an unknown ground truth function. We present a framework for modeling neural networks with piecewise linear activation functions, and apply it to derive LP and MIP formulations for trained neural networks with piecewise linear activation functions that are stronger than existing formulations. We present computational results showing that these new formulations allow us to solve verification tasks more quickly, and with a lower false negative rate, than existing approaches. Second, we study the problem of learning a linear model to set the reserve price in a second price auction, using available contextual information. This setting naturally arises in online ad auction markets, and is ill-suited for gradient-based methods due to an unusual, intrinsically discontinuous loss function. We present MIP- and LP-based methods for solving this learning problem, and show computationally that these new methods can lead to better-performing models than existing methods.

Biography:   Joey Huchette is an assistant professor in the Department of Computational and Applied Mathematics at Rice University. He received his PhD from the Operations Research Center at MIT in 2018. Before joining Rice, he was a postdoctoral researcher in the Operations Research group at Google Research. His work focuses on developing algorithmic and software technology for mathematical optimization, with a particular emphasis on mixed-integer programming and applications in machine learning.