Learning discrete distributions from i.i.d. samples is a well-understood problem. However, advances in generative machine learning prompt an interesting new, non-i.i.d. setting: after receiving a certain number of samples, an estimated distribution is fixed, and samples from this estimate are drawn and introduced into the sample corpus, undifferentiated from real samples. Subsequent generations of estimators now face contaminated environments, a scenario referred to in the machine learning literature as self-consumption. Empirically, it has been observed that models in fully synthetic self-consuming loops collapse—their performance deteriorates with each batch of training—but accumulating data has been shown to prevent complete degeneration. This, in turn, begs the question: What happens when fresh real samplesareadded at every stage? In this paper, we study the minimax loss of self-consuming discrete distribution estimation in such loops. We show that even when model collapse is consciously averted, the ratios between the minimax losses with and without source information can grow unbounded as the batch size increases. In the data accumulation setting, where all batches of samples are available for estimation, we provide minimax lower bounds and upper bounds that are order-optimal under mild conditions for the expected ℓ22and ℓ1losses at every stage. We provide conditions for regimes where there is a strict gap in the convergence rates compared to the corresponding oracle-assisted minimax loss where real and synthetic samples are differentiated, and provide examples where this gap is easily observed. We also provide a lower bound on the minimax loss in the data replacement setting, where only the latest batch of samples is available, and use it to find a lower bound for the worst-case loss for bounded estimate trajectories.

Learning discrete distributions from i.i.d. samples is a well-understood problem. However, advances in generative machine learning prompt an interesting new, non-i.i.d. setting: after receiving a certain number of samples, an estimated distribution is fixed, and samples from this estimate are drawn and introduced into the sample corpus, undifferentiated from real samples. Subsequent generations of estimators now face contaminated environments, a scenario referred to in the machine learning literature as self-consumption. Empirically, it has been observed that models in fully synthetic self-consuming loops collapse-their performance deteriorates with each batch of training-but accumulating data has been shown to prevent complete degeneration. This, in turn, begs the question: What happens when fresh real samples are added at every stage? In this paper, we study the minimax loss of self-consuming discrete distribution estimation in such loops. We show that even when model collapse is consciously averted, the ratios between the minimax losses with and without source information can grow unbounded as the batch size increases. In the data accumulation setting, where all batches of samples are available for estimation, we provide minimax lower bounds and upper bounds that are order-optimal under mild conditions for the expected$\ell_{2}^{2}$and$\ell_{1}$losses at every stage. We provide conditions and examples for regimes where there is a strict gap in the convergence rates compared to the corresponding oracle-assisted minimax loss where real and synthetic samples are differentiated. We also provide a lower bound on the minimax loss in the data replacement setting, where only the latest batch of samples is available, and use it to find a lower bound for the worst-case loss for bounded estimate trajectories.

In this paper, we consider the mismatched rate-distortion problem, in which the encoding is done using a codebook, and the encoder chooses the minimum-distortion codeword according to a mismatched distortion function that differs from the true one. For the case of discrete memoryless sources, we establish achievable rate-distortion bounds using multi-user coding techniques, namely, superposition coding and expurgated parallel coding. We study examples where these attain the matched rate-distortion trade-off but a standard ensemble with independent codewords fails to do so. On the other hand, in contrast with the channel coding counterpart, we show that there are cases where structured random codebooks can perform worse than their unstructured counterparts. In addition, in view of the difficulties in adapting the existing and above-mentioned results to general alphabets, we consider a simpler i.i.d. random coding ensemble, and establish its achievable rate-distortion bounds for general alphabets.

In this paper, we consider the mismatched rate-distortion problem, in which the encoding is done using a codebook, and the encoder chooses the minimum-distortion codeword according to a mismatched distortion function that differs from the true one. We establish achievable rate-distortion bounds using multi-user coding techniques, namely, superposition coding and expurgated parallel coding. We give examples where these attain the matched rate-distortion curve but a standard ensemble with independent codewords fails to do so. On the other hand, in contrast with the channel coding counterpart, we show that there are cases where structured codebooks can perform worse than their unstructured counterparts.