Date/Time : 19 Feb 2025 15:00
Venue : S17 #05-12 (SR4)
Speaker : Yue Xie, University of Hong Kong

The two-metric projection method is a simple yet elegant algorithm proposed by Bertsekas to address bound/box-constrained optimization problems. The algorithm’s low per-iteration cost and potential for using Hessian information make it a favorable computation method for this problem class. Inspired by this algorithm, we propose a two-metric adaptive projection method for solving the $\ell$_1-norm minimization problem that inherit these advantages. We demonstrate that the method is theoretically sound – it has global convergence. Furthermore, it is capable of manifold identification and has superlinear convergence rate under the error bound condition and strict complementarity. Therefore, given sparsity in the solution, the method enjoys superfast convergence in iteration while maintaining scalability, making it desirable for large-scale problems. We also equip the algorithm with competitive complexity to solve nonconvex problems. Numerical experiments are conducted to illustrate the advantages of this algorithm implied by the theory compared over other competitive methods, especially in large-scale scenarios. Compared with the two-metric projection method, our algorithm directly solves the l1-norm minimization problem without resorting to the intermediate reformulation as a bound-constrained problem, so it circumvents the issue of numerical instability.

Add to calendar :

Date/Time : 21 Jan 2025 16:00
Venue : S17 #04-05 (SR2)
Speaker : Yunpeng Shi, University of California, Davis

In this talk, we explore two classical image processing tasks motivated by cryo-electron microscopy imaging: tomographic image denoising and rigid image registration. Both tasks inherently involve operations of 2D rotations, where leveraging specific transforms can significantly enhance the speed and robustness of the algorithms.

In the first part of the talk, I will introduce an unsupervised image denoiser based on estimating the covariance matrix of clean images. A key insight is that if the image manifold is invariant under global in-plane rotations, this symmetry can be exploited to accelerate computations and reduce dimensionality. I will discuss recent advances in fast expansion into steerable bases that allow us to efficiently utilize this rotational symmetry, leading to a thousand fold improvement in the speed of covariance estimation over existing methods. This technique has been successfully applied to joint deconvolution and denoising of large-scale, real-world cryo-EM images.

In the second part, I will present a fast algorithm for aligning images using optimal transport. Our method leverages the sliced Wasserstein distance by computing the 1D Wasserstein distance between radial line projections of input images. By applying a special transform to the frequency domain, we achieve efficient alignment of two L by L images in O(L^2 log L) operations — matching the complexity of alignment using Euclidean distance. I will demonstrate the robustness of our method to translations and deformations.

Finally, I will comment on the practical limitations of both methods and discuss open questions that remain, highlighting areas for future exploration.

Add to calendar :

Date/Time : 21 Jan 2025 14:00
Venue : S17 #06-11 (SR6)
Speaker : Johannes Lederer, University of Hamburg

Artificial intelligence is arguably the hottest topic in all of science. Computer science and engineering currently set the agenda in this field, sidelining mathematics to a large extent. This talk, however, will highlight that mathematics has a lot to offer. We will introduce mathematical guarantees that provide deep insights into the inner workings of AI, and we will show how statistical principles can make AI more efficient. More generally, we will discuss the role of mathematics, especially statistics, in AI and data science.

Add to calendar :

Date/Time : 13 Jan 2025 11:00
Venue : S17 #05-11 (SR5)
Speaker : Stephen Wright, University of Wisconsin-Madison

Complexity analysis in optimization seeks upper bounds on the amount of work required to find approximate solutions of optimization problems in a given class with a given algorithm. There is also study of lower bounds, usually in the form of a worst-case example from a given problem class for a given algorithm class. The relationship between theoretical complexity bounds and practical performance of algorithms on “typical” problems varies widely across problem and algorithm classes, and relative interest among researchers between the theoretical and practical aspects of algorithm design and analysis has waxed and waned over the years. This talk surveys complexity analysis and its relationship to practice in optimization, with an emphasis on linear programming and convex and nonconvex nonlinear optimization, providing historical (and cultural) perspectives on research in these areas.

Add to calendar :

Date/Time : 10 Jan 2025 16:00
Venue : S17 #04-04 (SR3)
Speaker : Yufeng Wu, University of Connecticut

Suppose a person collected his/her own genome and wants to learn something about his/her ancestry. Further suppose this person’s genome originates from multiple ancestral populations, a phenomenon called population admixture in genetics. The genome of an individual from an admixed population consists of segments originated from different ancestral populations. Most existing ancestry inference approaches can provide an estimate of the percentage (called admixture proportion) of the genome originated from a specific ancestral population. Now what if someone wants to estimate admixture proportions of recent ancestors from his/her own genome? For example, let us say an individual has 50% European and 50% Asian ancestry. This individual’s parents can be also 50-50 European/Asian ancestry, but it is also possible one is 100% European and the other is 100% Asian. More generally, can one learn more about the ancestry of recent ancestors from his/her own genome?

In this talk, I will present research results on ancestry inference for estimating admixture proportions of recent ancestors from an extant genome. I will first briefly describe PedMix, one of the first methods for such inference. A major downside of PedMix is that it can only estimate admixture proportions for parents and grandparents, and cannot scale for more distantly related ancestors. I will then focus on PedMix2, a general approach that can estimate admixture proportions of all recent ancestors of this individual. This approach was published recently in PNAS (2024). To the best of our knowledge, there is no other method that can practically infer ancestors beyond grandparents from an extant individual’s genome. I will present results on both simulated and real data show that PedMix2 performs well in ancestry inference.

Add to calendar :

Date/Time : 10 Jan 2025 14:00
Venue : S17 #04-06 (SR1)
Speaker : Govind Menon, Brown University

We study the training dynamics of the Deep Linear Network (DLN) from the perspective of the geometric theory of dynamical systems. Rigorous results by several authors are unified into a thermodynamic framework for deep learning. The analysis begins with a characterization of the invariant manifolds and Riemannian geometry in the DLN. This is followed by exact formulas for a Boltzmann entropy, as well as stochastic gradient descent of free energy using a Riemannian Langevin Equation. Several links between the DLN and other areas of mathematics are discussed, along with some open questions.

Add to calendar :

Date/Time : 09 Jan 2025 16:00
Venue : S17 #04-06 (SR1)
Speaker : Govind Menon, Brown University

We study the training dynamics of the Deep Linear Network (DLN) from the perspective of the geometric theory of dynamical systems. Rigorous results by several authors are unified into a thermodynamic framework for deep learning. The analysis begins with a characterization of the invariant manifolds and Riemannian geometry in the DLN. This is followed by exact formulas for a Boltzmann entropy, as well as stochastic gradient descent of free energy using a Riemannian Langevin Equation. Several links between the DLN and other areas of mathematics are discussed, along with some open questions.

Add to calendar :

Date/Time : 08 Jan 2025 16:30
Venue : S17 #04-04 (SR3)
Speaker : Govind Menon, Brown University

We study the training dynamics of the Deep Linear Network (DLN) from the perspective of the geometric

theory of dynamical systems. Rigorous results by several authors are unified into a thermodynamic framework for deep learning. The analysis begins with a characterization of the invariant manifolds and Riemannian geometry in the DLN. This is followed by exact formulas for a Boltzmann entropy, as well as stochastic gradient descent of free energy using a Riemannian Langevin Equation. Several links between the DLN and other areas of mathematics are discussed, along with some open questions.

Add to calendar :

Date/Time : 18 Dec 2024 15:00
Venue : S17 #06-11 (SR6)
Speaker : Ding Lijun, University of California, San Diego

We revisit a formulation technique for inequality-constrained optimization problems that has been known for decades: the substitution of squared variables for nonnegative variables. Using this technique, inequality constraints are converted to equality constraints via the introduction of a squared-slack variable. Such formulations have the superficial advantage that inequality constraints can be dispensed with altogether. But there are clear disadvantages, not least being that first-order optimal points for the squared-variable reformulation may not correspond to first-order optimal points for the original problem, because the Lagrange multipliers may have the wrong sign. Extending previous results, this paper shows that points satisfying approximate second-order optimality conditions for the squared-variable reformulation also, under certain conditions, satisfy approximate second-order optimality conditions for the original formulation, and vice versa. Such results allow us to adapt complexity analysis of methods for equality-constrained optimization to account for inequality constraints. On the algorithmic side, we examine squared-variable formulations for several interesting problem classes, including bound-constrained quadratic programming, linear programming, and nonnegative matrix factorization. We show that algorithms built on these formulations are surprisingly competitive with standard methods.

Add to calendar :