I am learning this paper

Our lower bound on the latter algorithms holds even if the algorithms are enhanced with an arbitrary kernel function

does "bound holds" mean the "bound" has an almost fixed value?

2 Answers 2


This means that the lower bound, which is given by a formula later in the paper (the quote is from the abstract) is valid for both the initial algorithms and for the related enhanced algorithms.

"holds" here is a verb meaning "remains valid", and "lower bound" is a noun phrase, meaning the formula which specifies the smallest result of the algorithm, in this case the "loss".

"bound holds" is not a grammatical unit here.

This means that after seeing a fraction of A/2B of all n instances, the average loss is still at least the constant A/2 . (emphasis added)

"at least" indicates the lower bound.


I think it means that the lower bound is unchanged when the algorithms are changed in the specified way.

It says nothing about whether the bound changes or not in other circumstances.

You must log in to answer this question.