NeurIPS 2020

Simple and Fast Algorithm for Binary Integer and Online Linear Programming

Meta Review

The paper concerns online (approximate) solving of a general class of binary linear programs. The analysis of the algorithm is conducted under two models: stochastic inputs (columns of LP drawn i.i.d.) and random permutation model (columns of LP revealed in a random order). The authors develop a simple and fast online algorithm performing stochastic subgradient descent on a dual problem with provable guarantees on the regret and constraint violation. The paper received borderline reviews with a slight lean towards acceptance. The main strengths of the paper are: - New techniques for deriving the regret bounds in the random permutation model (permutational Rademacher complexity). - Appealing simplicity and efficiency of the algorithm: its time complexity is only O(m) per trial (m = number of rows of the constraint matrix A), while all other algorithms require explicitly solving linear programs. - Novel regret bounds of two previous algorithms (from past work) in the random permutation model. The main weaknesses were: - Insufficient comparison with the existing online LP literature, in particular with the competitive ratio bounds of previous work. - A similarity with the algorithm by Neely (2010). - The removal of positivity assumptions from the previous work, pointed out as a novel contribution, might not be technically difficult. The reviewers also pointed out some issues with the presentation which need to be fixed, and that the experimental evaluation is too short and non-reproducible. I urge the authors to take into account all the remarks of the reviewers in the final version of the paper, in particular: a clarified discussion on the competitive ratio bounds in the previous work, technical significance of handling negative signs in the constraint matrix, absorbing constraint violation in the regret, and similarity to the algorithm by Neely (2010).