Umeå University's logo

Modern technologies like machine learning and data-driven decision systems, depend on solving large and often highly complex optimization problems. These problems rarely come with simple shapes or smooth surfaces; instead, they can twist and bend in ways that make finding good solutions surprisingly difficult. This thesis explores two ideas that help us navigate such complexity more effectively. 

The first idea focuses on acceleration and investigates how optimization algorithms can reach good solutions faster while using only basic information such as function values and gradients. By studying these algorithms through a continuous-time analysis, we show that many of the fastest methods behave like carefully designed dynamical systems. This perspective not only clarifies why acceleration happens, but also allows us to design fast algorithms and understand how they behave in the presence of noisy information. 

The second idea focuses on a mathematical structural assumption called difference-of- convex (DC) programming, which captures a remarkably wide range of nonconvex problems. By leveraging this structure, we develop practical algorithms that avoid costly operations like projections or high dimensional gradient evaluations, making them efficient for large-scale applications. Through the connection between DC programming and the classical Expectation–Maximization (EM) algorithm, we develop more scalable EM variants and provide the first general performance guarantees for them. 

Recent work on high-resolution ordinary differential equations (HR-ODEs) captures fine nuances among different momentum-based optimization methods, leading to accurate theoretical insights. However, these HR-ODEs often appear disconnected, each targeting a specific algorithm and derived with different assumptions and techniques. We present a unifying framework by showing that these diverse HR-ODEs emerge as special cases of a general HR-ODE derived using the Forced Euler-Lagrange equation. Discretizing this model recovers a wide range of optimization algorithms through different parameter choices. Using integral quadratic constraints, we also introduce a general Lyapunov function to analyze the convergence of the proposed HR-ODE and its discretizations, achieving significant improvements across various cases, including new guarantees for the triple momentum method s HR-ODE and the quasi-hyperbolic momentum method, as well as faster gradient norm minimization rates for Nesterov s accelerated gradient algorithm, among other advances.

We introduce an extension of the Difference of Convex Algorithm (DCA) in the form of a randomized block coordinate approach for problems with separable structure. For n coordinate-blocks and k iterations, our main result proves a non-asymptotic convergence rate of O(n/k) in expectation, with respect to a stationarity measure based on a Forward-Backward envelope. Furthermore, leveraging the connection between DCA and Expectation Maximization (EM), we propose a randomized block coordinate EM algorithm.

We introduce a new projection-free (Frank-Wolfe) method for optimizing structured nonconvex functions that are expressed as a difference of two convex functions. This problem class subsumes smooth nonconvex minimization, positioning our method as a promising alternative to the classical Frank-Wolfe algorithm. DC decompositions are not unique; by carefully selecting a decomposition, we can better exploit the problem structure, improve computational efficiency, and adapt to the underlying problem geometry to find better local solutions. We prove that the proposed method achieves a first-order stationary point in  iterations, matching the complexity of the standard Frank-Wolfe algorithm for smooth non-convex minimization in general. Specific decompositions can, for instance, yield a gradient-efficient variant that requires only  calls to the gradient oracle by reusing computed gradients over multiple iterations. Finally, we present numerical experiments demonstrating the effectiveness of the proposed method compared to other projection-free algorithms.

We consider unconstrained minimization of smooth convex functions. We propose a novel variational perspective using forced Euler-Lagrange equation that allows for studying high-resolution ODEs. Through this, we obtain a faster convergence rate for gradient norm minimization using Nesterov's accelerated gradient method. Additionally, we show that Nesterov's method can be interpreted as a rate-matching discretization of an appropriately chosen high-resolution ODE. Finally, using the results from the new variational perspective, we propose a stochastic method for noisy gradients. Several numerical experiments compare and illustrate our stochastic algorithm with state of the art methods.

We address the line spectral estimation problem with multiple measurement corrupted vectors. Such scenarios appear in many practical applications such as radar, optics, and seismic imaging in which the measurements can be modeled as the sum of a spectrally sparse and a block-sparse signal known as outlier. Our aim is to demix the two components and for this purpose, we design a convex problem whose objective function promotes both of the structures. Using the Positive Trigonometric Polynomials (PTP) theory, we reformulate the dual problem as a Semidefinite Program (SDP). Our theoretical results state that for a fixed number of measurements N and constant number of outliers, up to O(N) spectral lines can be recovered using our SDP problem as long as a minimum frequency separation condition is satisfied. Our simulation results also show that increasing the number of samples per measurement vectors reduces the minimum required frequency separation for successful recovery.

We focus on developing an effective Direction Of Arrival (DOA) estimation method for wideband sources based on the super-resolution concept. In this letter, we represent the data model of a wideband DOA estimation problem in a new form. Then, using this model, we propose an atomic norm minimization problem that leads to an accurate wideband DOA estimation method with no need for any focusing matrices. Moreover, this method requires no initial estimate and can be implemented by non-uniform linear arrays. Numerical simulations show that in comparison to some well-known techniques, the proposed method generates outstanding accuracy and higher robustness to noise. The effectiveness of the method is also verified in presence of close adjacent sources.