In this project, we are interested in developing machine learning methods for complex inference problems that occur frequently in real world applications. Such problems are ubiquitous in many fields, ranging from natural language processing to bioinformatics, from computer vision to information retrieval. Examples include automatic translation of documents across languages, motion tracking of individuals in video sequences and identifying 3D structure of proteins. The predominant approach for such problems is to define simpler subtasks, to solve these subtasks in a cascaded manner and to use the output of the subtasks as input for the target task. This approach suffers from error propagation along the cascaded processes. Moreover, it does not take the correlation among the tasks into account, which might be a valuable source to improve the performance of each task. We propose a principled machine learning method for complex inference problems which overcomes the limitations of the cascaded approach and takes a unified approach in modeling the target task and the subtasks. Based on the assumption that the correlated tasks on an input space should have similar smoothness properties, we propose a novel and efficient learning method that performs optimization of the multiple tasks respecting the proposed model. We propose applying this method to various applications in natural language processing and computational biology. This project has the potential to contribute towards technological advances in a large spectrum of applications.