Date/Time : 11 Jan 2024 10:00
Venue : via Zoom
Speaker : Shaoning Han, University of Southern California

Join Zoom Meeting
https://nus-sg.zoom.us/j/83242625129?pwd=ZmRzME93QndWbTNZQUdPUVdIS080Zz09

Meeting ID: 832 4262 5129
Passcode: 157423

Many regression problems arising in modern data science involve combinatorial decisions. For instance, sparsity is often introduced into statistical models to enhance interpretability and generalization. Outlier detection before training can contribute to model robustness. When cast as optimization problems, they are typically NP-hard, posing significant computational hurdles. To ease the computational burden, practitioners often either resort to much easier convex surrogates, albeit at the cost of sacrificing model fidelity, or rely on heuristics that lack theoretical guarantees unless stringent (sub)optimality conditions are met. This presentation provides insights into understanding and solving combinatorial regression problems through the lens of mixed-integer nonlinear programming. The first part focuses on developing convexification techniques that are applicable to general objectives with low-rank decompositions. In the second part, we explore solution methods tailored for a specific class of regression problems defined over graphs.

Add to calendar :

Date/Time : 19 Dec 2023 15:00
Venue : S17 #04-06 (SR1)
Speaker : Zhuan Koh, The national research institute for mathematics and computer science (Netherlands)

Linear programs (LPs) can be solved in polynomial time using the ellipsoid algorithm or interior point methods (IPMs). However, it is a major open question whether LPs can be solved in strongly polynomial time. Given an LP with m inequalities and n variables, a strongly polynomial algorithm must compute an optimal solution using poly(m,n) elementary arithmetic operations (+,-,*,/,<?). In particular, the number of such operations cannot depend on the size of coefficients describing the LP. This question was first asked by Megiddo in 1983, and listed as one of Smale’s problems for mathematics in the 21st century. In this talk, I will cover recent progress on this open problem. By combining circuits from combinatorial optimization and IPMs from continuous optimization, we provide an affirmative answer to this question when every inequality has at most two variables.

Add to calendar :

Date/Time : 14 Dec 2023 15:00
Venue : S17 #04-06 (SR1)
Speaker : Wang Ligong, Northwestern Polytechnical University

Let \mu(G) denote the spectral radius of a graph G. We partly confirm a conjecture due to Nikiforov, which is a spectral radius analogue of the well-known Erdos-Sos Conjecture that any tree of order t is contained in a graph of average degree greater than t − 2. Let S_{n,k} be the graph obtained by joining every vertex of a complete graph on k vertices to every vertex of an independent set of order n−k, and let S_{n,k}^+ be the graph obtained from S_{n,k} by adding a single edge joining two vertices of the independent set of S_{n,k}. In 2010, Nikiforov conjectured that for a given integer k, every graph G of sufficiently large order n with \mu(G) \geq \mu(S_{n,k}^+) contains all trees of order 2k + 3, unless G = S_{n,k}^+. We confirm this conjecture for trees with diameter at most four, with one exception. In fact, we prove the following stronger result for k \geq 8. If a graph G with sufficiently large order n satisfies \mu(G) ≥ \mu(S_{n,k}) and G \neq S_{n,k}, then G contains all trees of order 2k + 3 with diameter at most four, except for the tree obtained from a star on k + 2 vertices by subdividing each of its k + 1 edges once. We also introduce some new results about the above conjecture. This is a joint work with Xiangxiang Liu and Hajo Broersma.

Add to calendar :

Date/Time : 14 Dec 2023 15:40
Venue : S17 #04-06 (SR1)
Speaker : Bai Xueli, Northwestern Polytechnical University

As a first attempt to understand the effects of temporal periodicity on dynamics of general periodic parabolic reaction-diffusion systems, we analyze the asymptotic behaviour of the principal eigenvalue for linear cooperative/competition periodic-parabolic systems with small/large diffusion rates and then discuss local and global stability of related periodic-parabolic Lotka Volterra competition diffusion system. This is a joint work with Xiaoqing He and Wei-Ming Ni.

Add to calendar :

Date/Time : 14 Dec 2023 16:20
Venue : S17 #04-06 (SR1)
Speaker : Xiao Manyu, Northwestern Polytechnical University

The common issue of surrogate models is to make good use of sampling data. In theory, the higher the fidelity of sampling data obtained, the more accurate the approximation model built. However, in practical engineering problems, high-fidelity data may be less available, and such data may also be computationally expensive. On
the contrary, we often obtain low-fidelity data under certain simplifications. Although low-fidelity data is less accurate, such data still contains much information about the real system. So, combining both high- and low-fidelity data in the construction of a surrogate model may lead to better representation of the physical phenomena.

In this work, the original principle of Multi-Fidelity Proper Orthogonal Decomposition will consist in projecting the high-dimensional system of equations into a low-dimensional space, with reduced basis vectors. These vectors are updated with incremental “on-the-fly” merges between costly high-fidelity simulation snapshots and more rapid lower-fidelity vectors. Successful achievements of this work will lead to potential benefits in the fields of large-scale mechanical engineering.

Add to calendar :

Date/Time : 28 Nov 2023 15:00
Venue : S17 #04-06 (SR1)
Speaker : Morris Ang, Columbia University

In the first half of the talk, I will introduce the central objects in random conformal geometry. Schramm-Loewner evolution (SLE) is a random planar curve describing the scaling limits of interfaces in statistical physics models (e.g. percolation, Ising model). Liouville quantum gravity (LQG) is a random 2D surface arising as the scaling limit of random planar maps. These fractal geometries have deep connections to bosonic string theory and conformal field theories. There are many powerful theorems which say that, roughly speaking, cutting LQG by independent SLE gives two independent LQG surfaces. In the second half, I present some new developments and their applications.

Add to calendar :

Date/Time : 27 Nov 2023 15:00
Venue : S17 #04-06 (SR1)
Speaker : Lai Lexiao, Columbia University

Lyapunov stability is an important notion for dynamical systems, which has been absent in the optimization literature. When studying optimization methods, the goal has always been proving convergence. However, convergence to critical points could sometimes be unrealistic or undesirable in practice. In this talk, I will introduce the notions of Lyapunov stability for optimization methods. I will then describe my works on characterizing the local and global stability of first-order methods. My results apply to problems arising in data science. In particular, I provide a guarantee of the SGD optimizer for training neural networks.

Add to calendar :

Date/Time : 22 Nov 2023 15:00
Venue : S17 #04-06 (SR1)
Speaker : Anant Raj, University of Illinois Urbana-Champaign

In this talk, we delve into the intricate relationships between heavy-tailed distributions, generalization error, and algorithmic stability in the realm of noisy stochastic gradient descent. Recent research has illustrated the emergence of heavy tails in stochastic optimization and their intriguing links to generalization error. However, these studies often relied on challenging topological and statistical assumptions. Empirical evidence has further challenged existing theory, suggesting that the relationship between heavy tails and generalization is not always monotonic. In response, we introduce novel insights, exploring the relationship between tail behavior and generalization properties through the lens of algorithmic stability. Our analysis reveals that the stability of stochastic gradient descent (SGD) varies based on how we measure it, leading to interesting conclusions about its behavior.Expanding upon these findings, we extend the scope to a broader class of objective functions, including non-convex ones. Leveraging Wasserstein stability bounds for heavy-tailed stochastic processes, our research sheds light on the non-monotonic connection between generalization error and heavy tails, offering a more comprehensive perspective.Additionally, we introduce a unified approach for proving Wasserstein stability bounds in stochastic optimization, emphasizing time-uniform stability and its role in various scenarios, including convex and non-convex losses. Our approach is versatile and applicable to popular optimizers, highlighting the importance of ergodicity.

Add to calendar :

Date/Time : 22 Nov 2023 11:00
Venue : S17 #04-05 (SR2)
Speaker : Eva Lütkebohmert, University of Freiburg

Sovereign loan portfolios of Multilateral Development Banks typically consist of only a small number of borrowers and hence are heavily exposed to single name concentration risk. Based on realistic MDB portfolios constructed from publicly available data, this paper quantifies the magnitude of the exposure to name concentration risk using exact Monte Carlo simulations. In comparing the exact adjustment for name concentration risk to its analytic approximation as currently applied by major rating agencies, we further investigate whether current capital adequacy frameworks for MDBs are overly conservative.

(This is joint work with Julian Sester and Hongyi Shen)

Add to calendar :