Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study revenue maximization for auctions from samples corrupted by bounded (adversarial) noise. They propose a condition called stability which, together with convergence bounds, guarantees that empirical risk minimization on the sample achieves near-optimal performance on the true distribution. They demonstrate that simple auction formats such as the second-price auctions with reserves satisfy stability. 

Finally, they use stability to help design auctions for multi-task settings where the distribution over values in each task is a translation of the base distribution over values (and the translation is unknown). The main insight is that the samples from other tasks can be appropriately transferred to improve the revenue approximation guaranteed for each task.
  

main_review: This paper builds on a line of recent work on revenue maximization from iid samples. The problem of revenue maximization from samples corrupted by adversarial noise is a natural extension. I found the setup for the multi-task setting and the insight that stability is helpful in this setting to be particularly interesting, and I would encourage the authors to add more detail about these results to the main body of the paper. The paper was well-written and seemed technically sound.

While the proofs that the auction formats were stable were clearly written and seemed technically sound, I did not find the fact that these auctions were stable to be surprising considering the robustness properties proven in previous work (e.g. [29] and (*) below). 

It is not clear that stability holds for revenue-optimal auction formats (i.e. the Myerson auction in the single item setup). Since the goal is ultimately revenue maximization, it seems important to design auctions from corrupted samples that achieve near-optimal revenue across all possible auction formats. 

Another weakness is the assumption that the adversarial noise is bounded, which seems necessary for the proposed stability property to guarantee a high revenue. However, this assumption seems very strong, and it would be interesting to design variants of stability that are suitable for more realistic noise models. 

Minor comments:
-	Parenthesis on last line of Def. 3.1 would help with clarity.

(*) Huang, Liu, and Wang. Learning Optimal Reserve Price against Non-myopic Bidders, 2018. 

——-
Update: Thanks to the authors for their detailed responses. Although investigating the stability of a richer class of mechanisms would provide a more comprehensive picture, the author response has convinced me that their results on multi-item auctions are sufficiently important for acceptance. I have thus decided to raised my score.

limitations_and_societal_impact: The authors adequately discussed the societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides robustness analysis for several existing types of auctions when the empirical bids can be perturbed within an L1 ball. The authors proposed two conditions: p-stable and q-convergent, under which the expected revenue of the empirically
optimal mechanism over the noisy samples is close to the expected revenue of the optimal mechanism in the class. The authors further show that several existing mechanisms satisfy these conditions to various degree.
main_review: Overall I find the paper well-written and the structure is relatively clear. I agree with the authors that robust auction design under noisy empirical data is an important problem with direct practical applications, and the authors did a good job in motivating the importance of auction design with noisy data. 
1. One main concern I have is about the bounded noise assumption, and I would like to see more justification for it in the auction setting. Based on my understanding, this assumption describes the scenario where each bid might be perturbed by a small epsilon distance w.r.t. the original true bids. However, as the authors also mentioned (in Cai and Daskalakis [18]), a seemingly more natural noisy data setting is to consider distributional changes. For example, a small fraction of the bids might be arbitrarily perturbed. The bounded noise assumption seems to be a bit restrictive in the sense that each bid can only be off by a small value.
2. From the results (e.g. theorem 3.6 and 3.9), the revenue loss scales linearly in n / m and epsilon, even for the two classes of mechanisms that are shown to be p-stable and q-convergent. This seems to be a bit unsatisfying especially when n / m and epsilon is large. I would be curious to see if this is the optimal guarantee. 
3. Based on my understanding, some other commonly studied auctions, e.g. second price auction with anonymous price, do not satisfy the p-stable and q-convergent condition. I wonder if the "sensitivity analysis" that the authors presented can provide insights on adapting auctions to be p-stable and q-convergent.
4, As the authors focused on ERM, I would be interested in seeing how the robustness guaranteed by p-stable and q-convergent is reflected in experiments, e.g. with simulated data.

--------------------------
Considering the authors' response, I decide to change my score from 5 to 6.
limitations_and_societal_impact: The authors have addressed the limitations and potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors provide guarantees for optimizing revenue using a learning-based framework over several common mechanism classes when an imperceptible adversarial noise is added to the training set. They then use the guarantees for multi-task mechanism design.  


main_review: - The authors make two original contributions - First, they study learning-based mechanism design under adversarial noise. Despite the volatility of the revenue functions, they conclude through a sensitivity analysis that there isn't a catastrophic loss in revenue when imperceptible adversarial noise is added. They also study the problem of multi-task mechanism design (which unlike existing literature doesn't assume that there is one single distribution defining the buyer's values).
- The paper is well written and easy to read.
- The problem that the authors' study and the results presented in the paper are of interest to both the fields of robust ML and mechanism design.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies the problem of learning revenue-maximizing auction mechanisms from samples when the observed samples may be adversarially corrupted. It shows that just applying ERM will still work well in terms of performance and sample complexity. It also shows that a particular multi-task version of the auction learning problem can be reduced to the problem of learning under adversarial noise, and so ERM will also work for this problem.

main_review: Longer summary:

The paper considers the problem of learning an auction from samples when the samples may be corrupted by decreasing valuations by epsilon. (Not quite the same thing as $\ell_\infty$ adversarial corruption, but close). The core claim of the paper is that ordinary ERM still works well for many classes of auctions.

The general quantity of concern is difference between mean revenue of the auction learned on true data, and mean revenue of the auction learned on noisy data. Various techniques are presented for bounding this quantity with high probability. In particular, the authors show that if a class of mechanisms is p-stable (on average over true samples, the mechanisms learned on corrupted and true data have revenue bounded by p) and q-convergent (simply a normal error bound on empirical vs. mean revenue). The classes of mechanism studied in the paper are already known to be q-convergent for various q, so by showing this result and then providing a bound of p-stability for each mechanism, it's shown that ERM works well.

In one additional case (item-price mechanisms with unit-demand buyers), p-stability does not hold. However, if it is assumed that the bidder's valuation vectors are well-dispersed (which holds with high probability if the joint valuation distribution is smooth in the sense of never having a peak density larger than $\kappa$), ERM again works well.

Finally, a limited but plausible multi-task version of the auction learning problem is defined, inspired by the common-base value model of auctions. Given multiple datasets with different, unknown base values, one can compile a larger training set which has only small errors with high probability. Learning on this new dataset is equivalent to learning under noise, so the results above showing that ERM works well also work.

Originality:

The paper leans heavily on existing theoretical results and techniques for learning auctions from samples (e.g. $\kappa$-boundedness of valuation distributions, dispersion). However, it is definitely still original.

Quality:

The paper is high quality and well argued. 

Clarity:

The NeurIPS page limit has produced some unavoidable fragmentation but there's nothing to be done about this.

Significance:

The problem is an important one. It's rare to have a large supply of truthful valuations to learn an auction, and even if they are available those valuations might shift over time. So understanding how to learn auctions robust to corrupted data is an important part of the overall project of learning auctions. The results don't present any new techniques to use, but rather show that naively training on the corrupted dataset should still work well, which is surprising and interesting.

Other comments:

There is a large body of research on learning auctions in the face of distributional adversaries. Two arbitrary examples:

Koçyiğit et al., Distributionally Robust Mechanism Design

Bergemann et al., Robust Monopoly Pricing

This is a different problem than what is addressed in this paper (which is particularly concerned with learning from samples, and does not present new learning algorithms, but rather shows that the naive approach is already fairly robust). But it is related, and I was surprised not to see any of this work even cited in the appendix. 

Given the discussion of ICML 21 reviews, it's possible this material was cut to prevent confusion, but I think it might be worth mentioning some of it.

There is also some adversarial robustness literature briefly cited, but only work focusing on test-time evasion attacks. I don't think it's essential to the message of the paper at all, but it couldn't hurt to cite some of the work on poisoning, where the training dataset is corrupted, as this is closer to the setting studied in this paper.

Final update: I enjoyed reading this paper and my opinion remained positive after the discussion period.
limitations_and_societal_impact: This is a theory-heavy paper that is unlikely to have much direct social impact, and the authors are very clear about the scope of their results.
review_title: null

Meta-review: The paper studies the revenue-optimal mechanism design when the bidder value distribution can be corrupted by bounded adversarial noise. This is a nice contribution and a good fit to NeurIPS.
Decision: Accept (Poster)