Obtaining Lower Query Complexities Through Lightweight Zeroth-Order Proximal Gradient Algorithms.

Area of Science:

• Machine Learning
• Optimization Theory

Background:

• Zeroth-order (ZO) optimization is crucial for machine learning when gradients are inaccessible.
• Existing variance-reduced ZO proximal algorithms often use coordinated estimators, which are computationally expensive (O(d)).
• Random ZO estimators offer computational savings (O(1)) but present convergence analysis challenges.

Purpose of the Study:

• To leverage the computational efficiency of random ZO estimators.
• To develop new theoretical frameworks for analyzing ZO optimization algorithms.
• To improve the state-of-the-art convergence rates for nonsmooth ZO optimization problems.

Main Methods:

• Introduced a Zeroth-Order Objective Decrease (ZOOD) property to handle estimator errors.
• Proposed two generic reduction frameworks for deriving convergence results for convex and nonconvex problems.
• Developed ZOR-ProxSVRG and ZOR-ProxSAGA, variance-reduced ZO proximal algorithms utilizing fully random estimators.

Main Results:

• Achieved improved function query complexities for nonconvex problems from O(min(d^(1/2)ε⁻²), dε⁻³) to O˜(n+dε⁻²) for d > n^(1/2).
• Improved function query complexities for convex problems from O(dε⁻²) to O˜(n log(1/ε) + dε⁻¹).
• Experimental results validated the superiority of the proposed methods.

Conclusions:

• The proposed ZOOD property and reduction frameworks effectively analyze ZO optimization with random estimators.
• The new algorithms and frameworks significantly advance the efficiency of nonsmooth ZO optimization.
• This work paves the way for more practical applications of ZO optimization in machine learning.