With the growing ubiquity of video content, efficient video analytics has become essential for applications such as surveillance, autonomous driving, and augmented reality. Yet, deploying video analytics models on resource-constrained edge devices and in low-bandwidth environments remains challenging. A dominant method for handling demanding video analytics tasks on edge devices has been to offload computation strategically from the edge device to servers. However, all prior solutions fail to offload under severely constrained, real-world network conditions (such as, a few-Mbps satellite network) due to the much higher data rates associated with video tasks. We introduce ApproxBit, a system to optimize shared edge-to-cloud processing for video analytics tasks; the two that we experiment with are video action recognition and video question answering. ApproxBit integrates an encoder within the video model, uses learned binary codes to effectively compress and offload data, and adaptively decides on the offloading point depending on the network bandwidth. ApproxBit’s adaptive and efficient data compression, which reduces the original feature map size by up to 2142.4 ×, makes it an ideal solution for video analytics on edge devices, especially with constrained networks. We evaluate ApproxBit on the two video tasks, across different model architectures (e.g., convolution- and Transformer-based) and multiple datasets (e.g., Something-Something-v2, Kinetics, and MSVD). Our results of latency and accuracy are superior over baselines: edge-only processing, server-only processing, DNN Surgery [ToCC ’23], full offloading of H.264-encoded videos, DeepCOD [SenSys ’20], neural video compression DCVC-FM [CVPR ’24], and LimitNet [MobiSys ’24]. We also demonstrate ApproxBit’s adaptivity to changing network conditions, and generalization in a real-world user study.