However the average rate vs. memory tradeoff has never been completely characterized for any non-trivial case. In this paper, we prove that the exact optimal tradeoff for the average rate for two-user case can be achieved using the caching scheme we provided in [@yu2016exact] (see Appendix \[app:ave2\]).

To prove the Theorem \[th:gconst\], we derive new converse bounds of $R^*$ and $R^*_{\textup{ave}}$ for all possible values of $K$, $N$, and $M$. We highlight the converse bound of $R^*$ in the following theorem:

\[th:general\] For a caching system with $K$ users, a database of $N$ files, and a local cache size of $M$ files at each user, $R^*$ is lower bounded by $$R^*\geq s-1+\alpha-\frac{s(s-1)-\ell(\ell-1)+2\alpha s}{2(N-\ell+1)} M, \label{eq:th2}$$ for any $s\in\{1,...,\min\{N,K\}\}$, $\alpha\in[0,1]$, where $\ell\in\{1,...,s\}$ is the minimum value such that[^12] $$\label{eq:sml}
            {\frac{s(s-1)-\ell(\ell-1)}{2}+\alpha s}\leq  (N-\ell+1)\ell.$$

The above theorem improves the state of the art in various scenarios. For example, when $N$ is sufficiently large (i.e., $N\geq \frac{K(K+1)}{2}$), the above theorem gives tight converse bound for $\frac{KM}{N}\leq 1$, as shown in (\[eq:46\]). The above matching converse can not be proved directly using converse bounds provided in [@ghasemi15; @lim2016information; @sengupta15; @DBLP:journals/corr/WangLG16; @tian2016symmetry; @prem2015critical] (e.g., for $K=4$, $N=10$, and $M=1$, none of these bounds give $R^*\geq 3$).

