Simultaneous Perturbation Stochastic Approximation for Mixed Variables

Stochastic optimization aims to minimize the loss functions with noisy function and/or gradient measurements <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">only</i>. Depending on the types of the underlying variables, optimization problems can often be categorized as continuous, discrete, or mixed (mixture of continuous and discrete variables). Motivated by the simultaneous perturbation stochastic approximation (SPSA) and the discrete simultaneous perturbation stochastic approximation (DSPSA) algorithms, we propose the mixed simultaneous perturbation stochastic approximation (MSPSA) that bridges the gap of dealing with mixed variables. The newly proposed MSPSA unifies the framework of simultaneous perturbation as both SPSA and DSPSA can now be deemed as two special cases of MSPSA. The almost sure convergence and the rate of convergence of the MSPSA iterates are derived. The convergence results reveal that the finite-sample bound of MSPSA is identical to DSPSA when the problem contains only discrete variables, and the asymptotic bound of MSPSA has the same order of magnitude as SPSA when the problem contains only continuous variables.