Summary
The paper studies Bayesian approximate mechanism design in a structured world, where each bidder's preferences can be roughly captured by a "topic model", i.e., the true valuation function is close to a linear combination of a few representative valutions. Inspired by prior work, the paper follows a two-stage design: the seller first "queries" each bidder and tries to recover the bidder's latent valuation (i.e., coefficients corresponding to the representative valuations) Then, with the recovered approximate latent valuations, the seller constructs a mechanism by placing blackbox queries to a good mechanism in the latent space. (Importantly, it is assumed that we already know a good mechanism in the latent space.) The main result is a design that requires much milder regularity conditions on the representative valuations, which also requires less communication with bidders. The new design works for metrics induced by $\ell_p$ norms for $p \in [1, \infty)$ whereas prior work focuses on the $\ell_\infty$ norm.
Strengths
The paper is fairly well organized. In particular, the authors clearly explain their technical contributions in the main paper without giving too much detail, which I appreciate very much. The paper studies a sensible and well recognized problem and makes solid progress. Conceptually, I like the "observation" that designing the query scheme is really closely related to central problems in numerical linear algebra, which indeed enables the authors to borrow ideas from that extremely rich body of research. Technically, the authors give a good overview of their approach, and I'm convinced that there are nontrivial ideas involved.
Weaknesses
The paper is (unavoidably) a bit dense with heavy notation, etc. I think it would help to use a simple running example to illustrate how things work. The mechanism is also a bit complex, which is not ideal but perhaps hard to avoid too.
Questions
(Also including detailed comments here)
Line 42, "... often depende on the number of items m, which could be prohibitively large ...": while this claim is largely true, I wonder to what extent this is because of the intrinsic richness of information induced by heterogeneous items. E.g., if all items are the same then at least the amount of communication needed shouldn't depend on m. Can you comment on this?
Line 69, conditions on A: do you mean "(i), (ii), *or* (iii)"?
Line 149, $v_i: \mathbb{R}^d \times [0, 1])^m \to \mathbb{R}_+$: so the allocation of a mechanism is one number between [0, 1] for each item? Is this general enough when bidders have non-additive valuations (e.g., a randomized mechanism may need to specify how items correlate in addition to the marginal probabilities)? Or do you really mean $\{0, 1\}^m$?
Line 154, "$x: \mathbb{R}_+^{nd} \to [0, 1]^{nm}$": again, why output only the marginal probabilities here?
Line 219, "we don't have bounds of the form ...": this is a bit confusing at this point because Definitions 3 and 5 both talk about bounds precisely of this form. Can you clarify?
Line 323, Theorem 2: here you do write "$v_i: \mathbb{R}^d \times 2^{[n]}$". Would be nice to be consistent (also see earlier comments).
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.