This thesis presents methodological advances in two distinct problem families, each centered on the development of scalable approximation schemes that leverage underlying structure in a systematic way. The first set of contributions concerns the development of a spectral methods framework for a rich class of optimization problems. Spectral methods leverage the eigenvalues and eigenvectors of carefully constructed matrices to extract information from large, noisy, or complex data, and underpin effective algorithms across a wide range of domains, from graph-based tasks such as spectral clustering, planted clique detection, and graph coloring to classical techniques such as principal component analysis and ranking. While conceptually unified, these methods are typically tailored to each problem through specialized matrix constructions and analyses. The first part of this thesis introduces a unified framework of spectral relaxations for polynomial optimization problems (POPs). These problems, which involve minimizing a multivariate polynomial over a region defined by polynomial constraints, capture many fundamental models in optimization — subsuming linear programs, quadratic programs, and combinatorial optimization problems — and their exact solution is computationally intractable in general. At the same time, their polynomial description endows them with rich algebraic structure that can be systematically exploited to derive tractable relaxations. In Chapter 3, we realize this potential through the construction of a hierarchy of tractable relaxations that yields a monotone sequence of bounds on the optimal value of a POP, each computed as the minimum generalized eigenvalue of a matrix pair obtained from the problem data. Because eigenvalue problems can be solved reliably using off-the-shelf methods at scales well beyond those accessible to general-purpose semidefinite programming (SDP) solvers, which underpin state-of-the-art relaxation methods for polynomial optimization, this approach provides a compelling alternative for obtaining bounds on medium- to large-scale instances. These gains are further amplified in Chapter 4, which adapts the framework to enable the exploitation of discrete symmetries of a POP, yielding substantial reductions in computational cost whenever such structure is present. The second part of the thesis concerns kernel quadrature, where the goal is to approximate the integral of a function by a weighted sum of finitely many function evaluations at carefully chosen nodes. We consider functions belonging to a reproducing kernel Hilbert space (RKHS) and select these nodes using randomly pivoted Cholesky (RPCholesky), a sequential sampling algorithm that, in our setting, exploits the kernel structure to adaptively identify informative evaluation points. The resulting method achieves near-optimal error rates while remaining computationally efficient and broadly applicable across kernels, measures, and domains. Beyond kernel quadrature, the analysis yields results of independent interest: it extends the RPCholesky algorithm—originally developed for low-rank approximation of positive semidefinite matrices—to infinite-dimensional settings, and provides efficient procedures for exact sampling from the distributions it induces.
Elvira Moreno Ferreira (Mon,) studied this question.