Machine learning models have achieved remarkable results across domains such as healthcare, finance, and natural language processing. However, their adoption in sensitive applications often requires interpretable models, where sparsity can enhance both interpretability and generalization. We investigate and improve soft decision trees for classification and regression, which are interpretable models, and kernel logistic regression for binary classification. Contributions include new model variants, sparsification methods, theoretical properties, and decomposition-based training algorithms. For soft classification trees, we propose \(\ell _0\) -based sparsification methods that are more effective in promoting both local and global sparsity compared to the previously proposed \(\ell _1\) and \(\ell _\infty \) regularizations. For soft regression trees, we present a model variant where, for each input vector, the prediction is given by the linear regression associated with a single leaf node. We design a nonlinear optimization formulation amenable to decomposition and develop a convergent node-based algorithm that includes a heuristic for rerouting input vectors. Concerning kernel logistic regression, we develop a sparsity-inducing formulation for binary classification and design a convergent second-order sequential minimal optimization algorithm that achieves a good balance between sparsity and accuracy, while maintaining informative probabilistic outputs.