Review for NeurIPS paper: Simple and Fast Algorithm for Binary Integer and Online Linear Programming

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). The main weaknesses were: - Insufficient comparison with the existing online LP literature, in particular with the competitive ratio bounds of previous work.