Title: Gradient-based Algorithms for Pessimistic Bilevel Optimization. Abstract: As a powerful framework for a variety of machine learning problems, bilevel optimization has attracted much attention. While many modern gradient-based algorithms have been devised for optimistic bilevel optimization, pessimistic bilevel optimization (PBO) is still less-explored and only studied under the linear settings. To fill this void, we investigate PBO with nonlinear inner- and outer-level objective functions in this work, by reformulating it into a  single-level constrained optimization problem. In particular, two gradient-based algorithms are first proposed to solve the reformulated problem, i.e., the switching gradient method (SG-PBO) and  the primal-dual method (PD-PBO). Through carefully handling the bias errors in gradient estimations resulted by the nature of bilevel optimization, we show that both SG-PBO and PD-PBO converge to the global minimum of the reformulated problem when it is strongly convex, which immediately implies the convergence to the original PBO. Moreover, we propose the proximal scheme (Prox-PBO) with the convergence guarantee for the nonconvex reformulated problem. To the best of our knowledge, this is the first work that investigates gradient-based algorithms and provides convergence analysis for PBO under non-linear settings. We further conduct experiments on an illustrative example and a robust hyperparameter learning problem, which clearly validate our algorithmic design and theoretical analysis.