Intuitively, what I am aiming for is just an inequality between the test and train error at that $\tilde f_t$. I don't hope to have a low error (on either train or test data) in general, but rather a claim saying that the model has started overfitting to the training data more than its fit to the unseen data. I hope this clarifies.

Sorry for the confusion. I meant to compare the losses (not the rate of convergence) on the training samples and unseen test samples. I want to obtain an inequality on training loss and test loss for any intermediate gradient solution. For simplicity, we can assume ℓ is convex in parameters. For example, will this hold for a linear regression problem where ℓ is MSE? If not, can we construct a counter example?