Conventional metasurfaces have demonstrated efficient wavefront manipulation by using thick and high-aspect-ratio nanostructures in order to eliminate interactions between adjacent phase-shifter elements. Thinner-than-wavelength dielectric metasurfaces are highly desirable because they can facilitate fabrication and integration with both electronics and mechanically tunable platforms. Unfortunately, because their constitutive phase-shifter elements exhibit strong electromagnetic coupling between neighbors, the design requires a global optimization methodology that considers the non-local interactions. Here, we propose a global evolutionary optimization approach to inverse design non-local metasurfaces. The optimal designs are experimentally validated, demonstrating the highest efficiencies for the thinnest transmissive metalenses reported to-date for visible light. In a departure from conventional design methods based on the search of a library of pre-determined and independent meta-atoms, we take full advantage of the strong interactions among nanoresonators to improve the focusing efficiency of metalenses and demonstrate that efficiency improvements can be obtained by lowering the metasurface filling factors.