Pedestrian localization systems often fuse inertial odometry with map information via hand-defined methods to reduce odometry drift, but such methods are sensitive to noise and struggle to generalize across odometry sources. To address the robustness problem in map utilization, we propose a system that forms a data-driven prior on possible user locations in a map by combining learned map and learned odometry embeddings. Our prior learns to encode which map regions are feasible locations for a user more accurately than previous hand-defined methods. This prior leads to a 49% improvement in inertial-only localization accuracy when used in a particle filter, approaching the performance of Bluetooth beacon-based absolute positioning. To show the generalizability of our method, we also show similar improvements using wheel encoder odometry instead of inertial odometry.