Can deep neural networks achieve real-time video analysis? Recently, convolutional neural network based, deep architectures (DNN) such as AlexNet and VGGnet have been very successful in image classification challenges (e.g. ImageNet) and action recognition/video classification tasks. They surpassed hand-crafted feature-based approaches by a large margin in various cases, and thus became the new state-of-the-art approach for many computer vision problems, including but not limited to classification, object detection, and action recognition.

In the state-of-the-art DNN papers, the focus is mostly on achieving a better classification or detection accuracy, whereas the complexity of the model and computational issues stay rather in the background. This made me think whether these DNN-based approaches would be suitable in future real-time action recognition applications (e.g. video surveillance, pedestrian detection etc.) where the test time speed is of utmost importance. It is very important, for example, whether an algorithm can classify the captured video in real-time and respond very quickly to the classification decision to take some pre-determined action.

Are there any DNN-based action recognition algorithms published so far that can satisfy these criteria about real-time operation (possibly even at the expense of classification accuracy)? 

I believe for many practical applications, achieving real-time or even faster-than-real-time performance is and will be much more important than providing marginally more accurate classification results compared to the previous state-of-the-art-.
Nvidia seems to have published some white papers comparing DNN inference performance between high-powered CPUs and (of course) Nvidia GPUs.  (one example)

Ballpark seems to be that some systems can meet or exceed typical video frame rate thru-put for some class of DNN classification tasks.  Whether those image sizes and/or DNN architectures and hyperparameters meets your needs is one question, and whether desktop/server-class GPUs fit your desired power envelope is another question.