$\displaystyle\|\tilde{\mathbf{z}}-\mathbf{z}\|_{\infty}$
$\displaystyle\leq\varepsilon_{\texttt{nq},\infty}\|(\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A})^{\dagger}\|_{\infty}\|\mathbf{D}_{\infty}\|_{\infty}\|\mathbf{S}_{\infty}\|_{\infty}$
$\displaystyle\quad+\|(\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A})^{\dagger}\|_{\infty}\|\mathbf{D}_{\infty}\|_{\infty}\|\mathbf{S}_{\infty}\|_{\infty}\|\mathbf{t}-\mathbf{A}\mathbf{z}\|_{\infty}$
$\displaystyle\leq\varepsilon_{\texttt{nq},\infty}\|(\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A})^{\dagger}\|_{\infty}\|\mathbf{D}_{\infty}\|_{\infty}+\varepsilon_{\texttt{mdl},\infty}\|(\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A})^{\dagger}\|_{\infty}\|\mathbf{D}_{\infty}\|_{\infty}$
$\displaystyle=(\varepsilon_{\texttt{nq},\infty}+\varepsilon_{\texttt{mdl},\infty})\|(\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A})^{\dagger}\|_{\infty}\|\mathbf{D}_{\infty}\|_{\infty}$
$\displaystyle\leq(\varepsilon_{\texttt{nq},\infty}+\varepsilon_{\texttt{mdl},\infty})\sqrt{s_{\infty}}\|(\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A})^{\dagger}\|_{2}\|\mathbf{D}_{\infty}\|_{\infty}$
$\displaystyle\leq\sqrt{s_{\infty}}(\varepsilon_{\texttt{nq},\infty}+\varepsilon_{\texttt{mdl},\infty})\sigma_{\min}^{-1}\left(\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A}\right)\|\mathbf{D}_{\infty}\|_{\infty},$
(20)

where for a matrix $\mathbf{X}\in\mathbb{R}^{m\times n}$ we have
$\|\mathbf{X}\|_{\infty}=\max_{i\in[m]}\sum_{j=1}^{n}{|\mathbf{X}_{ij}|}$ and
$\|\mathbf{X}\|_{2}=\max_{\|\mathbf{y}\|_{2}=1}{\|\mathbf{X}\mathbf{y}\|_{2}}=\sigma_{\max}(\mathbf{X})$.
In the above we used that fact that $\|\mathbf{S}_{\infty}\|_{\infty}=1$,
since $\mathbf{S}_{\infty}$ is a sampling matrix and the property
$\|\mathbf{X}\|_{\infty}\leq\sqrt{n}\|\mathbf{X}\|_{2}$ for any matrix
$\mathbf{X}\in\mathbb{R}^{m\times n}$. The use of eqn. (19) instead of eqn.
(18) improves the bound of [CD22] by avoiding an extra $\sqrt{k}$ term and a
quadratic dependency on
$\sigma_{\min}\left(\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A}\right)$.

The bound of eqn. (20) generalizes the bound of [CD22] to allow for sampling
and rescaling of the revealed noisy bidder preferences, as well as the
corresponding rows of the archetype matrix $\mathbf{A}$, following the lines
of Algorithm 1. It is important to note that in order to get meaningful
results using the bound of eqn. (20), we need a lower bound on
$\sigma_{\min}\left(\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A}\right)$
and an upper bound on $\|\mathbf{D}_{\infty}\|_{\infty}$. The approach of
[CD22] has no rescaling: it sets $\mathbf{D}_{\infty}=\mathbf{I}$ and,
therefore, $\|\mathbf{D}_{\infty}\|_{\infty}=1$. However, this makes it hard
to get non-trivial lower bound for the smallest singular value of the matrix
$\mathbf{S}_{\infty}\mathbf{A}$. This matrix is simply a sample of rows of the
matrix $\mathbf{A}$ without any rescaling and its smallest singular value
could, in general, be arbitrarily close to zero. As a result, only special
cases of the archetype matrix $\mathbf{A}$ were analyzed in [CD22]: for those
special cases, the smallest singular value of a sample of rows of the input
matrix (without rescaling) can be lower bounded. It is a well-known fact that
if one were to form the sampling matrix $\mathbf{S}_{\infty}$ and the
rescaling matrix $\mathbf{D}_{\infty}$ using Algorithm 1 and the row leverage
scores of $\mathbf{A}$ as the sampling probabilities, the smallest singular
value of $\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A}$ would be close to
the smallest singular value of $\mathbf{A}$. This, however, cannot be done
without rescaling, which would necessitate an upper bound on
$\|\mathbf{D}_{\infty}\|_{\infty}$. As a concrete example, if all the row
leverage scores of $\mathbf{A}$ were equal, as would be the case if
$\mathbf{A}$’s columns were a subset of the columns of a Hadamard matrix, the
sampling probabilities would all be equal to $\nicefrac{{1}}{{d}}$. In this
case, the diagonal rescaling matrix $\mathbf{D}_{\infty}$ has entries that are
propotional to the reciprocal of the sampling probabilities and
$\|\mathbf{D}\|_{\infty}=\sqrt{\nicefrac{{d}}{{s_{\infty}}}}$. This makes the
overall error bound depend on the number of bidder types $d$, since
$s_{\infty}$ (the query complexity) is much smaller than $d$. This tension
between lower-bounding the smallest singular value of
$\mathbf{D}_{\infty}\mathbf{S}_{\infty}\mathbf{A}$ and upper bounding the
infinity norm of $\mathbf{D}_{\infty}$ does not seem easy to resolve by
following the proposed analysis for arbitrary archetype matrices
$\mathbf{A}\in\mathbb{R}^{d\times k}$.

####  D.4.1 Discussing the assumptions of [CD22] for the archetype matrix

We conclude this section with a brief discussion of the three settings of
Theorem 2 of [CD22] for the archetype matrix. First, for the deterministic
structure, the assumption on the archetype matrix
$\mathbf{A}\in\mathbb{R}^{d\times k}$ is that it has to contain a square
$k\times k$ submatrix $\mathbf{C}$, which is both row- and column-diagonally-
dominant. It is unclear whether this is a reasonable assumption in the context
of archetype matrices; some connections with the non-negative matrix
factorization literature are briefly discussed [DS03]. Importantly, it is
unclear what the query protocol $\mathcal{Q}$ will be in this setting, since
the query matrix $\mathbf{Q}$ has to satisfy
$\mathbf{Q}\cdot\mathbf{A}=\mathbf{C}$ and it is not obvious how to recover
$\mathbf{Q}$ if $\mathbf{C}$ is unknown. The other two settings are both
probabilistic and draw $k$ archetypes either from a $d$-dimensional Gaussian
distribution, or as copies of a $d$-dimensional random vector. In both cases,
the archetypes are drawn from distributions that are designed to construct
matrices whose columns are approximately orthogonal, at least in expectation.
This observation results in large values for $\sigma_{\min}(\mathbf{A})$, and,
under additional technical assumptions stated in Theorem 2 and Proposition 1
of [CD22], large values for the smallest singular value of
$\mathbf{S}_{\infty}\mathbf{A}$. Our work directly characterizes the sample
complexity of the protocol in terms of a single parameter of the archetype
matrix that, intuitively, measures archetype independence with respect to
$p$-norms. We provide explicit query protocols that leverage information in
the archetype matrix and achieve the promised query complexity. We believe
that this is a natural way to connect mechanism design with active learning
for regression problems.