Globally Convergent Gradient Projection Type Algorithms for a Class of Robust Hypothesis Testings
Ting Ma, Enbin Song, Qingjiang Shi · IEEE Transactions on Signal Processing · 2021
This paper considers the popular minimax robust hypothesis testing problem—seeking the optimal decision rule with a minimum error probability for the least favorable distributions (LFDs) lying within an uncertainty set, which is characterized by an upper bound on the distance between actual and nominal densities. First, we convert the minimax robust hypothesis testing problem to a convex minimization problem. By leveraging Danskin's theorem, the gradient of the objective function of the transformed problem is derived as a function of LFDs. Then, we propose the gradient projection algorithm (GPA) and the hybrid gradient projection algorithm (HGPA) to solve the transformed problem. In particular, when the distance is chosen to be the Kullback-Leibler (KL) or$\alpha$-divergence, each LFD only relies on two unknown parameters which can be determined efficiently. In these two cases, the decision rule sequences generated by the GPA and the HGPA are respectively proved to converge weakly and strongly to the global minimizer under some mild conditions. To the best of our knowledge, these decision rules are the first to be guaranteed to globally converge towards the optimal solution for this type of robust hypothesis testing problems. We further propose an accelerated gradient projection algorithm (AGPA) to improve the efficiency of the GPA when the observation space of the robust hypothesis testing only contains finitely many points. Several simulations illustrate that the proposed GPA, HGPA and AGPA can obtain the globally optimal solution with high efficiency.