Gradient-Based Empirical Risk Minimization using Local Polynomial Regression
This work addresses the computational efficiency of optimization algorithms for machine learning practitioners, offering a novel approach that can outperform standard methods in specific settings, though it is incremental in its extension of existing techniques.
The paper tackles empirical risk minimization for smooth, strongly convex loss functions by proposing an algorithm that uses local polynomial regression to learn gradients, achieving an oracle complexity of $ ilde{O}((p \epsilon^{-1})^{d/(2\eta)})$, which beats gradient descent and stochastic gradient descent in regimes with small data dimension and modest smoothness.
In this paper, we consider the problem of empirical risk minimization (ERM) of smooth, strongly convex loss functions using iterative gradient-based methods. A major goal of this literature has been to compare different algorithms, such as gradient descent (GD) or stochastic gradient descent (SGD), by analyzing their rates of convergence to $ε$-approximate solutions. For example, the oracle complexity of GD is $O(n\log(ε^{-1}))$, where $n$ is the number of training samples. When $n$ is large, this can be expensive in practice, and SGD is preferred due to its oracle complexity of $O(ε^{-1})$. Such standard analyses only utilize the smoothness of the loss function in the parameter being optimized. In contrast, we demonstrate that when the loss function is smooth in the data, we can learn the oracle at every iteration and beat the oracle complexities of both GD and SGD in important regimes. Specifically, at every iteration, our proposed algorithm performs local polynomial regression to learn the gradient of the loss function, and then estimates the true gradient of the ERM objective function. We establish that the oracle complexity of our algorithm scales like $\tilde{O}((p ε^{-1})^{d/(2η)})$ (neglecting sub-dominant factors), where $d$ and $p$ are the data and parameter space dimensions, respectively, and the gradient of the loss function belongs to a $η$-Hölder class with respect to the data. Our proof extends the analysis of local polynomial regression in non-parametric statistics to provide interpolation guarantees in multivariate settings, and also exploits tools from the inexact GD literature. Unlike GD and SGD, the complexity of our method depends on $d$ and $p$. However, when $d$ is small and the loss function exhibits modest smoothness in the data, our algorithm beats GD and SGD in oracle complexity for a very broad range of $p$ and $ε$.