Hybrid Random-Local Search for High-Dimensional Optimization Without Convexity Assumption

• AMSE, Université Aix-Marseille, France [pierre.BERTRAND.1@univ-amu.fr]

• LPSM, Sorbonne Université, Paris, France [michel.broniatowski@sorbonne-universite.fr]

• Maths Department, FAU Erlangen, Germany [stummer@math.fau.de]

Keywords: Optimization – Random local search – High dimension – Non convexity – Lasso – Neural network pruning

Abstract

We propose a method to minimize a continuous function over a subset $\mathrm{\Omega }$ of high-dimensional space ${ℝ}^K$ without assuming convexity. The method alternates between Random Search (RS) and Local Search (LS) regimes to improve an eligible candidate in $\mathrm{\Omega }$, the starting point of the algorithm.

Beyond the alternation between regimes, the originality of the method lies in leveraging high dimensionality. We demonstrate concentration properties under the $LS$ regime. In parallel, we show that $RS$ reaches any point in finite time.

Finally, two applications are proposed. The first is the reduction of the $L_1$ norm in the Lasso to demonstrate the relevance of the method. In a second, more useful application, we accelerate neural network inference by pruning weights while maintaining performance. Our approach achieves significant weight reduction with minimal performance loss, offering an effective solution for network optimization.