We start with the case where \(f_j\)  may not be convex. By the matrix Hoeffding inequality [1]}, we have for some small constants \(c, c^{\prime },c^{\prime \prime }>0\)  and any \(\eta >0\) :
\(\mathbb {P}\big (\Vert {\hat{}}()-()\Vert \ge \eta \big )&\le 2d\exp \bigg (-\frac{c\eta ^2s}{\lambda _{\max }^2R^2}\bigg ) =\exp \bigg (-\log (2d)\Big (\frac{c\eta ^2s}{\lambda _{\max }^2R^2\log (2d)}-1\Big )\bigg ) \\&\le 2\exp \bigg (-\frac{c^{\prime }\eta ^2s}{\lambda _{\max }^2R^2\log (2d)}\bigg ) \le 2\exp \bigg (-\frac{c^{\prime \prime }\eta }{\lambda _{\max }R\sqrt{\log (d)/s}}\bigg ),\) 
