LotteryCodec: Searching the Implicit Representation in a Random Network for Low-Complexity Image Compression

We appreciate the reviewer’s valuable comments and for highlighting Choi’s ICML 2023 paper. Our detailed responses to each comment are as follows:

• (1). Following the suggestion, we have conducted additional MS-SSIM experiments on the Kodak dataset. The results, presented in Table 4.1, demonstrate that our method consistently outperforms VTM, achieving up to a -43.81% reduction in BD-rate, closely matching ELIC's performance. We note that previous overfitted codecs only focus on PSNR, and direct MS-SSIM optimization is unstable for those baselines (as reported in C3 and its extension work (Fig. 6 and line 3 in [1])).

  [1]. Ballé, Jona, et al. ``Good, Cheap, and Fast: Overfitted Image Compression with Wasserstein Distortion.''

Table 4.1 MS-SSIM / bpp performance on Kodak dataset

• (2-3). We have compared the encoding (NVIDIA L40S) and decoding latency of LotteryCodec and its BD-rate against other alternatives (see Table 4.2 with a structured pruning over masking ratio of 0.8). Additional latency results across resolutions are reported in Tables 2.1 (Reviewer bWTB) and an coding exmaple is given in Table 3.2 (Reviewer itee). Given the fast decoding speed of overfitted codecs, we evaluate all overfitted codecs on an Intel Xeon CPU. Overall, our method achieves faster decoding with slightly higher encoding time, compared with other overfitted codecs. Additional analysis is provided in our response to Reviewer itee. We want to note that real-world latency is affected by many uncontrollable factors in a lab setting and can be significantly reduced through various optimization techniques, making fair coding speed comparisons difficult. For example, [2] reported that Cool-chic achieves a 100ms latency using a C API for binary arithmetic coding, while our implementation is slower due to the lack of such optimization. Nonetheless, we recognize the importance of real-world latency and provide these evaluations for a practical perspective. To ensure fairness, all reported results are based on same unoptimized decoding implementations, with no methods using C API optimizations. We expect similar speedups across all methods with these techniques.

  [2] Blard, Théophile, et al. "Overfitted image coding at reduced complexity." 2024.

Table 4.2 Coding time for Kodak images

• (4). We have conducted extensive additional ablation studies in the rebuttal (as shown in these tables) and will include visualizations of these results to support our analysis in our revised manuscript, such as (a). impact of each component (Tables 3.1 from Reviewer itee ) and (b). training latency vs. performance (Tables 3.2 from Reviewer itee), (c) visual comparison for MS-SSIM results (Table 4.1 here). For clarity, here we provide the corresponding numerical results in tabular form in the above rebuttal.
• (5). We will add a discussion over Choi et al.’s ICML 2023 paper in our revised manuscript. Here, we highlight the key differences between their approach and ours: While both studies leverage the Lottery Ticket Hypothesis (LTH) for INRs, Choi et al. apply LTH to video representation using image-wise encoding with multiple supermask overlays and unpruned biases, boosting representation at the cost of increased complexity and bit rate. In contrast, our LotteryCodec adopts a pixel-wise model and focuses on low-complexity image compression problem. We introduce mechanisms such as Fourier initialization and Rewind modulation to enhance rate-distortion performance, distinguishing our approach from Choi’s. Although Choi’s method is a novel contribution to video representation, it still falls short of state-of-the-art compression techniques. We will also add one paragraph to discuss the potential extension of our work for video compression (see response to Reviewer bwTB for more details).
• (6). We have proofread the manuscript again and corrected the typos.

We appreciate the reviewer's valuable comments. Our responses to the reviewer's main concerns are as follows:

• Encoding/decoding complexity. Practical encoding/decoding time and peak memory usage across images with various resolutions are reported in Table 2.1 (see our response to Reviewer bWTB), with additional coding speed results reported in Table 4.2 (response to Reviewer ynP1) and Table 3.2 (this response). All of these results are based on unoptimized research code and current hardware, which can be significantly improved with proper engineering optimization (e.g., C API, optimized wavefront decoding). Overall, our method has a slightly longer encoding time than other overfitted codecs due to additional gradient-based mask learning process, but it offers greater flexibility and faster decoding. Notably, the lottery codec hypothesis (LCH) can provide potential for parallel encoding by re-parameterizing distinct network optimization into batch-wise mask learning, highlighting its advantage of scalability for efficient large-scale image encoding.

• Qualitative analysis. In addition to experimental evidence, we provide a rough analysis of the LCH to explain why it is likely to hold (see our response to Reviewer bWTB). Based on the LCH, we can intuitively justify why the proposed LotteryCodec outperforms previous overfitted codecs in terms of rate-distortion performance. The rate formulations for overfitted codecs and our LotteryCodec are given in Eqs. (2) and (5), respectively. They show that the rate of overfitted codecs depends on $\{\hat{z}, \hat{\psi}, \hat{W}\}$, while our method is determined by $\{\hat{z}, \hat{\psi}, \tau, \hat{\theta}\}$. According to LCH, to achieve the same level of distortion, we can find a pair of $(\hat{z},\tau)$ such that the bit cost for $\hat{z}$ and $\hat{\psi}$ is equal to that of overfitted codecs. While each quantized parameter in $\hat{W}$ typically requires over 13 bits, our binary mask $\tau$ uses just 1 bit per entry. Despite its higher dimensionality, $\tau$ contributes significantly less to the total rate. Moreover, since $\hat{\theta}$ is lightweight, the combined rate of $\tau$ and $\hat{\theta}$ remains lower than that of $\hat{W}$, resulting in a lower compression rate and improved RD performance.

• Ablation study. We conducted additional ablation studies to clarify the impact of each component in our design. As shown in Table 3.1 below, removing the Supermask network and using only the modulation network increases BD-rate by +12.45%, highlighting the importance of the random network. Removing ModNet and directly feeding ${z}$ into the random network (with different overparameterization configurations) results in a performance drop of up to +14.99% due to high overparameterization costs. Additional ablation studies and visualizations of other components are provided in Table 4 of Appendix C in our original paper.

Table 3.1 BD-rate change due to removal of individual components from LotteryCodec

Table 3.2 Encoding cost for a 2K image as an example

(Size: 1292 × 1945, “davide-ragusa-716” in CLIC2020, optimal PSNR: 37.18 at bpp 0.196, $d=24$, ratio=0.2, peak memory: 5.64 GB)
(10–20k steps can yield decent performance)

We thank the reviewer for valuable comments. We first respond to the reviewer's main concerns:

• W1: Proof of Lottery Codec Hypothesis (LCH). Although a rigorous bound supporting the LCH is not available, we can provide a rough validation based on existing proofs for the Strong Lottery Tickets Hypothesis (SLTH). Suppose a codec $g_{{W}}({z})$ is overfitted to an image $S$ with distortion $\sigma$. According to SLTH, for any $\epsilon>0$, there exists a subnetwork within a sufficiently overparameterized network $g_{W'}$, defined by a supermask $\tau$, such that $d(g_{{W}}({z}),g_{{W'}\odot \tau}({z})) \le \epsilon$ (suppose $d$ is a distortion evaluated pixel by pixel). Thus, reconstructing the image $S$ using $g_{{W'}\odot \tau}({z})$ results in a distortion of at most $\sigma+\epsilon$. Now, we can further decrease the distortion by optimizing the latent vector over a set of $z'$ satisfying $H(z')=H(z)$, along with the supermask $\tau$. Since $\epsilon$ can be made arbitrarily small, it is highly likely that we can find a pair of $(\tau',z')$ such that $d(S,g_{{W'}\odot \tau'}({z'}))\le \sigma$.
• W2: We will add the following discussion about the encoding time: "LotteryCodec’s low and flexible decoding cost is particularly beneficial in multi-user streaming scenarios, where encoding can be done once and offline, to support many users decoding the same content. While high encoding complexity remains a key bottleneck for all overfitted codecs, including ours, potential acceleration strategies include meta-learning, mixed-precision training, and neural architecture search. Notably, LotteryCodec also enables parallel encoding for overfitted codec by reparameterizing distinct network learning processes into a batch of mask learning process."
• W3: To address the reviewer's concern about ultra-high-resolution images, we provide Table 2.1 to detail the training and inference cost across various resolutions (with mask ratio $0.8$ and ARM model of $d=16$). An additional example of 2K image encoding is shown in Table 3.2 (responses to Reviewer itee).
• W4: We will add the following paragraph to discuss the potential extension to video compression: "LotteryCodec can be extended as a flexible alternative for video coding. By sharing modulation across adjacent groups of frames (GoF) and applying distinct/weighted masks, it can additionally encode temporal information into the network structure, potentially yielding a lower bit cost. Moreover, video coding enables adaptive mask ratio selection across GoF, offering greater flexibility in both computational complexity and rate control."

Table 2.1: Encoding time for different images. OM means out of memory ($>32$ GB).

Responses to questions:

• Q1&2: We refer the reviewer to Fig. 13 in Appendix E, which details the cost of each component. In the high-rate regime, the total cost of $\psi$, $\theta$, and $\tau$ accounts for less than 5%. The binary mask $\tau$ is compressed via range coding (range-coder on PyPI) with a static distribution.
• Q3: To validate the lottery codec hypothesis, the (4,128) setting suffices. While wider networks (e.g., 4-256) can reduce distortion without increasing the bit cost for $z$ (hence can validate the hypothesis), they also raise the bit cost for the mask $\tau$ and introduce greater training overhead, which often reduces overall compression efficiency. (An example of different configuration results can be seen in last column of Table. 3.1 for Reviewer itee). This motivates us to design the modulation mechanism.
• Q4. See our response to W1.
• Q5&6. We present the coding cost of various schemes in Table 4.2 of our response to Reviewer ynP1, and report resolution-dependent coding costs in Table 2.1 above. The proposed method shows scalability to ultra-high-resolution images, albeit with increased coding time. Note that, significant speedups can be achieved through engineering and hardware optimizations. For example, we can accelerate the method via ONNX/DeepSparse library to reduce the decoding time into $20–80$ ms on a CPU. Additional techniques, such as symmetric/separable kernels, filter-based upsampling, and wavefront decoding, can further enhance the speed of overfitted codecs.

We thank the reviewer for the valuable comments and recommending two interesting papers. We will add (a) proper discussions of both papers, and (b) suggested ablation studies and tables to the revised manuscript.

For a discussion of Choi et al. (2023), please refer to our response to Reviewer [ynP1]. Regarding Mehta et al. (2021), while their dual-MLP framework also uses a modulation and synthesis network, it targets multi-instance representation rather than compression. Key differences include: (1) our synthesis network is based on the Lottery Ticket Hypothesis; and (2) our ModNet introduces rewind modulation to the synthesis network via concatenation for greater flexibility. Additional ablations over different modulation methods can be seen in Table 4 and Fig. 12 of our original paper.

Responses to the remaining comments:

• Modifications for clarification: ”As shown in Eqs. (2) and (5), the rate of overfitted codecs depends on $\{\hat{z}, \hat{\psi}, \hat{W}\}$, while the rate of our method is determined by $\{\hat{z}, \hat{\psi}, \tau, \hat{\theta}\}$. According to Lottery Codec Hypothesis (LCH), our bit cost for $\hat{z}$ and $\hat{\psi}$ matches that of standard overfitted codecs. While each quantized parameter in $\hat{W}$ typically requires over 13 bits, our binary mask $\tau$ uses just 1 bit per entry. Despite its higher dimensionality, $\tau$ contributes significantly less rate. Moreover, since $\hat{\theta}$ is lightweight, the combined rate of $\tau$ and $\hat{\theta}$ remains lower than that of $\hat{W}$, resulting in improved compression efficiency.“

• Ablation study. We conducted additional ablation studies to assess the contribution of each component. See Table 3.1 and its discussion in our response to Reviewer [itee].

• Coding speed. We report coding speed for different baselines and resolutions in Table 4.2 (response to Reviewer [ynP1]) and Table 2.1 (response to Reviewer [bWTB]).

• Detailed BD-rate results are provided and will be included in the manuscript:

Table 1.1. Detailed BD-rate data points

• We will cite the C3 source in the revised manuscript. We would also like to clarify that using either a re-implementated or the original C3 code does not affect the validation of the LCH. The goal of the experiment (Fig. 6) is to demonstrate that, in an overfitted codec setting, the synthesis network can be replaced by a subnetwork of a randomly initialized network while maintaining comparable distortion performance. To ensure a fair comparison, only the synthesis network is replaced, with all other components kept identical to the target overfitted codec structure (see Fig. 8).

Answers to questions:

• Q1. The current figure reports theoretical minimum complexity, excluding the effect of masked parameters (similar evaluations can be seen in [1-2]). This theoretical lower bound can be approached using sparsity-aware implementations (cuSparse/DeepSparse) on compatible hardware. We adopt this metric to estimate the decoding complexity because both practical MACs and run-time for unstructured sparse networks are heavily influenced by many engineering factors. Thanks to the reviewer’s suggestion, we have decided to also report coding time with a simple structured pruning strategy (see Tables 2.1 of response to Reviewer [bWTB]), showing our decoding efficiency, especially on high-resolution images. Additionally, we provide both theoretical upper and lower bounds on complexity (Table 1.2), where the upper bound includes all operations without any pruning. The practical complexity lies between these bounds, depending on its implementation. Note that compared to the C3 baseline, even a unpruned LotteryCodec can achieve better BD results (-0.1% vs. 3.24%) with comparable complexity (2822 vs. 2626). We will revise the figure using a dashed region to clearly illustrate this range and clarify it in Fig. 1 and Fig. 14 as well. By presenting both the theoretical complexity and the measured run-times, we aim to offer a comprehensive evaluation of our flexible decoding complexity.

  [1]. Han, Song, et al. "Learning both weights and connections for efficient neural network"

  [2]. Han, Song, et al. "Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding"

Table 1.2 Flexible BD-rate vs. MACs/pixel region over Kodak

• Q2. Experiments in Figs. 7(a)-(b) do not impose such constraints, where model architectures follow their original papers.
• Q3. Our network is roughly half the size of C3, and our entropy model uses $d = \{8, 16, 24, 32\}$ vs. C3 ($d = \{12, 18, 24\}$). (Table 1 in our paper for more details)