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

Area of Science:

• Optimization
• Machine Learning Theory

Background:

• Empirical risk minimization (ERM) is central to machine learning.
• Existing methods like Gradient Descent (GD) and Stochastic Gradient Descent (SGD) have limitations in convergence speed.
• Local Polynomial Interpolation-based Gradient Descent (LPI-GD) offers improved oracle complexity for certain problems.

Purpose of the Study:

• To accelerate the Local Polynomial Interpolation-based Gradient Descent (LPI-GD) method.
• To analyze the theoretical performance of accelerated LPI-GD for ERM problems.
• To empirically validate the performance gains of LPI-GD and its accelerated variants.

Main Methods:

• Analysis of LPI-GD for strongly convex and smooth loss functions with η-Hölder continuity.
• Development of two novel accelerated methods building upon LPI-GD.
• Empirical evaluation comparing LPI-GD, accelerated LPI-GD, GD, and SGD.

Main Results:

• The theoretical oracle complexity of LPI-GD is established as $$ for accuracy ε, with $$ scaling as $$.
• Proposed accelerated LPI-GD methods achieve an improved oracle complexity of $$.
• Empirical results demonstrate LPI-GD's superior performance over GD and SGD in specific scenarios, with accelerated methods showing further gains.

Conclusions:

• Accelerated LPI-GD provides significant theoretical and empirical advantages for solving ERM problems.
• The proposed methods offer a promising direction for faster optimization in machine learning.
• This work presents the first empirical validation of local polynomial interpolation-based gradient methods.