This dissertation develops algorithms and theory for optimization, sampling, and generative modeling on manifolds, with Lie groups as a central object of study. Lie groups are manifolds with additional group structure; when endowed with a left-invariant Riemannian metric they become Riemannian manifolds, a setting that plays a central role throughout this work.
We first consider optimization on the Stiefel manifold $\mathrm{St}(n,d)$, the set of $n\times d$ matrices with orthonormal columns. By deriving a variational principle on this manifold, we construct the Momentum Stiefel Optimizer, a momentum-based algorithm that exactly preserves the orthogonality constraint at every iteration. The optimizer is applied to suitably-orthogonal attention in transformers and to optimal transport problems, achieving consistent improvements over existing methods.
We then establish quantitative convergence guarantees for momentum optimizers on Lie groups equipped with a left-invariant metric. Using the left-trivialization technique, which maps the curved dynamics to a flat Euclidean space for the momentum variable, we prove the first explicit convergence rates for both Heavy-Ball and Nesterov Accelerated methods on compact Lie groups, with rates that match Euclidean theory in terms of the smoothness and strong-convexity constants.
Next, we develop gauge-equivariant accelerated methods for optimization over the Grassmannian $\mathrm{Gr}(n,d)$, the set of $d$-dimensional subspaces of $\mathbb{R}^n$. Because each subspace has infinitely many orthonormal representatives related by an $\mathrm{O}(d)$ rotation, a naive lift of Stiefel algorithms to the Grassmannian is not gauge-equivariant. We introduce a gauge-fixing pipeline that converts any Stiefel optimizer into a gauge-equivariant Grassmann algorithm, yielding Grassmann Anderson Acceleration and Grassmann NAG, validated on density functional theory and low-rank matrix completion.
We then turn to sampling on Lie groups. By adding tractable noise to the left-trivialized momentum dynamics, we construct the first kinetic (momentum) Langevin Monte Carlo sampler on Lie groups with rigorous nonasymptotic convergence guarantees. The sampler preserves the group structure exactly at every step. Exponential convergence in $W_2$ distance is proved under only compactness of the Lie group and geodesic smoothness of the potential, without any convexity or isoperimetric assumption.
Finally, we address score-based generative modeling on general Riemannian manifolds. The standard denoising score matching framework requires a tractable forward-process transition kernel, which is unavailable on general manifolds because the heat kernel is intractable. We propose splitting diffusion, which lifts the dynamics to the tangent bundle and alternates closed-form stochastic momentum updates in the Euclidean tangent space with deterministic geodesic transport. The resulting transition kernel is closed-form, enabling denoising score matching training on general Riemannian manifolds requiring only exponential map as oracle.
Please Note: Zoom link: https://gatech.zoom.us/j/97454744253?pwd=bSRS939RDbV6PLbi7Os88aL8yoa1lG.1
Let $(S,\mathcal{A})$ be a measurable space and let $\mathcal{P}$ be a family of probability distributions on it. Given a Banach space $E$, a mapping $\theta:\mathcal{P}\to E$, and a smooth functional $f:E\to\mathbb{R}$, we consider the problem of estimating $f(\theta(P))$ from i.i.d. observations $X_1,\ldots,X_n\sim P$, where $P\in\mathcal{P}$. We write $f\in C^s(E)$ for a functional of Hölder smoothness $s=m+\rho$, where $m\ge 0$ is an integer and $\rho\in(0,1]$. Our aim is to construct estimators of $f(\theta(P))$ and to study their dependence on the sample size $n$, the smoothness $s$, and the dimension or complexity of the parameter $\theta(P)$.
When $\hat\theta_n$ is a $\sqrt{n}$-consistent base estimator of $\theta(P)$, the plug-in estimator $f(\hat\theta_n)$ is asymptotically efficient in classical low-dimensional models, but in high-dimensional and infinite-dimensional settings its bias is often too large to attain the rate $n^{-1/2}$. Existing bias reduction methods, based on iterated bootstrap or on linear aggregation of plug-in estimators, rely on concentration inequalities for $f(\hat\theta_n)$ that are available only for a limited class of models.
In this dissertation we study a class of estimators $T_f(X_1,\ldots,X_n)$ obtained from a Taylor expansion of $f$ about $\hat\theta_n$, of order determined by $s$, together with a sample split. Their analysis uses only bounds on the moments of the linear and higher order terms of $\hat\theta_n-\theta(P)$, rather than concentration inequalities. For functionals of smoothness $s\ge 1$, we derive upper bounds on the $L_p$-errors of $T_f$ whose dependence on $n$, on $s$, and on the dimension or complexity of the parameter matches the minimax lower bounds we obtain. We also give conditions under which these estimators are asymptotically normal and asymptotically efficient.
We develop these results in three settings: models composed of a large number of independent low-dimensional components, high-dimensional exponential families, and functionals of covariance operators in infinite-dimensional subgaussian models, where the complexity of the model is measured by the effective rank of the covariance operator.
Let $G$ be an $n$-vertex graph with Laplacian eigenvalues $0=\lambda_1(G)\le \lambda_2(G)\le\cdots\le \lambda_n(G)$. Motivated by the Alon--Boppana bound and the Ramanujan phenomenon for regular graphs, Spielman conjectured that, for every graph $G$ with fixed average degree $d\ge 1$, its Laplacian eigenratio satisfies $$\frac{\lambda_2(G)}{\lambda_n(G)} \le \frac{d-2\sqrt{d-1}}{d+2\sqrt{d-1}}+o_n(1),$$ where $o_n(1)\to 0$ as $n\to\infty$. The main purpose of this paper is to investigate this conjecture. We show that the situation is mixed. On the negative side, the conjecture fails for infinitely many average degrees $d>2$, via constructions based on bipartite Ramanujan graphs. On the positive side, it holds in two important settings: we verify it for all average degrees $d\le 2$, and we prove it for all regular graphs. In fact, for regular graphs we obtain stronger bounds comparing higher Laplacian eigenvalues. As a consequence, we show that for every fixed $d\ge 3$ and every $\varepsilon>0$, every sufficiently large $d$-regular Ramanujan graph has linearly many adjacency eigenvalues below $-2\sqrt{d-1}+\varepsilon$, thereby strengthening earlier results of Li and Cioabă by giving an unconditional result of this form. We also settle two related conjectures: one of You and Liu concerning the maximum Laplacian eigenratio of trees, and one of Gu concerning the Hamiltonicity of graphs with large Laplacian eigenratio.
Joint with Quanyu Tang, Yuchang Wang and Zhiheng Zheng.
Coupled oscillators appear in a large number of applications: e.g. in biological, chemical sciences, neuro science, power grids, and many more fields. They appear in nature: fireflies flashing in sync with each other is one fun situation.
In 1974, Yoshiki Kuramoto proposed a simple, yet surprisingly effective model for oscillators. We consider homogeneous Kuramoto systems (we will define these notions!). They are determined from a finite graph. In this talk, we describe some of what is known about long term behavior of such systems (do the oscillators self-synchronize? or are there other, "exotic" solutions?), and then relate these systems to systems of polynomial equations. We use algebra, computations in algebraic geometry, and algebraic geometry to study equilibrium solutions to these systems. We will see how computations using algebraic geometry and my computer algebra system Macaulay2 finds all graphs with at most 8 vertices (i.e. 8 oscillators) which have exotic solutions.
Note: we assume essentially NO dynamical systems nor algebraic geometry in this talk! This talk should be understandable to a general mathematical audience. The parts of the talk that are new represent joint work with Heather Harrington and Hal Schenck, and also Steve Strogatz and Alex Townsend.
Engel structures are maximally non-integrable rank-two plane fields on four-dimensional manifolds. They are closely related to contact geometry, but their global behavior is still much less understood.
In contact topology, complex tangencies of real hypersurfaces in complex manifolds give a fundamental source of contact structures, often with strong rigidity properties. This motivates the Engel analogue: can a compact four-dimensional submanifold of $\mathbb C^3$ have complex tangencies forming an Engel structure?
In this talk, I will explain how to construct such examples in the case of embeddings $M \times S^1 \subset \mathbb C^3$. The main idea is to start from a standard construction of Engel structures on circle bundles over $3$-manifolds, and then realize these Engel distributions as complex tangencies of a suitable embedding into $\mathbb C^3$. This gives the first compact examples of submanifolds of $\mathbb C^3$ whose complex tangencies are Engel, answering a question of Yakov Eliashberg. This is joint work with E. Fernández and Á. del Pino.
Please Note: This is the defense of the speaker's Master's thesis.
Combinatorial homotopy theory, or $A$-theory, is a homotopy theory of simplicial complexes which is known to have far-reaching applications. In the graph case, it coincides with a notion of homotopy first introduced by Maurer to study matroid basis graphs. In the language of $A$-theory, Maurer's celebrated homotopy theorem states that matroid basis graphs have trivial fundamental group. We ask whether this result can be strengthened and make progress toward showing that matroid basis graphs are $A$-contractible. We look at this problem through the lens of Malle's "gangster problem," which formulates $A$-contractibility of graphs in terms of gangsters travelling between towns.
Zoom link: https://gatech.zoom.us/j/99884528900
In many applications of mathematical optimization, one may wish to optimize an objective function without access to its derivatives. These situations call for derivative-free optimization (DFO) methods. Among the most successful approaches in practice are model-based trust-region methods, such as those pioneered by M.J.D Powell. These methods rely on function approximations via low degree polynomials and carefully adapt the local geometry of interpolation points to balance exploration and exploitation. While relatively complex to implement, these methods are now available in standard scientific computing platforms, including MATLAB and SciPy. However, theoretical analysis of their computational complexity lags behind practice. In particular, it is important to bound the number of function evaluations required to achieve a desired level of accuracy. Using concepts from Lagrangian interpolation and linear algebra we systematically derive complexity bounds for classical model-based trust-region methods and their modern variations. We establish, for the first time, that these methods can have the same worst case complexity than any other known DFO method.
Isometric embeddings between a domain manifold and a target manifold are differentiable maps f such that the pullback of the target metric h coincides with the metric g in the domain manifold. This problem can also be formulated as a non-linear PDE via $\nabla f^{\top} h \nabla f = g$. In the case of contact manifolds, it is additionally required that the embedding preserves a certain restriction on the tangent bundle.
We prove that the Nash iteration scheme can be quantified in order to construct infinitely many $C^{1,\alpha}$-isometric embeddings for contact manifolds. In this way, we extend an existing result regarding non-uniqueness for $C^1$ regularity. The strategy of the proof follows a paper by Conti, De Lellis and Szekelyhidi Jr. on the Riemannian case, which is built on the Nash-Kuiper scheme. The main difficulty in our case is to keep the additional linear constraint coming from the contact setting along the iteration procedure.
In the larger program of a quantitative analysis of isometric embeddings between sub-Riemannian manifolds, our result can be seen as an important first step. Another aspect is the flexibility of this convex integration method: the geometric constraint coming from the contact condition is just one special case of a (potentially large) class of admissible constraints, under which this scheme can still be applied.
