The Szemerédi Regularity Lemma states that for every $\epsilon>0$, there exists a constant $M$ (dependent only on $\epsilon$) such that every graph $G$ has a $\epsilon$-regular partition of its vertex set into at most $M$ parts.
If one follows the proof (or other discussion therein) closely, $M$ is actually an astronomically large quantity - basically, $M$ is of the order of $2^{2^{2^{\dots}}}$ where the height is polynomial in $1/\epsilon$. Thus, by the time one reaches an $\epsilon$-regular partition guaranteed by the lemma, the part sizes might be some vanishingly small fraction each.
Can I do better if I want to find just one $\epsilon$-regular pair of subsets (not necessarily disjoint or distinct)? Specifically, is it possible to find some $C>0$ such that for every sufficiently small $\epsilon$ (say for all $\epsilon < 1/4$), every graph contains some $\epsilon$-regular pair of vertex subsets (not necessarily disjoint/distinct) such that each is of size at least $(\frac{1}{2})^{(1/\epsilon)^C}|V(G)|$?
I tried the following approach (which is based on one of the common ways of proving the Szemerédi Regularity Lemma): Let the graph $G$ be given. Start off with $X_0=Y_0=V(G)$. If $(X_0,Y_0)$ is $\epsilon$-regular, we are good for this graph $G$. Otherwise, find $A_0\subset X_0, B_0 \subset Y_0$ which causes the regularity to be violated. Let $X_1$ be the larger of $X_0, X_0-A_0$ and $Y_1$ be the larger of $Y_0, Y_0-B_0$. Then each of $X_1, Y_1$ is of size $\ge \frac{1}{2}|V(G)|$. Once again check if $(X_1, Y_1)$ is $\epsilon$-regular and repeat the above argument.
The key then is to show that this process always terminates after a number of steps that is bounded above by polynomial in $1/\epsilon$. However, this is where I am unable to proceed. I tried to track the energy between the two partitions at each step but the increase in energy is getting smaller geometrically (specifically, the energy between the partitions is guaranteed to increase by $\epsilon^4 (1/4)^k$ at step $k$). Thus there is no reason why the process must terminate.
Another idea I have: By considering $G$ or its complement, we can reduce the problem to a bipartite graph with $\ge n(n-1)/8$ edges between the "left" and "right" parts, and the goal is to find a subset on the left and a subset on the right so that these two form a regular pair.