pwc-archive/papers-with-abstracts huggingface dataset:
Asymptotic Analysis of One-bit Quantized Box-Constrained Precoding in Large-Scale Multi-User Systems
Authors: Xiuxiu Ma, Abla Kammoun, Mohamed-Slim Alouini, Tareq Y. Al-Naffouri
Date: 2025-02-05 00:00:00
Tasks: Quantization

This paper addresses the design of multi-antenna precoding strategies, considering hardware limitations such as low-resolution digital-to-analog converters (DACs), which necessitate the quantization of transmitted signals. The typical approach starts with optimizing a precoder, followed by a quantization step to meet hardware requirements. This study analyzes the performance of a quantization scheme applied to the box-constrained regularized zero-forcing (RZF) precoder in the asymptotic regime, where the number of antennas and users grows proportionally. The box constraint, initially designed to cope with low-dynamic range amplifiers, is used here to control quantization noise rather than for amplifier compatibility. A significant challenge in analyzing the quantized precoder is that the input to the quantization operation does not follow a Gaussian distribution, making traditional methods such as Bussgang's decomposition unsuitable. To overcome this, the paper extends the Gordon's inequality and introduces a novel Gaussian Min-Max Theorem to model the distribution of the channel-distorted precoded signal. The analysis derives the tight lower bound for the signal-to-distortion-plus-noise ratio (SDNR) and the bit error rate (BER), showing that optimal tuning of the amplitude constraint improves performance.
A Comprehensive Survey on Feature Extraction Techniques Using I/Q Imbalance in RFFI
Authors: Muhammad Aqib Khan, Muhammad Usman Siddiqui
Date: 2025-02-04 00:00:00

The proliferation of Internet of Things (IoT) devices has increased the need for secure authentication. While traditional encryption-based solutions can be robust, they often impose high computational and energy overhead on resource-limited IoT nodes. As an alternative, radio frequency fingerprint identification (RFFI) leverages hardware-induced imperfections-such as Inphase/Quadrature (I/Q) imbalance-in Radio Frequency (RF) front-end components as unique identifiers that are inherently difficult to clone or spoof. Despite recent advances, significant challenges remain in standardizing feature extraction methods, maintaining high accuracy across diverse environments, and efficiently handling large-scale IoT deployments. This paper addresses these gaps by providing a comprehensive review of feature extraction techniques that utilize I/Q imbalance for RFFI. We also discuss other hardware-based RF fingerprinting sources, including power amplifier nonlinearity and oscillator imperfections, and examine modern machine learning (ML) and deep learning (DL) approaches that enhance device identification performance.
Gaussian Process Regression for Inverse Problems in Linear PDEs
Authors: Xin Li, Markus Lange-Hegermann, Bogdan Raiţă
Date: 2025-02-06 00:00:00
Tasks: Computational Efficiency, Gaussian Processes, regression

This paper introduces a computationally efficient algorithm in system theory for solving inverse problems governed by linear partial differential equations (PDEs). We model solutions of linear PDEs using Gaussian processes with priors defined based on advanced commutative algebra and algebraic analysis. The implementation of these priors is algorithmic and achieved using the Macaulay2 computer algebra software. An example application includes identifying the wave speed from noisy data for classical wave equations, which are widely used in physics. The method achieves high accuracy while enhancing computational efficiency.
Consistency of augmentation graph and network approximability in contrastive learning
Authors: Chenghui Li, A. Martina Neuman
Date: 2025-02-06 00:00:00
Tasks: Contrastive Learning, Data Augmentation

Contrastive learning leverages data augmentation to develop feature representation without relying on large labeled datasets. However, despite its empirical success, the theoretical foundations of contrastive learning remain incomplete, with many essential guarantees left unaddressed, particularly the realizability assumption concerning neural approximability of an optimal spectral contrastive loss solution. In this work, we overcome these limitations by analyzing the pointwise and spectral consistency of the augmentation graph Laplacian. We establish that, under specific conditions for data generation and graph connectivity, as the augmented dataset size increases, the augmentation graph Laplacian converges to a weighted Laplace-Beltrami operator on the natural data manifold. These consistency results ensure that the graph Laplacian spectrum effectively captures the manifold geometry. Consequently, they give way to a robust framework for establishing neural approximability, directly resolving the realizability assumption in a current paradigm.
Distribution learning via neural differential equations: minimal energy regularization and approximation theory
Authors: Youssef Marzouk, Zhi Ren, Jakob Zech
Date: 2025-02-06 00:00:00
Tasks: Bayesian Inference, Density Estimation

Neural ordinary differential equations (ODEs) provide expressive representations of invertible transport maps that can be used to approximate complex probability distributions, e.g., for generative modeling, density estimation, and Bayesian inference. We show that for a large class of transport maps $T$, there exists a time-dependent ODE velocity field realizing a straight-line interpolation $(1-t)x + tT(x)$, $t \in [0,1]$, of the displacement induced by the map. Moreover, we show that such velocity fields are minimizers of a training objective containing a specific minimum-energy regularization. We then derive explicit upper bounds for the $C^k$ norm of the velocity field that are polynomial in the $C^k$ norm of the corresponding transport map $T$; in the case of triangular (Knothe--Rosenblatt) maps, we also show that these bounds are polynomial in the $C^k$ norms of the associated source and target densities. Combining these results with stability arguments for distribution approximation via ODEs, we show that Wasserstein or Kullback--Leibler approximation of the target distribution to any desired accuracy $\epsilon > 0$ can be achieved by a deep neural network representation of the velocity field whose size is bounded explicitly in terms of $\epsilon$, the dimension, and the smoothness of the source and target densities. The same neural network ansatz yields guarantees on the value of the regularized training objective.
Signature Reconstruction from Randomized Signatures
Authors: Mie Glückstad, Nicola Muca Cirone, Josef Teichmann
Date: 2025-02-05 00:00:00

Controlled ordinary differential equations driven by continuous bounded variation curves can be considered a continuous time analogue of recurrent neural networks for the construction of expressive features of the input curves. We ask up to which extent well known signature features of such curves can be reconstructed from controlled ordinary differential equations with (untrained) random vector fields. The answer turns out to be algebraically involved, but essentially the number of signature features, which can be reconstructed from the non-linear flow of the controlled ordinary differential equation, is exponential in its hidden dimension, when the vector fields are chosen to be neural with depth two. Moreover, we characterize a general linear independence condition on arbitrary vector fields, under which the signature features up to some fixed order can always be reconstructed. Algebraically speaking this complements in a quantitative manner several well known results from the theory of Lie algebras of vector fields and puts them in a context of machine learning.
MXMap: A Multivariate Cross Mapping Framework for Causal Discovery in Dynamical Systems
Authors: Elise Zhang, François Mirallès, Raphaël Rousseau-Rizzi, Arnaud Zinflou, Di wu, Benoit Boulet
Date: 2025-02-06 00:00:00
Tasks: Causal Discovery

Convergent Cross Mapping (CCM) is a powerful method for detecting causality in coupled nonlinear dynamical systems, providing a model-free approach to capture dynamic causal interactions. Partial Cross Mapping (PCM) was introduced as an extension of CCM to address indirect causality in three-variable systems by comparing cross-mapping quality between direct cause-effect mapping and indirect mapping through an intermediate conditioning variable. However, PCM remains limited to univariate delay embeddings in its cross-mapping processes. In this work, we extend PCM to the multivariate setting, introducing multiPCM, which leverages multivariate embeddings to more effectively distinguish indirect causal relationships. We further propose a multivariate cross-mapping framework (MXMap) for causal discovery in dynamical systems. This two-phase framework combines (1) pairwise CCM tests to establish an initial causal graph and (2) multiPCM to refine the graph by pruning indirect causal connections. Through experiments on simulated data and the ERA5 Reanalysis weather dataset, we demonstrate the effectiveness of MXMap. Additionally, MXMap is compared against several baseline methods, showing advantages in accuracy and causal graph refinement.
Online Learning Algorithms in Hilbert Spaces with $β-$ and $φ-$Mixing Sequences
Authors: Priyanka Roy, Susanne Saminger-Platz
Date: 2025-02-05 00:00:00

In this paper, we study an online algorithm in a reproducing kernel Hilbert spaces (RKHS) based on a class of dependent processes, called the mixing process. For such a process, the degree of dependence is measured by various mixing coefficients. As a representative example, we analyze a strictly stationary Markov chain, where the dependence structure is characterized by the \(\beta-\) and \(\phi-\)mixing coefficients. For these dependent samples, we derive nearly optimal convergence rates. Our findings extend existing error bounds for i.i.d. observations, demonstrating that the i.i.d. case is a special instance of our framework. Moreover, we explicitly account for an additional factor introduced by the dependence structure in the Markov chain.
Preference-aware compensation policies for crowdsourced on-demand services
Authors: Georgina Nouli, Axel Parmentier, Maximilian Schiffer
Date: 2025-02-07 00:00:00

Crowdsourced on-demand services offer benefits such as reduced costs, faster service fulfillment times, greater adaptability, and contributions to sustainable urban transportation in on-demand delivery contexts. However, the success of an on-demand platform that utilizes crowdsourcing relies on finding a compensation policy that strikes a balance between creating attractive offers for gig workers and ensuring profitability. In this work, we examine a dynamic pricing problem for an on-demand platform that sets request-specific compensation of gig workers in a discrete-time framework, where requests and workers arrive stochastically. The operator's goal is to determine a compensation policy that maximizes the total expected reward over the time horizon. Our approach introduces compensation strategies that explicitly account for gig worker request preferences. To achieve this, we employ the Multinomial Logit model to represent the acceptance probabilities of gig workers, and, as a result, derive an analytical solution that utilizes post-decision states. Subsequently, we integrate this solution into an approximate dynamic programming algorithm. We compare our algorithm against benchmark algorithms, including formula-based policies and an upper bound provided by the full information linear programming solution. Our algorithm demonstrates consistent performance across diverse settings, achieving improvements of at least 2.5-7.5% in homogeneous gig worker populations and 9% in heterogeneous populations over benchmarks, based on fully synthetic data. For real-world data, it surpasses benchmarks by 8% in weak and 20% in strong location preference scenarios.
Coherent Local Explanations for Mathematical Optimization
Authors: Daan Otto, Jannis Kurtz, S. Ilker Birbil
Date: 2025-02-07 00:00:00
Tasks: Explainable artificial intelligence

The surge of explainable artificial intelligence methods seeks to enhance transparency and explainability in machine learning models. At the same time, there is a growing demand for explaining decisions taken through complex algorithms used in mathematical optimization. However, current explanation methods do not take into account the structure of the underlying optimization problem, leading to unreliable outcomes. In response to this need, we introduce Coherent Local Explanations for Mathematical Optimization (CLEMO). CLEMO provides explanations for multiple components of optimization models, the objective value and decision variables, which are coherent with the underlying model structure. Our sampling-based procedure can provide explanations for the behavior of exact and heuristic solution algorithms. The effectiveness of CLEMO is illustrated by experiments for the shortest path problem, the knapsack problem, and the vehicle routing problem.
A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees
Authors: Yuhao Zhou, Jintao Xu, Chenglong Bao, Chao Ding, Jun Zhu
Date: 2025-02-07 00:00:00

We consider the problem of finding an $\epsilon$-stationary point of a nonconvex function with a Lipschitz continuous Hessian and propose a quadratic regularized Newton method incorporating a new class of regularizers constructed from the current and previous gradients. The method leverages a recently developed linear conjugate gradient approach with a negative curvature monitor to solve the regularized Newton equation. Notably, our algorithm is adaptive, requiring no prior knowledge of the Lipschitz constant of the Hessian, and achieves a global complexity of $O(\epsilon^{-\frac{3}{2}}) + \tilde O(1)$ in terms of the second-order oracle calls, and $\tilde O(\epsilon^{-\frac{7}{4}})$ for Hessian-vector products, respectively. Moreover, when the iterates converge to a point where the Hessian is positive definite, the method exhibits quadratic local convergence. Preliminary numerical results illustrate the competitiveness of our algorithm.
Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data
Authors: Chen Fan, Mark Schmidt, Christos Thrampoulidis
Date: 2025-02-07 00:00:00

Different gradient-based methods for optimizing overparameterized models can all achieve zero training error yet converge to distinctly different solutions inducing different generalization properties. We provide the first complete characterization of implicit optimization bias for p-norm normalized steepest descent (NSD) and momentum steepest descent (NMD) algorithms in multi-class linear classification with cross-entropy loss. Our key theoretical contribution is proving that these algorithms converge to solutions maximizing the margin with respect to the classifier matrix's p-norm, with established convergence rates. These results encompass important special cases including Spectral Descent and Muon, which we show converge to max-margin solutions with respect to the spectral norm. A key insight of our contribution is that the analysis of general entry-wise and Schatten p-norms can be reduced to the analysis of NSD/NMD with max-norm by exploiting a natural ordering property between all p-norms relative to the max-norm and its dual sum-norm. For the specific case of descent with respect to the max-norm, we further extend our analysis to include preconditioning, showing that Adam converges to the matrix's max-norm solution. Our results demonstrate that the multi-class linear setting, which is inherently richer than the binary counterpart, provides the most transparent framework for studying implicit biases of matrix-parameter optimization algorithms.
Statistical guarantees for continuous-time policy evaluation: blessing of ellipticity and new tradeoffs
Authors: Wenlong Mou
Date: 2025-02-06 00:00:00

We study the estimation of the value function for continuous-time Markov diffusion processes using a single, discretely observed ergodic trajectory. Our work provides non-asymptotic statistical guarantees for the least-squares temporal-difference (LSTD) method, with performance measured in the first-order Sobolev norm. Specifically, the estimator attains an $O(1 / \sqrt{T})$ convergence rate when using a trajectory of length $T$; notably, this rate is achieved as long as $T$ scales nearly linearly with both the mixing time of the diffusion and the number of basis functions employed. A key insight of our approach is that the ellipticity inherent in the diffusion process ensures robust performance even as the effective horizon diverges to infinity. Moreover, we demonstrate that the Markovian component of the statistical error can be controlled by the approximation error, while the martingale component grows at a slower rate relative to the number of basis functions. By carefully balancing these two sources of error, our analysis reveals novel trade-offs between approximation and statistical errors.
Blackwell's Approachability with Approximation Algorithms
Authors: Dan Garber, Mhna Massalha
Date: 2025-02-06 00:00:00

We revisit Blackwell's celebrated approachability problem which considers a repeated vector-valued game between a player and an adversary. Motivated by settings in which the action set of the player or adversary (or both) is difficult to optimize over, for instance when it corresponds to the set of all possible solutions to some NP-Hard optimization problem, we ask what can the player guarantee \textit{efficiently}, when only having access to these sets via approximation algorithms with ratios $\alpha_{\mX} \geq 1$ and $ 1 \geq \alpha_{\mY} > 0$, respectively. Assuming the player has monotone preferences, in the sense that he does not prefer a vector-valued loss $\ell_1$ over $\ell_2$ if $\ell_2 \leq \ell_1$, we establish that given a Blackwell instance with an approachable target set $S$, the downward closure of the appropriately-scaled set $\alpha_{\mX}\alpha_{\mY}^{-1}S$ is \textit{efficiently} approachable with optimal rate. In case only the player's or adversary's set is equipped with an approximation algorithm, we give simpler and more efficient algorithms.
PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport
Authors: Di wu, Ling Liang, Haizhao Yang
Date: 2025-02-06 00:00:00

Optimal transport (OT) is a critical problem in optimization and machine learning, where accuracy and efficiency are paramount. Although entropic regularization and the Sinkhorn algorithm improve scalability, they frequently encounter numerical instability and slow convergence, especially when the regularization parameter is small. In this work, we introduce Proximal Iterations with Sparse Newton and Sinkhorn methods (PINS) to efficiently compute highly accurate solutions for large-scale OT problems. A reduced computational complexity through overall sparsity and global convergence are guaranteed by rigorous theoretical analysis. Our approach offers three key advantages: it achieves accuracy comparable to exact solutions, progressively accelerates each iteration for greater efficiency, and enhances robustness by reducing sensitivity to regularization parameters. Extensive experiments confirm these advantages, demonstrating superior performance compared to related methods.
First-ish Order Methods: Hessian-aware Scalings of Gradient Descent
Authors: Oscar Smee, Fred Roosta, Stephen J. Wright
Date: 2025-02-06 00:00:00
Tasks: valid

Gradient descent is the primary workhorse for optimizing large-scale problems in machine learning. However, its performance is highly sensitive to the choice of the learning rate. A key limitation of gradient descent is its lack of natural scaling, which often necessitates expensive line searches or heuristic tuning to determine an appropriate step size. In this paper, we address this limitation by incorporating Hessian information to scale the gradient direction. By accounting for the curvature of the function along the gradient, our adaptive, Hessian-aware scaling method ensures a local unit step size guarantee, even in nonconvex settings. Near a local minimum that satisfies the second-order sufficient conditions, our approach achieves linear convergence with a unit step size. We show that our method converges globally under a significantly weaker version of the standard Lipschitz gradient smoothness assumption. Even when Hessian information is inexact, the local unit step size guarantee and global convergence properties remain valid under mild conditions. Finally, we validate our theoretical results empirically on a range of convex and nonconvex machine learning tasks, showcasing the effectiveness of the approach.
The Performance Of The Unadjusted Langevin Algorithm Without Smoothness Assumptions
Authors: Tim Johnston, Iosif Lytras, Nikolaos Makras, Sotirios Sabanis
Date: 2025-02-05 00:00:00

In this article, we study the problem of sampling from distributions whose densities are not necessarily smooth nor log-concave. We propose a simple Langevin-based algorithm that does not rely on popular but computationally challenging techniques, such as the Moreau Yosida envelope or Gaussian smoothing. We derive non-asymptotic guarantees for the convergence of the algorithm to the target distribution in Wasserstein distances. Non asymptotic bounds are also provided for the performance of the algorithm as an optimizer, specifically for the solution of associated excess risk optimization problems.
An analysis of optimization problems involving ReLU neural networks
Authors: Christoph Plate, Mirko Hahn, Alexander Klimek, Caroline Ganzer, Kai Sundmacher, Sebastian Sager
Date: 2025-02-05 00:00:00

Solving mixed-integer optimization problems with embedded neural networks with ReLU activation functions is challenging. Big-M coefficients that arise in relaxing binary decisions related to these functions grow exponentially with the number of layers. We survey and propose different approaches to analyze and improve the run time behavior of mixed-integer programming solvers in this context. Among them are clipped variants and regularization techniques applied during training as well as optimization-based bound tightening and a novel scaling for given ReLU networks. We numerically compare these approaches for three benchmark problems from the literature. We use the number of linear regions, the percentage of stable neurons, and overall computational effort as indicators. As a major takeaway we observe and quantify a trade-off between the often desired redundancy of neural network models versus the computational costs for solving related optimization problems.
Early Stopping in Contextual Bandits and Inferences
Authors: Zihan Cui
Date: 2025-02-05 00:00:00
Tasks: Decision Making, Multi-Armed Bandits

Bandit algorithms sequentially accumulate data using adaptive sampling policies, offering flexibility for real-world applications. However, excessive sampling can be costly, motivating the devolopment of early stopping methods and reliable post-experiment conditional inferences. This paper studies early stopping methods in linear contextual bandits, including both pre-determined and online stopping rules, to minimize in-experiment regrets while accounting for sampling costs. We propose stopping rules based on the Opportunity Cost and Threshold Method, utilizing the variances of unbiased or consistent online estimators to quantify the upper regret bounds of learned optimal policy. The study focuses on batched settings for stability, selecting a weighed combination of batched estimators as the online estimator and deriving its asymptotic distribution. Online statistical inferences are performed based on the selected estimator, conditional on the realized stopping time. Our proposed method provides a systematic approach to minimize in-experiment regret and conduct robust post-experiment inferences, facilitating decision-making in future applications.