How to start doing "more theoretical" research? I guess, this question might be not only of my personal interest: I'm a first year PhD CS student, during my BSc and MSc, all research projects I did were purely practical - we hypothesize that certain way of computing or approximating something is "good" in some sense or another. Last year I was mostly doing deep learning that reduces to "if we wire network like this, those interesting properties might appear, here're some clues on possible reasons". But I used to (and still do) like doing math, learning new concepts and figuring out proofs, but:

a) I have no idea of how to come up with such a research project (closest thing to "theory research" I did was proving convergence bounds) 

b) professor I am (have been for a while) working with now (and who partially funds my RA) is not very inspired by my intent to do research in theory (with no guarantees that anything would work out) instead of performing real-world publishable  experiments (that also rarely lead to successes, but are at least more "measurable"). 

More specifically, I have been doing machine learning last few years, and I know that there exist a bunch of cool areas to explore and I took (and I liked)  courses on statistical learning theory, optimization, Bayesian inference and other more rigorous things. But I just don't know how to start "doing research" there.
I believe that you are at the transition between BSc/MSc(where one is used to textbook level research) to PhD where one is requested to read and publish papers. The transition is not smooth, it has to be done in various stages. You can start, by examples by reading different papers in domains related to your knowledge(and also what you really like), and try to understand in detail the methodology. The effort has to be continuously, 2 3 hours everyday, and also not to get distracted and stop the research. Also, don't forget that some answers might come after months or even years of research. I would start by reading and finding papers that are approachable in the present context, and try to understand the detail in one of them. This would lead you to another papers to learn and understand, and after you gain some background(a few months), you can start to explore new ideas connected to what you have learned. In the end, if an approach seems that is leading you nowhere, try another approach. Also, related to the question context, working at one side on real-world publishable experiments and on the other side on theoretical approaches seems to be the best option. Good luck!