Date/Time : 11 Jan 2024 16:00
Venue : S17 #05-12 (SR4)
Speaker : Mathias Weller, Technische Universität Berlin

In this talk, I will give a high-level introduction of some important computational problems in “Phylogenetics”, a branch of Biology that works with evolutionary histories of “taxa” (species, genes, samples, …). We will see some landmark results related to parameterized algorithms that analyze such histories.

In the second part of the talk, I would like to speak about a recently introduced layout-parameter for phylogenetic networks (basically rooted directed acyclic graphs with leaf-labels) called “scanwidth”, which has close ties to the treewidth of the underlying undirected graph. I will give examples for algorithmic results parameterized by the scanwidth and talk about efforts to efficiently compute the parameter itself.

Add to calendar :

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 : 10 Jan 2024 15:00
Venue : S17 #04-05 (SR2)
Speaker : Yu-Xiang Wang, University of California, Santa Barbara

Why do deep neural networks work better in practice than classical methods, e.g., kernels / splines? The talk covers a recent line of research that inspects DNNs from the classical non-parametric regression (or “curve fitting”) which reveals that the reason why DNNs work better might be due to its adaptivity when we tune its standard hyperparameters, which implicitly discovers hidden sparsity and low-dimensional structures. I will go over theory and examples to illustrate this point. For example, the effect of “Weight Decay” is in fact to select a small number of learned basis functions and the deeper the network is, the sparser it gets no matter how overparameterized the network is. Also, weight-decay helps a ConvResNeXT architecture to discover avoid the curse-of-dimensionality when the high-dimensional data is embedded in an unknown low-dimensional manifold. Last but not least, I will explain how the choice of “learning rate” determines the smoothness of functions that SGD can stably converge to, thus informing us on generalization.

References:
[1] Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive? https://arxiv.org/abs/2204.09664

[2] Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks. https://arxiv.org/abs/2307.01649

Add to calendar :

Date/Time : 09 Jan 2024 15:00
Venue : S17 #04-05 (SR2)
Speaker : Manlio Valenti, Swansea University

Ramsey’s theorem for n-tuples and k-colors can be generalized to colorings of binary trees. More precisely, TT^n_k states that given a k-coloring of the n-subsets of finite binary strings, there is a monochromatic set of strings that is isomorphic to the full binary tree. In the literature, this is sometimes referred to as
Chubb-Hirst-McNicholl tree theorem. In this talk, we will be focusing on the tree pigeonhole principle, namely the special case of the tree theorem for colorings of strings (i.e. n=1). We analyze its uniform computational content within the framework of Weihrauch reducibility. We show that different ways of phrasing the theorem yield different Weihrauch degrees. Our results provide new insights on the first-order part of the tree pigeonhole principle.

This is joint work with Damir Dzhafarov and Reed Solomon.

Add to calendar :

Date/Time : 04 Jan 2024 15:00
Venue : S17 #04-06 (SR1)
Speaker : Gal Chechik, Bar-Ilan University

Machine learning now heavily relies on “foundation models”, representations trained with massive data in a task-agnostic way, and then used for downstream tasks. But how can we make them most useful for our own tasks? I will discuss a series of studies addressing this problem in the context of vision-and-language models. These include textual-inversion techniques – where we teach new personalized visual concepts to the model that can be combined with known concepts, and ways to improve their editability and speed. I will also discuss generation of rare classes, personalized approaches to discriminative problems, and future directions in model personalization.

Add to calendar :

Date/Time : 22 Dec 2023 10:00
Venue : via Zoom
Speaker : Li Bowen, Duke University

Zoom link: https://nus-sg.zoom.us/j/81215174559?pwd=T21GRHJBSTRIMHhta0hVUlRrQVQvdz09

Meeting ID: 812 1517 4559
Passcode: 938817

In this talk, we discuss some recent results for photonic and quantum interacting systems. We first consider the scattering resonances in the wave interaction with nanoparticles of high refractive indices and their applications in imaging and material science. We will establish the existence and asymptotic behaviors of dielectric resonances and show that near a resonant frequency, a singular particle exhibits resonant magnetic dipole characteristics. We then discuss the topological properties of scattering resonances for the nanophotonic crystals. In particular, we prove the genericity of the Dirac dispersion cone for honeycomb lattice and the existence of embedded eigenvalue with Fano-type asymmetric peaks in transmission spectra. Further, we focus on two prototypical quantum interacting systems that are closely related to quantum optimal transport: the ground-state energy problem and open quantum dynamics. We will present an SDP relaxation hierarchy with optimized clusters for the ground-state energy of the quantum many-body Hamiltonian that admits a quantum embedding interpretation. For open quantum dynamics, we introduce quantum Beckner’s inequalities to quantify its long-time behavior with respect to convex entropies. We will discuss the properties of the Beckner constant in detail and provide a uniform lower bound in terms of the spectral gap. Moreover, we define a new class of quantum Wasserstein distances such that the quantum dynamic is a gradient flow and its convergence can be characterized by entropic Ricci curvature lower bound associated with the convex entropy. Some ongoing works and open questions will also be discussed.

Add to calendar :

Date/Time : 22 Dec 2023 15:00
Venue : S17 #04-06 (SR1)
Speaker : Gang Bao, Zhejiang University

Inverse problems are concerned with determining model parameters from the observed data, which arise in diverse application areas, such as nondestructive testing, seismic imaging, optical imaging, materials characterization, and medical imaging. A well-known representative inverse problem is electrical impedance tomography (EIT), also known as Calderón’s problem, which determines the electrical conductivity from the voltage to current map on the boundary. In general, inverse problems are known to be severely ill-posed, in particular, small perturbations in the measured data may lead to large errors in the reconstructions. Stable numerical solution of inverse problems remains a big challenge in computational inverse problems. In this talk, the speaker will discuss some new directions for solving inverse problems. Of particular interest are recursive linearization methods based on multiple frequency data, deep learning methods, and optimal transportation approaches. These methods are shown to be suitable for solving severely ill-posed problems. Numerical results will be presented to validate the effectiveness and feasibility of the methods.

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 :