Tang's conditional recommendation sampler

Put $b=\mathrm{\parallel }{A}_{i,\ast }\mathrm{\parallel }$. If $b=0$, return FAIL: then $D_{i,\ast }=0$ and the promised input is absent. Otherwise $b>0$ is available from exact access. Run ModFKV with failure budget $\delta \mathrm{/}3$, retaining its rank $k$, sample count, and $V$ of [F1]. If the retained rank is $k=0$, return FAIL because again $D_{i,\ast }=0$. The sketch event of [F1] has probability at least $1-\delta \mathrm{/}3$; all subsequent estimates use fresh randomness conditional on the actual sketch. Write $h=A_{i,\ast }{S}^T$ and $z=hU{\mathrm{\Sigma }}^{-1}$, so $D_{i,\ast }=z{V}^T$.

At stages $l=0,1,\dots$, set ${\rho }_l=2^{-l}$, ${\beta }_l=\delta 2^{-(l+1)}\mathrm{/}3$, and ${\alpha }_l={\rho }_l\mathrm{/}\sqrt{K}$. Put $m_l=\lceil 16\mathrm{/}{\alpha }_l^2\rceil$ and choose the least positive integer $r_l$ with $2^{-r_l}\le {\beta }_l\mathrm{/}q$. For each of the $q$ entries of $h$, use [F2]'s lower-median estimator with $m_l$ samples per block, $r_l$ blocks, tolerance ${\alpha }_l$, and failure budget ${\beta }_l\mathrm{/}q$; use mutually independent fresh sample batches for these estimates. Each row of $S$ has norm $F\mathrm{/}\sqrt{q}$. Thus on that stage's simultaneous success, $\mathrm{\parallel }{\widehat{h}}_l-h\mathrm{\parallel }\le {\alpha }_{l}bF$, and the explicit vector ${\widehat{z}}_l={\widehat{h}}_{l}U{\mathrm{\Sigma }}^{-1}$ obeys $\mathrm{\parallel }{\widehat{z}}_l-z\mathrm{\parallel }\le {\rho }_{l}b=:e_l$. Stop at the first stage with $\mathrm{\parallel }{\widehat{z}}_l\mathrm{\parallel }\ge (1+32\mathrm{/}ϵ)e_l$. All quantities in this rule are computable from stored coefficients and exact input row norms; no query of the unknown full output-row norm occurs.

Fix a realized sketch and use [F5] to predefine the disjoint finite sample batches for every potential stage $l$. Let $E_l$ be the cylinder event that at least one of that stage's $q$ inner-product estimates fails its tolerance. Fresh samples, [F2], and [F6] give $\mathbb{P}(E_l)\le {\beta }_l$. Since ${\sum }_{l\ge 0}{\beta }_l=\delta \mathrm{/}3$, [F6] gives $\mathbb{P}({\bigcup }_l{E}_l)\le \delta \mathrm{/}3$, and [F7] gives $\mathbb{P}(E_l\text{ infinitely often})=0$. Thus with probability at least $1-\delta \mathrm{/}3$ every stage estimate succeeds, and almost surely all sufficiently late stage estimates succeed. On those late stages $\mathrm{\parallel }{\widehat{z}}_l-z\mathrm{\parallel }\le e_l\to 0$, so ${\widehat{z}}_l\to z$. The nonzero-row promise implies $z\mathrm{\ne }0$; hence the stopping threshold $(1+32\mathrm{/}ϵ)e_l$ tends to zero while $\mathrm{\parallel }{\widehat{z}}_l\mathrm{\parallel }\to \mathrm{\parallel }z\mathrm{\parallel }>0$, and the procedure terminates almost surely, including for a sketch outside the successful sketch event whenever its realized target row is nonzero. On the event that every stage estimate succeeds, it stops no later than a stage with $e_l\le ϵ\mathrm{\parallel }z\mathrm{\parallel }\mathrm{/}64$, because $\mathrm{\parallel }{\widehat{z}}_l\mathrm{\parallel }\ge \mathrm{\parallel }z\mathrm{\parallel }-e_l\ge (1+32\mathrm{/}ϵ)e_l$. Hence the stopped stage satisfies $2^l\le \max \{1,128b\mathrm{/}(ϵ\mathrm{\parallel }z\mathrm{\parallel })\}$.

On the successful sketch and estimation event, at the stopping stage $\mathrm{\parallel }z\mathrm{\parallel }\ge \mathrm{\parallel }\widehat{z}\mathrm{\parallel }-e\ge 32e\mathrm{/}ϵ$. With $x=\widehat{z}{V}^T$ and $y=D_{i,\ast }=z{V}^T$, [F1] gives $\mathrm{\parallel }x-y\mathrm{\parallel }\mathrm{/}\mathrm{\parallel }y\mathrm{\parallel }\le \sqrt{3}e\mathrm{/}\mathrm{\parallel }z\mathrm{\parallel }\le \sqrt{3}ϵ\mathrm{/}32$. In particular $x\mathrm{\ne }0$, and [F3] yields $d_{\mathrm{T}\mathrm{V}}(D_x,D_y)\le \sqrt{3}ϵ\mathrm{/}16<ϵ$. This holds for every fixed successful sketch and estimate, so any mixture of their accepted output laws has the same bound when compared with the corresponding mixture of target laws.

Form the coefficient row $w=\widehat{z}{\mathrm{\Sigma }}^{-1}{U}^T$, so $x=wS$. Its numerator in the cancellation ratio is ${\sum }_j\mathrm{\parallel }{w}_j{S}_{j,\ast }{\mathrm{\parallel }}^2=(F^2\mathrm{/}q)\mathrm{\parallel }w{\mathrm{\parallel }}^2\le (F^2\mathrm{/}(q{\sigma }^2))\mathrm{\parallel }\widehat{z}{\mathrm{\parallel }}^2$. On the successful sketch, $\mathrm{\parallel }x{\mathrm{\parallel }}^2\ge \frac{1}{2}\mathrm{\parallel }\widehat{z}{\mathrm{\parallel }}^2$, so the ratio is at most $2K\mathrm{/}q$. Take $C_0=2K\mathrm{/}q$ as a proof-side bound and integer cap $R=\lceil 2K\log (3\mathrm{/}\delta )\rceil$, then invoke the finite sampler [F4] with $q$ terms and cap $R$. The bound $C\le C_0$ is established only on the successful sketch event; the procedure does not test or require a certificate for it. On every other history the sampler is still executable: if its component-square sum is zero it returns FAIL immediately, and otherwise its finite proposal/acceptance loop returns an accepted index or FAIL by the cap. Conditional on any fixed good coefficients, [F4] gives miss probability at most $\delta \mathrm{/}3$ and accepted law exactly $D_x$.

Sketch failure has probability at most $\delta \mathrm{/}3$. Conditional on every fixed sketch, any row-estimation failure has probability at most $\delta \mathrm{/}3$ by step 3.1. Conditional on a successful sketch and row estimate with nonzero target row, capped rejection failure has probability at most $\delta \mathrm{/}3$ by [F4]. By [F5], the finite conditional rejection laws are attached to their countably many finite stopping histories, so the failure event is measurable in the joint execution model; [F6] bounds the union of the sketch, estimation, and applicable rejection failures by $\delta$. Conditioning on rejection success does not manufacture confidence: for each fixed successful estimate its accepted law is already $D_x$ by [F4]. Step 4.1 supplies the asserted total-variation conclusion on that branch. Outside it the routine may return FAIL or an uncontrolled sample; no assertion treats a failed event as successful.

Stage $l$ uses $O(qK{4}^l\log (2q\mathrm{/}{\beta }_l))$ queries and arithmetic for inner products, plus $O(qk)$ coefficient arithmetic. Summing geometrically to the stopping stage gives $\tilde{O}(qK{ϵ}^{-2}{b}^2\mathrm{/}\mathrm{\parallel }z{\mathrm{\parallel }}^2+qK)$ on simultaneous success. Since $\mathrm{\parallel }{D}_{i,\ast }\mathrm{\parallel }\le \sqrt{3\mathrm{/}2}\mathrm{\parallel }z\mathrm{\parallel }$, this is $\tilde{O}(qK{ϵ}^{-2}(1+b^2\mathrm{/}\mathrm{\parallel }{D}_{i,\ast }{\mathrm{\parallel }}^2))$. Rejection uses $O(K\log (3\mathrm{/}\delta ))$ trials with $O(q)$ queries per trial; forming its weights costs $O(qk)$. Even the looser $\tilde{O}(K{q}^2)$ bound suffices.

Substituting $q=\tilde{O}(K^4\mathrm{/}({\eta }^2{ϵ}^4))$, the base query bound $\tilde{O}(K{q}^2)$ is $\tilde{O}(K^9\mathrm{/}({\eta }^4{ϵ}^8))$, and the SVD time $\tilde{O}(q^3)$ is $\tilde{O}(K^{12}\mathrm{/}({\eta }^6{ϵ}^{12}))$. Since $q\ge {ϵ}^{-2}$, the refined estimate cost in step 6.2 is at most these base bounds times $\tilde{O}(1+b^2\mathrm{/}\mathrm{\parallel }{D}_{i,\ast }{\mathrm{\parallel }}^2)$. On the successful sketch, $D_{i,\ast }=A_{i,\ast }V{V}^T$ and [F1], [F8] give $\mathrm{\parallel }V{V}^T{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}={\lambda }_{\max }(V^{T}V)\le 1+tK\le 3\mathrm{/}2$. Hence $\mathrm{\parallel }{D}_{i,\ast }\mathrm{\parallel }\le (3\mathrm{/}2)b$, so this last factor is $\tilde{O}(b^2\mathrm{/}\mathrm{\parallel }{D}_{i,\ast }{\mathrm{\parallel }}^2)$. Replacing $K$ by $F^2\mathrm{/}{\sigma }^2$ gives the stated powers, with all access preprocessing, precision and writing costs charged separately.