Structural-based Approach to Complexity of Optimization Algorithms

Abstract: The past few decades have witnessed tremendous progress in the field of Mathematical Optimization which led to a large proliferation of new optimization methods to many scientific fields. Among these is the field of machine learning whose applicability heavily relies on solvers which are capable of efficiently solving challenging large-scale optimization problems. Notwithstanding, we still lack an adequate complexity theory which satisfactorily quantifies the computational resources required for solving optimization problems of this nature. Motivated by the limitations of current computational models, in the present work we propose novel theoretical foundations for investigating the computational boundaries of optimization algorithms which scale well with the dimension of the problem. We then present recent results regarding application of this technique on various types of optimization problems.

Posted on May 14, 2018 in ACGO, Seminars