A Theoretical and Experimental Exploration in Permutation Randomization on Nonsmooth Nonconvex Optimization

Abstract

While gradient-based optimizers that incorporate randomization often demonstrate superior performance on complex optimizations, the theoretical foundations of this advantage remain underexplored. A central question arises: What role does randomization play in dimension-free, nonsmooth, nonconvex optimization? To address this gap, we examine both the theoretical and empirical impact of permutation randomization within gradient-based optimization frameworks, using it as a representative case to investigate broader implications. From a theoretical perspective, our analysis reveals that permutation randomization disrupts the shrinkage behavior characteristic of gradient-based optimizers, allowing for continued progress toward the global optimum with sufficient iterations. Moreover, we prove that permutation randomization preserves the convergence rate of the underlying optimizer. Empirically, we conduct extensive numerical experiments comparing permutation-randomized optimizers with three baseline methods. These experiments span tasks such as training deep neural networks with stacked architectures and optimizing noisy objective functions. The results not only support our theoretical findings but also demonstrate the practical benefits of permutation randomization. In summary, this work provides both rigorous theoretical justification and compelling empirical evidence for the effectiveness of permutation randomization, establishing a foundation for extending such analyses to broader implications of randomized strategies.