Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

Technically, 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.

I 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.

Overall, 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. 

**** POST REBUTTAL UPDATE ****

I acknowledge the authors' response and will retain my current evaluation.
strengths_and_weaknesses: Strengths:

-- The paper makes strong progress on an important problem essentially achieving optimal results for this particular approach
-- The technical ideas in the paper are novel, interesting and non-trivial

Weaknesses:

-- The technical exposition in the paper could be improved both in the main text and the appendix (see main review).
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. 

Additionally, 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
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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.

I 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.

It 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. 

Lemma 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.

I 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.
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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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:

- "Sample-competitive" of an estimator means: the failure probability of the estimator matches the standard $\exp(-\Omega(n\epsilon^2))$ failure probability.

- 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. 

- 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}$?

They 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. 
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. 

questions: - Can you give some comments on why do we care an approximate PML estimator in the intro explicitly?

- 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.
review_title: null

Meta-review: metareview: This work makes theoretical contributions to a long line of work on efficient property estimation. Specifically, the paper closes the gap on the best achievable results via the approximate profile maximum likelihood (PML) approach and the previously known information theoretic lower bound. The reviewers agreed that the technical arguments are novel and non-trivial and the result meets the bar for acceptance.
confidence: Certain
Decision: Accept