No-failure MMW rounds yield an approximate dual-feasible vector

By $\mathrm{\parallel }{A}_j\mathrm{\parallel },\mathrm{\parallel }C\mathrm{\parallel }\le 1$ and $\mathrm{\parallel }{y}_t{\mathrm{\parallel }}_1\le r$, the triangle inequality gives $\mathrm{\parallel }{M}_t\mathrm{\parallel }\le (r+1)\mathrm{/}w=1$, so the regret bound applies. The trace-estimate assumptions and ${\sum }_j{y}_{t,j}\le r$ give $\mid {\sum }_j{y}_{t,j}{\tilde{a}}_{t,j}-{\tilde{c}}_t-\mathrm{tr}\text{\hspace{0.17em}⁣}\left(({\sum }_j{y}_{t,j}{A}_j-C){\rho }_t\right)\mid \le (r+1)\theta =w\theta \mathrm{.}$ Together with the shifted-oracle inequality, this implies $\mathrm{tr}(M_t{\rho }_t)\ge -2\theta$.

Sum the lower bounds from step 1.1 and combine them with [F3]. Writing $S={\sum }_t{M}_t$, we get $-2\theta T\le {\lambda }_{\min }(S)+\eta T+\ln (n)\mathrm{/}\eta$, hence ${\lambda }_{\min }(S\mathrm{/}T)\ge -(2\theta +\eta +\ln (n)\mathrm{/}(\eta T))$.

The dual slack of $\bar{y}$ is ${\sum }_j{\bar{y}}_j{A}_j-C=\gamma I+(w\mathrm{/}T)S$, because the identity coefficient contributes $\gamma A_1=\gamma I$. Step 2.1 and the lower bound on $\gamma$ make this matrix positive semidefinite. Also $\bar{y}\ge 0$ and $b\cdot \bar{y}=\gamma R+T^{-1}{\sum }_{t}b\cdot y_t\le \gamma R+\alpha$. These are exactly the dual feasibility and objective claims in [F1].