A parametric algorithm called PADUA is introduced for the regression problem of smooth functions.PADUA aims to achieve a uniform error bound across the entire domain.It provides performance guarantees optimal up to constant or logarithmic factors.PADUA has optimal sample and space complexity, as demonstrated through numerical experiments.