English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the acceleration of the Local Polynomial Interpolation-basedGradient Descent method (LPI-GD) recently proposed for the approximate solutionof empirical risk minimization problems (ERM). We focus on loss functions thatare strongly convex and smooth with condition number $\sigma$. We additionallyassume the loss function is $\eta$-H\"older continuous with respect to thedata. The oracle complexity of LPI-GD is $\tilde{O}\left(\sigma m^d\log(1/\varepsilon)\right)$ for a desired accuracy $\varepsilon$, where $d$ isthe dimension of the parameter space, and $m$ is the cardinality of anapproximation grid. The factor $m^d$ can be shown to scale as$O((1/\varepsilon)^{d/2\eta})$. LPI-GD has been shown to have better oraclecomplexity than gradient descent (GD) and stochastic gradient descent (SGD) forcertain parameter regimes. We propose two accelerated methods for the ERMproblem based on LPI-GD and show an oracle complexity of$\tilde{O}\left(\sqrt{\sigma} m^d \log(1/\varepsilon)\right)$. Moreover, weprovide the first empirical study on local polynomial interpolation-basedgradient methods and corroborate that LPI-GD has better performance than GD andSGD in some scenarios, and the proposed methods achieve acceleration.

On Acceleration of Gradient-Based Empirical Risk Minimization using Local Polynomial Regression