# Criterion for task complexity

For deep learning, are there any theoretical or experimental criterions for task complexity?

For example, we can say roughly, within a set of tasks, tasks that take more gradient updates to achieve the same loss (assuming the losses are on the same scale) are more complex. But how do we talk about this idea rigorously?