Book contents
- Frontmatter
- Contents
- Contributors
- Introduction
- Part 1 Graphical Structure
- Part 2 Language Restrictions
- Part 3 Algorithms and their Analysis
- 6 Tree-Reweighted Message Passing
- 7 Tractable Optimization in Machine Learning
- 8 Approximation Algorithms
- 9 Kernelization Methods for Fixed-Parameter Tractability
- Part 4 Tractability in Some Specific Areas
- Part 5 Heuristics
7 - Tractable Optimization in Machine Learning
from Part 3 - Algorithms and their Analysis
Published online by Cambridge University Press: 05 February 2014
- Frontmatter
- Contents
- Contributors
- Introduction
- Part 1 Graphical Structure
- Part 2 Language Restrictions
- Part 3 Algorithms and their Analysis
- 6 Tree-Reweighted Message Passing
- 7 Tractable Optimization in Machine Learning
- 8 Approximation Algorithms
- 9 Kernelization Methods for Fixed-Parameter Tractability
- Part 4 Tractability in Some Specific Areas
- Part 5 Heuristics
Summary
Machine learning and data analysis have driven explosive growth in interest in the methods of large-scale optimization. Many commonly used techniques such as stochastic-gradients date back several decades, but owing to their practical success they have gained great importance in machine learning. Before interior point methods totally dominated the field of optimization, first-order methods had already been studied and theoretically analyzed in substantial detail. But interest in these techniques skyrocketed after the prolific rise of applications in machine learning, signal processing, etc. This chapter is a brief introduction to this vast and flourishing area of large-scale optimization.
Introduction
Machine Learning (ML) broadly encompasses a variety of adaptive, autonomous, and intelligent tasks where one must “learn” to predict from observations and feedback. Throughout its evolution, ML has drawn heavily and successfully on optimization algorithms; this relation to optimization is not surprising as “learning” and “adapting” ultimately involve problems where some quality function must be optimized.
But the interaction between ML and optimization is now undergoing rapid change. The increased size, complexity, and variety of ML problems, not only prompts a refinement of existing optimization techniques, but also spurs development of new methods tuned to the specific needs of ML applications.
In particular, ML applications must usually cope with large-scale data, which forces us to prefer “simpler,” perhaps less accurate but more scalable algorithms. Such methods can also crunch through more data, and may actually be better suited for learning – for a more precise characterization see [11]. The use of possibly less accurate methods is also grounded in pragmatic concerns: modeling limitations, observational noise, uncertainty, and computational errors are pervasive in real data.
- Type
- Chapter
- Information
- TractabilityPractical Approaches to Hard Problems, pp. 202 - 230Publisher: Cambridge University PressPrint publication year: 2014
- 1
- Cited by