QTW Workshop on Beyond Worst Case Analysis
About the Series
- Location: ITW Lecture Hall (1st floor), Ford Motor Company Engineering Design Center (map), Northwestern U, 2133 Sheridan Rd, Evanston, IL 60208.
- Transit: Noyes St. Purple Line (map).
- Parking: Validation for North Campus Parking Garage (map) available at workshop.
Registration is free. Please register at https://goo.gl/forms/OBh61KORT8hryksw1 if you plan to attend.
Titles and Abstracts
Speaker: Tim Roughgarden
Title: How Hard Is Inference for Structured Prediction?
Abstract: Structured prediction tasks in machine learning involve the simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise elements, each depending on two specific labels. The goal of this work is to develop a theoretical explanation of the empirical effectiveness of heuristic inference algorithms for solving such structured prediction problems. We study the minimum-achievable expected Hamming error in such problems, highlighting the case of 2D grid graphs, which are common in machine vision applications. Our main theorems provide tight upper and lower bounds on this error, as well as a polynomial-time algorithm that achieves the bound.
Joint work with Amir Globerson, David Sontag, and Cafer Yildirim.
Conceptually, any algorithm meeting the exact information-theoretic threshold in the average-case model must exploit the precise structure of the noise. These results point to an interesting new direction: Can semirandom (and related) models help explain why some algorithms are preferred to others in practice, in spite of gaps in their average-case performance?
Speaker: Yury Makarychev
Title: Algorithms for Stable and Perturbation-Resilient Problems
Abstract: We study the notion of stability and perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A combinatorial optimization problem is α-stable or α-perturbation-resilient if the optimal solution does not change when we perturb all parameters of the problem by a factor of at most α. We present improved algorithms for stable instances of various clustering and optimization problems, including k-means, k-median, Max Cut, and Minimum Multiway Cut. We also show several hardness results.
The talk is based on joint papers with Haris Angelidakis, Konstantin Makarychev, and Aravindan Vijayaraghavan.