We study the problem of attacking a machine learning model in the hard-label\nblack-box setting, where no model information is revealed except that the\nattacker can make queries to probe the corresponding hard-label decisions. This\nis a very challenging problem since the direct extension of state-of-the-art\nwhite-box attacks (e.g., CW or PGD) to the hard-label black-box setting will\nrequire minimizing a non-continuous step function, which is combinatorial and\ncannot be solved by a gradient-based optimizer. The only current approach is\nbased on random walk on the boundary, which requires lots of queries and lacks\nconvergence guarantees. We propose a novel way to formulate the hard-label\nblack-box attack as a real-valued optimization problem which is usually\ncontinuous and can be solved by any zeroth order optimization algorithm. For\nexample, using the Randomized Gradient-Free method, we are able to bound the\nnumber of iterations needed for our algorithm to achieve stationary points. We\ndemonstrate that our proposed method outperforms the previous random walk\napproach to attacking convolutional neural networks on MNIST, CIFAR, and\nImageNet datasets. More interestingly, we show that the proposed algorithm can\nalso be used to attack other discrete and non-continuous machine learning\nmodels, such as Gradient Boosting Decision Trees (GBDT).\n