pwc-archive/papers-with-abstracts huggingface dataset:
On the kernel learning problem
Authors: Yang Li, Feng Ruan
Date: 2025-02-17 00:00:00
Tasks: regression

The classical kernel ridge regression problem aims to find the best fit for the output $Y$ as a function of the input data $X\in \mathbb{R}^d$, with a fixed choice of regularization term imposed by a given choice of a reproducing kernel Hilbert space, such as a Sobolev space. Here we consider a generalization of the kernel ridge regression problem, by introducing an extra matrix parameter $U$, which aims to detect the scale parameters and the feature variables in the data, and thereby improve the efficiency of kernel ridge regression. This naturally leads to a nonlinear variational problem to optimize the choice of $U$. We study various foundational mathematical aspects of this variational problem, and in particular how this behaves in the presence of multiscale structures in the data.
Reconstruction of frequency-localized functions from pointwise samples via least squares and deep learning
Authors: A. Martina Neuman, Andres Felipe Lerma Pineda, Jason J. Bramburger, Simone Brugiapaglia
Date: 2025-02-13 00:00:00
Tasks: Deep Learning

Recovering frequency-localized functions from pointwise data is a fundamental task in signal processing. We examine this problem from an approximation-theoretic perspective, focusing on least squares and deep learning-based methods. First, we establish a novel recovery theorem for least squares approximations using the Slepian basis from uniform random samples in low dimensions, explicitly tracking the dependence of the bandwidth on the sampling complexity. Building on these results, we then present a recovery guarantee for approximating bandlimited functions via deep learning from pointwise data. This result, framed as a practical existence theorem, provides conditions on the network architecture, training procedure, and data acquisition sufficient for accurate approximation. To complement our theoretical findings, we perform numerical comparisons between least squares and deep learning for approximating one- and two-dimensional functions. We conclude with a discussion of the theoretical limitations and the practical gaps between theory and implementation.
Interpretable Machine Learning for Kronecker Coefficients
Authors: Giorgi Butbaia, Kyu-Hwan Lee, Fabian Ruehle
Date: 2025-02-17 00:00:00
Tasks: Interpretable Machine Learning

We analyze the saliency of neural networks and employ interpretable machine learning models to predict whether the Kronecker coefficients of the symmetric group are zero or not. Our models use triples of partitions as input features, as well as b-loadings derived from the principal component of an embedding that captures the differences between partitions. Across all approaches, we achieve an accuracy of approximately 83% and derive explicit formulas for a decision function in terms of b-loadings. Additionally, we develop transformer-based models for prediction, achieving the highest reported accuracy of over 99%.
Reduced Order Modeling with Shallow Recurrent Decoder Networks
Authors: Matteo Tomasetto, Jan P. Williams, Francesco Braghin, Andrea Manzoni, J. Nathan Kutz
Date: 2025-02-15 00:00:00
Tasks: Computational Efficiency, Decoder, Dimensionality Reduction, Uncertainty Quantification

Reduced Order Modeling is of paramount importance for efficiently inferring high-dimensional spatio-temporal fields in parametric contexts, enabling computationally tractable parametric analyses, uncertainty quantification and control. However, conventional dimensionality reduction techniques are typically limited to known and constant parameters, inefficient for nonlinear and chaotic dynamics, and uninformed to the actual system behavior. In this work, we propose sensor-driven SHallow REcurrent Decoder networks for Reduced Order Modeling (SHRED-ROM). Specifically, we consider the composition of a long short-term memory network, which encodes the temporal dynamics of limited sensor data in multiple scenarios, and a shallow decoder, which reconstructs the corresponding high-dimensional states. SHRED-ROM is a robust decoding-only strategy that circumvents the numerically unstable approximation of an inverse which is required by encoding-decoding schemes. To enhance computational efficiency and memory usage, the full-order state snapshots are reduced by, e.g., proper orthogonal decomposition, allowing for compressive training of the networks with minimal hyperparameter tuning. Through applications on chaotic and nonlinear fluid dynamics, we show that SHRED-ROM (i) accurately reconstructs the state dynamics for new parameter values starting from limited fixed or mobile sensors, independently on sensor placement, (ii) can cope with both physical, geometrical and time-dependent parametric dependencies, while being agnostic to their actual values, (iii) can accurately estimate unknown parameters, and (iv) can deal with different data sources, such as high-fidelity simulations, coupled fields and videos.
Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size
Authors: Naoki Takeshita, Masaaki Imaizumi
Date: 2025-02-17 00:00:00

Transformers are a type of neural network that have demonstrated remarkable performance across various domains, particularly in natural language processing tasks. Motivated by this success, research on the theoretical understanding of transformers has garnered significant attention. A notable example is the mathematical analysis of their approximation power, which validates the empirical expressive capability of transformers. In this study, we investigate the ability of transformers to approximate column-symmetric polynomials, an extension of symmetric polynomials that take matrices as input. Consequently, we establish an explicit relationship between the size of the transformer network and its approximation capability, leveraging the parameter efficiency of transformers and their compatibility with symmetry by focusing on the algebraic properties of symmetric polynomials.
On the robustness of ChatGPT in teaching Korean Mathematics
Authors: Phuong-Nam Nguyen, Quang Nguyen-The, An Vu-Minh, Diep-Anh Nguyen, Xuan-Lam Pham
Date: 2025-02-17 00:00:00

ChatGPT, an Artificial Intelligence model, has the potential to revolutionize education. However, its effectiveness in solving non-English questions remains uncertain. This study evaluates ChatGPT's robustness using 586 Korean mathematics questions. ChatGPT achieves 66.72% accuracy, correctly answering 391 out of 586 questions. We also assess its ability to rate mathematics questions based on eleven criteria and perform a topic analysis. Our findings show that ChatGPT's ratings align with educational theory and test-taker perspectives. While ChatGPT performs well in question classification, it struggles with non-English contexts, highlighting areas for improvement. Future research should address linguistic biases and enhance accuracy across diverse languages. Domain-specific optimizations and multilingual training could improve ChatGPT's role in personalized education.
Learning Euler Factors of Elliptic Curves
Authors: Angelica Babei, François Charton, Edgar Costa, Xiaoyu Huang, Kyu-Hwan Lee, David Lowry-Duda, Ashvni Narayanan, Alexey Pozdnyakov
Date: 2025-02-14 00:00:00

We apply transformer models and feedforward neural networks to predict Frobenius traces $a_p$ from elliptic curves given other traces $a_q$. We train further models to predict $a_p \bmod 2$ from $a_q \bmod 2$, and cross-analysis such as $a_p \bmod 2$ from $a_q$. Our experiments reveal that these models achieve high accuracy, even in the absence of explicit number-theoretic tools like functional equations of $L$-functions. We also present partial interpretability findings.
Studying number theory with deep learning: a case study with the Möbius and squarefree indicator functions
Authors: David Lowry-Duda
Date: 2025-02-14 00:00:00

Building on work of Charton, we train small transformer models to calculate the M\"obius function $\mu(n)$ and the squarefree indicator function $\mu^2(n)$. The models attain nontrivial predictive power. We then iteratively train additional models to understand how the model functions, ultimately finding a theoretical explanation.
Optimal control in combination therapy for heterogeneous cell populations with drug synergies
Authors: Simon F. Martina-Perez, Samuel W. S. Johnson, Rebecca M. Crossley, Jennifer C. Kasemeier, Paul M. Kulesa, Ruth E. Baker
Date: 2025-02-17 00:00:00

Cell heterogeneity plays an important role in patient responses to drug treatments. In many cancers, it is associated with poor treatment outcomes. Many modern drug combination therapies aim to exploit cell heterogeneity, but determining how to optimise responses from heterogeneous cell populations while accounting for multi-drug synergies remains a challenge. In this work, we introduce and analyse a general optimal control framework that can be used to model the treatment response of multiple cell populations that are treated with multiple drugs that mutually interact. In this framework, we model the effect of multiple drugs on the cell populations using a system of coupled semi-linear ordinary differential equations and derive general results for the optimal solutions. We then apply this framework to three canonical examples and discuss the wider question of how to relate mathematical optimality to clinically observable outcomes, introducing a systematic approach to propose qualitatively different classes of drug dosing inspired by optimal control.
Low-Rank Thinning
Authors: Annabelle Michael Carrell, Albert Gong, Abhishek Shetty, Raaz Dwivedi, Lester Mackey
Date: 2025-02-17 00:00:00

The goal in thinning is to summarize a dataset using a small set of representative points. Remarkably, sub-Gaussian thinning algorithms like Kernel Halving and Compress can match the quality of uniform subsampling while substantially reducing the number of summary points. However, existing guarantees cover only a restricted range of distributions and kernel-based quality measures and suffer from pessimistic dimension dependence. To address these deficiencies, we introduce a new low-rank analysis of sub-Gaussian thinning that applies to any distribution and any kernel, guaranteeing high-quality compression whenever the kernel or data matrix is approximately low-rank. To demonstrate the broad applicability of the techniques, we design practical sub-Gaussian thinning approaches that improve upon the best known guarantees for approximating attention in transformers, accelerating stochastic gradient training through reordering, and distinguishing distributions in near-linear time.
Double Momentum and Error Feedback for Clipping with Fast Rates and Differential Privacy
Authors: Rustem Islamov, Samuel Horvath, Aurelien Lucchi, Peter Richtarik, Eduard Gorbunov
Date: 2025-02-17 00:00:00
Tasks: Federated Learning

Strong Differential Privacy (DP) and Optimization guarantees are two desirable properties for a method in Federated Learning (FL). However, existing algorithms do not achieve both properties at once: they either have optimal DP guarantees but rely on restrictive assumptions such as bounded gradients/bounded data heterogeneity, or they ensure strong optimization performance but lack DP guarantees. To address this gap in the literature, we propose and analyze a new method called Clip21-SGD2M based on a novel combination of clipping, heavy-ball momentum, and Error Feedback. In particular, for non-convex smooth distributed problems with clients having arbitrarily heterogeneous data, we prove that Clip21-SGD2M has optimal convergence rate and also near optimal (local-)DP neighborhood. Our numerical experiments on non-convex logistic regression and training of neural networks highlight the superiority of Clip21-SGD2M over baselines in terms of the optimization performance for a given DP-budget.
Learning Surrogate Potential Mean Field Games via Gaussian Processes: A Data-Driven Approach to Ill-Posed Inverse Problems
Authors: Jingguo Zhang, Xianjin Yang, Chenchen Mou, Chao Zhou
Date: 2025-02-17 00:00:00
Tasks: Gaussian Processes

Mean field games (MFGs) describe the collective behavior of large populations of interacting agents. In this work, we tackle ill-posed inverse problems in potential MFGs, aiming to recover the agents' population, momentum, and environmental setup from limited, noisy measurements and partial observations. These problems are ill-posed because multiple MFG configurations can explain the same data, or different parameters can yield nearly identical observations. Nonetheless, they remain crucial in practice for real-world scenarios where data are inherently sparse or noisy, or where the MFG structure is not fully determined. Our focus is on finding surrogate MFGs that accurately reproduce the observed data despite these challenges. We propose two Gaussian process (GP)-based frameworks: an inf-sup formulation and a bilevel approach. The choice between them depends on whether the unknown parameters introduce concavity in the objective. In the inf-sup framework, we use the linearity of GPs and their parameterization structure to maintain convex-concave properties, allowing us to apply standard convex optimization algorithms. In the bilevel framework, we employ a gradient-descent-based algorithm and introduce two methods for computing the outer gradient. The first method leverages an existing solver for the inner potential MFG and applies automatic differentiation, while the second adopts an adjoint-based strategy that computes the outer gradient independently of the inner solver. Our numerical experiments show that when sufficient prior information is available, the unknown parameters can be accurately recovered. Otherwise, if prior information is limited, the inverse problem is ill-posed, but our frameworks can still produce surrogate MFG models that closely match observed data.
Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent
Authors: Ya-Chi Chu, Wenzhi Gao, Yinyu Ye, Madeleine Udell
Date: 2025-02-16 00:00:00

This paper investigates the convergence properties of the hypergradient descent method (HDM), a 25-year-old heuristic originally proposed for adaptive stepsize selection in stochastic first-order methods. We provide the first rigorous convergence analysis of HDM using the online learning framework of [Gao24] and apply this analysis to develop new state-of-the-art adaptive gradient methods with empirical and theoretical support. Notably, HDM automatically identifies the optimal stepsize for the local optimization landscape and achieves local superlinear convergence. Our analysis explains the instability of HDM reported in the literature and proposes efficient strategies to address it. We also develop two HDM variants with heavy-ball and Nesterov momentum. Experiments on deterministic convex problems show HDM with heavy-ball momentum (HDM-HB) exhibits robust performance and significantly outperforms other adaptive first-order methods. Moreover, HDM-HB often matches the performance of L-BFGS, an efficient and practical quasi-Newton method, using less memory and cheaper iterations.
Stochastic Optimization of Inventory at Large-scale Supply Chains
Authors: Zhaoyang Larry Jin, Mehdi Maasoumy, Yimin Liu, Zeshi Zheng, Zizhuo Ren
Date: 2025-02-16 00:00:00
Tasks: Stochastic Optimization

Today's global supply chains face growing challenges due to rapidly changing market conditions, increased network complexity and inter-dependency, and dynamic uncertainties in supply, demand, and other factors. To combat these challenges, organizations employ Material Requirements Planning (MRP) software solutions to set inventory stock buffers - for raw materials, work-in-process goods, and finished products - to help them meet customer service levels. However, holding excess inventory further complicates operations and can lock up millions of dollars of capital that could be otherwise deployed. Furthermore, most commercially available MRP solutions fall short in considering uncertainties and do not result in optimal solutions for modern enterprises. At C3 AI, we fundamentally reformulate the inventory management problem as a constrained stochastic optimization. We then propose a simulation-optimization framework that minimizes inventory and related costs while maintaining desired service levels. The framework's goal is to find the optimal reorder parameters that minimize costs subject to a pre-defined service-level constraint and all other real-world operational constraints. These optimal reorder parameters can be fed back into an MRP system to drive optimal order placement, or used to place optimal orders directly. This approach has proven successful in reducing inventory levels by 10-35 percent, resulting in hundreds of millions of dollars of economic benefit for major enterprises at a global scale.
Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks
Authors: Po Chen, Rujun Jiang, Peng Wang
Date: 2025-02-16 00:00:00

The optimization foundations of deep linear networks have received significant attention lately. However, due to the non-convexity and hierarchical structure, analyzing the regularized loss of deep linear networks remains a challenging task. In this work, we study the local geometric landscape of the regularized squared loss of deep linear networks, providing a deeper understanding of its optimization properties. Specifically, we characterize the critical point set and establish an error-bound property for all critical points under mild conditions. Notably, we identify the sufficient and necessary conditions under which the error bound holds. To support our theoretical findings, we conduct numerical experiments demonstrating that gradient descent exhibits linear convergence when optimizing the regularized loss of deep linear networks.
Convergence of Policy Mirror Descent Beyond Compatible Function Approximation
Authors: Uri Sherman, Tomer Koren, Yishay Mansour
Date: 2025-02-16 00:00:00

Modern policy optimization methods roughly follow the policy mirror descent (PMD) algorithmic template, for which there are by now numerous theoretical convergence results. However, most of these either target tabular environments, or can be applied effectively only when the class of policies being optimized over satisfies strong closure conditions, which is typically not the case when working with parametric policy classes in large-scale environments. In this work, we develop a theoretical framework for PMD for general policy classes where we replace the closure conditions with a strictly weaker variational gradient dominance assumption, and obtain upper bounds on the rate of convergence to the best-in-class policy. Our main result leverages a novel notion of smoothness with respect to a local norm induced by the occupancy measure of the current policy, and casts PMD as a particular instance of smooth non-convex optimization in non-Euclidean space.
Which Features are Best for Successor Features?
Authors: Yann Ollivier
Date: 2025-02-15 00:00:00
Tasks: Offline RL

In reinforcement learning, universal successor features (SFs) are a way to provide zero-shot adaptation to new tasks at test time: they provide optimal policies for all downstream reward functions lying in the linear span of a set of base features. But it is unclear what constitutes a good set of base features, that could be useful for a wide set of downstream tasks beyond their linear span. Laplacian eigenfunctions (the eigenfunctions of $\Delta+\Delta^\ast$ with $\Delta$ the Laplacian operator of some reference policy and $\Delta^\ast$ that of the time-reversed dynamics) have been argued to play a role, and offer good empirical performance. Here, for the first time, we identify the optimal base features based on an objective criterion of downstream performance, in a non-tautological way without assuming the downstream tasks are linear in the features. We do this for three generic classes of downstream tasks: reaching a random goal state, dense random Gaussian rewards, and random ``scattered'' sparse rewards. The features yielding optimal expected downstream performance turn out to be the \emph{same} for these three task families. They do not coincide with Laplacian eigenfunctions in general, though they can be expressed from $\Delta$: in the simplest case (deterministic environment and decay factor $\gamma$ close to $1$), they are the eigenfunctions of $\Delta^{-1}+(\Delta^{-1})^\ast$. We obtain these results under an assumption of large behavior cloning regularization with respect to a reference policy, a setting often used for offline RL. Along the way, we get new insights into KL-regularized\option{natural} policy gradient, and into the lack of SF information in the norm of Bellman gaps.
Learning Fair Policies for Infectious Diseases Mitigation using Path Integral Control
Authors: Zhuangzhuang Jia, Hyuk Park, Gökçe Dayanıklı, Grani A. Hanasusanto
Date: 2025-02-14 00:00:00
Tasks: Decision Making, Decision Making Under Uncertainty, Fairness, Sequential Decision Making

Infectious diseases pose major public health challenges to society, highlighting the importance of designing effective policies to reduce economic loss and mortality. In this paper, we propose a framework for sequential decision-making under uncertainty to design fairness-aware disease mitigation policies that incorporate various measures of unfairness. Specifically, our approach learns equitable vaccination and lockdown strategies based on a stochastic multi-group SIR model. To address the challenges of solving the resulting sequential decision-making problem, we adopt the path integral control algorithm as an efficient solution scheme. Through a case study, we demonstrate that our approach effectively improves fairness compared to conventional methods and provides valuable insights for policymakers.
A statistical theory of overfitting for imbalanced classification
Authors: Jingyang Lyu, Kangjie Zhou, Yiqiao Zhong
Date: 2025-02-17 00:00:00
Tasks: Classification, imbalanced classification

Classification with imbalanced data is a common challenge in data analysis, where certain classes (minority classes) account for a small fraction of the training data compared with other classes (majority classes). Classical statistical theory based on large-sample asymptotics and finite-sample corrections is often ineffective for high-dimensional data, leaving many overfitting phenomena in empirical machine learning unexplained. In this paper, we develop a statistical theory for high-dimensional imbalanced classification by investigating support vector machines and logistic regression. We find that dimensionality induces truncation or skewing effects on the logit distribution, which we characterize via a variational problem under high-dimensional asymptotics. In particular, for linearly separable data generated from a two-component Gaussian mixture model, the logits from each class follow a normal distribution $\mathsf{N}(0,1)$ on the testing set, but asymptotically follow a rectified normal distribution $\max\{\kappa, \mathsf{N}(0,1)\}$ on the training set -- which is a pervasive phenomenon we verified on tabular data, image data, and text data. This phenomenon explains why the minority class is more severely affected by overfitting. Further, we show that margin rebalancing, which incorporates class sizes into the loss function, is crucial for mitigating the accuracy drop for the minority class. Our theory also provides insights into the effects of overfitting on calibration and other uncertain quantification measures.