In　recent　years,　end-to-end　network　latency　estimation　has　attracted　much　attention　because　of　its　significance　for　network　performance　evaluation.　Given　the　widespread　use　of　personal　devices,　latency　estimation　from　partially　observed　samples　becomes　more　complicated　due　to　unstable　communication　conditions,　while　measuring　the　latencies　between　all　nodes　in　a　large-scale　network　is　infeasible　and　costly.　Hence,　reducing　the　measurement　cost　becomes　critical　for　the　latency　estimation　of　personal　device　network.　In　this　paper,　we　propose　an　adaptive　sampling　scheme　based　on　leverage　scores　to　reduce　the　measurement　cost　while　achieving　high　estimation　accuracy.　Furthermore,　we　provide　theoretical　analysis　to　characterize　the　performance　bounds　of　the　proposed　scheme　in　terms　of　sampling　complexity　and　estimation　error.　Finally,　we　demonstrate　the　efficiency　of　the　proposed　scheme　by　conducting　extensive　simulations　on　both　synthetic　and　real　datasets.　The　results　show　that　the　proposed　scheme　is　able　to　not　only　improve　the　estimation　accuracy　of　network　latency　but　also　reduce　the　sample　budget　compared　to　the　state-of-the-art　approaches.