Safely Learning Optimal Auctions: A Testable Learning Framework for Mechanism Design
Authors: Vikram Kher
Manolis Zampetakis
Venue: ICML 2025 poster (2025)
Keywords: Auction Theory
Mechanism Design
Testing Distributional Assumptions
Primary area: theory->game_theory
TL;DR: We develop a testable learning framework for mechanism design and apply it to important theorems in auction theory.

Abstract: When can the distributional assumptions of theorems and learning algorithms be trusted? Inspired by this question, Rubinfeld and Vasilyan (2023) initiated the study of testable learning. In this schema, we always learn one of the following two things: either we have achieved the desired accuracy regardless of whether the distributional assumptions are satisfied, or the input distribution does not satisfy the original distributional assumptions. Motivated by the challenge of relying on strong distributional assumptions in many theorems in mechanism design, we develop a testable learning framework for mechanism design. Traditional models in mechanism design assume that value distributions satisfy some notion of regularity. Unfortunately, testing regularity is not possible in the original testable learning framework as we show. To bypass this impossibility, we propose a regularized version of the testable learning framework. Under this framework, we always learn one of the following two things: either we achieve high revenue compared to the best possible revenue of any regular distribution close to the input distribution, or the input distribution does not satisfy regularity. We then use this framework to provide: 1) a tester-learner pair for revenue optimal mechanisms, 2) a tester for whether the fundamental Bulow-Klemperer Theorem (Bulow and Klemperer 1996) is applicable to a given dataset, and 3) a tester to confirm the existence of an anonymous reserve price that results in the anonymous price auction securing a constant fraction of the optimal revenue.

Safely Learning Optimal Auctions:
A Testable Learning Framework for Mechanism Design
Vikram Kher' Manolis Zampetakis
Abstract
1. Introduction
Data science field with celebrated applications across many scientific disciplines. Many important statements and algorithms in data science require distributional assumptions on the data that is being analyzed. In physical sciences, a common distributional assumption is the Gaussianity of the underlying data, whereas in social sciences and economics more heavy-tailed distributions arise (Clementi Galle- gati, 2005). An instantiation of this phenomenon appears in learning theory well, where strong computational impos- sibility results for agnostic learning prevent general learning guarantees and to bypass these lower bounds it is common to assume that the marginals are uniform or Gaussian (Kalai et al., 2008; Diakonikolas et al., 2021). A natural question to ask in all these settings the following: How can we infer which statements or algorithms can be applied in a given dataset? A straightforward way tackle this question would be to design testing algorithm that can help us dis- tinguish which of the distributional assumptions are satisfied by the given dataset. Unfortunately, directly verifying these assumptions is often computationally intractable (Goldreich, 2017). This brings us back to a dilemma for a given dataset: should we use methods that have stronger guarantees but require stronger distributional assumptions? Or, should use methods that have weaker guarantees but are applicable in settings with fewer assumptions?
When can the distributional assumptions of theo- rems and learning algorithms be trusted? Inspired by this question, Rubinfeld & Vasilyan (2023) initiated the study restable learning. In this schema we always learn one of the following two things: either we have achieved the desired ac- curacy regardless of whether the distributional assumptions are satisfied, or the input distribution does not satisfy the original distributional assump- tions. Motivated by the challenge of relying on strong distributional assumptions in many theo- rems in mechanism design, we develop a testable learning framework for mechanism design. Tradi- tional models in mechanism design assume that value distributions satisfy some notion of regu- larity. Unfortunately, testing regularity is not possible in the original testable learning frame- work as we show. To bypass this impossibility, we propose regularized version of the testable learning framework. Under this framework, we always learn one of the following two things: ei- ther we achieve high revenue compared to the best possible revenue of any regular distribution close to the input distribution, or the input distri- bution does not satisfy regularity. We then use this framework to provide: 1) a tester-learner pair for revenue-optimal mechanisms, 2) a tester for whether the fundamental Bulow-Klempend Klemperer The- orem (Bulow & Klemperer, 1996) is applicable to given dataset, and 3) tester to confirm the existence of an anonymous reserve price that re- sults in the anonymous price auction securing a constant fraction of the optimal revenue.
Motivated by this dilemma, the recent breakthrough work of Rubinfeld & Vasilyan (2023) introduced the framework of testable learning wherein a learning algorithm paired with a tester which satisfies the following properties: (1) if the tester accepts, then we can be confident that the learning algorithm is applicable to our dataset, whereas (2) if the tester rejects, then we know that the distributional assump- tions are not satisfied. This allows us to bypass the lower bounds of testing distributional assumptions because the case that the tester accepts we cannot make any conclusions about the distributional assumptions; we only know that the learning algorithm succeeds. Rubinfeld & Vasilyan (2023) develops computationally efficient tester-learner pair for agnostically learning half-spaces over Gaussians and the uniform hypercube. Many works have since followed that successfully apply this testable learning framework to va-
'Department of Computer Science, Yale University, Connecticut, USA. Correspondence to: Vikram Kher <vikram.kher@e @ule.....
Proceedings of the 4rnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Safely Learning Optimal Auctions
riety of different settings (Diakonikolas et al., 2023; Klivans et al., 2024; Gollakota et al., 2023a;b; 2024).
Completeness: If distribution D is close to some D' E DD then w.h.p. T should accept D on input.
In the context of mechanism design, there are distributional assumptions that underline the vast majority of results in single-item revenue maximization. When the distribution is explicitly known, Myerson (1981) effectively solved this question through his characterization of virtual valuation functions. For each bidder i [n], who draws their value from distribution with edf (.(e) and pdf fe(), Myerson (1981) I) defined their virtual value function to be
This is relaxation of the testable learning framework of Rubinfeld & Vasilyan (2023), due to the highlighted bold part in the soundness condition. The original definition of soundness from Rubinfeld & Vasilyan (2023) requires the learner to achieve good objective performance relative to the optimum concept of the distribution itself. In our setting, the family of distributions D is regular distributions and the optimal concept of any distribution D D is its Myerson optimal mechanism (Definition 6). Furthermore, in our setting, two distributions are close to each other if they have small Kolmogorov-Smirno distance (Definition 9).
6.(0)= = 1- F(()) fi(v)
If (v) is non-decreasing, then the underlying distribution is called regular. The use of regularity in mechanism design dates back to the celebrated work of Myerson (1981), and has remained a highly influential concept in auction theory ever since. Given that regularity is crucial many results and methods in mechanism design, it is natural ask the following question:
We formally introduce the regularized testable learning framework in Section 3. In Section we also show a proof that the original testable learning framework cannot give us nontrivial results in the revenue maximization setting. We instantiate our framework in the following settings:
(1) Learning Revenue-Optinal Mechanisms (Theo- rem 6). Under this model, first proposed by Cole & Rough- garden (2014), the goal is to characterize how many samples are needed to achieve a (1 - e) multiplicative approxima- tion to the revenue of the optimal mechanism. In a unify- ing result, Guo et al. (2019) effectively settled the sample complexity of single item revenue maximizing auctions by providing tight upper and lower bounds (up to poly-log fac- tors). Drawing an interesting connection with the work of Guo et al. (2021), we introduce a parameter a such that on an input distribution D our learner should output a mecha- nism M such that Rev(M. D) 2 (1 - (()))OPT(D)) for every regular distribution D' that is a-close in Kolmogorov- Smirnov (KS) distance (if the tester accepts). Importantly, if there is no a-close regular distribution, then our learner bears no guarantee. We present these results in Section 5.
Question:
When is it safe to apply methods that are based on regularity in an auction setup?
Our Contribution. In this work, our goal is to answer the question above by adapting the aforementioned frame- work of testable learning in the field of mechanism design. We first observe that a vanilla application of the testable learning framework of Rubinfeld & Vasilyan (2023) is not appropriate for mechanism design (see Section 3.1). Then, we introduce relaxation of this framework that we call Regularized Testable Learning, which relaxes the learning guarantee that we have when the tester algorithm accepts. This new framework allows us to build a powerful tester that distinguishes whether many theorems and methods in revenue maximization are applicable a given data source. We believe our framework will have applications beyond just the study of revenue-maxinizing mechanisms.
(2) Competition vs Optimality (Theorem 8). Bulow- Klemperer Theorem (Bulow & Klemperer, 1996) is a well- known result in auction theory that states that when the value distributions of the bidders are i.i.d. and regular, then the revenue of simple Vickrey auction with one additional player is higher than the revenue of an optimal mechanism for one less bidder, that is, competition in the i.i.d. setting is more important than optimality. The proof of this result heavily relies on the fact that the value distributions are regular. In Section 6 we show that there a regularity tester, based on samples from the value distributions, that: (I) when it accepts, then the conclusion of Hulow-Klemperee Theorem holds, and (2) when it rejects, then the value distri- butions are certainly irregular. This gives nice per-instance test of whether Bulow-Klemper 's result is applicable or not.
1.1. Our Results
Our primary conceptual contribution is our Regularized Testable Learning framework. In regularized testable leam- ing, we are informally guided by the following principles. Let C be a learner for the concept class C' with respect to a family of distributions D and a hypothesis class H. T a tester for the distributional assumptions of L then the following should hold:
> Soundness: If T accepts distribution D, then w.h.p. L should output a hypothesis which achieves good objective performance on D relative to the optimum concept of any close distribution to D in D.
(3) Anonymous Price Auctions (Theorem 10). A well-
2

---

Safely Learning Optimal Auctions
known result by Hartline & Roughgarden (2009); Alaei al. (2019) states that when the value distributions are reg- ular but not symmetric, the auction that sets an anonymous reserve price, i.e., a reserve price that is the same for all bidders, achieves a constant fraction of the optimal revenue of Myerson's auction. This result also relies heavily on the regularity of the value distributions, and hence it makes sense to ask if there is a way to test if this result is applicable or not. Similar to the previous case of the Bulow- nallow-llempere Theorem, we provide a tester that: (1) when it accepts, then anonymous price auctions achieve a constant approximation of the optimal revenue, whereas (2) when it rejects, then the value distributions are certainly irregular. We provide details on this Section 7.
uniform hypercube. Subsequent work by Gollakota et al. (2023b) gave testable learners for any concept class which admits low-degree sandwiching polynomials assuming the marginal is strongly log-concave. More recently, Gollakota et al. (2023a) showed testable learners for half-spaces for any marginal distribution that satisfies a Poincaire inequality. The testable learning framework has also been applied to settings that involve distribution shift and adversarial label noise (Diakonikolas et al., 2021; Klivans al., 2024).
Simple versus optimal auctions. A fruitful line of research has explored whether revenue-optimal mechanisms can be well approximated by simpler mechanisms. Several impor- tant results in this line of research include Bulow & Klem- perer (1996); Hartline & Roughgarden (2009); Alaei et al. (2019); Chawla et al. (2010); Haghpanah & Hartline (2015). A key assumption underlying many of these results is that the underlying distribution is regular. Lastly, Devanur et al. (2016) developed a key revenue monotonicity result that facilitates comparing the revenue of different mechanisms through the notion of first-order stochastic dominance.
Finally, in Section& 8 we show a single-bidder lower bound for the sample complexity of regularized testable learning for revenue maximization.
Novelty of Results. Under our framework, we obtain the first nontrivial revenue guarantees for learning single- item auctions when the bidders draw their values from un- bounded, irregular distributions. In contrast, previous work on learning irregular auctions (e.g.. Guo et al. (2019) and Roughgarden & Schrijvers (2016)) delivers sample com- plexity results that scale with an upper bound on the support of the distribution. By dropping this dependence, our frame- work is applicable to many new settings, such as when the underlying distribution is a mixture of Gaussians. Mixture models, like the previous example, commonly arise mar- ket settings when sampling from heterogeneous population (Sivan& & Syrgkanis, 2013).
2. Preliminaries
2.1. Auction Model
We focus on the fundamental single-item, n-bidder mecha- nism design setting. We assume each bidder draws their nonnegative valuation from an (unknown) distribution D; with a cumulative distribution function (cdf) of (x(x). For a given cdf F(z). we define its (reverse) quantile function as ((x))
- F(x). In other words, g(z) is the proba- bility of sale if a item is posted at price of x. We let ..., un)) denote the vector of valuations which e = (v),
1.2. Related Works
follows the product distribution D = 1; Henceforth, we utilize bold font to denote product distributions, which are typically (unless otherwise stated) over n bidders. We assume the auctioneer only has sample access to D rather than explicit knowledge of the distribution function.
We briefly outline three lines of relevant research for design- ing revenue-optimal mechanisms and testing the distribu- tional assumptions of learning algorithms.
Sample complexity of learning optimal auctions. Cole & Roughgarden (2014) first proposed studying the num- ber of samples needed to achieve a (1 e) multiplicative approximation to the optimal mechanism. Further work followed in single parameter settings (Huang al. (2015) and Roughgarden & Schrijvers (2016), among others) cul- minating in the result of Guo et al. (2021) that provided tight bounds (up to poly-log factors) on the sample com- plexity of learning single item auctions. A related line of research has explored the robust learning of mechanisms from noisy or corrupt samples in both single-parameter and multi- parti-parameter settings (Guo et al., 2021; Brustle et al., 2020; Cai & Daskalakis, 2017).
A mechanism M consists of an allocation function x and payment function p. To run an auction, M takes input vector of bids b = (b. ..., b,)) and allocates the item according to (b) E 10, where Σ (b) < 1, and charges bidders according to p(b) E R". For a vector of bids 6, each bidder i receives the item with probability x, (b) and pays ps (l). The utility of bidder is (b). = v,rr (6) (b). The seller's goal is to find a mechanism that maximizes the expected value of the payments (i.e., maximizes E (b)).
We restrict our attention to mechanisms which satisfy Domi- nant Strategy Incentive Compatibility (DSIC) and Individual
Testable Learning. The testable learning framework was first proposed by Rubinfeld & Vasilyan (2023) in the context of agnostically learning half-spaces over Gaussians and the
3

---

Safely Learning Optimal Auctions
Rationality (IR):
Before introducing the corresponding lemma, we recall the definition of first-order stochastic dominance.
(DSIC) uy (u, b-1) 2 (b(b,, b-i) for all i E [n], 04 by Rz0 and b E R200
Definition 4 (First-Order Stochastic Dominance). For two distributions D and D'. We say that D (firstooder) stochas- rically dominates D' (denoted by D = D')
(TR): (u b-:) 2
for all i E [n]] 14 E Rz0 and b_; E R220
FD(x) S FD)
where b-; denotes the vector of bids from every agent except bidder i. The DSIC constraint ensures that bidder maxi- mizes their expected utility by truthfully bidding their value for an item, regardless of what other bidders do. The IR constraint ensures that a bidder's utility for participating in the auction always nonnegative when they bid truthfully.
for all 2 A product distribution D stochastically dominates another product distribution D' if D; = Di all i E [m].
Lemma 1 (Lemma 3,4 of Guo et al. (2021)). A distribution D is regular iff its link function h(z; F) is a convex function of x. Moreover, for two distributions D and D', , if D first- order stochastically dominates D' then h(r; F) S h(x; F') for all O.
2.2. Reyenul-Optimal Auctions
In this section, we outline a variety of useful theorems and definitions that we will refer to throughout the paper. A natural starting point to define the expected revenue distribution. mechanism.
Later on, it will be useful to take the convex envelope of non-convex link function in order find a close regular
Definition 5 (Convex Envelope). The convex envelope of function f denoted by Conev()) is the maximum convex lower bound of f. i.e.,
Definition 1 (Expected Revenue of Mechanism). The ex- pected revenue of mechanism M distribution D is denoted by
Conv(f) = sup(g(x)) g is convex
Σ Ealoos
Rev(M,D)=
E (ni D
and g(x) S f(x) for all x E [Rzo)
For distribution D, we abuse notation by writing Conw (D) to denote the convex envelope of the distribution' 's link func- tion.
The Myerson optimal mechanism for D, which we refer to as MD. maximizes this expectation and has expected revenue equal (D).
Myerson (1981) fully characterizes the optimal single-item, multi-bidder mechanism, among all mechanisms that are DISC and IR compliant.
When important in context, we use the notation Rev, (M, D) to denote the revenue when mechanism M is run n i.i.d. bidders from the distribution D. In My- erson (1981), 1), they introduce the fundamental notion of regular distribution.
Definition 6 (Myerson's Optimal Mechanism). For a regu- lar product distribution D, the Myerson optimal mechanism MD awards the item the bidder i with the highest non- negative virtual valuation (if such bidder exists). The winner in turn pays o; (0o), where do is the maximum of O and the second highest virtual value.
Definition (Regularity). A distribution D with cdf F and density f is called a regular distribution if its corresponding virtual value function Φ(v) = V f(o)
L-F(u) is monotonically
non-decreasing for all 2 0. A product distribution D is
regular if D; is regular for all E [n].
Although Myerson's mechanism is optimal, it requires knowledge of the distribution function. Hence, simpler mechanisms such as the Vickrey auction and the anony- mous price auction are also of interest to auction designers.
In Guo et al. (2021), they provide an equivalent characteriza- tion of regularity through their definition of a distribution's link function.
Definition (Link Function). Let be a distribution with cdf Fx)). The link function of D is defined as
Definition 7 (Vickrey Auction). The Vickrey auction, de- noted by VA, awards the item to the highest bidder and charges them price equal to the second highest bid.
1
h(;; F)
I F(x)
Definition 8 (Anonymous Price Auction). The anonymous price auction with reserve p", denoted by APA(p") awards the item to the highest bidder if their bid is at least p". The auction then charges them a price equal to the maximum of the second highest bid and p²
We correspondingly denote the inverse of the link function as
h 1x; = 1
h(x))

---

Safely Learning Optimal Auctions
2.3. Revenue Monotonicity
to bound the KS distance between an empirical distribution and true distribution.
Often, we will need to compare the revenue of mechanism on competing distributions. The work of Devanur et al. (2016) provides convenient way to accomplish this through first-order stochastic dominance.
Definition 11 D
(DKW) in- cquality (Dvoretzky et al., 1956; Massart, 1990)), Given n samples (Xi)i=1 from a distribution D. the empirical dis-
tribution Dn with edf F = n "E= 1x,50 satisfies the following inequality:
Theorem 2 (Strong Revenue Monotonicity (Devanur et al., 2016)). Given two product distributions D and D' such
that D = D', it holds that
Pr(dks(Dn: D) c) S 2e 2nc?
MDD, D) 2 Reu(MD: =
3. Regularized Testable Learning
2.4. Probability Metries
As we explained above in many applications of auction theory, the regularity of the value distributions is assumed. Yet, it is not clear if we can test whether a given set of samples is drawn from distribution that is regular. If such a test existed, would allow us to know when we may apply certain results that require regularity source of data. In fact, in this section we show that we cannot efficiently test regularity directly, which motivates our regularized testable learning framework.
To compare how close two distributions are, we will use Kolmogorov-Sning -Siinoov distance.
Definition 9 (Kolmogorov--Simnl))
Distance). For two dis- tributions D and D', the Kolmogonov-Smirnon (KS) distance between D and D' is denoted by
particular
dxs(D, D, D') suplFo(()) (x)(
zER
We first show in Section 3.1 that no meaningful result can be derived for revenue optimization using the original frame- work of Rubinfeld & Vasilyan (2023). We then present our new framework of regularized testable learning in Sec- tion 3.2, which we subsequently use to prove revenue guar- antees in Section 5.
For a given distribution D, we denote the set of all distribu- tions that are a-close to D in Kolmogorov-Smirro distance by BKS,a (D) = (D'= dRs(D', D) S a.). A product dis- tribution D a-close in Kolmogorov-Smimoo distance to another product distribution D' dds(D',, D,) S for all
i [m].
For Kolmogorov-Smimee ball (a),a we define the minimal regular distribution Dunn in this ball to have cdf F (z) = h (x; h), where
3.1. Testing Regularity for Revenue is Hard
To motivate Definition 14, we will show that is impossible to design a tester-leamer pair with nontrivial guarantees for revenue- maxinneiimxiizzingggg auctions under the conventional learning and testing benchmarks defined below.
M(x))
max (xF)(x)) for all x E TR..
... Dt regular
Definition 12 (Conventional Learner). A family of distri- butions D has a f(e, ö, -)-covventio learner L if given access to J(e, 5, n) i.idd sumples from D E D, C. oulputs a mechanism M such that Rev(M, D) 2 (1 (1- (1-c))PT(D) with probability at least 1 -8.
In addition to KS distance, we will also utilize Kullback- Leibler Divergence to establish lower bounds on the min- imum number of samples required to distinguish between two close distributions.
Definition 13 (Conventional Tester). An algorithm 'T is h(c, 5, conventiool tester for the class of regular distri- butions with respect to a learner L. if it satisfies two con- straints.
Definition 10 "Kulbbcck-Lebble Divergence). The Kullback- Leibler (KL) divergence between two distributions D and D' with pdfs (D) and (u) is
dxz(D'IID) = EE In fD-(U) fo(u)
Soundness: Suppose T is presented with h(c, 8, n) Li.dd. sumples from distribution D and ouiputs "Yes" with probability at least 1 1-8. Then, the conventional learn- ing guarantee of Definition 12 should be achieved.
For a given distribution D, we denote the set of all dis- tributions which are c-close D in KL divergence by BLL.
( (D) (D' dx<(D")( S a). A product dis- tribution D' is a-close in KL divergence to another product distribution D if " (D,l D.) Sa.
Completeness: Suppose T is presented with ia(e, 8, n) i..dd samples from a distribution D that is regular, then T should output "Yes" with probability least 1 8.
Finally, for completeness, we also include a definition of the Dvoretzky-Kied -ieee---eeeeeeefooiiiiii Wolfowitz inequality, which is used
Under this definition, the learner must output a mechanism which achieves good revenue on the distribution relative
5

---

Safely Learning Optimal Auctions
to its optimal mechanism. The cnux of the issue with Def- initions 12 and 13 is learning the optimal mechanism for an irregular distribution is generally infeasible. We demon- strate this in the following theorem by showing that we cannot simultaneously satisfy the soundness and complete- ness conditions present in Definition 13.
to I [' 8,n) i.i.d samples from D, L outpuis mechanism M such that with probability 1 -
Rev(M, 2 (1- g(a.a
for all regular distributions D' that are a-close in KS dis- tance to D.
Let L be [(, 6, ne)-corventional learner. For any fixed number of samples m = hh(a, 6, n), there does not exist a m-conventional tester for L.
Theorem 3.
Definition 15 (Regularized Tester). An algorithm T is a h(a, 5, n)-regularized tester for the class of regular distri- butions with respect to a learner if it satisfies two con- straints.
Proof. Suppose for a contradiction that there exists a m- conventional tester T. Without loss of generality, assume that 8 1/4. We begin by constructing family of counter-examples parameterized by y. Let D2 be the stan- dard uniform distribution over the interval [0, 1] and let D2 be a mixed distribution; with probability - 7, it is uni- form over [o, 1] and with probability y it is uniform over straightforward to verify that Dj is
Soundness: Suppose T is presented with h(a, 8,n) ii.dd samples from a distribution and outputs "Yes" with probability at least 1 Then, the regular- ized learning guarantee of Definition 14 should be achieved.
(21/%, 22/7 + +1. regular and D2 is irregular by examining the convexity of their respective link functions.
Completeness: Suppose T is presented with h(a, 8, i.i.d. samples from a distribution D that is a-close in Kolmogorov-Sminno distance a regular distribution. then T should output "Yes" with probability at least 1- 6.
Without loss of generality, we will compare the distribu- tions in terms of KL-divergence since dxs (D1, D2) = S In - 7) = (c.g.. Huang et al. (2015)) that any algorithm which dis- tinguishes between D₃ and D2 with probability at least 3/4 requires at least (DI((D))
It is well-known
In -1)---
Compared to the conventional learner, Definition asks the regularized learner to produce a mechanism that gener- ates strong revenue compared to the optimal mechanism of any nearby regular distribution. We correspondingly alter the completeness guarantee of Definition 13 to ensure that w.h.p. the regularized tester accepts any distribution that is sufficiently close to a regular distribution. This alterna- tion allows us to prove meaningful revenue guarantees for unbounded, irregular distributions that are close to regular distributions. Although the above formulation is specific to the setting of learning revenue optimal auctions, in Ap- pendix G we present generic formulation of regularized testable learning that is applicable to broader range of learning tasks.
many samples. Myerson (1981) dictates that MD, sets reserve price of 1/2 and Rev(MD, D1) 1/4. It is simple to show that MD, sets reserve price of 2//r and Rev (M,, D2) = 72//7, Then,
lim Rev(MDa D2) lim 4/22/7 co. 7-40 Rev( (Mp,: D1) 70
T accepts D1 with probability at least 3/4, then T must accept D2 with at least probability 3/4 since for some > the two distributions are indistinguishable with only m sam- ples. This violates soundness, as the revenue-maximing auction for D2 cannot be learned with m samples. In par- ticular, if the mechanism could be learned, then we could use the learner to distinguish between the two distributions. Alternatively, if T rejects D with at least probability 1 //4, then completeness is violated, since D2 is a regular distribu-
4. A Regularized Tester for Revenue-Optimal Mechanisms
tion.
In this section, we present our regularized tester for revenue- optimal mechanisms and justify its function in relation to the learning guarantee of Definition 14. More precisely, any regularized learning algorithm should output a mechanism that performs well the input distribution compared to the optimal revenue of any close regular distribution. Unfor- tunately. in Section 4.2 we show that there exist irregular distributions that may not be sufficiently close to any regular distribution. Hence, the role of our tester is to verify if there exists a close regular distribution to the input distribution.
3.2. Definition of the New Regularized Testable Learning Framework
We now formally present our framework of regularized testable learning for revenue-optimal auctions.
Definition 14 (Regularized Learner. The class of revenue- optimal mechanisms over regular distributions has an (f 6, n), g(o,, rl)-regglarized learner C if given access
6

---

Safely Learning Optimal Auctions
4.1. The Testing Algorithm
4.2. Regular Distributions are not Dense
Our regularized tester algorithm is similar in spirit to the main algorithms of Guo et al. (2019) and Guo et al. (2021) with additional crucial conditional check the end. Its goal is to determine if there exists close regular distribution to the (possibly irregular) input distribution. Specifically, as input, the tester receives a distortion parameter a E (0, and m samples from a product distribution D = = D..
To motivate why we need to pair our regularized learner with Algorithm 1, we show that there exist distributions that are not suitably close to any regular distribution in terms of KS distance. We defer the proof of Lemmas 4 and 5 to Appendix A.
Lemma 4 (Regular Distributions are not Dense). There exists an irregular distribution D and an a > such that for all regular distributions D', holds that d, > a.
The algorithm then constructs quantile- shanttil-shifted version of the empirical distribution E that is both regular and stochas- tically dominated by true distribution D w.h.p.. The amount of quantile shift is determined via an application of the DKW inequality (Definition 11), along with union bound since is a product distribution. Unlike previous works, our tester then verifies w.h.p. if É, is in an a-radius KS ball around Dj for every E [n)] If so, the tester accepts:
Lemma 5 (Irregular Distributions are Dense). For any dis- tribution D and a > O, there exists an irregular distribution D' such that D' (xs,aDD..
5. Regularized Testable Learning for Optimal Auctions
otherwise, it rejects.
The first setting that we apply our regularized tester to learning revenue optimal auctions from i.i.d. samples, which we explore in this section. We begin by outlining our Iearn- ing algorithm (Algorithm 2). Similar to the tester described in Section 3, the learner receives distortion parameter a E (0 and m samples from the product distribution D = Ii D;. The learner then finds a regular distribution that is close to D. whilst also having the property that D E' and D' d E' for all regular distributions D' which are also close D. The learner then outputs the Myerson optimal mechanism with respect to E'. As with Algorithm 1, the learner can be implemented in polynomial time.
Algorithm 1 Regularized Tester
Require: m i..d. samples from distribution D and distortion parameter a
Ensure: YES or NO F. be the empirical distribution over the
1: Let E
1
samples
2: for 1 to do
3: Construct É; as follows:
4: Let gB((v) be the quantile function of E;
5: Define
2 Bz (v) (1 g (v)) In (22mmo0)
We present a proof of the main theorem in Appendix C. Theorem 6. Let D = II D, be product distribution, let a E (0, 1) be a distortion parameter, and let 8 >> O. Addi- tionally, fix m = Št(log (1/6)/a²) Suppose T is the tester described Algorithm and L is the learner described in Algorithm 2. Then, T is m-sample regularized tester for the (m, -rgularrde learner L.
4 In (2mmm=)) +
+
m
g (v) = (max(0 (0, q (v) -c)
if 0, if =
6:
7:
É, = (Con(
8:
for each value in the support of E, do
6. A Tester for Bulow-Klemperer Theorem
9:
if (v) (b)) > e then
10:
return NO 11: end if
In this section, we show that our regularized tester (Algo- rithm 1) can be used to verify when an approximate version of the Bulow-Klemperer theorem for irregular distributions holds. With i.i.d. regular bidders, the celebrated Bulow- Klemperer Theorem (Bulow & Klemperer, 1996) provides simple method for generating at least as much revenue as the optimal mechanism; just recruit another bidder and run the Vickrey auction.
12: end for
13:
end for
14:
return YES
A priori, it may not be clear whether the transformation associated with 9 ff (t) in Algorithm 1 corresponds to valid distribution function. For completeness, we include a proof of this fact in Appendix B. This algorithm can be implemented in polynomial time (see Guo et al. (2021)). We will utilize this tester both in conjunction with a regularized learner (Section 5) and by itself (Sections and 7).
Theorem 7 (Bulow-Klempens Let D be regular distri- bution and n a positive integer. Then,
Rev AV,, 2 OPT,(D),
when the bidders are i..dd. from D.
7

---

Safely Learning Optimal Auctions
Algorithm 2 Regularized Learner
resolves this question for regular, non-identical distributions.
Require: m i.idd. samples from a distribution D and a distortion parameter a
Theorem 9. Let D =1 D, be a product distribution, where Dj is regular for all i E [n]. There exists anony- mous reserve price p² such that
Ensure: Myerson's optimal auction ME w.r.t. E' 1: Let E = 1 E be the empirical distribution over the samples
2: for i 4 1 to do
Reu(APA(p"). 2)
| OPT(D)
3: Construct E; as follows:
4: Let ( be the quantile function of E,
5: Define
We extend these results to irregular, non-identical distribu- tions using the testing framework with the following theo- rem, whose proof is presented in Appendix
2 B (v) (1 (v)) In 1n(2mn8-))
Theorem 10. Ler D = D be product distribution, a E (0,1) be a distortion parameter, and T be the tester described in Algorithm 1, Fix (2(log(1/ / With probability least 6, if T outputs YES on input of m i.dd samples from D and a, then
4 1n(2mn8 +
+
(v) max(O, (0,
Ei (z) c)
v > 0, if = 0
6:
(eP((A((p")) D. (1- OPT(D')
7:
E = = (Conv(B:()))
8:
Construct E as follows:
for any regular product distribution D' [I D2 such that for all i [m] it holds that D2 E (B.sa(D:)..
max(0. (0. o Bi (v) ox)
a)) if 0 if = 0
9:
q
(i(())
10: end for
8. Information-Theoret Lower Bound
1 12: return Myerson's 's optimal auction Mg: w.r.t. E'
11: Set E'
In this section, we present an information--heeortic lower bound for our regularized testable learning framework. The single bidder lower bound involves finding two regular dis- tributions which are a-close in KS distance but for which mechanism can simultaneously achieve more than (1 - Ω ()) fraction of the optimal revenue for both distri- butions. We formalize this result in the lemma below, whose proof is found in Appendix F.
In Theorem we prove that if our tester approves an input distribution, then the Vickrey auction with an additional bidder achieves at least much expected revenue the multiplicative factor-as the opti- mal revenue of any close regular distribution. The proof is presented in Appendix D.
distribution-modud
Let M be some mechanism and let a < 0.1. There exists an irregular distribution D such that
Lemma 11.
Theorem 8. Let D be a distribution, E (0,1) be a dis- tortion parameter, and T be the tester described in Algo- rithm 1. Fix m = (b(log(1/8)/a))
Rev(M, S (1- (1-=2(()))PT))
With probability at least 5, T outputs YES on input of m ii.dd samples from D -I D and then
for some regular distribution D' BKs.a
Reun+1(VAA (VA,D) 2 (1- 0 (Vna)) (D')
9. Conclusion
for any regular distribution D' such that D' E (D).
In this work, we develop our Regularized Testable Learn- ing framework for mechanism design, wherein we relax the original testable learning benchmark proposed by Ru- binfeld Vasilyan (2023). This relaxation allows us to develop a tester to verify when we can expect to achieve nontrivial fraction of the revenue of the optimal mecha- nism without assuming the samples come from regular distribution. Unlike previous works, our tester-learner pair can provide meaningful revenue guarantees for irregular, unbounded distributions. We additionally show how our tester can be used to verify when important theorems from auction theory that rely on regularity can be safely applied.
7. A Tester for the Anonymous Price Auction
In multi-bidder settings where independence but not identi- cal distributions assumed, the optimal auction may imple- ment different reserve prices for different bidders (Hartline & Roughgarden, 2009). A natural question is whether there exists a single anonymous reserve price for all bidders which achieves a constant fraction of the optimal revenue. The following theorem, originally shown by Hartline & Rough- garden (2009) and later improved by Alaei et al. (2019),
8

---

Safely Learning Optimal Auctions
For future work, we note three fruitful directions. First, it would be intriguing to see if one could develop a tester for our assumption that the distribution is product distribution. Similarly. it would be interesting to understand if it is possi- ble to develop a tester for the assumption that the bidders are i...d. Finally, it would be interesting to establish a tight lower bound for the multi-bidder setting.
Clementi, F. and Gallegati, M. Pareto's law of income distri- bution: Evidence for germany, the united kingdom, and the united states. Econophysics of wealth distributions:
Econophys- Kolkata I, pp. 3-14, 2005.
Cole, R. and Roughgarden, T. The sample complexity of revenue maximization. In Proceedings of the Forty-Sixth Annual ACM Symposium Theory of Computing, STOC
'14, pp. 243-252, New York, NY, USA, 2014. Associa- tion for Computing Machinery. ISBN 9781 9781450327101 doi: 10.1 10.1145/259199661 2591 URL https: /doi. 2591867.
Acknowledgements
We would like to thank Justin Dominic for insightful dis- cussions on the empirical evaluation of our methods and the anonymous reviewers for their constructive feedback on improving the presentation of our results.
org 11w11114422111
Devanur, N. R., Huang, Z., and Psomas, C.-A. The sam- ple complexity of auctions with side information. In Proceedings of the Forty-Eighth Annual ACM Sympo- sium on Theory of Computing, STOC '16, pp. 426-439, New York, NY, USA, 2016. Association for Comput- ing Machinery. ISBN 9781450341325. doi: 10.1145/ 2897555. URL https://doi. org/ 1145/2897518
Impact Statement
This paper presents work whose goal is to advance the field of testable learning in mechanism design. While there are so- cietal consequences of our work, this paper is theoretical in nature. Hence, there are no particular socictal consequences that we feel we must specifically highlight here.
Diakonikolas, I., Kane, D. M., Kontonis, V., Tzamos, C., and Zarifis, N. Agnostic proper learning of halfspaces under gaussian marginals. In Belkin, M. and Kpotufe, S. (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 1522-1551. PMLR, 15-19 Aug 2021. httphhttps:/pprceeeeeee v1 #134/diakoo 0033//iaaknnkkoass221 html.
References
Alaci, S., Hartline, J., Niazadeh, R., Pountourakis, E., and Yuan, Y. Optimal auctions vs. anonymous pricing. Games and Economic Behavior, 1 11::94-5100, 2019.
ml mlr. press/
Brustle, J., Cai, Y., and Daskalakis, C. Multi-item mech- anisms without ttem-independence: Learnability via robustness. In Proceedings of the 21st ACM Con- ference on Economics and Computation, EC '20, pp. 715-761, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450379755. doi: 10. 1145/3391403.3399555 URL https: /dog 10. 1545 /0444//339443333 3399541.
Diakonikolas, I., Kane, D. M., Kontonis, V., Liu, S., and Zarifis, N. Efficient testable learning of halfspaces with adversarial label noise. In Proceedings of the 37th Inter- national Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
Dvoretzky, A., Kiefer, J., and Wolfowitz, J. Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator. The Annals of Mathematical Statistics, 27(3):642 669, 1956. doi: 10. 121 2114/amm//177728111 10. 1214/ / / / 11111117777711
Bulow, J. and Klemperer, P. Auctions versus negotiations. American Economic Review, 86(1):180-94, 1996. URL htttp:://cconP: http://eccoappppseeeee org...poeeer..........r..eeeee 94.
aea: sec:aecrerrv
URL https: / http//doooortoo/ooo
Cai, Y. and Daskalakis, C. Learning multi-item auctions with (or without) samples. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 516-527, 2017. doi: 10. 10.11000 109/FOCS.2017.54
Goldreich, O. Introduction to property testing. Cambridge University Press, 2017.
Gollakota, A., Klivans, A., Stavropoulos, K., and Vasilyan, A. Tester-learners for halfspaces: Universal algorithms. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 10145- 10169. Curran Associates, Inc., 2023a.
Chawla, S., Hartline, D., Malec, D. L., and Sivan, B. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC '10, pp. 311-320, New York, NY, USA, 2010. Associa- tion for Computing Machinery. ISBN 9781450300506. doi: 10. (1145//886689.180677777 URL https: /doi. org/10. 11.100114555 1ttp//..11145118669991109009
Gollakota, A., Klivans, A. R., and Kothari, P. K. A moment-matching approach to testable learning and a
9

---

Safely Learning Optimal Auctions
characterization of rademacher complexity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pp. 1657-1670,
Kalai, A. T., Klivans, A. R., Mansour, Y., and Servedio, R. A. Agnostically learning halfspaces. SIAM Journal Com- puting, 3766)1777-88855, 2008. doi: 10. 10.1137/060649057.
New York, NY, USA, 2023b. Association for Com- puting Machinery. ISBN 9781450399135. doi: 10.
URL https: /ww.i//oiiii// wtwp:/oo.....oooooo/oooooooo 110..1117/111011 00t.......000000000000
Klivans, A., Stavropoulos, K., and Vasilyan, A. Testable learning with distribution shift. In Agrawal, S. and Roth, A. (eds.), Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Ma- chine Learning Research, pp. 2887-2943. PMLR, 30 Jun- 03 Jul 2024. URL https: press /v47//224/// /tt.//kkvaaaa.. html.
114573564246.35852206 URL https:/ http::://do.o/////// 10. 10.1145/3564244 3585206.
Gollakota, A., Klivans. A., Stavropoulos, K., and Vasilyan, A. An efficient tester-learner for halfspaces. In The Twelfth International Conference on Learning Represen- tations, 2024. URL https:tt//// wwtph:tttt//ommmtee http:////peeeeeeeeeeoeee net/ Forum?id=a 6n1 FKMNC1.
httpt:://pocceeeeeeeeee http:////occeiddeeeeeooo mmlr.
Massart, P. The Tight Constant in the Dvoretzky- Stefer-Wolfowice Inequality. The Annals of Proba- bility, 18(3):1269 - 1283, 1990. doi: 10.1214/aop/ 1176990746. URL https: /ttp:://ddo..oo wtt.oi.orr//..11111 12144 aop/1176990745.
Guo, C., Huang. Z., and Zhang, X. Settling the sam- ple complexity of sinle-parameter revenue maximiza- tion. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 662-673, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367053 doi: 10. 1145/3313376.331666
Myerson, R. B. Optimal auction design. Mathemat- ics of Operations Research, 6(1):58-73, 1981. ISSN 0364765X, 15265471. URL http: /twp::/www... jstor. org/stable/ 3689266.
URL https: /org 33163225......
10.
Guo, W., Jordan, M., and Zampetakis, E. Robust learning of optimal auctions. In Ranzato, M., Beygelzimer, A. Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 21273-21222 Curran Associates, Inc., 2021. URL https: htttsss//ppoceednngg.eeeeee neurips.. cc hc//paper_files/peeeeeeeere /ttpe///eeeeeapppp////////////// bl bJJa23S5f39000972223006633233332 pdf.
Roughgarden, T. and Schrijvers, O. Ironing in the dark. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, pp. 1-18, New York, NY, USA, 2016. Association for Comput- ing Machinery. ISBN 9781450339360. doi: 10.1145/ 2940716.2940722 URL https://doi.org:
Rubinfeld, R. and Vasilyan, A. Testing distributional assumptions of learning algorithms. In Proceedings of the 55th Annual ACM Symposium Computing, STOC 2023, pp. 1643-1656. New York, NY, USA, 2023. Association for Computing Machin- ery. ISBN 9781450399135. 3585117. URL https://doii attp:://dai..orr/00.11.4 0564246.3585111
Haghpanah, N. and Hartline, J. Reverse mechanism design. In Proceedings of the Sixteenth ACM Con- ference on Economics and Computation, EC '15, pp- 757-758, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781 9781450334105. doi: 10. 1145727664468.7644988 URL https: htttt::://doiorgg///
Theory of
doi: 10.1145/3564246.
Sivan, B. and Syrgkanis, V. Vickrey auctions for irregular distributions. In Web and Internet Eco- nomics: 9th International Conference, WINE 2013, Cam- bridge, MA, USA, December 11-14, 2013, Proceed- ings, pp. 422-435, Berlin, Heidelberg, 2013. Springer- Verlag. ISBN 978-3-642-45045-7. 978-3-642-45046-44223 35. URL https://doi.crs
Hartline, D. and Roughgarden, T. Simple versus optimal mechanisms. In Proceedings of the 10th ACM Confer- Electronic Commerce, EC '09, pp. 225-234, New York, NY, USA. 2009. Association for Comput- ing Machinery. ISBN 9781605584584. 1145/15663341115664677 URL https: http:://doooooroo// 00.1145/1553744155555
doi: 10.
doi: 10.1007/
Huang, Z., Mansour, Y., and Roughgarden, T. Making the most of your samples. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, pp. 45-60, New York, NY, USA, 2015. Associa- tion for Computing Machinery. ISBN 978 9781450334105. doi: 01114452766448.27644777 URL https: / /oii
10

---

Safely Learning Optimal Auctions
Appendix: Missing Proofs
A. Proof of Lemmas and
In this section, we prove two lemmas on the density of regular and irregular distributions. We begin by establishing a helpful claim.
Claim 12. Let D and D' be two distributions with cdfs of ED and FDi, respectively, Let a >> 0 and suppose D D D'. If h(z; Fb) > 1/h(xiD/)--a' then FD FD (x) a
Proof.
-(t))-F((a)) (1- PD)()) (1= (1 - Fb(x)) M(:; Fb) hx: FD.)
h(2; FD) (2) FDr
1
h(x; hoz;FD)
>
We prove that regular distributions are not dense.
Lemma 4 (Regular Distributions are not Dense). There exists an irregular distribution D and an a: > such that for all regular distributions D', it holds that dxs(D, D') a.
Proof. Let D be the mixed distribution that is uniform over [0, 1] with probability 1 - and uniform over [2 21/e - I] with probability for some e < 0.1. Additionally, let a = e/2. Define
1 - 4a (3a) a) 1- =
D' -ー
By Lemma 1, D' regular since h(x; FD:) is linear. Our goal will be to show that for 2 1 the link function D' lower bounds the link function of every regular distribution that a-close in Kolmogorov-Smirnov distance. Once this established, we will use Claim 12 on D' and D achieve contradiction.
Let D be regular distribution such that dxs (D, D) a. It holds that h(0; Fb) I M0; FD.) and h(1; FB) 2 FD:) since Fp: (0) (D) and Fp (1) FD (1) Since every link function is convex, increasing function, it must be that h' (z; FD) 2 h' (z: FDr) for all 2 1. Moreover, we may utilize that fact that h(1; FD) 2 h(1; Fp:) to conclude that
Mar; Fb) 2 h(:; FD:)
for all æ 2 We will now lower bound h1;; FD:) and apply Claim 12. particular, for 1 15 x < 2//, FD(x) 1 2- so h(:; FD) Then,
1-
Mxx;FD) = (3a) a) 1 a
x +
1/h(z; Fp)
when 4 < x < 2/2 By Claim 12, this implies dxs (D, D) a, which is a contradiction.
In contrast, show below that irregular distributions dense.
Lemma (Irregular Distributions are Dense). For any distribution D and a > 0, there exists an irregular distribution D' such that D' Bxs.a(D) (D)-

---

Safely Learning Optimal Auctions
Proof. Without loss of generality, assume that D regular distribution and fix Let Uj be the value such that 1 FD(11)= a and let v2 be the value such that (D(22) a/2. We will construct irregular distribution by shifting the a22 probability in the region (v1, 02] to higher values. In particular, we may now define irregular distribution D' as follows:
Fn(#))
S V1,
(x)
FD(L1),
U1 < S 02:
U2 < z. is easy to verify that PDr (ar) is valid edf. We can also see that D' irregular, since h(2; FD:) not convex in the region
Vpl(x-00 02) + vi)),
[0, 02]. We conclude the proof by observing that dxs(D', , D) since we only shift around a/2 amount of probability between the two distributions.
B. Proof of Lemma 13
For completeness, we include below a proof that the quantile shift described in Algorithms and yields a valid cumulative density function.
Lemma 13. Let D be distribution with quantile function q(v) F(v) and let a e (0, 1). Consider the distribution defined by the quantile function
7(v)- = max (0, q(v) - c) i > 0,
if v 0,
where
== 2q(v)(1 - (()()) In (2mn8-1
4nn (2mno-1
+ a.
m
Then, it holds that F(u) = 1- q(v) is a valid cumulative distribution funciioon.
Proof. By construction, F(v) has the following properties: F(e) E [0, 1]. Limg O, and lim F()) = 1. We focus on proving that g(v) is monotonically decreasing by taking the derivative with respect to v. Without loss of generality, ignore additive constants and let t 2 In (2mno-') be a positive constant, independent of v. Then,
(0v) F(v) (-(1F(())FFF
and
d du 7(v)= = -f()-- (1+ Vi(1 (FL-2F(U)) 2/(1 F()))F())
(i(1-FF(u) Since F(v) is non-decreasing. fv) is nos-iisi Therefore, we seek verify that 1 F( (v)
nonnega-
tive from [0, a] and nonpositive from (a, Umaz], where is constant to be specified below and Unar is the maximum value in the empirical distribution. The first condition will ensure that Flv) is non-decreasing for E [0, a). The second condition will allow us to show that Fe)) = 1 for v E (a, Umaz]-
For the first condition, we rearrange the statement to prove instead that Vi(1 - 2FF(F) 2 -2 (1 F()))(())) now break into two cases.
F(v). We can
If F(v) < 1/2, then this inequality is clearly true, as the RHS is always negative.
If F(v) 2 1/2. then we may square both sides and observe that we get the quadratic form -(u)2-F(v)) + 4[+1] This quadratic has roots ( 2 The smaller vn is vacuous and introduced by squaring operation. It is also covered under the first case since U1 < 1/2. Consequently, we can determine that the derivative is nonpositive for v < 2 + 2/HFT'
Finally, for the region v E (} + 2 Umaz], we can show that quv) c < O using the fact that g(Umaz) c < 0 and de (())= 2 in this region. Thus, q(v)= 0 for v ( + 2/141 Uman] as desired.
12

---

Safely Learning Optimal Auctions
C. Proof of Upper Bound for Testable Learning
In this section, we will prove the main theorem for the testable learning revenue-maximizing auctions. Before proving Theorem 6, we show a useful lemma.
Lemma 14. Let D be a regular distribution with cdf of FD(x) and a E (0, 1). Define the distribution D' with the following cdft
(T)( = FD(x)+ +
0 x x < FF (1-
x x (1-1
Then, D' is also a regular distribution.
Proof. By Lemma 1, D' is regular if and only if its link function h(x; Fb:) is convex. We will take the derivative of hæ; FDr) and show that is an increasing function. In particular,
0h(r; FD)) dx
1
dr
1- (x)
0
8r
1-
(Fn(()) +
(D(
(1 FD( a)
By the regularity of D, (T))
(n(x)
[D(() is increasing, 80 (I-Fo(#)-a} also increasing.
We are now ready to present the proof of the main theorem.
Theorem Ler D product distribution. let (0, 1) be distortion parameter, and 8 Additionally, fix 22oog (1/5)/a²). Suppose T is the tester described in Algorithm I and L. is the learner described in Algorithum 2. Then, T is m-sample regularized tester for the (m, //na)--egllarizn learner C.
Proof. We begin by showing that the tester's completeness guarantee holds with probability at least 1 6. Choose m large enough so that
(1-0 In (2mno-11 4n (2mm8-11
S a
m
for every E [mz]. Suppose that there exists a regular product distribution D' such that D E BKs,o (D:) for all i [m]. By Lemma 5 of Guo al. (2019), with probability 1 for every value v and every E [n], it holds that
19 - (c))) Piv qP: (v)) In (2mno-) 1)
4 (2mn6-)
< a.
Fix an index E [n]. To show the correctness of the tester, we will prove that و - D = E, > É, Hence, by sandwiching argument, only need to upper bound the quantile distance between D' and E, and between É, and E,, respectively. Specifically.
< 2o. Observe that by construction
( (1) =((() 2a
and
l E
2a.
Thus, the tester outputs YES with probability at least 1 6.
We now prove the tester's soundness guarantee. Suppose that T(D, a, m) outputs YES and let M be the mechanism outputted by L(D, a, m) (that is, Rev(M, f E') = OPT(E')) As before, we begin by noting that D Z E, > E and that
13

---

Safely Learning Optimal Auctions
Dj = E by construction. Furthermore, by Lemma 14, E' regular. We now need to bound the distance between E and any regular distribution D2 E BKs (D;) for all i [n]. We accomplish this through the triangle inequality.
1a (w) (()) - 11 (1) (v) ( (v)
1 E. (v) -
(0)
1 a + 2a + ta
- Sa.
With this bound established, using Theorem 4.3 of Guo et al. (2021), with probability at least it holds that OPT(E') 2 (1 o (Vna) OPT(D')
for any regular product distribution D' -I Dj such that for all E [n]] it holds that D2 E (xss complete the proof, we utilize the fact that D E' and apply Theorem conclude that
Rev(M,D) OPT(E)) (1 O (Vna))OPP(D)
D. Proof of Tester for Bulow-Klemperer
In this section, we prove that our tester can be used to verify when we may apply the Bulow-Klemperer Theorem to a data source. We begin by establishing helpful revenue monotonicity claim.
Claim 15. Let D, D' be distributions such that D' D and the bidders for each distribution are ii.dd, respectively. Then, it holds that
Re (V A, D') 2 Revn+1 Reen+i(VA, D).
Proof. Recall that the Vickrey auction charges the winning bidder the value of the second highest bid. Hence, Reva+1 (V A, D) is equivalent to the expected value of the nth order statistic for the distribution D. well-known fact is that the odf of the nth order statistic is
G(FD(=)) = (n 1)FD()))()) -1-)111)))))))))))))))1 FD(x))*1
cumulative density function by definition is monotonically non-decreasing. Thus, since FD(x) 2 (x), this implies that GzF) 2 G(FD'(z)) (z)). Stochastic dominance further implies that the expected value of nih order statistic for the distribution D' is least large the expected value of the nith order statistic of the distribution D.
In the following, establish the main theorem of this section.
Theorem 8. Let D be distribution, a E (0, 1) be distortion parameter, and T be the tester described in Algorithm 1. Fix m = (lllol(000) and a then
With probability at least - 8, T outputs YES on input of m i...d. samples from D = TT
Revn+1 (VA, 2 (1 (1-0 for any regular distribution D' such that D' E Bxs.0 (D).
0 (Vna)) OPT,())))
Proof. Suppose T(D, a, m) outputs YES. Then with probability least 1 8, there exists a regular distribution D' such that D' BKs,a(D)) Let Damin be the minimal regular distribution in Bxs,e and define D to have the cdf:
F Fpmm (x) + a, 0 < F Dmin (1 a)
Fb(()
x 2 F Pp (1 a).
Notice, Dz D and dxs(D, D) < 2a. Additionally, by Lemma 14, D is regular and D' > D for all regular distributions D' E Bks,o(D) We complete the proof through the following chain of incqualities:
(1 - 0 (Vna)) OPT, < OPT,(D)
Theorem 4.3 (Guo et al., 2021)
< Revn+1 (V-++2(VAAA D
Theorem
< Revn+1 (VA, D)
Claim 15
for all regular distributions D' (D).a
14

---

Safely Learning Optimal Auctions
E. Proof of Tester for Anonymous Price Auction
Below, we show that our tester can be used to verify when the anonymous price auction achieves a non-trivial fraction the optimal revenue of any close regular distribution.
Theorem 10. Let D - D, be a product distribution, (0,1) be distortion parameter, and T be the tester described in Algorithm 1. Fix m (((lo(1/6)//²). With probability least 1- 6, if outputs YES input of m i.idd samples from D and a, then
Rev(AAA(p")) D) (1- OPT(())
for any regular product distribution D' = -1 D; such that for all E [n]] it holds that D2 E Bxss
Proof. L't = Dj be a regular product distribution such that for all i E [n] it holds that D2 E BKs, Further, let D be the regular distribution defined in Appendix D by (+). Then,
(1 - 0 OP(()) S 1 OPT(D) e
Theorem 4.3 (Guo et al., 2021)
< Rev( (ePP(((()))
Theorem 9
For the remainder of the proof, we will focus on showing that
Rev(APA(p"),D) s Rev(APP(p'))
utilizing the property that D 2 D. Let (() denote the random variable of the ith order statistic from n-sample. By the definition of APA(""), Rev (Po(AA(p'))
PrD((((--1) > >p)) ED[X((e ((nx > p"] + PrD(((() 2p' (m S sp') .p" + PrD((X(m) < <p')
It is straightforward to establish that
D (n)(X(() <p')= =1[===
12 = PrD(X(m) 2p" 0 (((n-1) Sp') = Σ (1-FF(())) II)x;F((D")
i=1
13 = >p') =1 Σ (1- F(('))
-1 -1
-1"
First, .P < xP because FP((') FP (p")) for all i [n]. Then, using the fact that a + +
D 1,
+
holds that
p¹ p² + ) S pp 2)
To complete the proof, we need establish that ED [D(X((n1)) (n-))) p¹1 2 [X (1)(x(1)XX(-->) >> p*). We will establish
this by showing that 2p > D which implies that the edf of the ((n-1) under D stochastically dominates the edf of the X(n-1) under D; consequently, the dominating distribution has larger conditional expected value.
To accomplish this, will show that the derivative of whD with respect F₁ for every t: E [n]] is non-positive. In particular,
a
Σ (11
( II F(())
OF,
1
[I ا Fy (x) 1T
11 F((x))
OF
=
1)-
Σ [1)z)E((()))
ift
50
15

---

Safely Learning Optimal Auctions
since (n 14 (1(x) Eite s ((r) (1)) and f& 2 0. To finish the proof, we note that
Rev(APA(p"). D) p" 22 + ED
> p'] 23
Sp 22
D +DD ( (1-1X1=)) > p'] .
Revl Ree(RAPAPl (APA()"),))
F. Proof of Lower Bound for Testable Learning
In this section, we present a lower bound proof for the testable learning of revenue-maximizing auctions in the single-bidder setting.
Lemma 11. Let M be some mechanism and let a < 0.1. There exists an irregular distribution D such that
Reo(M, D) s (1 ((Va)))PT(()
for some regular distribution D' E (BK.a(D).
Proof. Let 0 be value be defined later. We utilize the same two regular distributions D1, D2 which appear in Huang et al. (2015) and have the following edfs:
Fi(x) =
2 x+1
0 S x < 1-8 3
(2(2))
2+11 82
2-(1-3)
I
3
respectively. By Lemma 4. and Lemma 4.1 of Huang et al. (2015), there cannot exist mechanism M that simultaneously
achieves 1 - 3/2 fraction of the optimal revenue for both Dj and D2. Wlog, suppose Rev(M, D1) S (1 -/22)OP((Di)
By Lemma there must exist an irregular distribution D such that D1 2 D and D2.D2 E B (D). We may then apply strong revenue monotonicity find
Rev(M, D) s (1 B/2)OPT((1).
To complete the proof, we bound the Kolmogorov distance between D1 and D2. By solving for the derivative's 's zero, can be shown that
g²
max [F( Fx(x))
2 < 3
We achieve the desired bound by setting 3 = Va.
G. Generic Regularized Learning Definition
Below we present generic version of our regularized testable learning framework, which we believe will be applicable to variety of settings outside maximniin auctions.
Definition 16 (Generic Regularized Learner). An algorithm C is a (J 6, n), gal,,,(a,)aaaaaann sample regularized learner for the concept class with respect to a family of distributions D and hypothesis class H. given access f(a, n) i.i.d. samples from n-dimensional distribution D, L(D, a. m) outputs hypothesis h H. such that with probability at least 1 1-8
h(D) 2 -(((), e)) (D')
for all a-close distributions D' E to D, where e* E C is the optimal concept with respect D'. Definition 17 (Generic Regularized Tester), An algorithm T a f(a, 8, saaslm tester for a class of distributions D with respect to learner if it satisfies two constraints.
16

---

Safely Learning Optimal Auctions
Soundness: Suppose T is presented with f(a, n. i..d. samples from distribution D and outputs "Yes" with probability at least 1 6. Then, the regularized learning guarantee of Definition 16 should be achieved.
Completeness: Suppose the T is presented with f(a, 6, n) i...d. samples samples from a distribution D that is a-close to some distribution D' D, then T should output "Yes" with probability least 6.
In the case of learning revenue-optimal mechanisms, C is the set of revenue-optimal DISC and IR compatible mechanisms, H is the set all DISC and IR compatible mechanisms, and D the family regular distributions.
17


Reviews:
[{"review_id": "rNiUVsEFpN", "reviewer": "Reviewer_CS1L", "summary": "This paper considers auctions with possibly regular or near regular distributions, and considers a two step process of a) testing for regularity, and b) designing an approximately optimal auction if the distribution tests as near regular. Regularity is a key distributional assumption in auction theory: it states that the revenue from setting a price for a single agent is convex, so e.g., you could use local search to learn an optimal reserve. And, setting that optimal reserve in a Vickrey auction gives you the optimal auction. \n\nPrior work has considered similar questions, how to test distributions, how many samples are needed to learn almost the optimal auction, how much error can be present in draws from a regular distribution, and bounds for samples needed to learn near optimal auctions in possibly irregular settings (without testing).\n\nThis work focuses on empirical draws from a distribution that could be close to regular (but not all the way regular). They first show that direct distribution testing is insufficient: there are irregular distributions where the optimal auction cannot be learned for any fixed number of samples. They put forward a tester, that results in theoretical guarantees that are relative to the distance between the empirical distribution and regular distributions, so as the distance to regularity increases, the guarantees weaken. \n\nThey use first-order stochastic dominance to relate the near-regular distribution to all close-by regular distributions. Using this, they show that their approach can be used in three key results: optimal auctions, Bulow and Klemperer's approximation result (add a bidder is better than adding a reserve), and to monopoly pricing.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our paper and appreciating our results. We would first like to address the importance of our work in the context of Roughgarden and Schrijvers (2016) and, more generally, Guo et al. (2019) [2]. Both of these papers provide sample complexity results for learning optimal auctions over bounded, irregular distributions, where the learning benchmark is the irregular distribution’s optimal mechanism. These results do not apply to unbounded, irregular distributions. In contrast, our framework can handle this case; we can provide non-trivial revenue guarantees that hold for unbounded, irregular distributions. We will emphasize this important distinction in the next version of our manuscript. Next, we would like to address your question about whether the bounds for the regularized learners should also apply to nearby irregular distributions. These bounds should not apply to nearby irregular distributions. Even if the ironing region is small, nearby irregular distributions may exhibit radically different optimal revenues. \n\n[1] Tim Roughgarden and Okke Schrijvers. “Ironing in the Dark.” Proceedings of the 2016 ACM Conference on Economics and Computation (pp. 1-18) (2016).\n\n[2] Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. \"Settling the sample complexity of single-parameter revenue maximization.\" Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 662-673) (2019).", "claims_and_evidence": "Yes. The claims of the paper are supported by theoretical proofs and lower bounds.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I reviewed briefly the proof for the Bulow-Klemperer result and Theorem 3 and both appear to be correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This work builds on prior work in learning approximately optimal auctions and testing distributions. It makes a contribution by showing that testing for regularity and then operating on that is insufficient, and new results need to be leveraged.", "essential_references_not_discussed": "This work mentions Roughgarden and Schrijvers 2016, but should add a little more discussion and differentiation since that approach does give guarantees for irregular distributions.", "other_strengths_and_weaknesses": "In general, the paper is very well written and the three results gives it a breadth of applicability and illustrates well that this technique is broadly applicable within bayesian mechanism design. \n\nThe only missing piece (which needs to be there) is the use and discussion of the correct benchmark for irregular settings. With this, it is an accept or strong accept. \n\nWhen the auction is irregular, the optimal auction is not an optimal reserve by itself, but it includes ironing of the virtual values and allocation rule: the lower value bidders are given a preferred allocation to add competition to the higher valued bidders (Myerson '81). Now, I am almost 100% certain that the revenue from that in a situation where it is almost regular should also be near enough that the theoretical results here should still work against the optimal auctions for irregular distributions that are \\alpha close to the empirical distribution since the ironing will be very small if nearly regular. Please add to results if my intuition is correct, or discuss why nearby irregular auctions cannot be included in the benchmark.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "Do the bounds for the regularized learners also apply to irregular distributions that are \\alpha close to D, if they are also \\alpha close to a regular distribution?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wZLf5IJGqs", "reviewer": "Reviewer_kyL3", "summary": "Summary:\n\nThe paper proposes a framework for testably learning revenue-optimal auctions. In this setting, an auction designer has access to m samples (bids) and aims to design a DSIC and IR auction that maximizes revenue. Unlike prior work, which typically assumes conditions like regularity or MHR without testing their validity, the authors propose a framework to actively test for regularity. The goal is for the test to output YES with high probability when the distribution is regular, and for the learned auction to achieve high revenue (competitive with the optimal revenue of all close regular distributions) when it does so.\n\nWhile the paper addresses a relevant problem, the technical novelty and significance of the work are unclear, and the presentation requires improvement to meet the standards for ICML.\n\nDetailed comments:\n\n1. The presentation needs improvement to enhance clarity and readability. Several terms are used without proper definition or are introduced too late. Examples include:\n   - Stochastic dominance in Lemma 1 is mentioned before being defined.\n   - The term \"m-regularized tester\" in Theorem 3 is not clearly defined.\n   - In Definition 9, it is not initially clear that m refers to the number of samples.\n   - The notation m is confusing, as it initially suggests samples from the product distribution rather than individual distributions.\n   \nThese issues are individually minor but collectively hinder the readability of the paper.\n\n2. The technical novelty of the work is not well-explained. The authors do not adequately differentiate their contributions and proof techniques from prior work. \n   - For example, Algorithm 2 appears to be largely similar to Guo et al. (2019), while Algorithm 1 only adds a testing condition.\n   - Clearly and explicitly stating the novel aspects of the work would strengthen the paper. \n   - The purpose and significance of Section 6 are unclear and feel somewhat like an afterthought.\n\nOverall, while the paper addresses an interesting problem, it needs better presentation and a clearer articulation of its technical contributions to be suitable for publication.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reading our paper and providing helpful feedback and comments. We would first like to address your presentation concerns. We are committed to improving the preliminaries by ensuring that the definitions are introduced in the proper order. We will also improve the “m notation” to clarify when the samples are drawn from a product distribution versus an individual distribution. We believe these changes you suggest, among others, can be completed promptly. \n\nWe would also like to address the significance of our work in comparison to [1,2]. \n\n**Comparison with [1,2].** Both [1,2] only provide results for regular or bounded distributions. We demonstrate that without these assumptions it is necessary to relax the conventional learning benchmark found in the existing literature. Consequently, our learning benchmark is also different than [1,2].\n\n**Technical contribution.** It is indeed the case that many of the techniques that we use are based on proof techniques from [1,2], but (1) this is a coincidence, the problem that we are exploring is important on its own, and it happens that the techniques from [1, 2] are useful, and more importantly, (2) we cannot use the techniques from [1,2] in a black-box way. Instead, we need to carefully combine these techniques using some novel ideas. We believe that the fact that the techniques are based on [1,2] should not subtract value from our paper because the problem that we introduce and solve is well-motivated and important.\n\nAdditionally, both our tester and learner differ from [1,2]. In particular, for our tester, we introduce a new conditional check on the difference between the empirical quantiles and the quantiles of a close regular distribution. If this difference is too large, it indicates that there does not exist a regular distribution within the $\\alpha$ KL ball around our target distribution and thus we cannot expect our learner’s guarantee to hold. Our learner also differs from [1,2] in that the algorithm must further adjust the quantiles of the close regular distribution it finds to ensure that it is stochastically dominated by our target distribution.\n\nFinally, the primary purpose of Section 6 (A Tester for the Bulow-Klemperer Theorem) is to demonstrate that our Tester algorithm has utility outside of just being directly paired with a learning algorithm; the tester can be used to verify when important theorems in auction theory that rely on regularity can be expected to apply to a dataset. In particular, we demonstrate that we can test when the fundamental Bulow-Klemperer theorem can be applied to a dataset. This theorem says that when a distribution is regular and the bidders are i.i.d., there exists a simple method to generate as much revenue as the optimal mechanism. Namely, the auctioneer should just recruit another bidder and run the Vickrey Auction.\n\n\n[1] Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. \"Settling the sample complexity of single-parameter revenue maximization.\" Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 662-673) (2019).\n\n[2] Wenshuo Guo, Michael Jordan, and Emmanouil Zampetakis. \"Robust learning of optimal auctions.\" Advances in Neural Information Processing Systems 34 (2021).", "claims_and_evidence": "See above.", "methods_and_evaluation_criteria": "See above.", "theoretical_claims": "See above.", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "See above.", "essential_references_not_discussed": "See above.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B9ku7Q7LiB", "reviewer": "Reviewer_VbU2", "summary": "The authors study a variant of Rubinfeld and Vasilyan's *testable learning* in mechanism design, and give a concrete tester-learner for basic auction settings.\n\nMany classical results in mechanism design, e.g. Myerson's Optimal Mechanism for auctions, require the underlying distribution over valuations be *regular*, a specific technical condition requiring $v-\\frac{1-F(v)}{f(v)}$ be non-decreasing. The authors attempt to develop a \"tester-learner\" for this problem, meaning that given a bounded number of samples from the distribution, one should either \n\n1) detect the distribution is irregular and output **FAIL**, or \n2) output a (near)-optimal mechanism\n\nallowing the user to safely distinguish whether it is possible to use the algorithm on certain data from an unknown distribution. Unfortunately, for revenue maximization, the authors show the above guarantee for testing regularity is impossible. Namely they observe that it is easy to construct statistically indistinguishable distributions with far optimal revenue\n\nMotivated in this context, the authors introduce a relaxed version of testable learning for mechanism design which, given an unknown distribution D', only requires the learner to compete with the best regular distribution near D' in Kolmogorov-Smirnov distance. They give a tester-learner in this context for revenue maximization over independent bidders as well as for the Bulow-Klemperer Theorem and anonymous price auctions (i.e. that adding a bidder can get optimal revenue, and that a fixed reserve price across bidders can achieve within a constant of optimal). \n\nAt a technical level, the authors algorithm works by constructing a regular distribution from the convex envelope of a quantile-shifted empirical estimate. They reject if this distribution is far from the original, and otherwise argue since it is stochastically dominated by the original distribution, applying Myerson's optimal mechanism to this shifted distribution gives the desired guarantee.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reading our paper. We appreciate the constructive feedback and comments. \n\nWe would like to address your concern that our relaxed version of the completeness guarantee is too weak for what we wish to show. We agree that the completeness condition as mistakenly written in a Definition 14 is too weak. We should have instead written: “Suppose the tester T is presented with $h(\\alpha,\\delta,n)$ i.i.d. samples from a distribution $D$. $T$ should output yes with probability at least $1-\\delta$ if and only if there exists a regular distribution that is $\\alpha$-close to $D$. This stronger completeness guarantee avoids the scenario where the tester outputs yes on a distribution that has no close regular distribution, leading to a bad learning outcome. Importantly, in the proof of Theorem 6, we show that if there is a close regular distribution to the input distribution then the tester will find it and output yes.\n\nThe other direction is also simple to show. Namely, the Tester operates by explicitly constructing a regular distribution and testing whether this distribution is close to the input distribution. If the regular distribution that the Tester constructs is far away from the input distribution, then we can be sure that there is no close regular distribution. More specifically, in the Testing algorithm we first construct a (likely irregular) surrogate distribution $\\hat{E}$ that is close to the input distribution and whose link function upperbounds the link function of any close regular distribution. We then take the convex envelope of this link function, which yields a new link function that is the greatest convex lowerbound. Since convex link functions (Lemma 1) correspond to regular distributions, this procedure has located a regular distribution. If this regular distribution is not close to the input distribution, then by properties of the convex envelope and link function, we can be sure that there does not exist a close regular distribution. This update to the completeness condition is straightforward and does affect any of our theoretical results. We are committed to adding more details to clarify this in the next revision of the manuscript.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the lower bound proofs which seem correct, and don't see any issues with the other claims.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The key contribution of this paper is to give the first variants of several classic results in mechanism design with non-trivial guarantees for irregular distributions. Prior results rely strongly on regularity, while the authors show that at least for irregular distributions with some nearby regular distribution, it is either possible to detect irregularity or to output a mechanism as good as on the nearby distribution.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Removing the need for strong distributional assumptions is always a welcome direction in any type of learning, mechanism design included, and the tester-learner framework is an interesting approach to this problem. The authors give extensions in this sense to several classical theorems, potentially broadening their use case in theory and practice.\n\nThe main weakness of the work is that the relaxed version of completeness seems too weak to accomplish what the authors set out to do. Since the optimality guarantee is with respect to nearby regular distributions (and not the original distribution itself) and there are irregular distributions with *no* nearby such distributions, this means there are underlying distribution on which the full \"tester-learner\" fails, i.e. it may output yes and an arbitrarily bad mechanism. The whole point of Rubinfeld-Vasilyan's idea is to avoid this type of scenario, and ensure one can always trust the output of the tester-learner pair. Presumably there may also be settings where the optimum value of nearby regular distributions is simply much lower, which is better than the prior issue, but still seems somewhat questionable as a \"success case\" of the learner. I would suggest the authors spend a bit more space justifying why their relaxation and tester-learners are useful in this context (beyond just the fact that one cannot use standard completeness guarantee, which is not imo of itself a sufficient motivation for the proposed relaxed version).\n\nEDIT: The authors have partially addressed my concerns regarding the completeness of their tester-learner, though the issue of nearby regular distributions with significantly worse value remains. I have increased my score accordingly.", "other_comments_or_suggestions": "Def 13: It reads like D is known now since it is not drawn from some class as in the previous def, but presumably this is not what is meant?\n\nTypos: “It’s goal”, “minium”", "questions_for_authors": "See above: can you provide some clarification why the tester-learner framework remains useful in a setting where there are still distributions over which one cannot trust its output? This seems antithetical to the main point of tester-learners as introduced in Rubinfeld-Vasilyan (and indeed as the authors present as a way to *know* when one can safely apply a mechanism!)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper explores a potentially very interesting and exciting direction: The application of Rubinfeld and Vasilyan's (STOC 2023) "testable learning" framework to auction design. Importantly, they focus on the case of *unbounded* distributions. Unboundedness is important, because there are efficient learning algorithms for bounded irregular distributions (e.g. Roughgarden and Schrijvers 2016, and Guo et al. 2019). Their instantiation for the "testable learning" framework has two parts: (a) a tester which can decide whether a distribution is close to a regular distribution, and (b) in the case where the test is positive, the algorithm finds a mechanism that is close to the best mechanism over all close regular distributions. One thing that their framework does not exclude (and they show this is unavoidable) are irregular distributions which are close to regular distributions (so these distributions pass (a)), but where the revenue on the actual distribution is far more than the optimal revenue on any close-by regular distribution.

Overall we had a good mix of expertise on this paper (from reviewers well-versed in auction theory, and reviewers familiar with the "testable learning" framework). Ultimately we agreed that applying the "testable learning" framework to auction design is a nice idea, but the issue with "false positives" remains (and weakens the result a bit). Roughly the guarantee is: If you cannot be sure that it is not regular, then you may live with the fact that the revenue you get could be suboptimal.
Decision: Accept (poster)