In stochastic convex optimization, if $F(w) = E[l(w^Tx,y)]$, when l is a convex, L-Lipschitz loss function, it can be optimized using SGD such that

$E[F(\bar{w}_T)] = \frac{1}{T} E[F(w_t)] \leq \min F(w) + \frac{RL}{\sqrt{T}}$

Assuming that $\vert|w\vert| \leq R$ when the step size is chosen to be $\eta = \frac{R}{L\sqrt{T}}$

SGD's convergence proof relies on access to gradient samples from an unknown distribution D. However, in practice, I have only finite train and test sets. Often, samples are drawn uniformly without replacement from the train set. My questions is, what do you do when you use all available samples? Shuffle them and calculate another epoch? How does this affect convergence?

In general, I understand the concepts of empirical and true risks, but I'm not clear on how they relate to finite sets in practice

  • 2
    $\begingroup$ Yes, after the training data are exhausted, you can either (1) stop training or (2) shuffle the data again and do another loop over the training data. One pass over the training data is commonly called an "epoch," and it turns out that training a model for multiple epochs can often improve its quality. stats.stackexchange.com/questions/242004/… $\endgroup$
    – Sycorax
    Commented Mar 8, 2023 at 21:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.