Low-power embedded technology offers a roadmap for enabling deep learning (DL) applications in mobile scenarios, like future autonomous vehicles. However, the lack of breakthrough power efficiency improvements can jeopardize the realization of truly “cognitive” mobile systems that meet real-time deadlines. This work focuses on the new generation cloud-backed mobile cognition system architecture where vehicles execute DL applications with dynamic assistance from the cloud. We unveil opportunities for power-efficient inferencing at the edge through a technique that balances inference execution across the cloud and the vehicle. This level of adaptation results in significant power efficiency improvements compared to all or nothing solutions, where inferences execute either completely on the vehicle or completely in the cloud. In addition, the cloud can have an active role in helping the vehicle to improve its DL capabilities by communicating relevant model updates, with up to 63% bandwidth savings and negligible accuracy degradation when the proposed relevance-driven federated learning technique is used. Finally, the cloud-backed mobile cognition concept is extended to the case of “flying clouds” where vehicles connect to flying drones that provide services while in flight. Although their capabilities are not on par with the stationary cloud, the flying cloud reduces services’ latency significantly and enables critical functionalities.