Thesis Defence: Bregman generalized subgradient projected algorithms and applications

Xiaoyu Mao, supervised by Dr. Shawn Wang, will defend their thesis titled “Bregman generalized subgradient projected algorithms and applications” in partial fulfillment of the requirements for the degree of Master of Science in Mathematics.

An abstract for Xiaoyu Mao’s thesis is included below.

Defences are open to all members of the campus community as well as the general public. Please email shawn.wang@ubc.ca to receive the Zoom link for this defence.

---

ABSTRACT

Projected subgradient methods were thought as ideal algorithms for constrained minimization problems. But it is often hampered by the computational complexity of the projection operator. The generalized Bregman distance has been identified as a potential solution to this issue. This thesis delves into an in-depth analysis and conducts numerical experiments on projected subgradient methods that utilize Bregman distances.

Firstly, we discuss the existing mirror descent algorithm, which is designed for one-block constrained minimization problems. Previous research has revealed its equivalence with Bregman projected subgradient method. Subsequently, we expand this algorithm to accommodate two-block situations, thereby increasing its applicability. We also provide its convergence proof. Our algorithm has a strong correlation with another renowned method, the “proximal alternating linearized method,” which can be considered a specific variant of our approach.

In the numerical experiments, we choose a variety of examples from fields, such as matrix analysis and statistics. The data we used are derived from both artificial and real-world sources. The results consistently indicate that Bregman generalized algorithms significantly reduces computation time, particularly when the variable is constrained to a unit simplex. This further corroborates our hypothesis.