Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity.

Area of Science:

• Optimization methods
• Machine learning
• Derivative-free optimization

Background:

• Zeroth-order methods are crucial for machine learning when gradients are unavailable or costly.
• Existing methods suffer from high function query complexity and limitations with complex penalties and constraints.

Purpose of the Study:

• To develop faster zeroth-order methods addressing the drawbacks of existing approaches.
• To solve nonconvex finite-sum and online problems with multiple nonsmooth penalties.

Main Methods:

• Proposed zeroth-order stochastic alternating direction method of multipliers (ZO-SPIDER-ADMM) for finite-sum problems.
• Developed zeroth-order online ADMM methods (ZOO-ADMM+) for online problems.
• Proved improved function query complexity for both proposed methods.

Main Results:

• ZO-SPIDER-ADMM achieves a function query complexity of O(n^(1/2)ϵ⁻²) for ϵ-stationary points, improving existing methods by a factor of O(n^(1/2)).
• ZOO-ADMM+ achieves a function query complexity of O(ϵ⁻²) for ϵ-stationary points, improving existing methods by a factor of O(n^(1/2)).
• Experimental validation on adversarial attacks on deep neural networks confirms algorithm efficiency.

Conclusions:

• The proposed ZO-SPIDER-ADMM and ZOO-ADMM+ offer significant improvements in function query complexity for zeroth-order optimization.
• These novel algorithms are efficient for solving complex nonconvex problems with nonsmooth penalties and constraints.
• The methods demonstrate practical effectiveness, particularly in adversarial attack scenarios on deep learning models.