All charts of machine learning performance (y-axis:accuracy 0.0-1.0) across epochs have the below shape. Is there any research that explain how this convergence is bounded O(n) where n is the number epochs (and ultimately the number of examples the algorithm visits).

enter image description here

  • $\begingroup$ This does not look at all like a logarithmic shape. $\endgroup$
    – user16034
    Jun 15, 2023 at 13:27
  • $\begingroup$ @YvesDaoust. Thanks for the note. I rephrased. Would logistic be a better fit? $\endgroup$ Jun 15, 2023 at 22:04
  • $\begingroup$ Depends how exactly you define it. $\endgroup$
    – user16034
    Jun 15, 2023 at 22:22

1 Answer 1


From what I understand for Neural networks depending on the optimization method used Stochastic gradient Descent or Nesterov Acelerated Descent the convergence is bounded by $O (1/k)$ and $O(1/k^2)$ respectively. This is expressed in terms of loss reduction e.g. how quickly can the algorithm reduce error, where k is the number of iterations it takes for the algorithm to achieve it.

To describe the above chart that is performance overtime rather than loss reduction. We could say $1 - O(1/k)$ since 1.0 is considered the upper perfect learning scenario.

See https://angms.science/doc/CVX/CVX_FoM_tight_rate.pdf


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.