In this ACML 2013 workshop we intend to discuss what makes a theory relevant for practical development of algorithms and how the gap between theory and practice can be decreased. Several different forms of theoretical foundations for machine learning have been developed over the years for different settings. Conversely, there has been a recent and dramatic uptake in the application of machine learning techniques to an increasingly diverse range of problems. Arguably, some of the most successful algorithms on practical problems are not completely understood theoretically. We are interested in contributions relating to understanding or closing this gap, both specific technical contributions and general well-argued positions.