Abstract: Adaptive optimization plays a pivotal role in federated learning, where simultaneous server- and client-side adaptivity have been shown to be essential for maximizing its performance. However, the scalability of jointly adaptive systems are often constrained by limited resources in communication and memory. In this paper, we introduce a class of efficient adaptive algorithms, named FedAda$^2$, designed specifically for large-scale, cross-device federated environments. FedAda$^2$ optimizes communication efficiency by avoiding the transfer of preconditioners between the server and clients, while simultaneously utilizing memory-efficient adaptive optimizers on the client-side to reduce extra on-device memory cost. Theoretically, we demonstrate that FedAda$^2$ achieves the same convergence rates for general, non-convex objectives as its more resource-intensive counterparts that naively integrate joint adaptivity. Empirically, we showcase the benefits of joint adaptivity and the effectiveness of FedAda$^2$ on several image datasets.