Concentrated Optimization for Machine Learning: Complexity in High-Dimensions, Average-case Analysis, and Exact Dynamics

点击翻译按钮获取中文摘要

Learning algorithms play an integral role in machine learning and have had widespread empirical success in training high-dimensional problems (e.g., number of features and samples are large). In spite of their popularity, there is a gap between real-world performances and best known theoretical bounds. Traditionally, complexity theory of learning algorithms focuses on worst-case analysis, which guarantees convergence for all inputs under general assumptions of the objective function such as convexity and smoothness. High-dimensionality is often not explicitly assumed. High-dimensional data implies more possibilities for the inputs into an algorithm so the input which generate the worst-case complexity could be far from typical. Average-case analysis places a probability distribution on the inputs and computes the expected complexity. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. A challenge is finding a good probability distribution on the input (data set) that matches real-world successes and is amenable to analysis. This proposal addresses a series of research questions relating average-case complexity of first-order methods and high-dimensionality. The proposal seeks to answer the following question. Develop a general framework for average-case complexity of learning algorithms and analyze their exact dynamics to gain insights into step size selections and convergence properties. The proposal has two components. First, the PI explores questions concerning high-dimensional dynamics of stochastic optimization algorithms on a random least squares problem. In particular, the PI plans on investigating the relationships between average-case complexity, step-size and momentum parameter selection strategies, batch-size, and modeling assumptions on the data-set and targets. Indeed lots of computational time is wasted trying to find step-sizes which (1). yield good optimizers and (2). do so in a reasonable amount of time. Average-case analysis can illuminate parameter selections that work for typical high-dimensional problems. Second for various minimization problems (e.g., generalized linear models (GLMs), non-smooth objective functions), one lacks good models for the behavior of real-data as inputs into the objective functions and in particular a model for the Hessian. The spectrum of the Hessian provides a picture of the loss landscape for complicated objective functions. The PI plans on approximating this spectrum with random matrices. Using Hessians generated by random matrices, one can extend the average-case analysis beyond quadratic models to more complicated objective functions.