On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
Authors: Moses Charikar
Zhihao Jiang
Kirankumar Shiragur
Aaron Sidford
Venue: NeurIPS 2022 Accept (2022)
Keywords: property estimation
symmetric property estimation
profile maximum likelihood

Abstract: We provide an efficient unified plug-in approach for estimating symmetric properties of distributions given $n$ independent samples. Our estimator is based on profile-maximum-likelihood (PML) and is sample optimal for estimating various symmetric properties when the estimation error $\epsilon \gg n^{-1/3}$. This result improves upon the previous best accuracy threshold of $\epsilon \gg n^{-1/4}$ achievable by polynomial time computable PML-based universal estimators \cite{ACSS20, ACSS20b}. Our estimator reaches a theoretical limit for universal symmetric property estimation as \cite{Han20} shows that a broad class of universal estimators (containing many well known approaches including ours) cannot be sample optimal for every $1$-Lipschitz property when $\epsilon \ll n^{-1/3}$.

On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood
Moses Charikar Stanford University
Zhihao Jiang Stanford University faebdc@stanford.cem
Kirankumar Shiragur Stanford University
moses0cs stanford.edu
shiragur@stanffrd..o edu
Aaron Sidford Stanford University
ord. edu
Abstract
We provide an efficient unified plug-in approach for estimating symmetric prop- erties of distributions given independent samples. Our estimator is based on profil-mmaximun-iieliiooo (PML) and is sample optimal for estimating various symmetric properties when the estimation error e >> n -1/3 This result improves upon the previous best accuracy threshold E >> n 1/4 achievable by polynomial time computable PML-based universal estimators [ACSS21 ACSS20, Our esti- mator reaches a theoretical limit for universal symmetric property estimation as [Han2[] shows that broad class of universal estimators (containing many well known approaches including ours) cannot sample optimal for every 1-Lipschitz property when & n -1/3
1 Introduction
Given n. independent samples y1,..., E 'D from unknown discrete distribution p E A the problem of estimating properties of p. e.g. entropy, distance uniformity, support size and coverage are among the most fundamental in statistics and learning. Further, the problem of estimating symmetric properties of distributions p (i.e. properties invariant to label permutations) are well
studied and have numerous applications [Ca844 BF93 CCG+12 TE87 Für05 KL.999 PBG+01
DS13 RCS+ 09. GTPB07 [ННBBоT]
Over the past decade, symmetric property estimation has been studied extensively and there have been many improvements to the time and sample complexity for estimating different properties, e.g. support [VVTTb] WY15), coverage (ZVV+16 [SWI6)) entropy [VVI]b] [Y16 JVHW and distance uniformity (VIlaa JHW16). Towards unifying the attainment of computationally- efficient, sample-on sample-optimal optimal estimators a striking work of (ADOSI7) provided a universal plug-in in approach based on (approximate) profile maximum likelihood (PML) distribution, that (approxi- mately) maximizes the likelihood of the observed profile (i.e. multiset of observed frequencies).
Formally, (DDSS77] showed that given yi. yn if there exists estimator for symmetric property achieving accuracy e and failure probability 6, then this PMI--based plug-in approach achieves error 2e with failure probability exp (3 (3)).. As the failure probability ó for many estimators for well-known properties (e.g. support size and coverage, entropy, and distance to uniformity) is roughly exp (n) this result implied sample optimal unified approach for estimating these properties when the estimation error > 11/4
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

This result of [ADOS1]] laid the groundwork for a line of work on the study of computational and statistical aspects of PML-based approaches to symmetric property estimation. For example, follow up work of [HS21 improved the analysis of [ADOS17] and showed that the failure probability of PML is at most 8--c e'-=exp(-n'" - for any constant c > 0 and therefore it is sample optimal in the regime > n n-1/3, The condition > n -1/3 on the optimality of PML is tight [Han2]], in the sense that, PML is known to be not sample optimal in the regime 6 < n-1/3 In fact, no estimator (that obeys some mild conditions), is sample optimal for estimating all symmetric properties in the
regime < n -1/3; see Section 2 after Theorem 2.6 for details.
We also remark that the statistical guarantees in ADOSII HS21 hold for any B-approximate PMI for suitable values of B. In particular, [HS21 showed that any 8-approximate PML for B > exp(-n!-d') and any constant c' > 0, has failure probability of 8² exp(n1/3+e + n n² for any constant e > 0. These results further imply sample optimal estimator in the regime
e > n mim(1//n// /2) for properties with failure probability less than exp(-e²n). Note that better approximation leads to larger range of for which the estimator is sample optimal.
Regarding computational aspects of PML. [CSSI9a provided the first efficient algorithm with a non-trivial approximation guarantee of exp( 2/3 log which further implied sample optimal universal estimator for e >> n n-166 This was then improved by [ACSS21] which showed how to efficiently compute PML to higher accuracy of exp(- log n) thereby achieving sample optimal universal estimator in the regime e > n 1111/1 The current best polynomial time approximate PML. algorithm by (ACSS20) achieves an accuracy of exp(-k k log n),, where & is the number of distinet observed frequencies. Although this result achieves better instance based statistical guarantees, in the worst case still only implies a sample optimal universal estimator in the regime e >> n 1/4,
In light of these results, a key open problem is to close the gap between the regimes e > n -1/3 and > 1144,, where the former is the regime in which PML based estimators are statistically optimal and the later is the regime where efficient PML based estimators exist. In this work we ask:
Is there an efficient approximate PML-based estimator that is sample optimal for e > n 1/33
In this paper, we answer this question in the affirmative. In particular, we give an efficient PML-based estimator that has failure probability most 81- exp(n //++ + n²-(). ). and consequently sample optimal in the regime c >> n 1--1/ 1/3, As remarked, this result is tight in the sense that PML and broad class of estimators are known be not optimal in the regime
n -1/3
To obtain this result we depart slightly from the previous approaches in AADOSI7 CSSI9a ACSS21]. Rather than directly compute an approximate PML distribution we compute a weaker notion of approximation which we show suffices to get us the desired universal estimator. We propose a notion of a B-wwek approximate PML distribution inspired by [HS21] and show that an exp(-n' 1/3 n)- weak approximate PML achieves the desired failure probability of 81-c exp(n2/3+c) for any constant e >> O. Further, we provide an efficient algorithm to compute an exp(-n log weekk approximate PML distribution. Our paper can be viewed as an efficient algorithmic instantiation of [HS21].
Ultimately, our algorithms use the convex relaxation presented in [CSS19a ACSS2I] and provide a new rounding algorithm. We differ from the previous best exp(-k log approximate PML algorithm ACSS20) only in the matrix rounding procedure which controls the approximation guarantee. At high level, the approximation guarantee for the rounding procedure in (ACSS20) is exponential in the sum of matrix dimensions. In the present work, we need to round a rectangular matrix with an approximation exponential in the smaller dimension, which may be infcasible for arbitrary matrices. Our key technical innovation is introduce swap operation (see Section (41) which facilitates such an approximation guarantee. In addition to better approximation guarantee than ACSS20), our algorithm also exhibits better run times (see Section 2]
In Section 2 we state main results and also cover related work. In Section 3] we provide the convex relaxation to PML studied in [CSS19a ACSS2I]. Finally, in Section 4 we provide proof sketch of our main computational result. Many proofs are then differed to the appendix.
Organization: We introduce preliminaries in Section I.1
aappproximate PML is distribution that achieves a multiplicative 8-approximation the PML objective.

---

1.1 Preliminaries
General notation: For matrices A, E Rext, we use I B to denote that A, S Bi for all i E [s] and j E [t]. We let [a. bj and (a, bl2 denote the interval 2 a and S b of integers and reals respectively. We use Ō(-), Q(+)) notation to hide all polylogarithmic factors in and N. We let an > bn to denote that an E (t),,,n)) or b, E an,)), for some small constant c > 0.
Throughout this paper, we assume we receive sequence of independent samples from distribution P A where AD def {q E [0. 1 | = }} is the set of all discrete distributions supported on domain D. Let D" be the set of all length sequences of elements of DD and for y" D let yf
denoting its ith element. Let x)) def Ki E [n] yf z} and P.. be the frequency and probability of x E respectively. For sequence y" E D", let M
[ /00) be the set of all its non-zero distinct frequencies and m1 m2, ................................ MM be these distinct frequencies. The profile of
def Mx E D f(y", m is sequence y" denoted á ((v") is a vector in Z where 6, the number of domain elements with frequency m,, We call the length of profile & and let d denote the set of all profiles of length n. The probability of observing sequence y" and profile o for distribution p are P(p.y" = IILeD f(y",2) .) and P(p, Φ) "iree (()))=a) p(p.
Profile maximum likelihood: A distribution Ps A is profile maximum likelihood (PML) distribution for profile o E th if Ps argmaxpes ((p, Φ). Further, distribution P is a 9-- approximate PML distribution P(p #: Φ) 2 B P(P Ø). For a distribution and a length n, let X be a random variable that takes value ø E d with probability P (). We call (() (entropy of X) the profile entropy with respect (p, n) and denote by H
Probability discretization: Let R def [r,) be finite discretization of the probability space,
where r, [0, 1|R and & |R]. We call q E [0, 1]F a pseudo-distribution if |[ql] < 1 and discrete pseudo-distribution with respect to R if all its entries are in well. We A psoudo and AR to denote the set of all pseudo-distribttions and discrete pscudo-distributions with respect to R respectively. In our work, use the following most commonly used (CSS19a ACSS21 ACSS20 probability discretization set. For any a > 0,
R R def [1)
1 (1+ for all i Zzo such that 2n2
1 nn <1]
(1)
2n
For all probability terms defined involving distributions p. we extend those definitions to pseudo distributions q by replacing P. with q, everywhere.
See ?? for the definition of an estimator and optimal sample complexity.
2 Results
Here we provide our main results. In our first result (Theorem 2.2 we show that weaker notion of approximate PML suffices to obtain the desired universal estimator. Later we show that these weaker approximate PML distributions can be efficiently computed (Theorem 2.3
Definition 2.1. Given profile d, we call a distribution p' E A 3-approximate PML distribution with respect to R IP (p', Φ) 2 B maxqeap P
The above definition generalizes B-approximate PML distributions which is simply the special case when R [0, 1|.. Using our new definition, we show that for specific choice of the discretization set R,,,1 /3, a distribution p' that an approximate PML with respect to R,,1/3 suffices to obtain universal estimator; this result is formally stated below.
Theorem 2.2 (Competitiveness of an approximate PML w.r. R). For symmetric property f. suppose there exists an estimator ff that takes input profile o E t² drawn from E A and satisfies.
P ((((p)) - - 2 58,
3

---

then for R = R3,1/3 (See Equation 1 discrete pseudo distribution q' E A such that q q'/llg //ll//122 is an
log 1t)) aaproxxmmae PML distribution with respect to the R satisfies,
P ((= ( 119/111 (1111111111
q' f(p) 2c
- 8'' (xp(O((n/3to)), for any constant 0 (2)
The proof of the above theorem is implicit in the analysis of [SS21), however we provide short simpler proof using their continuity lemma (Lemma 2 in [HS21)). Note that the bound on the failure probability we get is the same asymptotically that of exact PML from [HS21], which is known to be tight [Han2l]. Furthermore, to achieve such an improved failure probability bound all we need is an approximate PML distribution with respect to R. for some R which is of small size. Taking advantage of this fact and building upon [CSS19a ACSS21], we provide a new rounding algorithm that outputs the desired approximate PML distribution with respect to R.
Theorem 2.3 (Computation of an approximate PML w.r.t R). We provide an algorithm that given probability discretization R R,,a for > 0 (See Equation
(T) and profile & with k.
in time Ô (IR) min(k. (min( n/k)k" min (R), (R),k))?)) where
distinct frequencies,
w < 2.333 is the current matrix multiplication constant Wil12 Gall4 distribution q' AR such that,
AW27) and returns a pseudo
q |
PP
2 exp (-O(min(k,||)) l))
max F
geap
When R, our algorithm computes an exp(-O(k log n)) approximate PML distribution, therefore our result is at least as good as the previous best known approximate PML algorithm due (CSS200, In comparison (ACSS20), our rounding algorithm is simpler and we suspect, more practical. We provide more detailed comparison to it later in this section.
Applications: Our main results have several applications which we discuss here. First note that, combining Theorem 2.2 and [2.3 i.3mmditttlyyy yields the following corollary.
Corollary 2.4 (Efficient unified estimator). Given a profile e E th with k distinct frequencies, we can compute an approximate PML distribution q' that satisfies Equation (2) in Theorem 2.2 in time (min(n2/3, ,n/k)) + min(n)2/3,k))
For many symmetric properties the failure probability is exponentially small as stated below.
Lemma 2.5 (Lemma in [ADOSI7. Theorem 3 in (HS2I). For distance to uniformity, entropy. support size and coverage, and sorted {, distance there exists an estimator that is sample optimal and the failure probability is at most exp(-e21) (()=) for any constant > O.
The above result combined with Corollary 2.4 immediately yields the following theorem.
Theorem 2.6 (Efficient sample optimal unified estimator). There exists an efficient approximate PML-based estimator that for n 1/3 and symmetric properties such as, distance to uniformity, entropy, support size and coverage, and sorted & distance achieves optimal sample complexity and has failure probability upper bounded by exp(-n2/3/) 2/3)
log m)) approximate PML, we recover efficient version of Lemma 2.3 and Theorem 2.4 from [ACSS20). The first result uses exp(-O(k: log n)) approximate PML algorithm to efficiently implement an estimator that has better statistical guarantees based on profile entropy [HO20] (See Section I.Ib. The second result provides efficient implementation of the PseudoPML estimators CCSS1bb HO19] Please refer to the respective papers for further details.
As our work computes an
Tightness of our result:
Recall that HS21 showed that the failure probability of an (approximate) PML based estimator is upper bounded by gl-e exp(-n 13+te), for any constant e > 0. This result further implied a sample optimal universal estimator in the regime e >> n -1/3 for various symmetric properties (Theorem 2.6). In our work, we efficiently recover these results and a natural question to ask here is if these results can be improved.
As remarked earlier, [Han2]] showed that the condition for optimality of PMI. (e >> -1/3) is in some sense tight. More formally, they showed that PML is not sample optimal in estimating every

---

1-Lipschitz property in the regime e < n n-1/3, In fact, the results in [Han2]] hold more broadly for any universal plug-in based estimator that outputs a distribution p satisfying,
max I p P DEAP
pll < <A(n)
where A(n) S n² for every 7 > 0 and |pp - glll def perpperrttiio or Ip 12-4-l1 11 denotes the sorted & distance between p and q. other words, if an estimator is based on a reasonably good estimate of the true distribution p (in terms of sorted-(, distance), then it cannot be sample optimal for every 1-Lipschitz property. Furthermore, many well-known universal estimators including PML and LLM [HJW18] indeed provide a reasonably good estimate of the true distribution and therefore cannot be sample optimal in the regime < n -1/3, Please refer to [Han2 for further details.
Comparison to approximate PML algorithms: All prior provable approximate PML algo- rithms CSSI9a ACSS2T the PML and (Step 2) round the (fractional) solution to a valid approximate PML distribution.
have two key steps: (Step 1) solve a convex approximation to
convex approximation to PML was first provided in CSST9a] and better analysis for it is shown in [ACSS2]]. In particular, [CSS19a] and [ACSS2] showed that an integral optimal solution to step 1 approximates the PMI up to accuracy exp(-n log n) and exp(- min(k: [R] log n) respectively, where l and || are the number of distinct frequencies and distinct probability values respectively. In addition to the loss from convex approximation, the previous algorithms also incurred loss in the rounding step (Step 2). The loss in the rounding step for the previous works is bounded by exp(-n2/3 logn) n) [CSST9a] exp(-v/nlog [ACSST]] and exp(-klogg [ACSS20).
In our work, we show that there exists a choice of R 1//) that is of small size (R) S n//33 and suffices to get the desired universal estimator. As |R| S n/33,, our approach only incur loss of exp(-min( R|) logn) E exp(-n1/2 logn) n) the convex approximation step (Step 1). Further- more for the rounding step (Step 2), we provide new simpler and practical rounding algorithm with better approximation loss of exp( (miiin)
[R] log n)) exp(- (0(0OO(n* 1/3
(0n-OOnn///) log n)).
Regarding the run times, both [ACSS20) and ours have times of the form Tsulve + + Tsparsifyy+ +Tround- where the terms correspond to the time required to solve the convex program, sparsify and round solution. In our algorithm, we pay the same cost as [ACSS20) for the first two steps but our run time guarantees are superior to theirs in the rounding step. In particular, the run time of (ACSS20) is shown large polynomial and perhaps not practical their approach requires enumerating all the approximate min cuts. In contrast, our algorithm has a run time that is subquadratic.
Other related work PML was introduced by OSS- Many heuristic approaches have been pro- posed to compute approximate PML, such as the EM algorithm [OSS+04), an algebraic approaches in ADM* 10). Bethe approximation in [Von12] and [Von14], and dynamic programming approach in P. For the broad applicability of PML in property testing and to estimate other symmetric properties please refer to [O19). Please refer (HO20) for details related to profile entropy. Other approaches for designing universal estimators are: [VVITb] based on (LT76). (HJ188) based on local moment matching, and variants of PML by ICSSI9b H019 that weakly depend on the target property that we wish to estimate. Optimal sample complexities for estimating many symmetric prop- erties were also obtained by constructing property specific estimators, e.g. support [VVITb WYT5). support coverage [OSWT6 16 IVV+16), entropy [VV1lb] WY16 [VHWIS). distance to unifor- mity [VVlla [HW16), sorted l distance [VVila HIW18 Renyi entropy [AOST44 AOST17)
KL divergence BZLV16 HJW16] and others.
Limitations of our work One of the limitations of all the provable approximate PML algo- rithms [CSS19a ACSS21 ACSS20) (including ours) is that they require the solution of convex program that approximates the PML objective and all these previous works use the CVX solver which is not practical for large sample instances; note that our results hold for small error regimes which lead to such large sample instances. Therefore, designing a practical algorithm to solve the convex program is an important future research direction. As discussed above, local moment matching (LLM) based approach is another universal approach for property estimation. It is unclear which of the two (PML or LLM) can lead to practical algorithms.
5

---

3 Convex relaxation to PML
Here we restate the convex program from [CSS]9a that approximates the PML objective. The current best analysis of this convex program is in (ACSS2I]. We first describe the notation and later state several results from CCSTT9a ACSS2T that capture the guarantees of the convex program.
For any matrices X E Raxc and Y E Rbxc, we let concal Y) denote the matrix W E [a++)ixe that satisfies, W = X, for all E [a] jnd E [c] and W Watis = Vij for all i E [b]
Notation:
and j E [c]. Recall we let R def {ri be a finite discretization of the probability space, where
E [0, 1|R and 8 def R Let E [0, 1// be a vector whose i'th element is equal to r;
Lemma 3.1 (Lemma 4.4 (CSST9a) Let R R for some a > For any profile b E Hh and distribution p AP, there exists a pseudo distribution q AB that satisfies P(p, Φ) 2 P(q, Z exp (-an 6) P(p. 6) and therefore,
max P(p, Φ) 2 max P(q: 6) 2 exp (-an max P P(p.o) PEA
gEAR
PEAD
For any probability discretization set R, profile é and pseudo distribution q E A define:
Z def
EXERXXI
Ex(o,K]
X1 E Z", X 1, oj for all j E [1, and T X1 و <1)
(3)
20
a frac def x
(0.)
x 115 = 6j for all j E [1, k) and r X1 و <
(4)
The j'th column corresponds to frequency my and we use mo def 0 to capture the unseen elements.
Without loss of generality, we assume mo < m < <.. < m.- Let Cij def
mj logr, for all E [$]
and [0, k). The objective of the optimization problem is follows: for any 12 (0,8]
define,
g(X) def
exp
Σ [C,, - Xij log X + ΣxIT log [ol()
(5)
vE(E]JE[O.M)
iE!
For any q E AR the function g(X) approximates the P(q 6) term and is stated below.
Lemma 3.2 (Theorem 6.7 and Lemma 6.9 in (ACSS2I).. Let R be a probability discretization
set. For any profile Φ thth with i distinct frequencies the following statements hold for min(k, k, |R) log n. exp (-O(a)) Cs maxxezz 8(X) < ma P(g. S exp (0 (a)) Co
xeze (X) and max P(q, Φ) I exp (O (min(k, [R) log (logg))-CC, (Csmmxxxra tree g (XX. where
def n!
C
I 1y a term that only depends on the profile
The proof of concavity for the function g(X) and a running time analysis to solve the convex program are provided in [CSSI9a]. For any X E Z pseudo-distributions associated with it is defined below.
Definition 3.3. For any X E Zg the discrete distrid-ittiiitoonn 4x associated with X and R is defined as follows: for arbitrary [X1]; number of domain elements assign probability r. Further Px
def 9x/ dx/119xl1 ll is the distribution associated with X and R.
Note that 4x is a valid pseudo-distribution because of the third condition in Equation 3 and these pseudo distributions Px and 4x satisfy the following lemma.
Lemma 3.4 (Theorem 6.7 in (ACSS2I)). Let R and á E 5" be probability discretization set and a profile with i distinct frequencies. For any X Zz the discrete pseudo distribution qx and distribution Px associated with X and R satisfy: exp (-O(k (ogg)) Co g(X) S <P(gxx x) S
(Px: ④).
only written with approximation factor of exp(O(k log m)). However, their proof provides a stronger approximation factor which upper bounded by non negaaveee rank of the probability matrix, which in turn is upper bounded by the minimum of distinct frequencies and distinct probabilities. Therefore the theorem statement in [ACS21] holds with a much stronger approximation guarantee of exp (O (min(k, R] logn)..
"The theorem statement in ACSS21

---

Approximate PML algorithm
Here we provide a proof sketch of Theorem and provide rounding algorithm that proves it. Our rounding algorithm takes as input matrix X E Z z.ffrrnc which may have fractional row sums and round it to integral values. This new rounded matrix Xfnal corresponds to our approximate PML distribution (See Definition 3.3
The description of our algorithm is as follows.
Algorithm ApproximatePMLL.. Ø, R -
1: Let X be any solution that satisfies, logg(X) 2 max Yez maxyez
log g( Y) - (min(k; [R]) log
2: X' sparsify(X).
(A, B) swapmatrixround
4: (Xfinal; Rfinal) = create(A, AA B, R)
5: Let p' be the distribution with respect to Xfinal and Ritna (See Definition 3.3
6: Return discretize(p'
We now provide guarantee for each of these lines of Algorithm ! We later use these guarantees to prove our final theorem (Theorem 2.3 The guarantees of the approximate maximizer X computed in the first step of the algorithm are summarized in the following lemma.
Lemma 4.1
ACSS21)). Line of the algorithm Ö(R h22 + R() time and the approximate maximizer X satisfies: Co .g(X) Z
CSSI19
be implemented in
exp (-0 (min((: R)) log max P(). Φ)
The guarantees of the second step of our algorithm are summarized in the following lemma. Please refer to [ACSS20] for the description the procedure sparsify. We use this procedure so that we assume R S le + 1 as we can ignore the zero rows of the matrix X.
Lemma 4.2 (Lemma 4.3 in (ACSS20). For any X E Z g.ffrac the algorithm sparsify (X) runs in time
Ö(R) kd) and outputs X' e Zx & such that: g(X') g(X) and {i E [4] [X I], 0} 1k
To explain our next step, we need to define a new operation called the swap.
Definition 4.3. Given a matrix A, indices i < i2. j1 < j2 and a parameter 2 0, the operation swap(A, in, J2, e) outputs matrix A' that satisfies,
A + 6 for i1 j fn
Ai.j 6 for i i1, j j2
Aly
Ai, for i i2, j = fn
Ai. + for i2, j =j2
(6)
Aij otherwise.
Definition 4.4 (Swap distance). A' is swap distance from A, if A' can obtained from through
sequence of swap operations and the summation of the value e's in these operations is at most
ie. there set of parameters [(2(a) (s))
:11 J2 ,e())))=e(t) where E.Ely c(*) S x, such that
(() (s)
(s) swap(A (a-1), 21 11 :22 ,e())) for E [t]. where (0) A and A (1) =A'
(s)
(a) (e)
The following lemma directly follows from Definition 4.3 and Definition 4.4
Lemma 4.5. For any matrices A,A' E Rext if'' is a-swap distance from A for some 2 0, then A' AT and A = T....
Recall that our objective g(X) contains two terms: (I) the linear term EiElg,E CiyX, and (2) the entropy term Σietel (XT); log XT), Eie Xij log Xij- The swap operation always increases the first term, and in the following lemma we bound the loss due to the second term.
Lemma 4.6. IfA's e [ (0,4] æ-swap distance from A Zr.frac then, A' E Zefraac and g(A') 2 exp(-O(z log (A))
One of the main contributions of our work the following lemma, where we repeatedly apply swap operation to recover matrix A which exhibits several nice propertics stated below.
7

---

Lemma 4.7. For any matrix A E Rext (s S t) that satisfies A A E I'20 The algorithm
swapmatrixround runs in () time and returns matrices A' and B such that,
A' is (ss-swapp distance from A, A'T =AT and A A T
0 S B.j S Aly for all i E [s] and E [4] BY E 2g B BT 222 and ||' - B|| S (()..
The above lemma helps us modify our matrix to a new matrix A that we can round using the create procedure. The guarantees of this procedure are summarized below.
Lemma 4.8 (Lemma 6.13 in (ACSS2T). For any E Z..fiac
R and B E 20 C. C220
Ex
such that S A, B E Z B E Z and ||A Bll S. The algorithm create(A, B, R) runs in time ((tk) and returns a solution A' and probability discretization set R' such that R R| min(k + 1,t), A' E Zgg. and andg(A's ( 2 exp(-4) (tlogn) (llogn))((1) g(A)
g(A')
As our final goal is to return a distribution in AR. we also use the following discretization lemma.
Lemma 4.9. The function discretize takes as input a distribution E A with E' distinct proba- bility values, a profile o. a discretization set of the form R
Rn,a for some a > O and outputs
a pseudo distribution q E AK such that: IP
9911 . z exp( exp(-O(min(k; [R) + min(k, EY) +
a log I.) (p.0) x)
In Section 5 we use the guarantees stated above for each line of Algorithm to prove Theorem 2.3
The description of the function discretize is specified in the proof of Lemma 4.9 We describe the procedure swapmatrixround and provide a proof sketch of Lemma in Section
4.1
Description of swapmatrixround and comparison
ACSS20
Here we describe the procedure swapmatrixround and compare our rounding algorithm to ACSS20 Both of (CSS20)) and our approximate PML algorithm have four main lines 4
: we differ from 3 This line in [ACSS20) invokes procedure called matrixround that
ACSS20 in the key Line
takes as input matrix A IR ex [0.8] and outputs matrix B [x(A0 such that: B < A, B T Z
B B E [0.M] and |A B
O((+k) k)). Such matrix B is crucial the procedure create uses B to round fractional row sums of matrix A integral values. The eπror incurred in these two steps is at most exp(O(I|A B||1 1 log n)) E exp(O((E++ k)) log n)). As the procedure sparsify allows us to assume e < k 1, we get exp( log approximate PML using (ACSS20). However, the setting that are interested in is when < k: for instance when E (n and & @(vn)) In these settings, we desire an (ep(-O(min((,, (f, k) logn)) E exp( ( n)) approximate PML. In order get such an improved approximation using [ACSS20),
need matrix B satisfying the earlier mentioned inequalities along with || B//1 S O(min(k: (ki, E)). However, such a matrix B may not exist for arbitrary matrices A and the best guarantee any algorithm can achieve is ||A BlI1 O(e k).
To overcome this, we introduce a new procedure called swapmatrixround that takes as input, a matrix A and transforms it new matrix A' that satisfies: g(A') 2 exp( exp(-O(min(kk; E) log n) }g({)) Furthermore, this transformed matrix exhibits a matrix that satisfies the guarantees: B <
BÍ E 0 B invoke the procedure create, which would output valid distribution with required guarantees. the following we provide description of the algorithm that finds these matrices A' and B.
z and |A' - BI|: S O()). These matrices A' and B are nice in that we can
Algorithm 2 swapmatrixxouud(A)
1: Let A (0) = A and ()) 0.
2: for 1. do
(Y,j) = PartialRound(A (r-1)
3:
4: A (r) roundiRow (Y, r).
5: (r)) 1) Y A (r)
6: end for
7: Return A' ( and (
8

---

Our algorithm includes two main subroutines: partialRound and roundiRow. At each iteration i, the procedure partialRound considers row and modifies it by repeatedly applying the swap operation. This modified row is nice as the procedure roundiRow can round this row to have an integral row sum while not affecting the rows (i - 1]. By iterating through all rows, we get the required matrices A' and B that satisfy the required guarantees. In the remainder, we formally state the guarantees achieved by the procedures partialRound and roundiRow.
Lemma 4.10. The algorithm part Raluid takes as inputs X 1e and i [e- 1] that satisfies
the following, [X [i] ls for all í' e [1, 1] and [X T1 E Zoo all j [0, kl. and outputs
a matrix Y E E 1200 tx(0,k) and an index j' such that:
Y is within 3-swap distance from X.
.Yy 2 o and Σ Yey + Yop - Z20. where o [XT]: }:- [XT]J.
Furthermore, the running time of the algorithm is O(Ek).
Note that by Lemma 4.5 if Y is within 3-swap distance from X, then YT = Xi and Y T
Lemma 4.11. The algorithm roundiRow takes as inputs Y E R R2000 an column index j E k]
and a row index E [e- 1] such that: y z
[0,k]
Yjj 2 and Σ Yej + Yij E Zzo.
20
where o = | - - Outputs matrix X E R fx(0000 [0Ab such that, 20
X < Y and |X - Y|1 $
xTT [y for all i' ei- [TT, Ezo. and X
T U.M
220
We defer the description of all the missing procedures and proof's to appendix.
5
Proof of Main Result (Theorem 2.3
Here we put together the results from the previous sections to prove, Theorem 2.3
Proof of Theorem 2.3 Algorithm | achieves the guarantees of Theorem 2.3 In the remainder of the proof, we combine the guarantees of each step of the algorithm prove the theorem. To- ward this end, we first show the following two inequalities: Xfinal E Z and g(Xinat) Z exp(-O(min(k; RR) n))())((X). By Lemma the Line of Algorithm returns a solution X E Z p.aac that satisfies,
Co g(X) 2 exp ( (-0 (min(k, [R] log n)) max IP 6).
qeaR
By Lemma 4.2 the Line of Algorithm takes input X and outputs X' such that
X' E Z
d.frac and g( g(X') 2 g()).
(8)
and (i E [e] [x] 07| < k + 1. As the matrix X' has at most k + 1 non-zero rows, without loss of generality we can assume R < k + (by discarding zero rows).
As matrix X' E - frace we have that X' has integral column sums and by invoking Lemma 4.7 with parameters
R and
get matrices A and B that satisfy guarantees of Lemma 4.7
As [ T = [X T) for all E [4]. [A T) = X T) for all j E [0, k] and X' E 7 ftfc we
immediately get that A Z frac Further note that A is within O([R) ( R] -swap
distance from X' and by Lemma 4.6 we get that g(A) 2 exp(-O R ke) log n) )XX'. To summarize, we showed the following inequalitics,
A Z frac and g(A) 2 exp(- (ep(-O(min(()) RR k) log logn)) nX))
(9)

---

Note that, Lemma 4.7 also outputs matrix B that satisfies: B A, Ez'.
z and
||A Bll1 < ( R k)). These matrices A and B satisfy the conditions of Lemma 4.8 with
parameter value 1 = O(min( R], k.). Therefore, the procedure create takes in input matrices A, B
and returns solution (nall Rinal) such that R Rnall - | + min k) S 2 and,
final E Z
Ranal and g(Xnaa)) 2 exp(
( R log (A()
(10)
As X final E Z 2
"Rimal" by definition Definition 3.3 and Lemma 3.2 the distribution p' satisfies,
P (p'
exp( (00(--00mmm) O0in Rimal) log n)) Co ((naaa))))) exp(=O(min(k;; RR)) log)))
exp(
Ominn (k: R) (oag)))Cag(XX 2 exp(-O(min(A) [R] log n))Cag(X)
IV exp( (0min R| log m)) max
P(q. Φ)
q
In the second inequality we used Equation 10 and Rimall < 2 R. In the third, fourth and fifth inequalities, we used Equation (9). Equation (8)
and Equation respectively.
Recall we need distribution that approximately maximizes max P ( 6) instead of just qax P(g. Φ). In the remainder of the proof we provide procedure to output such distribution.
For any constant c 0, let R T Tmin < || S 1, we get that,
def tc
ri R]. For any q E A as
|||||
satisfies:
max P ()
max cE(1.1/Fmiol
max p(
(11)
4EAR 1
qE
The above expression holds as the maximizer q" of the left hand side satisfies: q" E A (1/l
Define C def {(1 + he(a) for some 3 E o(1), where a E O() (rr()/) is such that
Tmin (1 + 3) = 1. For any constant e E 1/, note that there exists a constant c' E C such that c(1 - 3) d < c. Furthermore, for any distribution q E A with ||]]: = 1/c, note
that the distribution q' c'q E A and satisfies:
[P(1
Φ) P(c q. o) 9(
($)" P('" Φ) Therefore we get that, P(q', Ø)
c''
IP(
(1 P) |मीा +) >
q
exp(-28n))P (Igl: Φ) Combining this analysis with Equation
11
we get that,
max CEC
max P(q. の) 2 exp(- max A c.R
P ye
(12)
|qll
For each e > 0 as
|
le- R our algorithm (Algorithm D
returns distribution P. that satisfies,
P (Par Φ) 2
(k. R l)g max P(q. Φ).
qEA
Let p" be the distribution that achieves the maximum objective value to our convex program among the distributions {pee. Then note that p" satisfies; IP (p", Φ) 2 exp(-O(min((;; R log 2.n) yax
P( 9 | 6) Substituting 3 = mik(k.IR in the previous expression, we get,
P (p" 6) 2 exp(-O(min) RJ) log n)) max P(
qE
|
As each of our distributions P. (including p²) have the number of distinct probability values upper bounded by 2| by applying Lemma 4.9 we get a pscudo distribution E A with the desired guarantees. The final run time of our algorithm is O(C)T)) O [R Ti). where Ti is the time implement Algorithm 1 Further note that by Lemma 3.1, without loss of generality can assume R S n/k: As all the lines of Algorithm [ are polynomial in n, our final running time follows from the run times of each line and we conclude the proof.
Acknowledgments and Disclosure of Funding
We would like to thank the reviewers for their valuable feedback. Researchers on this project were supported by an Amazon Research Award, Dantzig-Lieberman Operations Research Fellowship, Google Faculty Research Award, a Microsoft Research Faculty Fellowship. NSF CAREER Award CCF-1844855, NSF Grant 195-1955039, a PayPal research gift, Simons-Berkeley Research Fellowship, a Simons Investigator Award, a Sloan Research Fellowship and Stanford Data Science Scholarship.
10

---

References
[ACSS20] Nima Anari, Moses Charikar, Kirankumar Shiragur, and Aaron Sidford. Instance based approximations to profile maximum likelihood. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[ACSS21] Nima Anari, Moses Charikar, Kirankumar Shiragur, and Aaron Sidford. The bethe and sinkhorn permanents of low rank matrices and implications for profile maximum likelihood. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 93-158. PMLR, 2021.
[ADM+10] J. Acharya, H. Das, H. Mohimani, A. Orlitsky, and S. Pan. Exact calculation of pattern probabilities. In 2010 IEEE International Symposium on Information Theory, pages 1 1498-1502, June 2010.
[ADOS17] Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh. A unified maximum likelihood approach for estimating symmetric properties of discrete distributions. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 11-21. PMLR, 06-11 Aug 2017.
[AOST14) Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. The complexity of estimating rényi entropy. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1855-1869, 2014.
[AOST17] Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. Es- timating renyi entropy of discrete distributions. IEEE Trans. Inf. Theor, 63(1):38-56, January 2017.
[AW21] Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithmms, SODA 2021, Virtual Conference, January 10 13, 2021, pages 522-539. SIAM, 2021.
[BP93] John Bunge and Michael Fitzpatrick. Estimating the number of species: a review. Journal of the American Statistical Association, 88(421):364 373, 1993.
[BZLV16] Y. Bu, S. Zou, Y. Liang, and V. V. Veeravalli. Estimation of kl divergence between large-alphabet distributions. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 1118-1122, 1122, July 2016.
(CCG+ 12] Robert K Colwell, Anne Chao, Nicholas J Gotelli, Shang-Yi Yi Lin, Chang Xuan Mao, Robin Chazdon, and John T Longino. Models and estimators linking andvidual-basee and sample-based rarefaction, extrapolation and comparison of assemblages. Journal of plant ecology, 5(1):3 20: 2012.
[Cha84] A Chao.
Nonparametric estimation of the number of classes in population. scandina- vianjournal of statistics 1,, 265-270. C Scandinaavin Journal of Statistics1984, 1984.
[CSS19a] Moses Charikar, Kirankumar Shiragur, and Aaron Sidford. Efficient profile maximum likelihood for universal symmetric property estimation. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 780- 791, New York, NY, USA, 2019. ACM.
[CSS19b] Moses Charikar, Kirankumar Shiragur, and Aaron Sidford. A general framework for symmetric property estimation. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Bue, E. Fox, and R. Garnett, editors, Advonces in Neural Information Processing Systems 32, pages 12447-12457. Curran Associates, Inc 2019.

---

[DS13] Timothy Daley and Andrew D Smith. Predicting the molecular complexity of sequencing libraries. Nature methods, 10(4):325, 2013.
[ET76] Bradley Efron and Ronald Thisted. Estimating the number of unseen species: How many words did shakespeare know? Biometrika, 63(3):435-441 1976.
[Für05] Johannes Fürnkranz. Web mining. In Data mining and knowledge discovery handbook, pages 899-920. Springer, 2005.
[Gal14] François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium Symbolic and Algebraic Computation, ISSAC "14, Kobe, Japan, July 23-25, 2014, pages 296-303. ACM, 2014.
[GTPB07] Zhan Gao, Chi-hong Tseng, Zhiheng Pei, and Martin J Blaser. Molecular analysis of human forearm superficial skin bacterial biota. Proceedings of the National Academy of Sciences, 104(8):927-2232,, 2007.
[Han21] Yanjun Han. On the high accuracy limitation of adaptive property estimation. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statisties, volume 130 of Proceedings of Machine Learning Research, pages 910-918. PMLR, 13-15 Apr 2021.
[HHRBO1] Jennifer Hughes, Jessica J Hellmann, Taylor H Ricketts, and Brendan JM Bohannan. Counting the uncountable: statistical approaches to estimating microbial diversity, Appl. Environ. Microbiol., 67(10):4399 2001.
[HJW16] Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Minimax estimation of KL divergence between discrete distributions. ArXiv e-prints, (bss/1605.09124, 2016.
(HJW18) Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under wasserstein distance. ArXiv e-prints, arXiv: 2018.
[HO19] Yi Hao and Alon Orlitsky. The Broad Optimality of Profile Maximum Likelihood. ArXiv e-prints, page arXiv:1906.03794. Jun 2019.
[HO20] Yi Hao and Alon Orlitsky. Profile entropy: A fundamental measure for the learnability and compressibilitt of distributions. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS' 20, Red Hook, NY, USA, 2020. Curran Associates Inc.
[HS21] Yanjun Han and Kirankumar Shiragur. On the competitive analysis and high accuracy optimality of profile maximum likelihood. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 13, 2021, pages 1317-1336. SIAM, 2021.
[JW166] J. Jino, Y. Han, and T. Weissman. Minimax estimation of the 11 distance. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 750-754, July 2016.
[VHW115] J. Jiao, K. Venkat, Y. Han, and T. Weissman. Minimax estimation of functionals of discrete distributions. IEEE Transactions Information Theory, 61(55:2835-2888 2885, May 2015.
[KLR99] Ian Kroes, Paul W Lepp, and David A Relman. Bacterial diversity within the human subgingival crevice. Proceedings of the National Academy of Sciences, 96(25):14547 14552, 1999.
[OSS+ + 04] A. Orlitsky, S. Sajama, N. P. Santhanam. K. Viswanathan. and Junan Zhang. Algo- rithms for modeling distributions over large alphabets. In International Symposium on Information Theory, 2004. ISIT 2004. Proceedings. pages 304-304, 2004.
[OSW16] Alon Orlitsky, Ananda Theertha Suresh, and Yihong Wu. Optimal prediction of the num- ber of unseen species. Proceedings of the National Academy of Sciences, 113(47):3323- 13288, 2016.
12

---

[PBG* [P] Bruce Paster, Susan K Boches, Jamie L Galvin, Rebecca E Ericson, Carol N Lau, Valerie A Levanos, Ashish Sahasrabudhe, and Floyd E Dewhirst. Bacterial diversity in human subgingival plaque. Journal of bacteriology, 183((12)3770-3383 2001.
[PJWI7] D. S. Pavlichin, J. Jiao, and T. Weissman. Approximate Profile Maximum Likelihood. ArXiv e-prints,
December 2017.
09C Harlan Robins, Paulo V Campregher, Santosh K Srivastava, Abigail Wacher, Cameron J Turtle, Orsalem Kahsai, Stanley R Riddell, Edus H Warren, and Christo- pher S Carlson. Comprehensive assessment of t-cell receptor (-chain diversity in aB t cells. Blood, 14(19):499-4107, 2009.
[TE87] Ronald Thisted and Bradley Efron. Did shakespeare write newly-discovered poem? Biometrika, 74(3):445 455, 1987.
[Von12] Pascal O. Vontobel. The bethe approximation of the pattern maximum likelihood distribution. 2012 IEEE International Symposium on Information Theory Proceedings, pages 2012-2016, 2012.
[Von14] P. O. Vontobel. The bethe and sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the valiant-valiant estimate. In 2014 Information Theory and Applications Workshop (IIAA), pages 1-10, Feb 2014.
[VV11a] G. Valiant and P. Valiant. The power of linear estimators. In 201 JEEE 52nd Annual Symposium on Foundations of Computer Science, pages 403-412, Oct 2011.
[VV11b] Gregory Valiant and Paul Valiant. Estimating the unseen: An for entropy and support size, shown optimal via new clts. In Proceedings of the Forty- third Annual ACM Symposium on Theory of Computing, STOC '11, pages 685-694, New York, NY, USA, 2011. ACM.
estimator
[Wil12] Virginia Vassilevska Williams, Multiplying matrices faster than coppersmith-winogen In Proceedings of the Forty-Fourth Fourth Annual ACM Symposium Theory of Computing, STOC 12, page 887-898, New York, NY, USA, 2012. Association for Computing Machinery.
[WY15] Y. Wu and P. Yang. Chebyshev polynomials, moment matching, and optimal estimation of the unseen. ArXiv e-prints, arXiv: BoKYv:5504.0122. April 2015.
[WY16] Y. Wu and P. Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory, 62(6):3702- 3720, June 2016.
[6V James Zou, Gregory Valiant, Paul Valiant, Konrad Karczewski, Siu On Chan, Kaitlin Samocha, Monkol Lek, Shamil Sunyaev, Mark Daly, and Daniel G. MacArthur. Quanti- fying unobserved protein-coding variants in human populations provides roadmap for large-scale sequencing projects. Nature Communications, 7:13293 EP-, Oct 2016.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 2
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "nqRQ8LOOSCd", "reviewer": "Reviewer_BTch", "summary": "The paper studies the now classical method of profile maximum likelihood (PML) and provides an efficient estimator that works for tiny errors below n^{-1/4}, where n is the sample size.", "questions": "It would be great if the authors could address the improper definitions, references, and lemmas mentioned above.", "limitations": "Page 5 presents a section on the limitations of the proposed algorithm, as solving the involved convex program can be problematic in the large-sample regime. Maybe the authors can also describe some theoretical limitations, if any. I couldn't find much discussion on the potential negative social impact of the authors' work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength is that n^{-1/3} is one type of theoretical limit: For any plug-in estimator, a symmetric functional exists for which the plug-in estimator is suboptimal. This point is also a weakness since prior work already provided efficient estimators for any error above n^{-1/4}; closing this tiny gap between n^{-1/3} and n^{-1/4} might be incremental.\n\nI like that the proofs are relatively short compared to prior works. However, this may rely on the fact that existing results can serve as lemmas.\n\nIt is not entirely clear what a 'sample optimal universal estimator' means in the paper. I would say it's better if the authors can provide a concrete & mathematical definition for this. Also, it doesn't seem that [ADOS16] establishes the PML estimator's optimality beyond the four mentioned functionals. And [HO19] showed that PML is sample-optimal for a \"Lipschitz\" functional class, which should appear around line 28. \n\nLemma 2.4 is simply Incorrect. Theorem 3 in [HS20] shows the existence of a sublinear estimator with no sample optimality guarantees for functionals like 1-Lipschitz. It seems that [HO19] presented something close to the desired claim.\n\nI didn't check the proofs in the appendix. But besides the above error, looking at the references also concerned me about this paper's rigorousness. For example, the citation for [HS20] provides no more than the publishing year (how about which journal/conference?). Maybe this would hint that the paper was completed in a rush.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NYLhWSW_7Lu", "reviewer": "Reviewer_w8eP", "summary": "The submission considers the problem of estimating some symmetric properties of finite-supported discrete distributions. The paper is interested in a very specific type of such methods, an \"approximate profile maximum likelihood (PML) estimator\", a variant of MLE optimized on a more compactly defined objectives. The paper concerns a highly technical question: can any efficient and approximate PML estimator be and sample competitive in the regime $\\epsilon \\gg n^{-1/3}$? Maybe I should summarize a few preliminaries as well:\n\n- \"Sample-competitive\" of an estimator means: the failure probability of the estimator matches the standard $\\exp(-\\Omega(n\\epsilon^2))$ failure probability.\n\n- The exact PML estimator is shown to be sample-optimal in $\\epsilon \\gg n^{-1/3}$ regime, and cannot be sample-optimal below the $n^{-1/3}$ threshold. \n\n- Existing *approximate* PML estimators are shown to be sample optimal in the regime $\\epsilon \\gg n^{-1/4}$. Can they tighten this to $n^{-1/3}$?\n\nThey answers this question positively, closing the problem (in my guess). For this, the paper improves the algorithm proposed in [ACSS20, ACSS21]. Main technical innovation seems to be a certain swap operator, which is hard for me to follow further. ", "questions": "- Can you give some comments on why do we care an approximate PML estimator in the intro explicitly?\n\n- It would have been helpful to make more contrast between this paper and previous work in [ACSS21]. e.g., why previous work can only work in $\\epsilon \\gg n^{-1/4}$. ", "limitations": "I do not see any negative societal impact. ", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It seems like that the paper is mostly an extension of [ACSS21], but I feel that the paper is not sufficiently self-contained. Overall the presentation is very hard to follow. It might be just because I am not familiar with the problem. But even when considering that, in my opinion, the authors should have more taken care of broader audiences, given that the scope of the paper is very narrow and specific. For instance, Section 3 and 4 are extremely technical and very hard to follow. Most of the results (theorems and lemmas) seem to be coming from [ACSS21] without much explanation. I could not evaluate the merit of the paper further if not I just believe their claim. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GN2TnIrbMMo", "reviewer": "Reviewer_qCnJ", "summary": "The paper concerns the computation of an approximate profile maximum likelihood estimator (APML) -- a plug-in estimator used to estimate symmetric properties of discrete distributions. Formally, one is given access to $n$ iid samples from a discrete distribution over a set $\\mathcal{D}$ and the goal is to estimate symmetric properties of this distribution (properties independent of the permutation of the labels of the distribution). This is a broad class of properties which includes practically important examples such as entropy and support size. While information theoretically optimal estimators for specific properties were known previously, the past decade or so has witnessed much interest in the development of statistically and computationally efficient _universal_ estimators for all symmetric properties. Instead of developing specialized approaches for specific properties, these approaches instead propose a unified framework for estimating all symmetric properties. Broadly speaking, there are two main approaches towards building such estimators -- one based on computing APML plug-in estimators and an alternative based on local moment matching. The local moment matching framework is both computationally and statistically efficient and is known to recover optimal sample complexity up to an accuracy threshold of $\\epsilon \\gg n^{-1/3}$. However, while the statistical limit of the APML approach has been established as the regime $\\epsilon \\approx n^{-1/3}$ with prior work demonstrating that no reasonable variant of APML succeeds below the $n^{-1/3}$ threshold, the best known computationally efficient results only hold when $\\epsilon \\gg n^{-1/4}$. The goal of this paper is to bridge this gap by proposing a computationally efficient estimator achieving this $n^{-1/3}$ threshold. \n\nTechnically, the APML approach first constructs a distribution over $\\mathcal{D}$ from the observed data and estimates a symmetric property by evaluating the property on the fitted distribution. A naive approach to do this would be to use the distribution maximizing the likelihood of the observed sample -- i.e the empirical distribution of the samples. However, this leads to sub-optimal sample complexity. The Profile Maximum Likelihood approach instead constructs the plug-in distribution by maximizing the observed profile of the samples which consists of the multiset of frequencies observed in the sample. Unfortunately, this exact formulation while statistically more efficient and optimal in several regimes (when $\\epsilon \\gg n^{-1/3}$), introduces several computational barriers. Fortunately, it suffices to compute an Approximate Profile Maximum Likelihood distribution where one uses any distribution, $q$ which satisfies $\\mathbb{P} (\\phi, q) \\geq \\beta \\max_p \\mathbb{P} (\\phi, p)$ where $\\phi$ is the observed profile for $\\beta \\geq \\exp (-n^{1-\\delta})$ with $\\delta > 0$ and the quality of approximation improving with $\\delta$ ($\\epsilon \\gg n^{- \\min (1/3, \\delta / 2)}$). Prior work had constructed APML distributions for $\\delta = 1/2$ leading to the sub-optimal $n^{-1/4}$ threshold. Informally, this approach first re-parameterizes the distribution being optimized over by discretizing it over a pre-defined set of levels (at levels $(1 + \\alpha)^{i} / (n^2)$ for $i \\in [0, \\ell]$) and only storing the number of elements at a particular level of the distribution. Subsequently, a convex approximation to the PML objective is constructed over this re-parameterized space. Unfortunately, these two steps result in a trade-off where refining the discretization (by lowering $\\alpha$) may better approximate the underlying distribution but worsens the quality of the convex relaxation. The combination of these two factors result in the optimal choice of $\\alpha$ (in prior work) being $n^{-1/2}$ leading to the aforementioned sub-optimal results. The key technical idea of this paper is to effectively eliminate the first step (of approximating the true PML distribution by a discretized approximation) and instead only search for _weak_ APML distributions; i.e distributions satisfying $\\mathbb{P} (\\phi, q) \\geq \\beta \\max_{p \\in \\Delta^R_\\mathcal{D} \\mathbb{P} (\\phi, p)}$ where $\\Delta^R_\\mathcal{D}$ consists of a discretized set of distributions. Here, we are only competitive with respect to the optimal discretized distribution as opposed to the unconditionally optimal distribution. While the objective value of the recovered distribution might be a poor approximation of the optimal PML objective, this nevertheless suffices to accurately estimate a broad class of symmetric properties. In fact, the recovered distribution is at best a $\\exp (- n^{-2/3})$ approximate PML distribution but nevertheless, this still suffices to achieve the optimal $\\epsilon \\gg n^{-1/3}$ threshold. Constructing this estimator however requires a significant refinement of the rounding algorithm which converts the fractional solution of the convex program to a discrete integral solution corresponding to a true distribution. Informally, the novel regime studied in this paper results in a solution matrix which much fewer rows than columns and the guarantee of the rounding algorithm is required to be depend exponentially in only the smaller (row number) dimension while the previous approach only achieved the much looser row + column number bound. The authors construct such a rounding algorithm leading to their improved results.\n\nI do have concerns about the technical writing in the paper. While the proof looks correct and the technical ideas are novel, there are some steps which could benefit from further exposition and others in need of correction. Specifically, Lemmas 4.8 and 4.9 in the paper are applied in a chained fashion in the proof of Lemma 4.5 (Lemma E.1 in the appendix from line 671-677). However, as stated the precondition of the application of Lemma 4.9 are not satisfied by the conclusion of Lemma 4.8. In particular, the condition that the columns sum to integral values is not satisfied as stated in Lemma 4.8. While this is probably true since the construction of the $\\mathrm{trans}$ operation (in Lemma C.1) underlying the transformation $\\mathrm{PartialRound}$ is built off of the operation $\\mathrm{swap}$ which maintains row and column sums by definition, this should still be stated and clarified in the main text. Likewise, this also requires a more precise formulation of Lemma C.1. Additionally, the technical exposition could also be improved surrounding the definition of the rounding algorithm in the appendix. While the main idea behind the rounding algorithm is neat and intuitive, the notation is extremely cumbersome and makes the exposition hard to follow. Providing some intuition prior to their technical definitions in Appendices C-E would help greatly.\n\nOverall, I quite like this paper. It makes significant progress on an important problem essentially closing the gap between the best results achieved by prior computationally efficient APML based estimators and a strong information theoretic barrier. The technical ideas behind the improvement are novel and intricate and are potentially of broad interest to the theoretical machine learning and algorithms communities. While there are minor bugs in the technical statements and some of the technical writing could be improved, these seem quite easy to fix. \n\n**** POST REBUTTAL UPDATE ****\n\nI acknowledge the authors' response and will retain my current evaluation.", "questions": "It would be great if the authors could clarify some of the technical material in the paper in case my current understanding is correct. \n\nAdditionally, I'm also curious about when this $n^{-1/3}$ barrier may be circumvented for narrower classes properties as opposed to all symmetric properties. Applications of such ideas to domains beyond the discrete setting studied in this field would also be interesting to see.", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n-- The paper makes strong progress on an important problem essentially achieving optimal results for this particular approach\n-- The technical ideas in the paper are novel, interesting and non-trivial\n\nWeaknesses:\n\n-- The technical exposition in the paper could be improved both in the main text and the appendix (see main review).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept