In fair machine learning, the goal is to train models that exhibit low bias while maintaining the utility. Most fair learning approaches assume the existence of demographic attributes on all of the data, which limits their usability. In contrast, some recent works introduce algorithms that can function without any demographic labels. In this work, we show these approaches tend to exhibit relatively high bias. Given that, we develop fair learning algorithms that can function with only a small number of demographically labeled data. Our experiments illustrate that our approaches train models better fairness-utility trade-offs.