Oracle efficient truncated statistics

The paper emphasizes that its primary contribution is improving the poly(1/α) dependency from Lee et al. (2023) to poly-log(1/α). However, a quick look at that paper reveals that Lee et al. (2023) focuses on estimating the parameter, not the truncated distribution. Therefore, I am unsure how significant this improvement is.

$**Response:**$ Our result implies the parameter estimation of Lee et al. (2023) (see Corollary 1.7, line 156), as their assumptions include the strong convexity of $\mathcal{L}_S$ (or properties that imply strong convexity). Consequently, close values in $\mathcal{L}_S$ (as per our result) immediately imply close values in $\theta$ (see Corollary 1.7). However, in our setting, we do not assume strong convexity, allowing us to handle a more general class of problems, albeit with a trade-off in guarantees.

Section 3 is quite dense, and the logical flow of the proof is not well explained. Overall, the section feels extremely unstructured. I suggest that the authors improve the writing in Section 3 by, for example, providing a clear roadmap of the proof at the beginning of this section and clearly explaining how each lemma contributes to the final proofs. Please also refer to the "Questions" section.

$**Response:**$ Thank you for the suggestion. Taking this into account, we have included a roadmap starting on line 365.

Questions: I assume you are using θ∗ to denote the ground truth parameter throughout the paper, but in Corollary 3.9, it seems to be defined differently. Is the θ∗ in Corollary 3.9 the ground truth as well? In the second assertion of Corollary 3.10, why is the consequence stated for θ∗ when your condition is for θ0?

$**Response:**$ You are absolutely right; it was a typo. The stated consequence applies to $\theta^0$, i.e., $p_{\theta}(S) \geq p_{\theta^0} \alpha \exp(-\epsilon)$.

Can you provide a detailed proof of Corollary 3.10? Specifically, it is unclear how the definition θ0=Ep[X] plays a role in the proof.

$**Response:**$ Certainly, here is a detailed proof of Corollary 3.10. First, I hope any misunderstanding wasn’t due to the typo $\theta^0 =E_p(T(x))$. Now, to proceed with the proof: From Corollary 3.9, we have that $p_{\theta^0}(S) > \alpha$, as $\theta^0$ is the parameter that minimizes $\mathcal{L}(\theta)$ and thus also minimizes $\mathcal L_S(\theta)$. Consequently, $\theta^0$ is the only feasible parameter for this sublevel set due to the strong convexity of $\mathcal L(\theta)$. Therefore, we can invoke part 2 of Corollary 3.9. Specifically, applying Corollary 3.9, part 2 (exponential decrease) with $\theta_2 = \theta^\ast$ and $\theta_1 = \theta^0$, we obtain: $P_{\theta_2}(S) \leq P_{\theta_1}(S) \exp(\mathcal L(\theta_1) - \mathcal L(\theta_2)).$ Since $P_{\theta_2}(S) = \alpha$ and $P_{\theta_1}(S) \leq 1$, taking the logarithm and rearranging terms yield: $\mathcal L(\theta^\ast) \leq \mathcal L(\theta^0) + \log(1/\alpha).$ The second part follows immediately from Observation 3.8, applied to $\mathcal L(\theta) \leq \mathcal L(\theta^0) + \log(1/\alpha) + \epsilon$ and the minimizer $\theta^0$.

In the proof of Theorem 3.3, how do you derive pθ(S)≥1α2e−ϵ? I assume you are referring to Corollary 3.10, not Corollary 3.9? Moreover, what is the significance of this result in the overall proof?

$**Response:**$ Correct, this is Corollary 3.10. The significance of this result is that, for every $\theta$ in the projection domain $D$ (line 515), the probability mass that each $\theta$ assigns to $S$, i.e., $P_{x \sim p_{\theta}}[x \in S]$, is at least a constant fraction of $\alpha^2$. This clarification has been added to the roadmap to the proof on lines 365–377.

Can you clarify the terms w and f in the proof of Theorem 3.3? How do they relate to θ and L?

$**Response:**$ Thank you this has been clarified, $f$ is $\mathcal L_S$ and $w$ is $\theta$. Typos: Line 466: min{min... } Line 519: It should be "Here" instead of "Where" to start a new sentence.

$**Response:**$ Thank you, we fixed these typos/mistakes.

-- It would be nice if the analogues of 1.6 and 1.7 from prior work were stated formally rather than alluded to in prose, for easier comparison. For example, I am still a little unsure after reading the prose if prior work gives an algorithm with poly(1/α) dependence for the special case of Gaussians?

$**Response:**$ Thank you for the suggestion on improving our exposition. To address this, we have included a section in the appendix rephrasing these results to reflect our perspective. Interestingly, the exponential family algorithm by Lee et al. represents an improvement over the pre-existing result for Gaussians, as their abstraction streamlined the proofs and avoided relying on inefficient bounds for how the mass assigned to a truncation set $S$ changes with parameter adjustments. Our result is tight in this sense, providing an optimal solution for the Gaussian case as well, particularly in identifying high-mass regions.

Questions: l.45: the definition of A(θ) is wrong given the previous definition of pθ;

$**Response:**$ Thank you, we fixed it.

Definition 1.1 should not be a definition but a proposition;

$**Response:**$ This is a definition; we define $\mathcal{L}$ as a function possessing specific properties.

Theorem 3.3 and Theorem 3.4 are nearly identical, differing only in their dependencies on α and α^2, I find it confusing to present both; what is the rationale behind this choice?;

$**Response:**$ The reason is that the theorem with dependency on $\alpha$ is sharp (line 374-5), so in that sense it gives a complete answer to how low can the dependency on $\alpha$ in terms of finding a suitable optimization domain that has at least a constant fraction of mass of $\alpha$. However its proof is a little bit tedious and technical, but as outlined in lines 376-377 it is just a repeated application of the techniques used in theorem 3.3. To summarize the proof for $\alpha^2$ is much cleaner and demonstrates the main idea of our paper, without tiring the reader. On the other hand, the inclusion of theorem 3.4 gives best possible dependency of alpha possible.

In Lemma 3.7, u and u^ are never defined, I guess that they authors meant θS∗ and θ^?

$**Response:**$ Thank you that was a typo, it is as you suspected. It has been fixed.

Proof of Theorem 3.3: Inconsistent notation for Θ0 that appears as $Θ0 and θ0; l.519:

$**Response:**$ The notation is not inconsistent; we use $\theta^0$ as it appears on corollary 3.10. This has been made clear in the newest version, thank you.

why is there a L^3 term in the lower bound on N?

$**Response:**$ Notice that the bound there is not $\epsilon$ but $\epsilon/L$, therefore the $L^3$ term. I hope this has made it clear.

It appears as L in Lemma 3.7; l.521: the bound on ‖θ0−E[T(x)]‖2 holds with probability at least 1−δ (according to Lemma 3.7). However, the bound is treated as if it hold almost surely in the rest of the proof. I believe that this will cause an issue when bounding the deviation of f(θ¯) from f(θ∗(l.529). Can it be easily fixed?

$**Response:**$ Everything we write subsequently, in the proof, holds almost surely on that event. And then the result follows from a union bound, this is a common argument in this literature, i.e. finding a good initialization point with good probability and then conditional on that amplifying the probability of the output of gradient descent. If this doesn’t clarify things please inquire further.

I do not understand the inequalities l.525. Since it it never defined, I assumed that w(0):=θ0. In this case I don't understand where the 1/λ multiplicative term comes from in the first inequality.

$**Response:**$ Indeed $w^{(0)} = \theta_0$, the $1/\lambda$ should have been after the $\leq$ sign. Thank you for catching that. We have also added that w, f come from the statement of the theorem 3.12.

Moreover, I cannot reproduce the second inequality using the current information in the proof. Can the authors clarify this part?

$**Response:**$ Is the inequality $| \theta_0 - \theta^\ast|^2 / \lambda \leq O( \log^2 ( 1/\alpha) )$ that you are inquiring for? In that case it is from strong convex i.e. $| \theta_0 - \theta^\ast| ^2 \leq 2/\lambda \left (\mathcal L ( \theta_0) - \mathcal L( \theta^\ast) \right ).$

There are many typos in the proof: f instead of L, w is not defined, l.525 the bound holds for the norm of the gradient, the index θ is not defined l.524.

$**Response:**$ The variables $f$ and $w$ were introduced in the statement of Theorem 3.12 (PSGD) to aid the exposition, but this was not explicitly stated. We have corrected the typo regarding the norm of the gradient and revised the text to clarify this connection, thereby improving the overall clarity of the exposition.

Minor comments: -Line 53: “resoursed”->“resourses”

$**Response:**$ Thank you we fixed it.

-Lines 109-114: The example here needs some rephrasing. I get the point you are making, but technically, when you fix a set (S=[0,1] in this case), the mass assigned to it and the variance of the distribution, there is a unique distribution (NOT multiple ones) satisfying these constraints. Maybe you could say O(α) mass.

$**Response:**$ In the example, we considered the family $N(\mu, \sigma^2)$ without fixing the variance. However, we fixed the variance in the case where the learner can make queries to ensure that the probability bound holds. We have added a clarification to the example to make this more explicit. Thank you for your feedback.

-Lines 131 and 371: In the second argument of the KL distance, it should be θ^ in the subscript. -Line 388: Usually the word “requires” is used for lower bounds. Maybe say “a good initialization can be found” -Line 399: “estimate of”->”bound on”

$**Response:**$ Thank you for the suggestions. We have implemented all of them.

-Line 448: Proof of Observation 3.8: The statement seems reasonable, but I think that the proof is incomplete. You show that the exponential is at most 1, but you need something stronger since it could be that Prθ′[S]>Prθ[S] right?

$**Response:**$ For the proof of Observation 3.8: Since $\theta'$ is the minimizer of the constrained optimization problem $\bar{L}$, we immediately deduce that $\mathcal L_S(\theta') \leq \mathcal L_S(\theta)$. Interestingly, this result is purely a consequence of this observation. Specifically, by rearranging terms, we obtain: $\log(\Pr_{\theta'}[S]) \leq \log(\Pr_{\theta}[S]) + \mathcal L(\theta) - \mathcal L(\theta').$ Applying the exponential function to both sides yields: $\Pr_{\theta'}[S] \exp(\mathcal L (\theta') - \mathcal L(\theta)) \leq \Pr_{\theta}[S].$ Thus, the result follows. You are absolutely correct that $\Pr_{\theta'}[S] > \Pr_{\theta}[S]$ may indeed hold, but only under the condition, as the proof demonstrates, that $\mathcal{L}(\theta') < \mathcal{L}(\theta)$.

-Line 490: “SE(K,β)”->“SE(K2,β)”

$**Response:**$ We fixed it, thank you.

I believe the authors should make the assumptions they need to use clearer from the introduction to improve the presentation quality. For example, the strong convexity and smoothness assumption is not mentioned in the statement of Theorem 1.5, which makes it seem too strong.

$**Response:**$ Thank you for the suggestion, it is indeed something that should have been included in the theorem.

Questions: In section 1.1 (line 133), you mention that: “the fact that our algorithm only requires an α-truncated sample oracle is what enables us to achieve a polynomial number of oracle calls to the membership oracle to S”. Can you elaborate on that? Is this not due to the threshold that you introduce in the optimization problems? It seems that assuming the truncated oracle access only allows logarithmic dependence instead of polynomial, which you would get via rejection sampling.

$**Response:**$ You are correct; this is due to the optimization problems we introduce. These optimization problems ensure that the algorithm operates using only an $\alpha$-truncated oracle, with each call to the oracle assumed to always produce an answer. Please let us know if this does not fully address your concern.