Date/Time : 29 May 2024 16:00
Venue : S17 #04-05 (SR2)
Speaker : Renbo Zhao, University of Iowa

We present and analyze a new Frank–Wolfe method for minimizing a -log-homogenous self-concordant barriers, with applications including positron emission tomography, D-optimal design, TV-regularized Poisson image de-blurring, quantum state tomography. The iteration complexity of our method is essentially , which recovers that obtained by Khachiyan (1996) on the D-optimal design problem. In addition, we also present and analyze an away-step variant of our proposed Frank–Wolfe method, and we show the global linear convergence of this method. When specialized to the D-optimal design problem, this settles an open problem in Ahipasaoglu, Sun and Todd (2008).

Add to calendar :

Date/Time : 06 Mar 2024 15:00
Venue : S17 #05-12 (SR4)
Speaker : Akiko Takeda, University of Tokyo

Random projection techniques based on the Johnson-Lindenstrauss lemma are used for randomly aggregating the constraints or variables of optimization problems while approximately preserving their optimal values, which leads to smaller-scale optimization problems. In this talk, we show a few applications of random matrix techniques for constructing random subspace algorithms that iteratively solve smaller-scale subproblems and discuss their convergence speed. This talk is based on joint works with Ryota Nozawa, and Pierre-Louis Poirion.

Add to calendar :

Date/Time : 06 Mar 2024 15:40
Venue : S17 #05-12 (SR4)
Speaker : Pierre-Louis Poirion, University of Tokyo

In this talk, we present a randomized subspace regularized Newton method for a non-convex function. We show that our method has global convergence under appropriate assumptions, and its convergence rate is the same as that of the full regularized Newton method. Furthermore, we can obtain a local linear convergence rate, under some additional assumptions, and prove that this rate is the best we can hope, under local strong convexity sumptions, when using random subspace. Finally, we will prove that under rank deficiency conditions, one can obtain super-linear convergence in the subspace setting.

Add to calendar :

Date/Time : 28 Feb 2024 15:00
Venue : S17 #04-05 (SR2)
Speaker : Jiequn Han, Flatiron Institute, USA

Partial differential equations (PDEs) are among the most ubiquitous tools in modeling natural phenomena, and various numerical methods have been developed for decades to solve PDE problems. While deep learning has introduced new techniques to the field, the limited accuracy of deep neural networks hinders their application to scientific problems that require high precision.

This talk will present a warm-start approach that combines the strengths of deep neural networks and classical numerical solvers. The approach uses neural networks to provide an initial guess, enabling classical numerical solvers to achieve a good solution more efficiently. We will demonstrate the advantages of the proposed method through two examples. In the first example, we will demonstrate how the initial guess provided by neural networks helps identify the basin of attraction of the true solution in the inverse scattering problem. In the second example, we will show how the initial guess provided by neural networks leads to faster convergence in solving the Reynolds-averaged Navier-Stokes equations. In both examples, the combination of the classical PDE solver and the neural network outperforms either approach alone. The potential of this approach will be discussed, along with the new challenges that must be tackled to solve challenging scientific problems using this new paradigm

Add to calendar :

Date/Time : 20 Feb 2024 15:00
Venue : S17 #04-06 (SR1)
Speaker : Yin Zhang, Chinese University of Hong Kong, Shenzhen

The Transformer architecture, in which the key innovation is a Self-Attention (SA) mechanism, has revolutionized AI fields since its introduction in 2017. However, it is difficult to extend the original architecture to deeper models with 10 or more layers. In this work, we show that this depth problem is caused by a phenomenon called token similarity escalation (TSE) which is driven by spectral properties of attention matrices in the SA mechanism. Based on the gained insights, we propose a simple de-escalation strategy to surgically removes excessive token similarity without discounting SA as a whole. Empirical evidence is presented to demonstrate the effectiveness of our scheme on small-scale models.

Add to calendar :

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 : 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 : 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 : 11 Dec 2023 15:00
Venue : S17 #04-06 (SR1)
Speaker : Heng Yang, Harvard University

Many fundamental estimation and decision-making problems in robotics are formulated as non-convex mathematical optimization problems. Decades of research have produced numerous algorithms to efficiently solve these problems, yet offering few performance guarantees. In this talk, I aim to advocate using convex semidefinite relaxations to design a new paradigm of algorithms that work out of the box and offer strong performance certificates.

I first briefly introduce the celebrated Lasserre’s hierarchy of moment and sums-of-squares (SOS) relaxations, which relaxes polynomial optimization and decision problems as a hierarchy of convex semidefinite programs (SDP). I then present three applications of this hierarchy in robotics. In the first application, we apply the hierarchy to solve outlier-robust estimation problems in robot perception and show that SDP relaxations provide certificates of optimality. In the second application, we combine this hierarchy with conformal prediction from statistics and set-membership estimation from control theory and demonstrate such relaxations provide certificates of uncertainty. In the third application, we revisit trajectory optimization problems arising in nonlinear optimal control and show that, by exploiting correlative sparsity, SDP relaxations produce near-optimal control trajectories. I end the talk by discussing computational challenges of this framework in our applications and opportunities to tackle them.

Add to calendar :