Turning Stale Gradients into Stable Gradients: Coherent Coordinate Descent with Implicit Landscape Smoothing for Lightweight Zeroth-Order Optimization

Researchers propose Coherent Coordinate Descent (CoCD), a deterministic zeroth-order optimization method that improves sample efficiency for scenarios where backpropagation is unavailable. The approach reframes stale gradients as computational assets and demonstrates that larger finite-difference step sizes create implicit landscape smoothing, achieving superior convergence stability compared to existing randomized methods across neural network architectures.

Zeroth-order optimization addresses a fundamental constraint in modern machine learning: situations where gradient computation through backpropagation is infeasible, such as on-device learning with limited memory or optimization of black-box systems. The CoCD framework tackles a critical limitation of existing approaches by eliminating the efficiency-variance tradeoff that has defined the field. Rather than treating historical gradients as stale artifacts, the method leverages them constructively through block cyclic coordinate descent with warm starts, achieving constant query complexity per optimization step while maintaining directional descent guarantees.

The theoretical insight regarding implicit landscape smoothing—where larger finite-difference step sizes paradoxically improve convergence by reducing effective smoothness constants—challenges conventional optimization intuitions and offers practical guidance for practitioners. This counter-intuitive finding suggests that deterministic, structure-aware optimization strategies may fundamentally outperform randomization-based approaches in resource-constrained settings. Experimental validation across diverse architectures from MLPs to ResNets with 270k parameters demonstrates consistent improvements in sample efficiency and convergence behavior relative to baseline methods.

For the machine learning infrastructure landscape, this research has implications for edge computing, federated learning systems, and derivative-free optimization applications. The approach is particularly relevant for scenarios involving proprietary neural networks, adversarial robustness testing, and hardware constraints common in mobile and embedded AI deployment. The deterministic nature of CoCD also provides reproducibility advantages over randomized methods, important for production systems requiring consistent behavior across inference runs and deployment environments.

• →CoCD converts historical gradients into computational assets rather than liabilities, enabling efficient zeroth-order optimization without backpropagation
• →Larger finite-difference step sizes induce implicit landscape smoothing that improves convergence stability in non-intuitive ways
• →Method achieves O(1) query complexity per step while maintaining global descent properties across tested architectures
• →Deterministic structure-aware updates outperform randomized zeroth-order methods in sample efficiency and stability metrics
• →Results indicate practical advantages for memory-constrained on-device learning and black-box optimization applications