跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1680新增论文
+1333其中 AI 相关
+187已有论文修订
+59新增 AI 导读

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

统计口径与数据新鲜度

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

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

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

25,786 已收录论文21,491 AI 相关7,725 有修订112 HF 社区发现

浏览论文库

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

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

Susceptibility optimization for wisdom of crowds: A social power reformulation and realization framework

Ye Tian, Anzhi Sheng, Angela Fontan, Long Wang, Karl H. Johansson

原文摘要

Whether social influence makes a crowd wiser or more biased hinges on who yields to others and who holds firm. Such heterogeneous susceptibilities to social influence, together with the influence network, determine the weight each agent's initial estimate carries in the collective estimate, known as social power. This paper studies susceptibility optimization for maximizing the wisdom of crowds under the Friedkin-Johnsen model. Minimizing the squared collective bias over susceptibilities leads to a nonconvex problem. To overcome this nonconvexity, we develop a social power reformulation and realization framework, which decomposes the problem into two stages: first characterizing the social power that minimizes the collective bias, then determining the susceptibilities that induce such social power. Social power reformulation yields a quadratic program over the probability simplex. Under uniform-sign biases, the optimal social power concentrates on the least biased agents and immediately determines the optimal susceptibilities; under mixed-sign biases, its geometry enables a linear-time construction algorithm. For social power realization, we introduce the notions of susceptibility realizability and establish necessary and sufficient conditions for them, under which we derive all optimal susceptibilities in closed form using the Laplacian pseudoinverse and eigenvector centrality. These results yield a unified algorithm that solves the original problem globally, with worst-case complexity cubic in the number of agents when realizability holds. Finally, we develop a fully distributed implementation with linear communication complexity, illustrating how collective intelligence can emerge from local interactions.

eess.SY · cs.SI · math.OC

版本更新 · v2arXiv:2610.38496

Accelerating Nonlinear MPC by Behavior Cloning with Separated Timescales: Application to Nuclear Reactor Load-Following

Perceval Beja-Battais, Alain Grosset{ê}te, Nicolas Vayatis

原文摘要

Behavior Cloning (BC) of expert controllers for multiscale dynamical systems is challenging: state variables evolving at widely separated timescales induce highly nonlinear couplings that a shared latent space may fail to adequately represent, degrading closed-loop generalization. We propose Structured Representation Learning for Behavior Cloning (SRLBC), an architecture designed to leverage the physical knowledge of multiscale systems in which slow state variables, fast (stiff) state variables, and predictable exogenous inputs evolve at different timescales. On 500 long-horizon roll-outs of a pressurized water reactor (PWR) load-following benchmark -a high-dimensional, stiff industrial system with challenging safety constraints -and across 20 training seeds, separated embeddings systematically outperform shared embedding baselines on cumulative cost, imitation accuracy and constraint satisfaction. The resulting standalone policies approach NMPC closed-loop performance at a computational cost 15 times lower on average. Since standalone policies still leave a few percent of trajectories infeasible, we embed the learned policies in a safety-augmented approximate NMPC framework, in which the optimizer is only called when the predicted input sequence is not certified as safe. This yields controllers still 6.8 times faster than the NMPC controller on average, with a feasibility (i.e., constraint satisfaction) of at least 99.8% for all architectures, SRLBC retaining the lowest closed-loop cost. Under distribution shift, standalone BC policies degrade sharply: SRLBC degrades the least, and once safety-augmented, it retains a feasibility above 98% with the lowest closed-loop cost. Beyond the quantitative results, Jacobian-based sensitivity analysis shows that the resulting controller relies on a sparse and less redundant set of latent features, each attributable to a single group of physical variables, and aligned with the physical timescale decomposition of the system.

cs.AI · cs.LG · math.OC

新论文 · v1arXiv:2611.03101

Diagonal Equivalence in State Space Models: Characterization, Retrieval Rank, and Selective Extensions

Dennis Rochau

原文摘要

We classify real and complex state-space models (SSMs) with linear transitions, distinguishing fixed-basis diagonal equivalence from input-output equivalence and tracking coefficient-conditioning windows under coordinate changes. We characterize diagonal equivalence through commuting transition families whose members are diagonalizable over the chosen field. With time-shared token-local matrix maps, we identify this class's state-mediated kernels with unnormalized scalar-mode linear attention with multiplicative masks. Mamba 3's multiple-input, multiple-output (MIMO) construction lifts one value per local interface; SSD-MIMO routes independent values for local retrieval rank above one. HybridMamba combines Mamba 1's per-coordinate decay, Mamba 2-style heads and Mamba 3's complex rotations and two-endpoint writes, mixing real and rotating state blocks with different decay laws. They recover Mamba 1-3 single-input, single-output (SISO) configurations as exact special cases. On five large H100 bfloat16 workloads, our fused GPU kernels improve geometric-mean training time over official Mamba 1/3 in matched SISO recoveries, with Mamba 2 near parity at SSM-core scope. Memory tradeoffs depend on the baseline and metric: saved-for-backward versus peak allocation. In small-model multi-token recall experiments, both designs outperform Mamba 1-3 on the hardest tier; higher routing ranks perform best in gated or phase-diverse configurations. In single-seed language models with about 500M parameters, both improve on Mamba 1/2 in test loss at 2B tokens, but the routing gains do not translate into lower language-model loss. Our best configurations approach Mamba 3 SISO through 10B tokens while remaining behind it and Mamba 3 MIMO in language-model loss.

cs.LG · math.OC · stat.ML

新论文 · v1arXiv:2611.03088

Optimal Configurations for Mordell's Problem

Xiang Ji, Tiancheng Xu, Wensheng Yu

原文摘要

Mordell's problem asks for the largest product of squared pairwise distances among $n$ points in the complex plane with a prescribed sum of squared distances from the origin. When this sum equals $n$, the maximum for $2\le n\le5$ is known to be $n^n$, attained precisely by the $n$th roots of unity up to rotation and relabeling. For $n\ge6$, Chalk showed that a regular polygon together with its center gives a larger product than the regular $n$-gon. We prove that for $6\le n\le9$ the maximum is $(n-1)^{n-1}r_n^{n(n-1)}$, where $r_n=\sqrt{n/(n-1)}$. Up to the same symmetries, the unique maximizer consists of the origin and the vertices of a regular $(n-1)$-gon of radius $r_n$. For six points, algebraic elimination reduces the proof to an exact comparison of stationary values. For seven points, we compare all twelve classes in a published classification of equilibria. For eight and nine points, rigorous interval arithmetic establishes an inequality for every admissible pair. Summing over pairs gives the sharp global bound, and the equality conditions determine the configuration. An explicit ten-point comparison and a known instability result together exclude Chalk's configuration for every $n\ge10$. For each $n$ from two through eight, Mordell's problem and the minimum-diameter problem studied by Bateman and Erdős have a common optimal configuration.

math.CO · cs.SC · math.OC

新论文 · v1arXiv:2611.03030

A Cooperative Game-Theoretic Framework for Real-Time Deviation Settlement in Local Energy Communities

Angel M. González-Rueda, Iago Núñez Lugilde, Jose L. Crespo-Vazquez, Tarek Alskaif

原文摘要

This paper proposes a cooperative game-theoretical framework for the financial settlement of real-time deviations in Community-Based Local Energy Markets (CB-LEMs). The real-time settlement process is modeled as a transferable-utility cooperative game, and the resulting Real-Time Local Energy Market (RTLEM) game is shown to be superadditive and balanced. We analyze two game-theoretical allocation mechanisms, the Shapley value and the nucleolus, and evaluate their efficiency, individual rationality, coalitional rationality, and temporal-aggregation properties. We subsequently compare these mechanisms with a settlement rule based on proportional imbalance responsibility. The three mechanisms are efficient and individually rational, but only the nucleolus is guaranteed to satisfy coalitional rationality for every RTLEM instance. The proposed framework is demonstrated using real-world data from a residential energy community in Amsterdam, showing the trade-offs among the three allocation mechanisms in terms of surplus distribution, coalitional stability, interpretability, and computational requirements.

cs.GT · eess.SY · math.OC

版本更新 · v2arXiv:2505.15212

Group Distributionally Robust Optimization with Flexible Sample Queries

Haomin Bai, Dingzhi Yu, Shuai Li, Haipeng Luo, Lijun Zhang

原文摘要

Group distributionally robust optimization (GDRO) aims to learn models that perform well across $m$ distributions simultaneously. Existing methods either (i) query $m$ samples per round, which imposes strict implementation requirements, or (ii) query only a single sample per round, which requires many rounds to converge and therefore leads to long runtime. To avoid these limitations, we introduce a novel setting called \emph{flexible sample queries} (FSQ), which allows the number of samples that can be queried to vary across rounds. Under the FSQ setting, we cast GDRO as a two-player game: one performs non-oblivious online convex optimization, while the other tackles a non-oblivious prediction with limited advice (PLA) problem. In this game, the first player updates its decision using follow-the-regularized-leader with stochastic gradients. For the second player, we develop a new PLA method equipped with an adaptive exploration strategy that can leverage an arbitrary per-round sample size. We then establish the \emph{first} high-probability regret bound for non-oblivious PLA. By integrating these components, we develop an anytime GDRO algorithm that supports FSQ, and derive a high-probability optimization error bound of $O\left(\frac{1}{t}\sqrt{\sum_{j=1}^t \frac{m}{r_j}\log m}\right)$, where $r_j$ is the sample size at round $j$. This result demonstrates that the optimization error decreases as the per-round sample sizes increase, and implies the same near-optimal sample complexity of $O(m\log (m)/ε^2)$ for any fixed sample size $r\in[m]$.

cs.LG · math.OC

新论文 · v1arXiv:2611.02823

Efficient Detailed Scheduling of Multiproduct Pipelines using Action-Decoupled Deep Reinforcement Learning

Kai Shao, Ling Jian, Liming Liu, Serguey V. Bogomolov, Xinmin Wang

原文摘要

Multiproduct pipelines transport refined products to delivery stations in sequential batches, and their detailed scheduling must meet market demand while respecting nonlinear hydraulic constraints. Retaining the full hydraulic nonlinearity yields a mixed-integer nonlinear program that is computationally intractable, while the linearization commonly adopted for solver-based optimization degrades hydraulic accuracy without resolving the heavy computational burden. This paper develops an action-decoupled proximal policy optimization (PPO) framework that efficiently produces detailed schedules while preserving hydraulic fidelity. The scheduling process is cast as a semi-Markov decision process (SMDP) with flexible action durations. To handle the discrete-continuous hybrid action space, a cascaded dual-actor architecture decouples the discrete operating duration from the continuous flow decisions, eliminating the gradient interference that destabilizes conventional coupled-action policies and thereby yielding high-quality schedules far more efficiently. Validated on a real-world multiproduct pipeline in China and benchmarked against a single-actor baseline and a linearized MILP solved by Gurobi, the proposed framework achieves delivery accuracy close to the exact optimum while substantially improving flow rate stability and substantially reducing solution time.

cs.LG · eess.SY · math.OC

新论文 · v1arXiv:2611.02812

When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret

Ridham Patel

原文摘要

Dynamic regret measures an online learner against a moving comparator, and standard analyses assume the learner may move freely at every round. We study what happens when it may not: the learner is given a hard budget $S$ on its total movement $\sum_t \|x_t - x_{t-1}\|$. Our main result is that a movement budget creates a feasibility barrier. On a domain of diameter $D$ with $G$-Lipschitz convex losses, for every comparator path length $P_T \in [D, DT]$ we exhibit a deterministic adversary that forces $R_d = Ω(GDT)$ on every budget-feasible algorithm whenever $S \le c P_T$ for a universal constant $c>0$. This barrier is caused by the budget rather than by a volatile environment: for fixed $D$, it applies when $P_T = o(T)$, where the unconstrained minimax rate $Θ(G\sqrt{D(D+P_T)T})$ is sublinear, so the same instances are learnable with an unbounded budget and unlearnable without one. Conversely, projected online gradient descent with a budget-aware step size is budget-feasible and attains $o(GDT)$ once $S = ω(D + P_T)$. Thus the critical movement scale is $D+P_T$: linear regret is unavoidable below a sufficiently small constant multiple of $P_T$, while sublinear regret is achievable when $S/(D+P_T)\to\infty$ in the learnable regime. The construction rests on a distinction we make explicit: what makes a comparator expensive to track under a movement budget is the distance it forces the learner to travel, not its path length. Above the threshold we give a budget-dependent upper bound and identify the tight minimax rate in this region as an open problem rather than claiming a product law. Experiments support the predicted transition location and the $1/S$ decay.

cs.LG · eess.SY · math.OC · stat.ML

新论文 · v1arXiv:2611.02809

Offline Approximate Value Iteration: A Reinforcement Learning Approach for Satellite Constellation Deployment

Tristan Leuridan, Yiping Fang, Adam Abdin

原文摘要

This paper introduces a reinforcement learning-based approximate dynamic programming approach to optimize the deployment of Walker-type satellite constellations under uncertainties, including launch failures and satellite malfunctions. We formulate the problem as a Markov Decision Process that incorporates low-injection orbit launches, continuous low-thrust orbit raising, and variable satellite loads. We adopt the offline approximate value iteration solution method, using linear function approximation with basis functions and action pruning strategies to substantially reduce the computational and memory requirements for finding optimal decision policies. Preliminary results demonstrate convergence to policies with low expected costs and deployment times, both of which are lower than those of a rolling-horizon baseline, showcasing a novel application of approximate dynamic programming in space logistics.

cs.AI · math.OC

新论文 · v1arXiv:2611.02764

Equivalent Graphical Conditions for Angle Rigidity and Angle-Based Network Localization

Jinpeng Huang, Gangshan Jing, Kai Zhao, Yongduan Song

原文摘要

Angle rigidity theory provides a theoretical basis for characterizing the geometric shape of graphs embedded in the plane under angle constraints, and establishing global convergence of angle-based network localization algorithms. The related references, however, are largely restricted to graphs generated by triangulation or bilateration ordering, which are sufficient but not necessary for angle rigidity. This paper addresses this challenge by focusing on establishing the equivalence between angle constraints and bearing constraints. The conditions for cycle compatible frameworks (with possibly non-generic configurations) to be angle fixable are provided. Moreover, it is shown for the first time that Laman graphs equivalently characterize minimally globally angle rigid graphs, implying that a Laman graph is the simplest graph that allows a generic embedding in the plane to be uniquely determined by subtended angles. As an application, a distributed algorithm for angle-based sensor network localization is proposed, which guarantees global convergence under a much milder network topology condition than those in the literature.

math.OC · cs.IT

新论文 · v1arXiv:2611.02722

The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization

Long Vu, Jongseong Brad Choi, Binoy Ravindran, Zhoulai Fu

原文摘要

A staged search must decide which candidate to advance next and when to stop. Some observations only inform later decisions; others can be kept as results. We formulate these choices as a staged Pandora's box with a designated set of collectable stages. For independent finite-stage candidates with bounded readings and positive bounded own-history costs, an exact covered-call recursion gives the reservation index, the optimal value and the loss of every advance or stop; advancing an index-maximal candidate while its index exceeds the incumbent is optimal. The representation recovers classical single-stage search, nested inspection and the all-collectable Markov setting, and prices changes in the problem: enlarging the collectable set or lowering costs raises the value by an explicit covered-call overshoot. Resumption can be valuable even when future reward laws do not change, but has no value for deterministic readings. With information sharing across candidates, no rule using only their separate remaining-reading laws is universally optimal, and making an intermediate reading collectable can change which candidate is inspected first. Under a coherent joint path law with own-history costs, an approximate-planning bound controls the recomputed index's regret by changes in untouched candidates' local values; a common-component specialization bounds those changes through predictive total-variation dispersion. Exact finite-law experiments check the representation, the loss accounting and the bounds.

cs.LG · math.OC · stat.ML

版本更新 · v4arXiv:2503.18974

An Efficient Frequency-Based Approach for Maximal Square Detection in Binary Matrices

Swastik Bhandari

原文摘要

We present FreqBased, a frequency-based algorithm for the maximal square problem in binary matrices. The algorithm maintains a vertical run-length array and a horizontal counter to validate candidate squares, matching the standard single-array dynamic programming algorithm in O(mn) time and O(n) space while reducing the amount of work performed during execution. Experiments on synthetic random binary matrices reveal a clear density-dependent performance transition: FreqBased consistently outperforms the dynamic programming baseline on moderate- and high-density inputs across Intel and AMD processors, achieving peak speedups of 1.175x and 1.277x, respectively, while executing up to 2.08x fewer instructions. On 180 real aerial image masks from the INRIA dataset, FreqBased outperforms the baseline on every instance with speedups of up to 4.63x, confirming that the instruction-count advantage observed on synthetic inputs extends to real binary matrices with spatial structure. Hardware performance counter analysis shows that the performance advantage arises primarily from reduced instruction count despite lower execution efficiency, demonstrating that algorithms with identical asymptotic complexity can exhibit substantially different practical performance depending on input characteristics.

cs.DS · math.OC

新论文 · v1arXiv:2611.02375

Allen--Cahn Residual-Constrained Topology Optimization via an Augmented Lagrangian Method

Run Du, Xuan Xiao, Wenming Cheng, Zeqiang Zhang

原文摘要

This paper presents a residual-constrained topology optimization framework that controls interface transition bandwidth without requiring external density filters. The steady conserved Allen--Cahn (AC) equation is formulated as an equality residual constraint and solved via a mass-weighted Augmented Lagrangian Method (ALM) coupled with the Method of Moving Asymptotes (MMA). A closed-form chemical potential projection eliminates the constant residual mode, ensuring algebraic compatibility with external volume targets. Variational sensitivity analysis reveals a symmetric-plus-rank-one Jacobian that yields matrix-free sensitivities without additional adjoint PDE solves, reducing residual sensitivity overhead to only 0.11% of the state elasticity solve time in 3D. Systematic 2D benchmarks confirm that interface bandwidth is governed intrinsically by reaction--diffusion parameters across mesh refinements. While diffuse interfaces incur a continuous compliance elevation (1.4%--12.3%), a volume-preserving 0/1 post-processing audit across 48 benchmark cases demonstrates that this gap stems primarily from intermediate-density penalization: binarized AC-ALM designs achieve equal or superior stiffness in 45 configurations (averaging 1.2% stiffer than SIMP). Simultaneously, single-node hinges and strut fragmentation are substantially suppressed compared to unregularized baselines. Three-dimensional benchmarks further demonstrate practical spatial viability for complex structures.

cs.CE · math.OC

版本更新 · v5arXiv:2506.20533

Global Convergence of Iteratively Reweighted Least Squares for Robust Subspace Recovery

Gilad Lerman, Kang Li, Tyler Maunu, Teng Zhang

原文摘要

Robust subspace estimation is fundamental to many machine learning and data analysis tasks. Iteratively Reweighted Least Squares (IRLS) is an elegant and empirically effective approach to this problem, yet its theoretical properties remain poorly understood. This paper establishes that, under deterministic conditions, a variant of IRLS with dynamic smoothing regularization converges linearly to the underlying subspace from any initialization. We extend these guarantees to affine subspace estimation, a setting that lacks prior recovery theory. Additionally, we illustrate the practical benefits of IRLS through an application to low-dimensional neural network training. Our results provide the first global convergence guarantees for IRLS in robust subspace recovery and, more broadly, for nonconvex IRLS on a Riemannian manifold.

stat.ML · cs.LG · math.OC

新论文 · v1arXiv:2611.02055

Rare Event Constrained Reinforcement Learning with Large Deviations

Rahul Misra

原文摘要

We study finite-horizon reinforcement learning with a safety constraint on the probability of reaching a failure set. In contrast to the well-studied safe reinforcement learning literature, we consider problems where the probability of reaching the failure set is vanishingly small, but the consequences of reaching the failure set are catastrophic. Direct simulation and estimation of the optimal policy is naturally ineffective when the failure probability is extremely small. Moreover, on a real system the controller can only choose actions, and this is not enough to make failures frequent. In contrast to the rare event simulation literature, our goal is not to estimate the probability of the rare event occurrence, but to upper bound it such that the failure constraint is satisfied. Thus, instead of sampling failures, we use the large deviations principle. We define a damage variable that on exceeding a certain threshold indicates failure. We study the cumulant generating function (CGF) as its positive root provides an upper bound on the failure probability via Cramer's theorem. We extend this approach to Markov decision processes with hitting times through state-action CGFs, and give finite-horizon and state-dependent versions of the bound. The state-action CGFs do not depend on the policy and can be estimated from regular transitions, so the bound can be checked for any policy a priori. This gives a policy improvement algorithm in which every policy satisfies the failure constraint with high probability.

stat.ML · cs.LG · eess.SY · math.OC · math.PR · math.ST

新论文 · v1arXiv:2611.01965

OC-OPD: Observation-coordinated Supervision for On-Policy Distillation

Ruoran Xu, Yilun Zhao, Ziyu Chen, Arman Cohan

原文摘要

Reverse and forward Kullback--Leibler (KL) divergences provide complementary supervision in on-policy distillation: reverse KL refines the student's active token rankings, and forward KL allocates mass to teacher-supported candidates. At student-generated prefixes, we form a four-observation matrix by treating the student and teacher as both candidate sources and evaluators. The diagonal self-observations measure uncertainty, while source-centered cross-observations recover the two KL objectives. We establish an exact identity equating the Fisher inverse-metric coupling of their logit gradients with the sum of these contrasts, yielding a common local descent direction for distinct positive distributions. Observation-coordinated on-policy distillation (OC-OPD) uses observations to set preferences, closed-form bargaining to coordinate gradients, and distributional discrepancy to scale the update. Across three heterogeneous student settings (non-thinking generation, thinking generation, and base-model initialization), OC-OPD achieves strong gains in mathematical reasoning and transfers effectively to out-of-distribution scientific question answering and code generation. Our code is publicly available at: https://github.com/RuoranXu/OC-OPD.

cs.LG · cs.AI · math.OC

版本更新 · v2arXiv:2610.01662

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

Jiayi Song, Zi Xu

原文摘要

We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an $L$-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most $D_Y$, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most $Δ$. The target accuracy $\varepsilon$ is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter $1/(2L)$. Under an unbiased stochastic first-order oracle with variance at most $σ^2$ and mean-squared smoothness, we prove the lower bound $Ω\!\left(L^2D_YΔ\varepsilon^{-3}+L^3D_Y^2Δσ^2\varepsilon^{-6}\right)$. This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter $μ>0$ and condition number $κ:=L/μ$, we obtain $Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+LΔκσ^2\varepsilon^{-4}\right)$ under the bounded-variance oracle model. Under the additional mean-squared smoothness condition with constant $\bar L$, we obtain $Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+Δ\bar Lσκ^{3/2}\varepsilon^{-3}\right)$. Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.

math.OC · cs.LG · stat.ML

版本更新 · v2arXiv:2605.00654

Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation

Andrzej Ruszczynski, Tiangang Zhang

原文摘要

For a risk-averse finite-horizon Markov Decision Process, we introduce a special class of Markov coherent risk measures, called mini-batch measures. We also define the class of multipattern risk-averse problems that reduce to linear MDPs in the risk-neutral case. We use both concepts in a feature-based $Q$-learning method with multipattern $Q$-factor approximation and we prove a high-probability regret bound of $\widetilde{\mathcal{O}}\big(d^{3/2}HN^{H-1}\sqrt{K}\big)$, where $d$ is the number of features, $H$ is the horizon, $N\ge2$ is the mini-batch size, $K$ is the number of episodes, and $\widetilde{\mathcal{O}}$ hides logarithmic factors. We also propose an economical version of the $Q$-learning method that streamlines the policy evaluation (backward) step. The theoretical results are illustrated on a stochastic assignment problem and a short-horizon multi-armed bandit problem.

cs.LG · cs.AI · math.OC · stat.ML

新论文 · v1arXiv:2611.01786

IncVNM: An Interactive Recommender System with Incremental von Neumann-Morgenstern Utility Learning

Jiaxin Wei, Jia Liu

原文摘要

In modern recommender systems, users are often presented with products whose outcomes are random. The values of such products depend on their entire outcome distributions and on users' attitudes toward risk, making them difficult to evaluate using traditional product-level recommendation methods. We propose \textsc{IncVNM}, an interactive recommender system that incrementally learns a user-specific von Neumann--Morgenstern (VNM) utility function from ordinal click feedback generated during ordinary webpage browsing. At each interaction, \textsc{IncVNM} converts the click order within a displayed product list into pairwise comparisons between outcome distributions and updates the nominal utility by minimizing its deviation from the previous estimate while incorporating the newly observed pairwise comparisons. To close the interaction loop, an entropy-regularized sampling policy balances exploitation of the learned utility against exploration for additional preference information. We evaluate \textsc{IncVNM} in a rolling-window experiment with different response-error probabilities and show that it substantially outperforms the expected-return, mean--variance, discounted-UCB, and distribution-aware BPR baselines.

cs.IR · math.OC

版本更新 · v2arXiv:2605.06884

Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decomposition

Sayantan Choudhury, Xiaoran Cheng, Martin Takáč, Sen Na, Mladen Kolar

原文摘要

Most first-order optimizers treat matrix-valued parameters as vectors, ignoring the intrinsic geometry of hidden-layer weights in neural networks. Muon addresses this mismatch by updating along the polar factor of a momentum matrix, but its theoretical understanding has lagged behind practice. In particular, practical implementations incorporate Nesterov momentum, compute the polar factor only approximately, and operate with stochastic gradients that may be heavy-tailed. We close this gap by developing a convergence theory for Muon with Nesterov momentum and inexact polar decomposition in non-convex matrix optimization under heavy-tailed noise. Our analysis builds on a unified framework for inexact polar decomposition that captures practical iterative approximations such as Newton-Schulz and quantifies how their errors propagate through the optimization dynamics. Under uniform bounds on polar errors, we establish an optimal iteration and sample complexity of $O \left(\varepsilon^{\frac{-(3α-2)}{(α-1)}} \right)$ for finding an $\varepsilon$-stationary point, where $α\in(1,2]$~denotes the heavy-tail index. For the inexact-polar setting with $σ_1=0$, we also provide guarantees that do not require prior knowledge of $α$. We analyze a randomized low-rank polar decomposition that is substantially more efficient than full-space methods while remaining compatible with our theory. Numerical experiments further demonstrate the effectiveness of the proposed inexact and randomized~variants.

math.OC · cs.LG

新论文 · v1arXiv:2611.01754

Optimization Frameworks & Learning Algorithms for Discrete-Time Mean Field Games

Xin Guo, Mathieu Laurière

原文摘要

This monograph introduces discrete-time mean field games with finite state and action spaces, emphasizing optimization formulations and learning algorithms. Starting from Markov decision processes and finite-player stochastic games, it develops the notion of mean field Nash equilibrium, establishes existence and uniqueness results under suitable assumptions, and explains how mean field equilibria yield approximate equilibria in large finite-player games. Building on the linear programming formulation of Markov decision processes, occupation measures and primal-dual formulations connect equilibrium computation with mathematical optimization. The monograph presents fixed-point iterations, fictitious play, online mirror descent, and optimization-based methods, discussing their convergence properties and limitations. Numerical examples illustrate crowd motion, traffic routing, epidemic management, and the computation of multiple equilibria. It combines examples, theoretical results, and implementable algorithms, with bibliographic notes providing connections to the broader literature.

math.OC · cs.LG

新论文 · v1arXiv:2611.01744

Convex Regression at Scale: Geometry-Preserving Constraint Sparsification

Anish Senapati, Jose Blanchet

原文摘要

Convex regression provides a flexible nonparametric estimation framework while incorporating appropriate shape information. However, its standard least-squares formulation has $O(n^2)$ supporting-hyperplane constraints creating a computational bottleneck as the sample size $n$ increases. We study a $K$-nearest-neighbor (KNN) localized relaxation for convex regression where we for each sample, we only maintain the $K$ nearest hyperplane constraints. Under mild regularity conditions, we establish statistical guarantees for our modified estimator in every fixed dimension $d\ge2$. In particular, for $d>4$, the population risk of our modified problem can be shown to have equivalent convergence rates as the original least square convex regression estimator of $\widetilde O(n^{-2/d})$ using neighborhoods sizes (i.e. $K=K_n$) of order $\widetilde O(n^{2(d-1)/(2d-1)})$ for general convex functions and $\widetilde O(n^{(d+1)/(d+2)})$ for strongly convex functions. To corroborate our theory, we implement iterative optimization methods to compare the prediction accuracy of the KNN relaxation with those of the full estimator across synthetic convex benchmarks. Our experiments demonstrate that KNN prediction risk approaches the full-estimator prediction risk at neighborhood sizes matching the theoretical scale.

stat.ML · cs.LG · math.OC

版本更新 · v2arXiv:2607.01525

Mean Field Reinforcement Learning: Theory and Algorithms for Mean Field Control

René Carmona, Mathieu Laurière

原文摘要

This monograph provides an introduction to mean field reinforcement learning through the lens of Markov decision processes arising from large-population stochastic control with mean field interactions and common noise. Starting from the connection between multi-agent reinforcement learning and mean field control, it develops the probabilistic, mathematical, and control-theoretic framework needed to formulate representative-agent learning problems, analyze their relationship with finite-population systems, and study both general and linear-quadratic models. The presentation includes dynamic programming principles, propagation-of-chaos limits, and theoretical analyses of tabular Q-learning and policy-gradient methods. It also discusses numerical implementations, including tabular schemes and deep reinforcement learning methods such as deep deterministic policy gradient. The goal is to give readers a coherent bridge between mean field control theory and reinforcement learning methodology, emphasizing the mathematical structure of the problems and the design of tractable learning approaches for large stochastic populations.

math.OC · cs.LG · cs.MA · math.PR

新论文 · v1arXiv:2611.01584

Smoothed analysis of stability radii for the assignment problem

Michael P. Friedlander

原文摘要

Every linear program can tolerate small changes to its costs and still yield a solution of the original problem. The size of this tolerance measures how robust an optimal decision is to noise or numerical error, and how much regularization the problem can support. Classical sensitivity analysis can determine this tolerance only from an optimal solution. This paper provides a priori lower bounds on two measures of this tolerance -- the optimality gap and the $\infty$-norm stability radius -- for the $n$-by-$n$ linear assignment problem over the Birkhoff polytope. The bounds derive from a smoothed analysis, which adds Gaussian noise with standard deviation of at least $σ$ in every direction to an arbitrary base cost. At every fixed confidence level, uniformly over the base cost, both quantities are at least of order $σ/(n\sqrt{\log n})$. The radius bound is asymptotically sharp. Under isotropic noise, the worst case occurs when every assignment has equal cost, and in this case, a scaled stability radius converges in distribution to a standard exponential variable.

math.OC · cs.DS · math.PR

新论文 · v1arXiv:2611.01530

Learning Gradients of Homogeneous Functions

Mayur S. Gowda, Srinivasa Pranav, Shreyas Chaudhari, José M. F. Moura

原文摘要

Homogeneous gradient functions have widespread significance, including applications in maximum energy subspace selection and retrieval problems. Euler's homogeneous function theorem specifies how the potential associated with a positively k-homogeneous gradient field can be recovered directly from the field itself. We use Euler's theorem to build on GradNets and propose a homogeneous gradient network architecture that is guaranteed to correspond to the gradient of a homogeneous function. Then, we describe how monotone homogeneous GradNets universally approximate the gradients of k-homogeneous convex functions. The inductive bias of homogeneous GradNets enables them to outperform baseline ICNNs by up to 7dB in our max energy subspace projection experiment and by up to 13% higher accuracy, 98% fewer parameters, and 70% fewer FLOPS in our amortized inner product search experiment.

cs.LG · eess.SP · math.OC

新论文 · v1arXiv:2611.01442

Dual Path Following for an Aerial Manipulator Under State and Input Constraints via Transverse Feedback Linearization

Hamza Tariq, Adeel Akhtar

原文摘要

This paper studies dual path following for a quadrotor carrying a three-degree-of-freedom arm. The center of mass of the combined system must follow a vehicle path and the end effector must follow a second path, while the arm respects its joint limits and avoids its singular postures. The vehicle and the arm are mechanically coupled, so one controller must handle both paths. With the center of mass and the end-effector path coordinates as outputs, and a dynamic extension of the thrust, the system admits a normal form without internal dynamics. We characterize the states where this normal form fails. We formulate the transverse feedback linearizing controller as a quadratic program that relaxes only the speed of the end effector along its path and imposes safety and actuator limits as inequality constraints. The program reduces to a scalar problem with a closed-form solution. If it remains strictly feasible for all time, the feedback is locally Lipschitz, both paths are invariant and attractive, and every constraint holds. In the physics engine Drake, the controller resolves a conflict between the two speed references by slowing the end effector while both paths remain invariant. By contrast, a cascade with a safety filter leaves both paths. Code and animations are available at https://gradslab.github.io/am_dual_pf-/

cs.RO · eess.SY · math.OC

新论文 · v1arXiv:2611.01387

Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm

Sailesh Kamalahasan, Raghav Paladugu, Archana Khurana

原文摘要

The three-phase time minimization transportation problem partitions the origin-terminal links into three sets used in consecutive phases and minimizes the sum of the phase shipment times. Optimal solutions may leave a phase idle, as in the main example of the original study. We require every phase to carry a positive integer quantity while leaving the split of the total requirement across phases free. Discarding idle solutions from the original algorithm does not, in general, solve this variant. We prove that the optimum is attained by fixing one witness link in each of two phases and deciding the third phase by a single network flow computation, with the optimal Phase-3 time of each witness pair located by binary search. The resulting exact algorithm is strongly polynomial. It extends to any fixed number of phases, whereas, when the number of phases is part of the input, even non-idle feasibility is strongly NP-complete; feasibility alone is fixed-parameter tractable in the number of phases via known rainbow-matching results. We also characterize the minimum time of each phase. On the main example, non-idleness raises the optimum from 38 to 41. On 3,650 random instances with up to $50\times50$ links the algorithm took at most 50.2 seconds, and non-idleness raised the optimal value in 41% of the 2,250 instances with equal phase sizes; on 90 sampled instances it was faster than a mixed integer programming solver on 80 with a direct formulation and on 65 with a tighter threshold formulation.

math.OC · cs.DS

新论文 · v1arXiv:2611.01384

Benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization

Penghao Wang, Mateo Díaz, Liwei Jiang

原文摘要

Benign landscapes provide a geometric explanation for the success of iterative methods on nonconvex problems arising in data science. The landscape is benign if every local minimizer is global and every other critical point is a strict saddle. For methods that avoid strict saddles, convergence to a critical point therefore implies convergence to a global minimizer. For smooth stochastic optimization, a common strategy for establishing such landscapes proceeds in two steps: $(i)$ establish benign geometry for the population objective---which is often easier to analyze---and $(ii)$ transfer this geometry to the empirical objective using concentration of gradients and Hessians. Recent work has extended saddle-point avoidance guarantees to weakly convex nonsmooth optimization through the notion of active strict saddles. We show, however, that benign population geometry need not transfer to empirical objectives in this setting. Specifically, for robust phase retrieval with Gaussian measurements---a well-studied and highly structured problem---the population objective is benign. Nevertheless, the empirical objective has sharp spurious local minima with probability bounded away from zero as the sample size tends to infinity. This asymptotic probability lower bound is independent of the dimension.

math.OC · cs.LG

版本更新 · v3arXiv:2605.24795

Lifted Schrödinger Bridges for Gaussian Mixture Endpoints: Projection Gaps and Path-Space Obstructions

Siddhartha Ganguly, George Rapakoulias, Panagiotis Tsiotras

原文摘要

We study stochastic density control between Gaussian-mixture endpoint distributions under Brownian prior dynamics. Since the direct Schrödinger bridge between Gaussian mixtures is generally not available in closed form, we introduce a lifted path-space construction in which each trajectory is augmented with a source--target component label. Consequently, the problem decomposes into Gaussian component-to-component Schrödinger bridges with explicit marginal, drift, and cost formulas, while the mixture-level assignment reduces to a finite-dimensional entropic coupling problem with a Sinkhorn scaling form. We then analyze the projection obtained by discarding or forgetting the label. By construction, the projected law satisfies the original Gaussian-mixture endpoint constraints, but its relative entropy generally differs from the lifted relative entropy by a nonnegative conditional label-information gap. This gap reveals a path-space obstruction: the lifted optimizer cannot, in general, be identified with the direct unlabeled Schrödinger bridge after projection. We also derive the posterior-averaged Markov drift associated with the projected marginal flow, prove a kinetic-energy upper bound, and identify a common path-potential condition under which the projection gap vanishes. Several numerical illustrations showing density and shape control are recorded for a self-contained exposition.

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

版本更新 · v2arXiv:2603.26993

On the Reliability Limits of LLM-Based Multi-Agent Planning

Ruicheng Ao, Siyang Gao, David Simchi-Levi

原文摘要

LLM-based multi-agent planning delegates operational decisions to specialists that communicate through finite reports. In this research, we study its reliability limits when a coordinator can revisit source records before completing a resource-constrained plan. A useful report can support an immediate decision or direct later reading, so its value depends on how these stages communicate. We derive exact communication and access tradeoffs and prove that two report forms suffice for a broad class of allocation requirements, one favoring immediate resource identification and the other distinguishing absence from unnamed availability. For shared capacity, this reduction permits joint optimization of reporting roles and adaptive reads for a fixed number of source types with unequal workloads and reading costs. Identical specialists can optimally report different facts, and maximizing immediate completion can impose an unbounded recovery cost penalty even with full-record access. We also conduct numerical experiments to quantify the benefits of the proposed joint optimization and show how source access improves language-agent decisions that already use their reports optimally. In particular, an exhaustive evaluation of 207,632 report designs on small allocation instances recovers the predicted joint optima. Our analysis suggests that reliable agent communication should be evaluated by the complete decisions it supports and the cost of finishing its unresolved cases, instead of solely by report length, local prediction accuracy, or immediate task completion, as is often the case in current practice.

cs.MA · cs.LG · math.OC · stat.ML