a $(1 -\epsilon)$-competitive solution for online packing LP’s with $m$ constraints in the random permutation model whenever $B \ge \Omega(\frac{m^2}{\epsilon^2} \log \frac{m}{\epsilon})$. Another way of stating this result is that the algorithm has competitive ratio $1 - O(m \sqrt{\log B}/\sqrt{B})$. Contrasting to previous results, our guarantee does not depend on $n$ and in the case $m = 1$ matches the bounds for the $B$-Choice Secretary Problem up to lower order terms. We finally remark that we can replace the requirement $B \ge \Omega(\frac{m^2}{\epsilon^2} \log \frac{m}{\epsilon})$ by ${\ensuremath{\textrm{OPT}}}\ge \Omega(\frac{\pi_{\max} m^3}{\epsilon^2} \log \frac{m}{\epsilon})$ exactly as done in Section 5.1 of [@agrawal].

[*High-level outline.*]{} As mentioned before, we use the connection between solving an online LP and PAC-learning a good linear classification of its columns; in order to obtain the improved guarantee, we focus on tightening the bounds for the generalization error of the learning problem. More precisely, solving the LP can be seen as classifying the columns into 0/1, which corresponds to setting their associated variable to 0/1. Consider a family $\mathcal{X} \subseteq \{0,1\}^n$ of linear classifications of the columns. Our algorithms sample a set $S$ of columns and learn a classification $x^S \in \mathcal{X}$ which is “good” for the columns $S$ 