The paper introduces a novel framework for extracting model-agnostic human\ninterpretable rules to explain a classifier's output. The human interpretable\nrule is defined as an axis-aligned hyper-cuboid containing the instance for\nwhich the classification decision has to be explained. The proposed procedure\nfinds the largest (high \\textit{coverage}) axis-aligned hyper-cuboid such that\na high percentage of the instances in the hyper-cuboid have the same class\nlabel as the instance being explained (high \\textit{precision}). Novel\napproximations to the coverage and precision measures in terms of the\nparameters of the hyper-cuboid are defined. They are maximized using\ngradient-based optimizers. The quality of the approximations is rigorously\nanalyzed theoretically and experimentally. Heuristics for simplifying the\ngenerated explanations for achieving better interpretability and a greedy\nselection algorithm that combines the local explanations for creating global\nexplanations for the model covering a large part of the instance space are also\nproposed. The framework is model agnostic, can be applied to any arbitrary\nclassifier, and all types of attributes (including continuous, ordered, and\nunordered discrete). The wide-scale applicability of the framework is validated\non a variety of synthetic and real-world datasets from different domains\n(tabular, text, and image).\n