Users often forget or misplace mobile devices, e.g., smartphones. To find or recover such devices, users can utilize find my device features, if available on the device, cause the device to emit a sound, etc. However, no mechanisms exist for a device to automatically detect that it is lost or about to be lost. Per techniques described herein, an on-device predictor determines that a device is lost (separated from the owner) or is about to be lost. The prediction is based on various factors, including device sensor data, recent use of apps, recent user context, etc. for which the user has provided access. If it is determined that the device is lost, various mitigating actions as permitted by the user are performed. For example, such actions include sending notifications to other devices of the same user, initiating communicating with the user or a trusted contact, locking the device, encrypting user data, disabling notifications, etc.