Seminar Details
2020-10-20 (14:00) : Welcome Seminar for new postdocs (#1)
At MS Teams
Organized by Mathematical Engineering
Section 1: Oracle Complexity Separation in Convex Optimization
Speaker :
Evgeniia Vorontsova
Abstract :
Empirical risk minimization problems in machine learning are considered. Such kind of problems are often consisted of several blocks that can be treated
with different types of oracles, e.g., full gradients, stochastic gradients or coordinate derivatives. Optimal oracle complexity is known and achievable
separately for each type of the oracles. We propose a generic framework to combine several optimal algorithms for different types of oracles in order to
achieve separate optimal oracle complexity for every block. As a particular example, we demonstrate that in a case of full and stochastic gradient oracles' combination
our approach leads to the optimal number of oracle calls separately for the full gradient part and the stochastic part.
Section 2: Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
Speaker :
Masoud Ahookhosh
Abstract :
In this study, four accelerated (sub)gradient algorithms (ASGA) are introduced and analyzed for solving several classes of convex optimization problems with a large number of variables. The objective function is the sum of two convex functions in which the first one is weakly smooth (either nonsmooth with the bounded variation of subgradients or smooth with Hölder continuous gradients). Specifically, two novel estimation sequences are presented to majorize the objective function, and accordingly two iterative schemes are developed with respect to these upper estimations. In both cases, the first scheme requires the smoothness parameter and a Hölder constant, while the second scheme is fully parameter-free (except for the strong convexity parameter which we set zero if it is not available) at the price of applying a finitely terminated backtracking line search. Notably, the proposed algorithms attain the optimal complexity for smooth problems with Lipschitz continuous gradients, nonsmooth problems with the bounded variation of subgradients, and weakly smooth problems with Hölder continuous gradients. In addition, for strongly convex problems, they are optimal for smooth problems while nearly optimal for nonsmooth and weakly smooth problems. Finally, numerical experiments for applications in sparse optimization and machine learning are reported, which support our theoretical foundations.