pwc-archive/papers-with-abstracts huggingface dataset:
Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics
Authors: Herman Chau, Helen Jenne, Davis Brown, Jesse He, Mark Raugas, Sara Billey, Henry Kvinge
Date: 2025-03-09 00:00:00
Tasks: Abstract Algebra, Program Synthesis

With recent dramatic increases in AI system capabilities, there has been growing interest in utilizing machine learning for reasoning-heavy, quantitative tasks, particularly mathematics. While there are many resources capturing mathematics at the high-school, undergraduate, and graduate level, there are far fewer resources available that align with the level of difficulty and open endedness encountered by professional mathematicians working on open problems. To address this, we introduce a new collection of datasets, the Algebraic Combinatorics Dataset Repository (ACD Repo), representing either foundational results or open problems in algebraic combinatorics, a subfield of mathematics that studies discrete structures arising from abstract algebra. Further differentiating our dataset collection is the fact that it aims at the conjecturing process. Each dataset includes an open-ended research-level question and a large collection of examples (up to 10M in some cases) from which conjectures should be generated. We describe all nine datasets, the different ways machine learning models can be applied to them (e.g., training with narrow models followed by interpretability analysis or program synthesis with LLMs), and discuss some of the challenges involved in designing datasets like these.
Diffusion Models for Cayley Graphs
Authors: Michael R. Douglas, Cristofero Fraser-Taliente
Date: 2025-03-07 00:00:00
Tasks: Rubik's Cube

We review the problem of finding paths in Cayley graphs of groups and group actions, using the Rubik's cube as an example, and we list several more examples of significant mathematical interest. We then show how to formulate these problems in the framework of diffusion models. The exploration of the graph is carried out by the forward process, while finding the target nodes is done by the inverse backward process. This systematizes the discussion and suggests many generalizations. To improve exploration, we propose a ``reversed score'' ansatz which substantially improves over previous comparable algorithms.
Riemannian Metric Learning: Closer to You than You Imagine
Authors: Samuel Gruffaz, Josua Sassen
Date: 2025-03-07 00:00:00
Tasks: Causal Inference, Metric Learning, Representation Learning

Riemannian metric learning is an emerging field in machine learning, unlocking new ways to encode complex data structures beyond traditional distance metric learning. While classical approaches rely on global distances in Euclidean space, they often fall short in capturing intrinsic data geometry. Enter Riemannian metric learning: a powerful generalization that leverages differential geometry to model the data according to their underlying Riemannian manifold. This approach has demonstrated remarkable success across diverse domains, from causal inference and optimal transport to generative modeling and representation learning. In this review, we bridge the gap between classical metric learning and Riemannian geometry, providing a structured and accessible overview of key methods, applications, and recent advances. We argue that Riemannian metric learning is not merely a technical refinement but a fundamental shift in how we think about data representations. Thus, this review should serve as a valuable resource for researchers and practitioners interested in exploring Riemannian metric learning and convince them that it is closer to them than they might imagine-both in theory and in practice.
Encoding Argumentation Frameworks to Propositional Logic Systems
Authors: Shuai Tang, Jiachao Wu, Ning Zhou
Date: 2025-03-10 00:00:00

The theory of argumentation frameworks ($AF$s) has been a useful tool for artificial intelligence. The research of the connection between $AF$s and logic is an important branch. This paper generalizes the encoding method by encoding $AF$s as logical formulas in different propositional logic systems. It studies the relationship between models of an AF by argumentation semantics, including Dung's classical semantics and Gabbay's equational semantics, and models of the encoded formulas by semantics of propositional logic systems. Firstly, we supplement the proof of the regular encoding function in the case of encoding $AF$s to the 2-valued propositional logic system. Then we encode $AF$s to 3-valued propositional logic systems and fuzzy propositional logic systems and explore the model relationship. This paper enhances the connection between $AF$s and propositional logic systems. It also provides a new way to construct new equational semantics by choosing different fuzzy logic operations.
Data-Driven Sequential Sampling for Tail Risk Mitigation
Authors: Dohyun Ahn, TaeHo Kim
Date: 2025-03-10 00:00:00

Given a finite collection of stochastic alternatives, we study the problem of sequentially allocating a fixed sampling budget to identify the optimal alternative with a high probability, where the optimal alternative is defined as the one with the smallest value of extreme tail risk. We particularly consider a situation where these alternatives generate heavy-tailed losses whose probability distributions are unknown and may not admit any specific parametric representation. In this setup, we propose data-driven sequential sampling policies that maximize the rate at which the likelihood of falsely selecting suboptimal alternatives decays to zero. We rigorously demonstrate the superiority of the proposed methods over existing approaches, which is further validated via numerical studies.
Automated Proof of Polynomial Inequalities via Reinforcement Learning
Authors: Banglong Liu, Niuniu Qi, Xia Zeng, Lydia Dehbi, Zhengfeng Yang
Date: 2025-03-09 00:00:00
Proceeding: CVPR 2025 1
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Polynomial inequality proving is fundamental to many mathematical disciplines and finds wide applications in diverse fields. Current traditional algebraic methods are based on searching for a polynomial positive definite representation over a set of basis. However, these methods are limited by truncation degree. To address this issue, this paper proposes an approach based on reinforcement learning to find a {Krivine-basis} representation for proving polynomial inequalities. Specifically, we formulate the inequality proving problem as a linear programming (LP) problem and encode it as a basis selection problem using reinforcement learning (RL), achieving a non-negative {Krivine basis}. Moreover, a fast multivariate polynomial multiplication method based on Fast Fourier Transform (FFT) is employed to enhance the efficiency of action space search. Furthermore, we have implemented a tool called {APPIRL} (Automated Proof of Polynomial Inequalities via Reinforcement Learning). Experimental evaluation on benchmark problems demonstrates the feasibility and effectiveness of our approach. In addition, {APPIRL} has been successfully applied to solve the maximum stable set problem.
BARK: A Fully Bayesian Tree Kernel for Black-box Optimization
Authors: Toby Boyne, Jose Pablo Folch, Robert M Lee, Behrang Shafei, Ruth Misener
Date: 2025-03-07 00:00:00
Tasks: Bayesian Optimization, Gaussian Processes, global-optimization, Uncertainty Quantification

We perform Bayesian optimization using a Gaussian process perspective on Bayesian Additive Regression Trees (BART). Our BART Kernel (BARK) uses tree agreement to define a posterior over piecewise-constant functions, and we explore the space of tree kernels using a Markov chain Monte Carlo approach. Where BART only samples functions, the resulting BARK model obtains samples of Gaussian processes defining distributions over functions, which allow us to build acquisition functions for Bayesian optimization. Our tree-based approach enables global optimization over the surrogate, even for mixed-feature spaces. Moreover, where many previous tree-based kernels provide uncertainty quantification over function values, our sampling scheme captures uncertainty over the tree structure itself. Our experiments show the strong performance of BARK on both synthetic and applied benchmarks, due to the combination of our fully Bayesian surrogate and the optimization procedure.
Tractable Representations for Convergent Approximation of Distributional HJB Equations
Authors: Julie Alhosh, Harley Wiltzer, David Meger
Date: 2025-03-07 00:00:00
Tasks: Reinforcement Learning (RL)

In reinforcement learning (RL), the long-term behavior of decision-making policies is evaluated based on their average returns. Distributional RL has emerged, presenting techniques for learning return distributions, which provide additional statistics for evaluating policies, incorporating risk-sensitive considerations. When the passage of time cannot naturally be divided into discrete time increments, researchers have studied the continuous-time RL (CTRL) problem, where agent states and decisions evolve continuously. In this setting, the Hamilton-Jacobi-Bellman (HJB) equation is well established as the characterization of the expected return, and many solution methods exist. However, the study of distributional RL in the continuous-time setting is in its infancy. Recent work has established a distributional HJB (DHJB) equation, providing the first characterization of return distributions in CTRL. These equations and their solutions are intractable to solve and represent exactly, requiring novel approximation techniques. This work takes strides towards this end, establishing conditions on the method of parameterizing return distributions under which the DHJB equation can be approximately solved. Particularly, we show that under a certain topological property of the mapping between statistics learned by a distributional RL algorithm and corresponding distributions, approximation of these statistics leads to close approximations of the solution of the DHJB equation. Concretely, we demonstrate that the quantile representation common in distributional RL satisfies this topological property, certifying an efficient approximation algorithm for continuous-time distributional RL.
Spectral-Spatial Extraction through Layered Tensor Decomposition for Hyperspectral Anomaly Detection
Authors: Quan Yu, Yu-Hong Dai, Minru Bai
Date: 2025-03-07 00:00:00
Tasks: Anomaly Detection, Tensor Decomposition

Low rank tensor representation (LRTR) methods are very useful for hyperspectral anomaly detection (HAD). To overcome the limitations that they often overlook spectral anomaly and rely on large-scale matrix singular value decomposition, we first apply non-negative matrix factorization (NMF) to alleviate spectral dimensionality redundancy and extract spectral anomaly and then employ LRTR to extract spatial anomaly while mitigating spatial redundancy, yielding a highly efffcient layered tensor decomposition (LTD) framework for HAD. An iterative algorithm based on proximal alternating minimization is developed to solve the proposed LTD model, with convergence guarantees provided. Moreover, we introduce a rank reduction strategy with validation mechanism that adaptively reduces data size while preventing excessive reduction. Theoretically, we rigorously establish the equivalence between the tensor tubal rank and tensor group sparsity regularization (TGSR) and, under mild conditions, demonstrate that the relaxed formulation of TGSR shares the same global minimizers and optimal values as its original counterpart. Experimental results on the Airport-Beach-Urban and MVTec datasets demonstrate that our approach outperforms state-of-the-art methods in the HAD task.
Self-Supervised Penalty-Based Learning for Robust Constrained Optimization
Authors: Wyame Benslimane, Paul Grigas
Date: 2025-03-07 00:00:00
Tasks: Combinatorial Optimization

We propose a new methodology for parameterized constrained robust optimization, an important class of optimization problems under uncertainty, based on learning with a self-supervised penalty-based loss function. Whereas supervised learning requires pre-solved instances for training, our approach leverages a custom loss function derived from the exact penalty method in optimization to learn an approximation, typically defined by a neural network model, of the parameterized optimal solution mapping. Additionally, we adapt our approach to robust constrained combinatorial optimization problems by incorporating a surrogate linear cost over mixed integer domains, and a smooth approximations thereof, into the final layer of the network architecture. We perform computational experiments to test our approach on three different applications: multidimensional knapsack with continuous variables, combinatorial multidimensional knapsack with discrete variables, and an inventory management problem. Our results demonstrate that our self-supervised approach is able to effectively learn neural network approximations whose inference time is significantly smaller than the computation time of traditional solvers for this class of robust optimization problems. Furthermore, our results demonstrate that by varying the penalty parameter we are able to effectively balance the trade-off between sub-optimality and robust feasibility of the obtained solutions.
Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity
Authors: Daniel Yiming Cao, August Y. Chen, Karthik Sridharan, Benjamin Tang
Date: 2025-03-06 00:00:00

We study the optimization of non-convex functions that are not necessarily smooth (gradient and/or Hessian are Lipschitz) using first order methods. Smoothness is a restrictive assumption in machine learning in both theory and practice, motivating significant recent work on finding first order stationary points of functions satisfying generalizations of smoothness with first order methods. We develop a novel framework that lets us systematically study the convergence of a large class of first-order optimization algorithms (which we call decrease procedures) under generalizations of smoothness. We instantiate our framework to analyze the convergence of first order optimization algorithms to first and \textit{second} order stationary points under generalizations of smoothness. As a consequence, we establish the first convergence guarantees for first order methods to second order stationary points under generalizations of smoothness. We demonstrate that several canonical examples fall under our framework, and highlight practical implications.
A Graph-Partitioning Based Continuous Optimization Approach to Semi-supervised Clustering Problems
Authors: Wei Liu, Xin Liu, Michael K. Ng, Zaikun Zhang
Date: 2025-03-06 00:00:00
Tasks: Clustering, graph partitioning

Semi-supervised clustering is a basic problem in various applications. Most existing methods require knowledge of the ideal cluster number, which is often difficult to obtain in practice. Besides, satisfying the must-link constraints is another major challenge for these methods. In this work, we view the semi-supervised clustering task as a partitioning problem on a graph associated with the given dataset, where the similarity matrix includes a scaling parameter to reflect the must-link constraints. Utilizing a relaxation technique, we formulate the graph partitioning problem into a continuous optimization model that does not require the exact cluster number, but only an overestimate of it. We then propose a block coordinate descent algorithm to efficiently solve this model, and establish its convergence result. Based on the obtained solution, we can construct the clusters that theoretically meet the must-link constraints under mild assumptions. Furthermore, we verify the effectiveness and efficiency of our proposed method through comprehensive numerical experiments.
Fredholm Approach to Nonlinear Propagator Models
Authors: Eduardo Abi Jaber, Alessandro Bondi, Nathan De Carvalho, Eyal Neuman, Sturmius Tuschmann
Date: 2025-03-06 00:00:00

We formulate and solve an optimal trading problem with alpha signals, where transactions induce a nonlinear transient price impact described by a general propagator model, including power-law decay. Using a variational approach, we demonstrate that the optimal trading strategy satisfies a nonlinear stochastic Fredholm equation with both forward and backward coefficients. We prove the existence and uniqueness of the solution under a monotonicity condition reflecting the nonlinearity of the price impact. Moreover, we derive an existence result for the optimal strategy beyond this condition when the underlying probability space is countable. In addition, we introduce a novel iterative scheme and establish its convergence to the optimal trading strategy. Finally, we provide a numerical implementation of the scheme that illustrates its convergence, stability, and the effects of concavity on optimal execution strategies under exponential and power-law decay.
Reheated Gradient-based Discrete Sampling for Combinatorial Optimization
Authors: Muheng Li, Ruqi Zhang
Date: 2025-03-06 00:00:00
Tasks: Combinatorial Optimization

Recently, gradient-based discrete sampling has emerged as a highly efficient, general-purpose solver for various combinatorial optimization (CO) problems, achieving performance comparable to or surpassing the popular data-driven approaches. However, we identify a critical issue in these methods, which we term ''wandering in contours''. This behavior refers to sampling new different solutions that share very similar objective values for a long time, leading to computational inefficiency and suboptimal exploration of potential solutions. In this paper, we introduce a novel reheating mechanism inspired by the concept of critical temperature and specific heat in physics, aimed at overcoming this limitation. Empirically, our method demonstrates superiority over existing sampling-based and data-driven algorithms across a diverse array of CO problems.
On the Convergence of Adam-Type Algorithm for Bilevel Optimization under Unbounded Smoothness
Authors: Xiaochuan Gong, Jie Hao, Mingrui Liu
Date: 2025-03-05 00:00:00
Tasks: Bilevel Optimization, LEMMA, Meta-Learning

Adam has become one of the most popular optimizers for training modern deep neural networks, such as transformers. However, its applicability is largely restricted to single-level optimization problems. In this paper, we aim to extend vanilla Adam to tackle bilevel optimization problems, which have important applications in machine learning, such as meta-learning. In particular, we study stochastic bilevel optimization problems where the lower-level function is strongly convex and the upper-level objective is nonconvex with potentially unbounded smoothness. This unbounded smooth objective function covers a broad class of neural networks, including transformers, which may exhibit non-Lipschitz gradients. In this work, we introduce AdamBO, a single-loop Adam-type method that achieves $\widetilde{O}(\epsilon^{-4})$ oracle complexity to find $\epsilon$-stationary points, where the oracle calls involve stochastic gradient or Hessian/Jacobian-vector product evaluations. The key to our analysis is a novel randomness decoupling lemma that provides refined control over the lower-level variable. We conduct extensive experiments on various machine learning tasks involving bilevel formulations with recurrent neural networks (RNNs) and transformers, demonstrating the effectiveness of our proposed Adam-type algorithm.
Stochastic Epidemic Models with Partial Information
Authors: Florent Ouabo Kamkumo, Ibrahim Mbouandi Njiasse, Ralf Wunderlich
Date: 2025-03-10 00:00:00
Tasks: parameter estimation

Mathematical models of epidemics often use compartmental models dividing the population into several compartments. Based on a microscopic setting describing the temporal evolution of the subpopulation sizes in the compartments by stochastic counting processes one can derive macroscopic models for large populations describing the average behavior by associated ordinary differential equations such as the celebrated SIR model. Further, diffusion approximations allow to address fluctuations from the average and to describe the state dynamics also for smaller populations by stochastic differential equations. In general, not all state variables are directly observable, and we face the so-called "dark figure" problem, which concerns, for example, the unknown number of asymptomatic and undetected infections. The present study addresses this problem by developing stochastic epidemic models that incorporate partial information about the current state of the epidemic, also known as nowcast uncertainty. Examples include a simple extension of the SIR model, a model for a disease with lifelong immunity after infection or vaccination, and a Covid-19 model. For the latter, we propose a ``cascade state approach'' that allows to exploit the information contained in formally hidden compartments with observable inflow but unobservable outflow. Furthermore, parameter estimation and calibration are performed using ridge regression for the Covid-19 model. The results of the numerical simulations illustrate the theoretical findings.
Graph Alignment via Birkhoff Relaxation
Authors: Sushil Mahavir Varma, Irène Waldspurger, Laurent Massoulié
Date: 2025-03-07 00:00:00

We consider the graph alignment problem, wherein the objective is to find a vertex correspondence between two graphs that maximizes the edge overlap. The graph alignment problem is an instance of the quadratic assignment problem (QAP), known to be NP-hard in the worst case even to approximately solve. In this paper, we analyze Birkhoff relaxation, a tight convex relaxation of QAP, and present theoretical guarantees on its performance when the inputs follow the Gaussian Wigner Model. More specifically, the weighted adjacency matrices are correlated Gaussian Orthogonal Ensemble with correlation $1/\sqrt{1+\sigma^2}$. Denote the optimal solutions of the QAP and Birkhoff relaxation by $\Pi^\star$ and $X^\star$ respectively. We show that $\|X^\star-\Pi^\star\|_F^2 = o(n)$ when $\sigma = o(n^{-1.25})$ and $\|X^\star-\Pi^\star\|_F^2 = \Omega(n)$ when $\sigma = \Omega(n^{-0.5})$. Thus, the optimal solution $X^\star$ transitions from a small perturbation of $\Pi^\star$ for small $\sigma$ to being well separated from $\Pi^\star$ as $\sigma$ becomes larger than $n^{-0.5}$. This result allows us to guarantee that simple rounding procedures on $X^\star$ align $1-o(1)$ fraction of vertices correctly whenever $\sigma = o(n^{-1.25})$. This condition on $\sigma$ to ensure the success of the Birkhoff relaxation is state-of-the-art.
Distortion risk measures of sums of two counter-monotonic risks
Authors: Chunle Huang
Date: 2025-03-07 00:00:00

In this paper, we will show that under certain conditions, associated to any fixed distortion function $g$, the distortion risk measure of a sum of two counter-monotonic risks can be expressed as the sum of two related distortion risk measures of the marginals involved, one associated to the original distortion function $g$ and the other associated to the dual distortion function of $g$. This result extends some of the work in \cite{Chaoubi et al. (2020)} and \cite{HLD} since the class of distortion risk measures includes the risk measure of VaR and TVaR as special cases.