Deep Convolutional Neural Networks (CNNs) have achieved great success in image classification. While conventional CNNs optimized with iterative gradient descent algorithms with large data have been widely used and investigated, there is also research focusing on learning CNNs with non-iterative optimization methods such as the principle component analysis network (PCANet). It is very simple and efficient but achieves competitive performance for some image classification tasks especially on tasks with only a small amount of data available. This paper further extends this line of research and proposes a deep Marginal Fisher Analysis (MFA) based CNN, termed as DMNet. It addresses the limitation of PCANet like CNNs when the samples do not follow Gaussian distribution, by using a local MFA for CNN filter optimization. It uses a graph embedding framework for convolution filter optimization by maximizing the inter-class discriminability among marginal points while minimizing intra-class distance. Cascaded MFA convolution layers can be used to construct a deep network. Moreover, a binary stochastic hashing is developed by randomly selecting features with a probability based on the importance of feature maps for binary hashing. Experimental results demonstrate that the proposed method achieves state-of-the-art result in non-iterative optimized CNN methods, and ablation studies have been conducted to verify the effectiveness of the proposed modules in our DMNet.