Compression schemes provide a general framework for deriving data-dependent risk bounds for learning algorithms. For learning rules based on preferent compression, existing results upper-bound the risk in terms of a sample-dependent complexity
k \boldsymbol{k} k , defined as the cardinality of the compression augmented by the training examples on which the reconstructed hypothesis is inappropriate. These results, however, yield a margin of order
O ( ln N / N ) O(\sqrt{\ln N/N}) O ( ln N / N ) above
k / N \boldsymbol{k}/N k / N . In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level
1 − δ 1-δ 1 − δ , the risk is bounded with probability at least
1 − δ 1-δ 1 − δ by
k N + O ( 1 N ) , \frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right), N k + O ( N 1 ) , uniformly over all possible values of
k \boldsymbol{k} k . Thus, risk estimates for learning algorithms based on preferent compression attain the same law-of-large-numbers rate as the empirical estimate of the probability of a fixed event. We also show that the leading term
k / N \boldsymbol{k}/N k / N is necessary and investigate its relation to the empirical risk. In particular, we identify regimes in which the empirical risk retains the
O ( 1 / N ) O(1/\sqrt{N}) O ( 1/ N ) convergence rate, as well as regimes in which it converges more slowly or ceases to be consistent, while the complexity-based estimator preserves the
O ( 1 / N ) O(1/\sqrt{N}) O ( 1/ N ) rate.