From Ronald Ross to ChatGPT: the birth and strange life of the random walk - Jordan Ellenberg

Oxford Mathematics Public Lecture - 5pm, Wednesday 26 June 2024

Between 1905 and 1910 the idea of the random walk was invented simultaneously and independently by people in multiple countries for completely different purposes – in the UK, with Ronald Ross and the problem of mosquito control, but elsewhere in domains from physics to finance to winning a theological argument (really!).

New starter

A warm welcome to Clea Boorman, Internal Communications Officer: S0.37 

Mon, 14 Oct 2024

14:00 - 15:00
Lecture Room 3

Complexity of Finding Local Minima in Continuous Optimization

Amir Ali Ahmadi
(Princeton University, NJ)
Abstract

 

Can we efficiently find a local minimum of a nonconvex continuous optimization problem? 

We give a rather complete answer to this question for optimization problems defined by polynomial data. In the unconstrained case, the answer remains positive for polynomials of degree up to three: We show that while the seemingly easier task of finding a critical point of a cubic polynomial is NP-hard, the complexity of finding a local minimum of a cubic polynomial is equivalent to the complexity of semidefinite programming. In the constrained case, we prove that unless P=NP, there cannot be a polynomial-​time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c\geq 0$) of a local minimum of an $n$-​variate quadratic polynomial over a polytope. 
This result (with $c=0$) answers a question of Pardalos and Vavasis that appeared on a list of seven open problems in complexity theory for numerical optimization in 1992.

Based on joint work with Jeffrey Zhang (Yale).

 

 

Biography

Amir Ali Ahmadi is a Professor at the Department of Operations Research and Financial Engineering at Princeton University and an Associated Faculty member of the Program in Applied and Computational Mathematics, the Department of Computer Science, the Department of Mechanical and Aerospace Engineering, the Department of Electrical Engineering, and the Center for Statistics and Machine Learning. He serves as the Director of the Certificate Program in Optimization and Quantitative Decision Science. He has also held visiting appointments with the industry, as a Visiting Senior Optimization Fellow at Citadel, Global Quantitative Strategies, and a Visiting Research Scientist at Google Brain (in the Robotics group). Amir Ali received his PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson Research Center prior to joining Princeton. His research interests are in optimization theory, computational aspects of dynamical systems, control-oriented learning, and algorithms and complexity.

Amir Ali's distinctions include the Sloan Fellowship in Computer Science, the Presidential Early Career Award for Scientists and Engineers (PECASE), the NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA Faculty Award, the Google Faculty Award, the MURI award of the AFOSR, the Howard B. Wentz Junior Faculty Award, as well as the Innovation Award of Princeton University, the Goldstine Fellowship of IBM Research, and the Oberwolfach Fellowship of the NSF. His undergraduate course at Princeton (ORF 363, ``Computing and Optimization'') is a three-time recipient of the Teaching Award of the Princeton Engineering Council, as well as a recipient of the Excellence in Teaching of Operations Research Award of the Institute for Industrial and Systems Engineers, the Princeton SEAS Distinguished Teaching Award, and the Phi Beta Kappa Award for Excellence in Undergraduate Teaching at Princeton. Amir Ali's research has been recognized by a number of best-paper awards, including the INFORMS Optimization Society's Young Researchers Prize, the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the best conference paper award of the IEEE International Conference on Robotics and Automation, and the best paper prize of the SIAM Journal on Control and Optimization. Amir Ali was a plenary speaker at the 2021 SIAM Conference on Optimization and the 2022 Colombian Conference on Applied and Industrial Mathematics.

 

 

 

 

Thu, 17 Oct 2024

14:00 - 15:00
Lecture Room 3

On the loss of orthogonality in low-synchronization variants of reorthogonalized block classical Gram-Schmidt

Kathryn Lund
(STFC Rutherford Appleton Laboratory)
Abstract
Interest in communication-avoiding orthogonalization schemes for high-performance computing has been growing recently.  We address open questions about the numerical stability of various block classical Gram-Schmidt variants that have been proposed in the past few years.  An abstract framework is employed, the flexibility of which allows for new rigorous bounds on the loss of orthogonality in these variants. We first analyse a generalization of (reorthogonalized) block classical Gram-Schmidt and show that a "strong'' intrablock orthogonalization routine is only needed for the very first block in order to maintain orthogonality on the level of the unit roundoff. 
Using this variant, which has four synchronization points per block column, we remove the synchronization points one at a time and analyse how each alteration affects the stability of the resulting method. Our analysis shows that the variant requiring only one synchronization per block column cannot be guaranteed to be stable in practice, as stability begins to degrade with the first reduction of synchronization points.
Our analysis of block methods also provides new theoretical results for the single-column case. In particular, it is proven that DCGS2 from Bielich, D. et al. {Par. Comput.} 112 (2022)] and CGS-2 from Swirydowicz, K. et al, {Num. Lin. Alg. Appl.} 28 (2021)] are as stable as Householder QR.  
Numerical examples from the BlockStab toolbox are included throughout, to help compare variants and illustrate the effects of different choices of intraorthogonalization subroutines.


 

Using real-time modelling to inform the 2017 Ebola outbreak response in DR Congo
 Thompson, R Hart, W Keita, M Fall, I Gueye, A Chamla, D Mossoko, M Ahuka-Mundeke, S Nsio-Mbeta, J Jombart, T Polonsky, J Nature Communications volume 15 issue 1 (06 Jul 2024)

A blooming good time

Join us in the Radcliffe Science Library to plant a plug (young plant) in a pot, pack in compost and take away the plant with you. Book your place and enjoy the texture of fresh soil on your hands and the joy of a plant to bring home. Drop in anytime during the 2 hour slot.

Date: Wednesday 12 June

Time: 10am-12pm

Location: Wellbeing Room, Radcliffe Science Library

Subscribe to