Computational Mathematics and Applications Seminar

Professor Luis Nunes Vicente will talk about 'Reducing Sample Complexity in Stochastic Derivative-Free Optimization via Tail Bounds and Hypothesis Testing';

We introduce and analyze new probabilistic strategies for enforcing sufficient decrease conditions in stochastic derivative-free optimization, with the goal of reducing sample complexity and simplifying convergence analysis. First, we develop a new tail bound condition imposed on the estimated reduction in function value, which permits flexible selection of the power used in the sufficient decrease test, q in (1,2]. This approach allows us to reduce the number of samples per iteration from the standard O(delta^{−4}) to O(delta^{-2q}), assuming that the noise moment of order q/(q-1) is bounded. Second, we formulate the sufficient decrease condition as a sequential hypothesis testing problem, in which the algorithm adaptively collects samples until the evidence suffices to accept or reject a candidate step. This test provides statistical guarantees on decision errors and can further reduce the required sample size, particularly in the Gaussian noise setting, where it can approach O(delta^{−2-r}) when the decrease is of the order of delta^r. We incorporate both techniques into stochastic direct-search and trust-region methods for potentially non-smooth, noisy objective functions, and establish their global convergence rates and properties. 

This is joint work with Anjie Ding, Francesco Rinaldi, and Damiano Zeffiro.

Professor De Terran will talk about: 'New results on the inclusion of closure orbits and bundles of matrices and matrix pencils' 

Orbits of nxn matrices under similarity are sets of matrices with the same Jordan Canonical form (JCF). When computing the JCF (or just the eigenvalues) of a matrix, the knowledge of all possible JCFs of small perturbations of a given JCF can help to understand the output of the algorithm, which is affected by roundoff errors.

The JCFs that can be obtained after small perturbations of a given JCF, say J, correspond to orbits that ``dominate" the orbit of J. In other words, the orbit of J is in the closure of its dominant orbits. The hierarchy of orbit closures of general matrices is well-known, as well as that of the set of matrices with bounded rank.

For matrix pencils (namely, pairs of matrices with the same size) the inclusion relationship between orbit closures has been also considered since, at least the 1980's. In this case, the standard equivalence relation is the so-called strict equivalence, which preserves the eigenstructure of the pencil, and the canonical form for this relation is the Kronecker canonical form (KCF). The hierarchy of orbit closures of general pencils under strict equivalence is also well-known. However, when the pencil has some particular structure (e. g., symmetric or Hermitian) then we encounter a different problem if we want the perturbations to maintain this structure. Some effort has been devoted in recent years to the analysis of orbit closures of structured pencils.

In this talk, we will review some recent results on the inclusion relationship between orbit closures of general and bounded-rank structured matrix pencils. We will also consider the inclusion relation of bundle closures. Bundles are generalizations of orbits, allowing the eigenvalues to change, while keeping the KCF. 
 

Dr Lindon Roberts will talk about: 'Optimization Algorithms for Bilevel Learning with Applications to Imaging'

Many imaging problems, such as denoising or inpainting, can be expressed as variational regularization problems. These are optimization problems for which many suitable algorithms exist. We consider the problem of learning suitable regularizers for imaging problems from example (training) data, which can be formulated as a large-scale bilevel optimization problem. 

In this talk, I will introduce new deterministic and stochastic algorithms for bilevel optimization, which require no or minimal hyperparameter tuning while retaining convergence guarantees. 

This is joint work with Mohammad Sadegh Salehi and Matthias Ehrhardt (University of Bath), and Subhadip Mukherjee (IIT Kharagpur).

TBA 

TBA

Applications involving optimization over graphs include molecular design, graph neural network verification, neural architecture search, etc. This talk discusses formulating graph spaces using mixed-integer optimization and incorporating application-specific constraints. We discuss computational challenges with these mixed-integer optimization formulations and zoom in on the practical implications for these applications. We mention what has been done (by both ourselves and others) and what other research still needs to be done.

Co-authors: Shiqiang Zhang, Yilin Xie, Christopher Hojny, Juan Campos, Jixiang Qing, Christian Feldmann, David Walz, Frederik Sandfort, Miriam Mathea, Calvin Tsay

This talk is hosted by Rutherford Appleton Laboratory, Harwell Campus

TBA