The performance of statistical estimators in several scenarios, such as adaptive nonparametric estimation, aggregation of estimators and estima- tion under the sparsity constraint can be assessed in terms of sparsity oracle inequalities (SOI) for the prediction risk. One of the challenges is to find estimators that attain the sharpest SOI under minimal assumptions on the dictionary. Methods of estimation adapted to the sparsity scenario like the Lasso, the Dantzig selector or their modifications, can be easily realized for very large dimensions of the problem but their performance is conditioned by severe restrictions on the dictionary. Such methods fail when the ele- ments of the dictionary are not approximately non-correlated. This is some- what unsatisfactory, since it is known that the BIC method enjoys better SOI without any assumption on the dictionary. However, the BIC method is NP-hard. This talk will focus on Sparse Exponential Weighting, a new tech- nique of sparse recovery aiming to realize a compromise between theoretical optimality and computational efficiency. The method is based on aggrega- tion with exponential weights using a heavy-tailed sparsity favoring prior. The theoretical performance of Sparse Exponential Weighting in terms of SOI is comparable with that of the BIC and is even better in some aspects. No assumption on the dictionary is needed. At the same time, we show that the method is computationally feasible for relatively large dimensions of the problem. We prove that Langevin Monte-Carlo (LMC) algorithms can be successfully used for computing Sparse Exponential Weighting estimators. Numerical experiments confirm fast convergence properties of the LMC and demonstrate nice performance of the resulting estimators. This is a joint work with Arnak Dalalyan.