跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1205新增论文
+949其中 AI 相关
+153已有论文修订
+59新增 AI 导读

arXiv 最近完成扫描:2026-11-18 04:28 · 全站最近入库:2026-11-18 12:34各信源进度 →

统计口径与数据新鲜度

统计 2026-11-17 13:14 — 2026-11-18 13:14(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-18 12:34库内论文最新更新时间:2026-11-18 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

26,054 已收录论文21,703 AI 相关7,828 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 402 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
新论文 · v1arXiv:2611.23221

An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization

Zhaosong Lu, Yifeng Xiao

原文摘要

In this paper, we study a class of constrained convex finite-sum optimization problems. In many practical applications, all or some of the constraints are hard constraints that represent imperative requirements. Consequently, any desirable approximate solution must (nearly) satisfy these constraints. Motivated by this, we focus on computing an $ε$-$surely\ feasible\ stochastic\ optimal$ ($ε$-SFSO) solution, in which the constraint violation is deterministically bounded by $ε$, and the expected optimality gap is at most $ε$. While a recently proposed stochastic variance-reduced first-order penalty method can compute an $ε$-SFSO solution, there remains a significant gap between its first-order oracle complexity for computing an $ε$-SFSO solution and that for computing an $ε$-$expected\ feasible\ stochastic\ optimal$ solution, where both the expected constraint violation and the expected optimality gap are bounded by $ε$. To narrow this gap, we propose an inexact stochastic variance-reduced gradient (SVRG) method that significantly improves the previously best-known first-order oracle complexity for computing an $ε$-SFSO solution. Furthermore, when the objective consists of a single function, the proposed method reduces to a novel deterministic first-order method for solving standard convex conic optimization. It achieves a significantly lower gradient evaluation complexity with respect to the objective function compared to existing methods, and can outperform them when computing constraint gradients and projections onto the associated cone is cheaper than evaluating the objective gradient. Preliminary numerical results are presented to illustrate the performance of the proposed method.

math.OC · cs.LG

版本更新 · v2arXiv:2506.20630

First-order methods for stochastic and finite-sum convex optimization with deterministic constraints

Zhaosong Lu, Yifeng Xiao

原文摘要

In this paper, we study a class of stochastic and finite-sum convex optimization problems with deterministic constraints. Existing methods typically aim to find an $ε$-$expected\ feasible\ stochastic\ optimal$ solution, in which both the expected constraint violation and the expected optimality gap are within a prescribed tolerance $ε$. However, in many practical applications, constraints must be nearly satisfied with certainty, rendering such solutions potentially unsuitable due to the risk of substantial violations. To address this issue, we propose stochastic first-order methods for finding an $ε$-$surely\ feasible\ stochastic\ optimal$ ($ε$-SFSO) solution, where the constraint violation is deterministically bounded by $ε$ and the expected optimality gap is at most $ε$. Our methods apply an accelerated stochastic gradient (ASG) scheme or a modified variance-reduced ASG scheme $only\ once$ to a sequence of quadratic penalty subproblems with appropriately chosen penalty parameters. We establish first-order oracle complexity bounds for the proposed methods in computing an $ε$-SFSO solution. Preliminary numerical results are presented to illustrate the performance of the proposed methods.

math.OC · cs.LG · math.NA

新论文 · v1arXiv:2611.22557

Balancing Exploration and Exploitation in Constrained Combinatorial Optimization with U(1)-Symmetric Tensor Trains

Sergei Iudin, Mikhail Podobrii, Dmitry Zheltkov, Stanislav Moiseev

原文摘要

Tensor Train (TT) decomposition has emerged as a powerful tool for mitigating the curse of dimensionality in a variety of machine learning and combinatorial optimization tasks. Recent advances show that TT-based generative models can efficiently represent and explore high-dimensional discrete spaces, even when the cost function structure is unknown. However, incorporating hard linear constraints into TT-based optimization remains challenging, as existing interpolation and sampling approaches often fail when feasible points are rare. In this work, we develop a general TT-based framework for constrained combinatorial optimization built upon U(1)-symmetric tensor networks. Our method introduces an expressibility-enhancement mechanism for constructing sparse symmetric tensors and a graph-based diversity measure that guides sample selection during training. On assignment benchmarks, expressibility enhancement and diversity-aware selection improve mean solution quality over their respective baselines. The assignment-selected diversifying strategy also extends to nonpolynomial Set Partitioning, with larger relative gains observed in the higher-tensor-rank data families. Separate runtime benchmarks show substantial speedups over ConstrainTNet and PROTES on non-degenerate assignment workloads; comparisons with simulated annealing depend on constraint information and computational budget, but, overall, support the practicality of the current implementation.

math.OC · cs.LG

新论文 · v1arXiv:2611.22518

The Multivariate Feedback Particle Filter for State-dependent Multiplicative Noises and Its Application to Attitude and Pose Estimations

Jingyao You, Xue Luo

原文摘要

Nonlinear filtering with state-dependent multiplicative measurement noise poses a notable challenge for spacecraft attitude determination and robotic pose estimation. This work develops the FPF-DM, a decomposition scheme for feedback particle filters tailored to this family of filtering problems. Extending prior decomposition techniques for additive noise and polynomial measurement models, the proposed method resolves the key difficulty that state-dependent multiplicative noise breaks the polynomial assumption and prevents Hermite spectral backward recursion for the weighted Poisson's equation. By measure transformation and importance reweighting, we incorporate the inverse measurement covariance into particle weights and rescale the feedback gain to restore the polynomial-form Poisson's equation, with the decomposition generalized to non-uniformly weighted mixtures for closed-form gain computation. This general FPF-DM is instantiated on quaternion and dual-quaternion manifolds for attitude tracking and point-cloud registration. Simulations on 4D attitude tracking and 8D point-cloud registration verify that the instantiated filters using only 10 particles achieve superior accuracy and computational performance relative to baseline filters.

cs.RO · math.OC

版本更新 · v2arXiv:2610.10666

Explaining the Saliency Map Sparsity of Adversarially-Trained Neural Networks

Yannick Lunk, Atell Yehor Krasnopolsky, Damien Garreau, Leon Bungert

原文摘要

Understanding why deep neural networks make a given prediction is of great importance for their safe deployment. In computer vision, saliency maps, which highlight the image region most influential for a prediction, remain a widely-used form of explanation. An empirical observation is the apparent sparsity of gradient saliency maps of adversarially-trained neural networks. In this paper, we propose a theoretical explanation of this phenomenon for two-layer ReLU networks. We build on the established equivalence of adversarial training to the minimization of the empirical risk with weight-decay penalization and an added adversarial total variation term -- valid for certain loss functions. As the number of data points and neurons grows and the regularization parameters are sent to zero at appropriate rates, we prove that minimizers converge to a Bayes classifier with minimal gradient and Barron norm. Sparsity appears since for adversarial training with $\ell_\infty$-attacks the gradient norm is anisotropic and favors axis-aligned / sparse gradients. We illustrate our theoretical findings experimentally by evaluating the gradient $\ell_1$-norm and thresholded sparsity of naturally versus adversarially trained models.

cs.LG · math.OC · stat.ML

新论文 · v1arXiv:2611.21432

Just sort it! A note on the LP behind rank-one anti-loop edits

Matteo Fischetti

原文摘要

Weight-space programming removes the thinking loops of a small reasoning model by a rank-one edit W' = W + u v^T of an MLP output matrix, where u is a loop direction and v is the solution of a sparse Linear Program (LP) over the neuron activations. We investigate whether the LP is needed. We replace it by a sort: we take the 8 neurons whose activation has the smallest coefficient of variation, and give them equal shares of the push that the LP solution realizes. On Qwen3.5-0.8B the sorted edit scores 67.0% on 1000 problems (MATH-500 and GSM8K) against 67.4% for the LP edit and 9.5% for the unedited model; the paired difference is -0.4 points, with 95% confidence interval [-2.9, +2.1], inside a non-inferiority margin of 5 points declared before the runs. On three further sampling seeds the difference is -0.6 points, interval [-2.0, +0.8], and -0.8 points, interval [-2.3, +0.6], when the dose is set without the LP. The sort does not solve the LP, but the neurons it shares with the LP solution carry most of its mean push. The outcome is that, on this model, the edit acts as a nearly constant bias along u.

cs.LG · cs.CL · math.OC

版本更新 · v3arXiv:2412.14291

Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes

Guanghui Lan, Tianjiao Li, Yangyang Xu

原文摘要

We present a novel class of projected gradient (PG) methods for minimizing a smooth but not necessarily convex function over a convex compact set. We first provide a novel analysis of the constant-stepsize PG method, achieving a unified iteration complexity for finding an approximate stationary point for convex and nonconvex problems. We then develop an "auto-conditioned" projected gradient (AC-PG) variant that achieves the same iteration complexity without requiring the input of the Lipschitz constant of the gradient or any line search procedure. The key idea is to estimate the Lipschitz constant using first-order information gathered from the previous iterations, and to show that the error caused by underestimating the Lipschitz constant can be properly controlled. We then generalize the PG methods to the stochastic setting, by proposing a stochastic projected gradient (SPG) method and a variance-reduced stochastic gradient (VR-SPG) method, achieving new unified complexity bounds in different oracle settings. We also present auto-conditioned stepsize policies for both stochastic PG methods and establish comparable convergence guarantees.

math.OC · cs.LG · stat.ML

新论文 · v1arXiv:2611.21404

Efficient Modeling of Multi-Agent Systems via Structure-Aware Physics-Informed Learning

Yulun Wu, Nicola Bastianello, Karl Henrik Johansson, Matthieu Barreau

原文摘要

Modeling large multi-agent systems poses challenges for trajectory inference and parameter identification, as network size and coupling increase computational demands and partial observations require reconstructing unobserved states. We propose MAS-PINN, a neural-network architecture with a tailored training algorithm for a physics-informed learning framework that leverages the network topology and the agents' similarity to reduce computational and memory costs of simulating and identifying multi-agent systems. Its architecture represents agent trajectories through shared temporal features and agent-specific coefficients. Training alternates between learning features, fitting coupled trajectories, and estimating physical parameters. A matrix-free update exploits local interactions to fit trajectories without forming large global matrices. Experiments on Lorenz rings, Lotka--Volterra networks, and Rössler oscillators show improved trajectory and parameter accuracy over baselines, including inference in large systems and identification under partial observations or unknown topology, alongside substantial computational savings in coefficient fitting.

cs.LG · math.OC

新论文 · v1arXiv:2611.21256

Odd faces as a parameter for maximum independent set in embedded graphs

Samuel Fiorini, Stefan Kober, Caleb McFarland

原文摘要

We give a polynomial-time algorithm for finding a maximum weight independent set in a graph embedded in a surface of bounded genus and with a bounded number of vertex-disjoint odd faces. In particular, we obtain an algorithm for graphs with an even-faced embedding in a torus and for planar graphs with a bounded number of odd faces, answering a question of Thomassé (2018) and a question of Choi, Gorsky, Kim, McFarland, and Wiederrecht (2025) respectively. We reduce the original problem to finding a minimum cost non-negative integer circulation with homology constraints in the dual of a certain double cover of the original graph.

math.CO · cs.DM · cs.DS · math.OC

版本更新 · v2arXiv:2605.10668

A Spectral Framework for Closed-Form Relative Density Estimation

Francis Bach

原文摘要

We propose a closed-form spectral framework for relative log-density estimation in linearly parameterized probabilistic models, including unnormalized and conditional models. This is achieved by representing the Kullback-Leibler (KL) divergence as an integral of weighted chi-squared divergences, converting KL estimation into a family of least-squares problems. We derive an explicit spectral formula based only on first- and second-order feature moments, yielding closed-form estimators of both divergences and log-density potentials for fixed features. The framework extends to a broad class of $f$-divergences and can be combined with kernelization or feature learning with neural networks (with then only a closed form for the last layer). We prove convergence guarantees for the resulting estimators and empirically compare them on synthetic data with optimization-based variational formulations, including logistic and softmax regression for normalized conditional models.

cs.LG · math.OC · math.ST

新论文 · v1arXiv:2611.20926

Advancing Cognitive Pairwise Comparisons for Human-Centric Artificial Intelligence and Data Science: A Human-in-the-Loop Framework

Kevin Kam Fung Yuen

原文摘要

Human-centric artificial intelligence and data science (HCAD) systems increasingly involve human-in-the-loop (HITL) interventions to overcome the limitations of fully automated machine learning algorithms, such as automation bias and the inability to incorporate tacit domain knowledge, and continuously improve predictive performance. Data transformations, feature selection, feature weighting, and model selection usually require laborious human involvement across iterations of artificial intelligence and data science (AI&DS) pipelines, making development a challenging and time-consuming process. The Cognitive Pairwise Comparison (CPC) framework is proposed as a human-centric methodology to elicit preferences and priorities in a structured format. To establish essential facets of human-centricity, this research advances the CPC methodology so that user preference elicitation can be systematically quantified in these challenging AI&DS tasks. To demonstrate the usability and validity of these facets, this study presents several applications within movie recommender systems using the MovieLens dataset. It exemplifies how the extended CPC framework can facilitate interactions between human judgments and data across supervised learning, dimensionality reduction, and unsupervised learning algorithms.

cs.AI · cs.HC · math.OC

版本更新 · v2arXiv:2607.11603

WarpMPC: Large-Batch MPC on GPU via ADMM with Unrolled $LDL^\top$ Factorization

Henrik Hose, Se Hwan Jeon, Charles Khazoom, Sangbae Kim, Sebastian Trimpe

原文摘要

This paper introduces numerical optimizations for maximizing throughput on GPU when solving large batches (10,000 to over 100,000) of sequential quadratic programming (SQP) iterations, where all problems have the same structure. The optimizations are implemented in a toolbox WarpMPC for model-predictive control (MPC) in JAX and Warp. Based on the insight that all MPC problem instances in a batch share the same sparsity in time, cost, and constraints, we propose unrolling sparse linear factorizations and solves, which dominate alternating direction method of multipliers (ADMM) solver runtime. We avoid memory access bottlenecks and wasting computations via optimized memory layout, padding-reducing segmentation of the unrolled factorization, and dependency level scheduled backsolves, additionally accelerating sensitivity computation. We achieve throughputs of 8,000 to 250,000 SQP iterations per second on nonlinear cartpole, quadrotor, and humanoid robot benchmarks, outperforming baselines by 3$\times$ to 25$\times$. We illustrate practical usefulness by synthesizing a dataset and training a neural network approximation of an MPC in under 5 minutes that stabilizes a nano quadrotor in hardware experiments.

cs.RO · eess.SY · math.OC

新论文 · v1arXiv:2611.20797

Correspondence-Free Camera Pose Estimation by Matching Moments

Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome

原文摘要

The blind perspective-$n$-point (PnP) problem is to estimate the pose of a calibrated camera from 2D and 3D point sets with unknown correspondences. We show that, for complete, noiseless observations, fourteen permutation-invariant image moments up to order four identify a fixed camera pose for almost every 3D point set containing at least twenty points. Our learning-free method, MomentPnP, matches these moments between the observed 2D points and the projected 3D points to initialize a camera pose without correspondences and refines the pose and correspondence weights using expectation--maximization. Across the test sets of three benchmarks, our method reduces median rotation error by $5$--$170\times$ relative to the best learned baseline, both with and without outliers. We recover accurate poses even with as many outliers as inliers. On dense ETH3D scans, pose accuracy improves as the point sets grow, even as individual correspondences become harder to resolve.

cs.CV · cs.LG · cs.RO · eess.IV · math.OC

版本更新 · v2arXiv:2609.32083

When Should a Human Take Back Control? Optimal Delegation under Turbulent AI Risk

Haoze Yan, Julien Roze, Ved Upadhyay, Unal Tatar, Thibaut Mastrolia

原文摘要

When should a human take control from an autonomous AI agent, how much checking is worthwhile, and when should autonomy resume? These decisions become harder when incidents cluster and recent errors signal elevated risk. Exploratory analyses of AgentLogs coding-agent traces and ODCV-Bench task runs show higher held-out log likelihood for Hawkes incident-history models than matched no-history baselines, with positive gains whose conditional $90\%$ intervals exclude zero. AgentLogs evaluates continuous-time incident timing and type; ODCV evaluates failure occurrence at discrete decisions. Motivated by this predictive evidence, we formulate a continuous-time delegation problem that jointly chooses productive action, verification effort, and switching rates between human-directed, AI-assisted operation and autonomous AI operation. The model assumes that verification weakens incident propagation and balances project benefits against operating, supervision, risk, and handoff costs. Our Hawkes-PPO method summarizes observed incidents with exponential memory filters and learns these decisions from rewards. In synthetic experiments, it achieves a higher evaluated objective than either fixed regime and PPO without history filters, and approaches an approximate full-information benchmark. Further experiments show how incident excitation and supervision costs shape delegation.

cs.LG · cs.AI · math.OC

新论文 · v1arXiv:2611.20483

Parallelizable Interior-Point ADMM for Block-Structured Nonconvex Programs

Zherong Pan

原文摘要

Physics simulation is an increasingly important computational primitive for AI, and local--global/ADMM splitting exposes its parallel structure but lacks matching finite-time convergence guarantees. We close this gap with two ADMM variants, Interior-Point ADMM (IP-ADMM), for block-structured nonconvex composite programs with smooth nonlinear inequality and affine constraints. A one-sided finite-activation wall keeps each constraint split state strictly feasible while the original-space infeasibility vanishes, giving closed-form constraint updates, one proximal call per objective block, and one equality-constrained quadratic consensus solve per iteration. \rev{To our knowledge, this makes IP-ADMM the first single-loop method that updates nonconvex inequality constraints locally and in parallel with finite-time convergence guarantees.} Ordinary IP-ADMM attains a CQ-free best-iterate weak-KKT rate of $O(K^{-1/3})$ or a banded Fritz--John rate of $O(K^{-1/4})$, which converts to KKT at $O(K^{-1/4})$ under a uniform constraint qualification; these are nearby-point certificates that reduce to conventional KKT for smooth blocks. A checkpoint variant, IP-ADMM-Ckpt, improves the asymptotic KKT exponent to $O(K^{-1/3})$. We also show how the bounds scale with the objective- and constraint-block counts and the coupling norm.

math.OC · cs.LG

版本更新 · v4arXiv:2307.07735

Faster Algorithms for Structured Linear and Kernel Support Vector Machines

Yuzhou Gu, Zhao Song, Lichen Zhang

原文摘要

Many machine learning problems are quadratic programs, including Support Vector Machines (SVMs). A general quadratic program has input size $Θ(n^2)$, and assuming the Strong Exponential Time Hypothesis (SETH), no $O(n^{2-o(1)})$ time algorithm exists when the objective matrix is positive semidefinite (Backurs, Indyk, and Schmidt, NeurIPS'17). SVMs, however, are given by $n$ data points of dimension $d$, often much smaller than $n$, and have only $O(1)$ equality constraints. In this work, we design the first nearly-linear time algorithm for solving quadratic programs whenever a low-rank factorization of the quadratic objective matrix is given, the number of linear constraints is small, the coefficients of the objective and some optimal solution are bounded by $\mathrm{poly}(n)$, and some feasible point has all entries between $1/\mathrm{poly}(n)$ and $\mathrm{poly}(n)$. For linear SVM on $d$-dimensional data, our randomized algorithm runs in expected time $\widetilde O(nd^{(ω+1)/2}\log(n/ε))$ when $(d+1)^{ω-1}\le n$ and the data points have norms at most $\mathrm{poly}(n)$ and margin at least $1/\mathrm{poly}(n)$, where $ω<2.258$ is the matrix multiplication exponent. Its output satisfies the equality constraint only approximately. For Gaussian kernel SVM, when $d=O(\log n)$, the squared dataset radius is $o(\log n/\log\log n)$ and the dual variables lie in a box $[0,R]^n$ with $R\le\mathrm{poly}(n)$, our randomized algorithm runs in expected time $n^{1+o(1)}$ for any accuracy $ε\ge 1/\mathrm{poly}(n)$. We also prove that, assuming SETH, when the squared dataset radius is $Ω(\log^2 n)$, $Ω(n^{2-o(1)})$ time is required on some inputs to reach error $\exp(-Θ(\log^2 n))$ for the program without the bias term. This improves upon the prior best lower bound in both the dimension $d$ and the squared dataset radius.

math.OC · cs.LG · stat.ML

版本更新 · v3arXiv:2507.00358

Data-Driven Exploration for a Class of Continuous-Time Indefinite Linear--Quadratic Reinforcement Learning Problems

Yilie Huang, Xun Yu Zhou

原文摘要

We study reinforcement learning (RL) for a class of continuous-time stochastic linear-quadratic (LQ) control problems, where volatilities depend on both states and controls while states are scalar-valued and there are no running control rewards, the last feature also leading to the so-called indefinite LQ controls. We propose a model-free, data-driven exploration mechanism that adaptively adjusts entropy regularization by the critic and policy variance by the actor. Unlike the constant or deterministic exploration schedules employed in the existing literature, which require extensive tuning for implementations and ignore learning progress during iterations, our adaptive exploratory approach boosts learning efficiency with minimal tuning. Despite its flexibility, our method achieves a sublinear regret bound that matches the best-known model-free results for this class of LQ problems, which were previously derived only with fixed exploration schedules. Numerical experiments demonstrate that adaptive explorations accelerate convergence and improve regret performance compared to the non-adaptive model-free and model-based counterparts.

cs.LG · cs.AI · eess.SY · math.OC

新论文 · v1arXiv:2611.20437

On the Convergence of Continuous-Time AdamW

Bangjie Wang, Ning Ning

原文摘要

Continuous-time AdamW provides a framework for understanding whether an optimizer widely used to train large-scale neural networks settles to an equilibrium or sustains persistent motion. We study this long-time behavior while retaining bias correction and fixed positive weight decay. Under suitable assumptions, we establish that the dynamics are well defined for all time and remain bounded when the decay is sufficiently small. Our main result connects their limiting behavior to the geometry of the objective: trajectories approach a locally invariant manifold whose dimension equals the Hessian nullity along the associated critical component. When critical points are isolated and have at most one such direction, the trajectory converges to a single equilibrium. With two degenerate directions, however, bounded persistent motion can occur even for a smooth, strictly convex objective with a unique minimum. We also quantify how close the long-time trajectory remains to the critical set as weight decay decreases, without assuming convergence to a point. These results identify objective geometry as a key to understanding when continuous-time AdamW converges and when persistent motion is possible.

math.OC · cs.LG

版本更新 · v2arXiv:2509.23280

Continuous-Time Reinforcement Learning for Asset-Liability Management

Yilie Huang

原文摘要

This paper proposes a novel approach for Asset-Liability Management (ALM) by employing continuous-time Reinforcement Learning (RL) with a linear-quadratic (LQ) formulation that incorporates both interim and terminal objectives. We develop a model-free, policy gradient-based soft actor-critic algorithm tailored to ALM for dynamically synchronizing assets and liabilities. To ensure an effective balance between exploration and exploitation with minimal tuning, we introduce adaptive exploration for the actor and scheduled exploration for the critic. Our empirical study evaluates this approach against two enhanced traditional financial strategies, a model-based continuous-time RL method, and three state-of-the-art RL algorithms. Evaluated across 200 randomized market scenarios, our method achieves higher average rewards than all alternative strategies, with rapid initial gains and sustained superior performance. The outperformance stems not from complex neural networks or improved parameter estimation, but from directly learning the optimal ALM strategy without learning the environment.

cs.LG · cs.AI · math.OC · q-fin.MF

版本更新 · v5arXiv:2412.16175

Mean--Variance Portfolio Selection by Continuous-Time Reinforcement Learning: Algorithms, Regret Analysis, and Empirical Study

Yilie Huang, Yanwei Jia, Xun Yu Zhou

原文摘要

We study continuous-time mean--variance portfolio selection in markets where stock prices are diffusion processes driven by observable factors that are also diffusion processes, yet the coefficients of these processes are unknown. Based on the recently developed reinforcement learning (RL) theory for diffusion processes, we present a general data-driven RL approach that learns the pre-committed investment strategy directly without attempting to learn or estimate the market coefficients. For multi-stock Black--Scholes markets without factors, we further devise an algorithm and prove its performance guarantee by deriving a sublinear regret bound in terms of the Sharpe ratio. We then carry out an extensive empirical study implementing this algorithm to compare its performance and trading characteristics, evaluated under a host of common metrics, with a large number of widely employed portfolio allocation strategies on S\&P 500 constituents. The results demonstrate that the proposed continuous-time RL strategy is consistently among the best, especially in a volatile bear market, and decisively outperforms the model-based continuous-time counterparts by significant margins.

q-fin.PM · cs.LG · eess.SY · math.OC

版本更新 · v5arXiv:2607.02137

Adaptive Reparametrized Time for Score-Based Diffusion Sampling

Yilie Huang, Wenpin Tang, Xun Yu Zhou

原文摘要

We study timestep allocation for score-based diffusion sampling, where the learned reverse-time dynamics is discretized on a finite grid. Uniform and hand-crafted schedules are standard, but their fixed, ad hoc prescriptions can be suboptimal. We propose Adaptive Reparameterized Time (ART), a continuous-time control formulation that learns a time change by treating sampling-clock speed as the control, so a uniform grid on the learned clock induces adaptive timesteps in diffusion time and a leading-order Euler error surrogate defines the allocation objective. To solve the resulting high-dimensional deterministic control problem, we introduce ART-RL, an auxiliary randomized Gaussian-policy formulation that turns schedule learning into continuous-time reinforcement learning. We prove ART-RL is equivalent to ART at optimality: the mean of the optimal Gaussian policy solves ART. We further establish policy evaluation and policy improvement characterizations and derive trajectory-based moment identities that yield implementable actor-critic updates. Experiments ranging from controlled low-dimensional settings to image generation show that ART-learned schedules, when plugged into existing samplers by changing only the timestep grid, consistently improve sample quality over strong baselines at matched budgets. The learned schedules also exhibit broad generalizability, transferring without retraining across sampling budgets, data sets, solvers, pipelines, and representation spaces.

cs.LG · cs.AI · eess.SY · math.OC

版本更新 · v4arXiv:2510.18218

DualHash: Stochastic Primal-Dual Algorithms for W-Type Regularized Deep Hashing

Luxuan Li, Xiao Wang, Chunfeng Cui

原文摘要

Deep hashing encodes high-dimensional image features into compact binary codes, enabling efficient similarity search in large-scale content-based image retrieval, a problem akin to semantic-preserving lossy compression under extreme bit-rate constraints. A fundamental challenge in deep hashing stems from the discrete nature of quantization in generating the codes. W-type regularizations, such as $z\mapsto\||z|-1\|_1$, are widely adopted and empirically effective at pushing network outputs toward binary values. However, existing methods often directly optimize these regularizations without convergence guarantees. While proximal gradient methods offer a promising solution, the coupling between W-type regularizers and neural network outputs results in composite forms that generally lack closed-form proximal solutions. In this paper, using Fenchel duality, we reformulate the nonconvex W-type regularization term through its convex conjugate, yielding a min-max problem with tractable proximal updates. We show that this min-max problem captures the stationarity of the original deep hashing objective up to the quantization error. Building on this problem, we present a stochastic primal-dual hashing algorithm, referred to as DualHash, with oracle complexity guarantees. We derive two algorithm instances: a momentum-based version with $O(\varepsilon^{-4})$ oracle complexity and an improved $O(\varepsilon^{-3})$ version using variance reduction, both for $\varepsilon$-KKT points of the min-max problem, which yield near-stationarity guarantees for the original objective. Experiments on three standard datasets demonstrate competitive retrieval accuracy and reduced quantization error, validating the practical value of DualHash for image retrieval problems. Our implementation of DualHash is available at https://github.com/RailLee/DualHash.

math.OC · cs.CV

版本更新 · v11arXiv:2606.11171

Bellman-sufficient Information Complexity

Yunbei Xu

原文摘要

We introduce Bellman-sufficient information complexity for minimax analysis of sequential decision problems. A Bellman-sufficient state retains the history needed for the controlled recursion; an index $Y=χ(Ω)$ specifies which information the bounds charge. A log-penalized Bellman program gives the upper bound, and a Bellman--Fano comparison with an algorithm-dependent reference trajectory gives the lower bound. When admissibility, calibration, and growth conditions hold and the bounds match at a common localization scale, they yield an information-risk sandwich. UCB bounds the immediate decision loss through calibration and optimism, while AMS/EBO gives a robust relaxation of the AIR Bellman program. Our main application gives a negative answer to a widely studied form of the GP--UCB minimax-optimality question. For every $0<α<1/4$, we construct a fixed bounded continuous kernel with minimax regret $Θ(T^{1-α})$ along an infinite sequence of horizons. At those horizons, two globally calibrated GP--UCB rules incur linear regret under one fixed truth. A policy that applies action-index AMS to a predetermined finite set in each epoch attains the minimax order; EBO gives a dual interpretation. Many low-value directions inflate the global exploration multiplier even though ignoring them is inexpensive. Through the canonical RKHS feature map, the same construction gives a finite-horizon polynomial minimax gap for the specified maximal-information-calibrated LinUCB rule. A numerical experiment illustrates the mechanism.

cs.LG · cond-mat.stat-mech · cs.IT · math.OC · math.ST

新论文 · v1arXiv:2611.20318

Near-Optimal Methods for Generalized Lipschitz Convex Optimization

Dmitry Kovalev, Grigory Malinovsky

原文摘要

In this paper, we consider a convex optimization problem, where the upper bound on the subgradient norm depends on the objective function. We establish a lower bound on the number of iterations required by any first-order method to find an approximate solution to the problem. Furthermore, we present two near-optimal algorithms that can match the lower bound up to logarithmic factors. The first algorithm is a projected GD with a carefully designed stepsize schedule which incorporates warm-up and decay phases. The second algorithm is scalar-stepsize clipped AdamW which extends the near-optimal guarantees to the stochastic setting, where only a noisy unbiased estimator of the subgradient is available.

math.OC · cs.LG

新论文 · v1arXiv:2611.20310

Strengthening Compact Vehicle Routing Formulations through Arc-Flow Aggregation and Refinement

Julian Yarkony, Willem-Jan van Hoeve, Anthony Karahalios, Martin Karyamsetty, Soheyl Khalilpourazari, Louis-Martin Rousseau, Xiaohang Zhu

原文摘要

Arc-flow formulations can provide strong relaxations for mixed-integer program formulations of vehicle routing problems, but the associated networks may be prohibitively large. We study the setting in which multiple arc flow relaxations may be applied, and introduce a dual-guided aggregation and refinement framework that constructs substantially smaller arc-flow formulations while recovering the LP bound of the original networks. Dual information is used both to identify states that can be aggregated without weakening the bound and to guide node disaggregation. We show that the resulting procedure converges finitely to the arc-flow bound of the full arc-flow formulation. The framework retains the original decision variables, allowing cutting planes to be added directly in the original variable space. Moreover, it produces an explicit MILP formulation without relying on column generation or pricing to determine the arc-flow relaxation bound. We apply our approach to the vehicle routing problem with time windows for which we define two arc flow relaxations, as well as two families of cutting planes over the original variable space. Computational experiments show that strong bounds can be obtained using substantially aggregated networks. The resulting root bounds are competitive with those obtained by the branch-and-price solver RouteOpt, while retaining a formulation that can be solved directly by a general-purpose MILP solver.

math.OC · cs.DM

版本更新 · v2arXiv:2603.01430

On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation

Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Iman Shames

原文摘要

We establish a connection between the stability of discrete-time algorithms (DTAs) and continuous-time dynamical systems, in particular their $O(s^r)$-resolution ordinary differential equations (ODEs). We show that exponential stability of a common equilibrium transfers to the DTA whenever the one-step error is small relative to the distance to the equilibrium and the one-step Lyapunov decay. This condition is sharp in order, and one-step consistency alone is insufficient. The result is local and allows step-size-dependent ODEs and Lyapunov functions, covering $O(s)$-resolution ODEs whose decay rate vanishes as the step size tends to zero. Asymptotic stability is not inherited in general, but a comparison criterion and a checkable compatibility condition ensure it carries over for equilibria and compact sets. For resolution ODEs, joint regularity of the update map guarantees the required error bound. We apply the framework to two-timescale gradient descent ascent (TT-GDA), generalised extragradient, two-timescale proximal point, and (regularised) damped Newton, showing that for small step sizes and suitable parameters, every saddle point with invertible Hessian is locally exponentially stable for all but TT-GDA. For degenerate saddle points, the framework yields asymptotic stability and convergence rates.

math.OC · cs.LG · eess.SY · math.NA

版本更新 · v2arXiv:2611.11046

Integer Programming Parametrized by Imbalanced Circuit Packing

Yuheng Shi

原文摘要

We study the standard form Integer Programming problem (IP) parametrized by the imbalanced circuit packing number. This number is $0$ if and only if $A$ can be transformed to a totally unimodular matrix by row operations, in which case (IP) is solvable in polynomial time. We show that if the constraint matrix represents a graphic matroid, (IP) is fixed-parameter tractable when parametrized by the imbalanced circuit packing number of the matrix. The proof combines an Erdős-Pósa property for edge-colored non-monochromatic cycles with a reduction to mixed-integer programming using few integer variables. In contrast, by a reduction from the parity potential problem, we show NP-completeness of feasibility of (IP) when the constraint matrix represents a cographic matroid, even if kernel of the constraint matrix is $2$-regular and imbalanced circuits pairwise intersect.

math.OC · cs.DS

版本更新 · v4arXiv:2608.23986

The Shadow Price of Intelligence: Quality Degradation and Retry Feedback in LLM Inference

Elioth Sanabria

原文摘要

Large language model providers are compute constrained, and a common response to congestion is to degrade service: route queries to smaller models, cut reasoning budgets, or shorten context windows. A user who receives an unsatisfactory answer either retries, adding load while the system is busy, or abandons, possibly as churn. We model inference serving as a control problem in which service quality is the provider's decision. A two-regime fluid approximation with retries folded into the service rate gives closed-form trajectories and crossing times, so the dynamic program over quality tiers needs no simulation. We characterize a region in which a weaker tier uses less energy per task but more capacity per task, and show that in the fluid model reactive throttling to such a tier can keep the queue from draining. With heterogeneous customers the problem is a transportation problem with retry-inflated capacity coefficients; optimal routing follows a $cμ$-type index, and the dual of the capacity constraint gives the marginal cost of one more query by class and time. We illustrate the method on five instances calibrated to public benchmark data.

math.OC · cs.AI · cs.PF

版本更新 · v2arXiv:2603.29921

Quantale-Enriched Co-Design: Toward a Framework for Quantitative Heterogeneous System Design

Hans Riess, Yujun Huang, Matthew Klawonn, Gioele Zardini, Matthew Hale

原文摘要

Monotone co-design enables compositional engineering design by modeling components as feasibility relations between required resources and provided functionalities. However, its boolean formulation cannot natively represent quantitative criteria such as cost, confidence, or implementation choice. In practice, these considerations are introduced through ad-hoc scalarization or by augmenting the resource space, which obscures system structure and increases computational complexity. Therefore, we develop a quantale-enriched theory of co-design in which resources and functionalities are quantale-enriched categories and design problems are quantale-enriched profunctors, which lifts co-design from boolean feasibility to quantitative evaluation. Series, parallel, and feedback composition remain valid over any commutative quantale, and change-of-base maps between quantales yield heterogeneous composition, so that subsystems evaluated in different local semantics can be composed in a common framework. Numerical examples on a target-tracking system and a UAV delivery problem demonstrate this framework and show how it avoids the drawbacks of boolean-only formulations.

eess.SY · cs.LO · math.CT · math.OC

新论文 · v1arXiv:2611.20060

Communication-Efficient Distributionally Robust Federated Averaging with Multi-Source Data

Yingzhu Liu, Zhongkui Li, Pengcheng You, Ashish Cherukuri

原文摘要

Federated learning trains a shared model from distributed client data. The deployment risk is typically specified through two approximations: each unknown local distribution is replaced by its empirical distribution, and the unknown deployment mixture across clients is replaced by empirical or prescribed training weights. Existing robust methods usually address one approximation at a time through local distributional ambiguity sets or worst-case client mixtures. However, joint treatment of both approximations remains underexplored. To address this gap, we construct a global ambiguity set formed by admissible mixtures of client-wise Wasserstein ambiguity sets, yielding a distributionally robust optimization formulation. The construction allows client-dependent ambiguity radii, preserves client-wise separability of the objective function, and yields a high-probability out-of-sample guarantee for the resulting robust problem. We then introduce a penalty-based approximation of this formulation and develop a communication-efficient algorithm called BiDRO-FedAvg, for which we establish a convergence guarantee. We validate the proposed framework through a market-demand prediction simulation.

cs.LG · math.OC