converse bounds tightly characterize the peak rate-memory tradeoff in all three presented scenarios.[]{data-label="fig:compare"}](K3.pdf "fig:"){width="0.95\linewidth"}

[.45]{} ![Numerical comparison among the two converse bounds presented in Theorem \[th:general\] and Theorem \[th:2\], and the upper bound achieved in [@yu2016exact]. Our converse bounds tightly characterize the peak rate-memory tradeoff in all three presented scenarios.[]{data-label="fig:compare"}](K4.pdf "fig:"){width="0.95\linewidth"}

[.45]{} ![Numerical comparison among the two converse bounds presented in Theorem \[th:general\] and Theorem \[th:2\], and the upper bound achieved in [@yu2016exact]. Our converse bounds tightly characterize the peak rate-memory tradeoff in all three presented scenarios.[]{data-label="fig:compare"}](K5.pdf "fig:"){width="0.95\linewidth"}

In the rest of this paper, we prove Theorem \[th:gconst\] for the peak rate in Section \[sec:ge\], and we prove Theorem \[th:general\] in Section \[sec:gconv\]. For brevity, we prove the rest of the results in the appendices. Specifically, Appendix \[app:proof\_tm3p\] proves Theorem \[th:exact5\] for the peak rate, Appendix \[app:proof\_tm4\] proves Theorem \[th:2\], Appendix \[app:ave1\] proves Theorem \[th:gconst\] for the average rate, and Appendix \[app:ave3\] proves Theorem \[th:exact5\] for the average rate.

Proof of Theorem \[th:gconst\] for peak rate {#sec:ge}
============================================

In this section, we prove Theorem \[th:gconst\] assuming the correctness of Theorem \[th:general\]. The proof of Theorem \[th:general\] can be found in Section \[sec:gconv\]. For brevity, we only prove Theorem \[th:gconst\] for 