This thesis explores the integration of machine learning (ML) into algorithm design for solving complex combinatorial optimization problems. We focus on solving problems that arise in bilevel optimization, two-stage robust optimization, and phylogenetics. Although these problem classes seem vastly different, they share the common characteristic of being extremely challenging to solve. Current solution methods for these problems are computationally heavy and their solving duration is often impractical for already small-sized instances. Adding a component of machine learning also adds complexity. We primarily attempt to mitigate this effect by proposing learning methods that utilize efficient training data generation schemes that rely on solving sub-problems or are even based on a simple procedure, instead of learning from optimal solutions of many instances similar to the target problem.