We introduce a general-purpose hierarchical approximation algorithm based on the principles of online deterministic annealing, showcasing its properties in the context of explainable machine learning. The main idea is to progressively construct a partition of the data space using gradient-free stochastic approximation updates and use local learning models that can be trained online using two-timescale stochastic approximation. As the partition adapts to the data space at hand, a progressively more detailed representation of the data space is constructed in the form of a hierarchically structured set of regions. Mathematically, this is a tree-structured partition in a multi-resolution representation of the data space. As a result, the complexity of the local models is greatly reduced and common problems such as over-fitting and poor local minima can be mitigated. In addition, this process introduces hierarchical variable-rate feature extraction properties similar to certain classes of deep learning architectures. Experimental results for supervised learning problems illustrate the properties of the proposed method as an explainable machine learning algorithm.