Optimization methods for solving large-scale problems play a very critical role in machine learning. In recent years, unprecedented growths in scale and dimensionality of data raise big computational challenges for traditional optimization algorithms; thus it becomes very important to develop efficient and effective optimization algorithms for solving numerous machine learning problems. In this dissertation, I will develop new and efficient optimization algorithms for solving different optimization problems in machine learning by leveraging problems’ structural conditions.