Safety-critical cyber-physical systems (CPS), such as autonomous vehicles and robots, increasingly rely on deep neural networks. While these systems require high prediction accuracy, they must simultaneously satisfy strict end-to-end timing constraints under tight memory and energy budgets. The challenge extends beyond static inference: realistic deployments face non-stationary data and fluctuating power conditions, necessitating online adaptation systems. However, existing machine learning methods largely overlook the timing, memory, and accelerator-contention constraints inherent to embedded CPS, resulting in unpredictable latencies and frequent out-of-memory failures.This dissertation addresses the gap between algorithmic machine learning and real-time systems by developing a predictable and self-adaptive On-Device machine learning stack. We demonstrate that predictable learning is a distinct systems problem requiring cross-layer coordination rather than isolated algorithmic...