Our analysis is based on the notion of average stability (for more details we refer to e.g., [1]} and reference therein). Although there is a vast literature on stability based techniques, with several recent related papers [2]}, [3]}, we could not find any general result that implies Theorem REF . Therefore, we provide an elementary proof. One of the differences compared with some of the previous results is that we provide an exact formula for the average stability as well as an exact analysis of the fitting term as an intermediate step in our proof. Our analysis of the fitting term exploits the curvature of the quadratic loss and, in particular, allows to rewrite the stability term as the multiplier term that appears in Theorem REF . Crucially, stability based approach allows us to replace the quadratic term appearing in the proof of Theorem REF  by a bias term that scales as \(\frac{\lambda b^2}{n}\)  and consequently, removes multiplicative factor \(\log (\min \lbrace n, d\rbrace )\)  that is unimprovable for constrained ERM as we demonstrate in Proposition REF .
