跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+0新增论文
+0其中 AI 相关
+0已有论文修订
+93新增 AI 导读

arXiv 最近完成扫描：2026-11-16 01:34 · 全站最近入库：2026-11-14 15:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-15 07:00 — 2026-11-16 07:00（北京时间） · 点击数字查看对应简报；AI 相关包含在新增论文内。

最近完成检查：2026-11-16 01:34最近发现新增版本：2026-11-14 15:09库内论文最新更新时间：2026-11-13 02:59

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

23,348 已收录论文19,580 AI 相关6,729 有修订112 HF 社区发现

浏览论文库

研究日报 / 周报 →按信源浏览 →

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

找到 346 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-16 01:33（北京时间）
新论文 · v1arXiv:2611.04151

On the Role of Geometry in Solving Variational Inequalities

Ioannis Anagnostides, Ioannis Panageas, Jingming Yan

原文摘要

The geometry of constraints in variational inequalities (VIs) plays a central role in applications ranging from resource allocation and equilibrium computation to constrained optimization. Yet, its effect on computational complexity has received surprisingly little attention beyond special cases. We examine this question when the constraint set is an $\ell_p$ ball. This family of problems encompasses two of the most extensively studied classes of problems in algorithmic game theory: symmetric bimatrix games for $p = 1$ and multi-player polymatrix games for $p = \infty$. Both of these problems are known to be PPAD-complete even for affine operators. We establish a comprehensive complexity landscape for VIs over $\ell_p$ balls across the full range $p\in[1,\infty]$. First, for any $p\neq 2$, we show that finding an inverse-polynomial approximate VI solution is PPAD-complete even for affine operators. In contrast, for $p=2$, we give a polynomial-time algorithm for affine VIs, extending a classic result of Ye (1992) beyond symmetric operators. On the other hand, once the operator becomes quadratic, we establish PPAD-completeness even at inverse polynomial precision. From a technical standpoint, we develop a new toolkit for exploiting the geometry of the constraint set and the structure of the operator to characterize the complexity of equilibrium and optimization problems, which is of independent interest.

cs.CC · cs.GT · math.OC

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2609.14892

An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB

Jeff Calder, Nadejda Drenska

原文摘要

In this paper, we derive an explicit solution of the stationary prediction with expert advice PDE for five experts. The formula is given in three regions. In the first two regions, it is the four-expert solution plus a single integral with an elementary positive density. In the third region, it is a finite sum of hyperbolic products whose coefficients are determined by one scalar quadrature. Our formula establishes that the rank ordered adversary $(1,0,1,0,0)$ achieves the Hamiltonian maximum in the PDE everywhere in the ordered sector, while the COMB strategy $(1,0,1,0,1)$ is optimal only on a lower dimensional subset of the sector (where $x_1=x_2$ and $x_3=x_4$). The verification of the Hamiltonian inequalities is a tedious task, part of which is completed with a computer assisted proof. The verification reduces to 21 scalar inequalities, which we prove using 147 exact rational Bernstein polynomial certificates. The exact certificates and their independent arithmetic checks are included in a supplement to this paper, and a Lean 4 formalization machine-checks the verification and both main theorems, apart from the viscosity characterization.

math.AP · cs.GT · cs.LG · math.OC

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03945

The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients

Argyrios Deligkas, Michail Fasoulakis, Stavros D. Ioannidis

原文摘要

Computing a Karush-Kuhn-Tucker (KKT) point of a quadratic polynomial over the unit hypercube is known to be $CLS$-complete, when the coefficients of the polynomial are encoded in binary. We prove that the problem remains $CLS$-complete even when the coefficients are encoded in unary. This is the first problem proven to remain $CLS$-hard when the input is given in unary.

cs.CC · math.OC

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03598

Online Matching with Arbitrary Stochastic Rewards

Rajan Udwani

原文摘要

Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability. Each arrival allows at most one attempt and the success probabilities of its edges are revealed when it arrives. Greedy is 0.5-competitive, which is the best possible for deterministic algorithms. While better competitive ratios are known in several special cases, beating 0.5 for arbitrary probabilities has remained open. We show that, against the adaptive offline benchmark and for arbitrary probabilities, a randomized Perturbed Greedy algorithm is at least 0.591-competitive in the unweighted setting and at least 0.531-competitive with vertex weights. The perturbation functions combine Greedy with scaled versions of the classic exponential function.

cs.DS · math.OC

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03472

Tilted Convexity and an Exact Offline-Online Separation

Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn, Vaneet Aggarwal

原文摘要

Convexity has three equivalent descriptions: support by affine functions, monotonicity of the subdifferential, and increasing secant slopes. We weaken all three by one distortion with parameter $γ\in(0,1]$, which multiplies positive changes by $γ$ and divides negative ones by $γ$. The resulting classes are the convex functions at $γ=1$ and, for $γ<1$, are distinct and nested, with the parameter dropping by at most a square along the chain. For proper lower semicontinuous functions in these classes, the effective domain is convex, local minimizers are global, and the function is locally Lipschitz on the relative interior of its domain. The classes separate offline from online optimization over compact convex sets with efficient projection, with access to function values and bounded support vectors. A smooth member of any class can be minimized to additive accuracy $\varepsilon$ with $\mathrm{poly}(1/\varepsilon)$ first-order queries and projections. Online, with nonpositive losses and $α$-regret measured against $α$ times the best fixed point, a polynomial-time algorithm achieves $γ$-regret $O(\sqrt T)$ on the largest class. For every fixed, effectively specified $γ\in(0,1)$ and every $α\in(γ,1]$, no randomized polynomial-time algorithm has sublinear expected $α$-regret unless $\mathbf{NP}=\mathbf{RP}$, already for smooth concave polynomial losses in the smallest class, each minimized by one linear optimization. Thus, unless $\mathbf{NP}=\mathbf{RP}$, $γ$ is the exact online coefficient of each class, while the offline coefficient is one.

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

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03466

A Bayesian Framework for Safe Optimal Control of Unknown Systems from Input-Output Data

Robert Lefringhausen, Annalena Daniels, Michael Fink, Sandra Hirche

原文摘要

As control engineering is applied to increasingly complex systems, learning-based control, which uses empirical data to reduce the reliance on first-principles models, has emerged as a promising paradigm. However, such approaches must cope with nonlinear and stochastic dynamics, the absence of state measurements, and scarce data, while ensuring safe operation under constraints, which requires rigorous uncertainty quantification. Whereas existing methods treat these challenges in isolation, this article proposes a Bayesian framework that jointly addresses them. A prior in state-space form is updated from input-output data using particle Markov chain Monte Carlo methods, yielding a representation of joint uncertainty over dynamics and latent states. Building on this representation, a validation procedure is developed that provides probabilistic guarantees for constraint satisfaction under arbitrary causal control laws. For control synthesis, a formulation penalizing the conditional value-at-risk of the constraint function is proposed, together with an adaptive calibration mechanism that adjusts the performance-robustness trade-off to achieve a desired robustness level. The probability of successful certification is characterized theoretically. The framework is extended to a receding-horizon setting, where posterior updates from new measurements allow the controller to progressively reduce uncertainty and improve performance. The approach is demonstrated on the optimal control of a vertical farm.

eess.SY · cs.LG · math.OC

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2601.06514

Inference-Time Alignment for Diffusion Models via Variationally Stable Doob's Matching

Jinyuan Chang, Chenguang Duan, Yuling Jiao, Ruoxuan Li, Yi Xu, Jerry Zhijian Yang

原文摘要

Inference-time alignment for diffusion models aims to adapt a pre-trained reference diffusion model toward a target distribution without retraining the reference score network, thereby preserving the generative capacity of the reference model while enforcing desired properties at inference time. A central mechanism for achieving such alignment is guidance, which modifies the sampling dynamics through an additional drift term. In this work, we introduce variationally stable Doob's matching, a novel framework for provable guidance estimation grounded in Doob's $h$-transform. Our approach formulates guidance as the gradient of the logarithm of an underlying Doob's $h$-function and employs gradient-regularized regression to simultaneously estimate both the $h$-function and its gradient, resulting in a consistent estimator of the guidance. Theoretically, we establish non-asymptotic convergence rates for the estimated guidance. Moreover, we analyze the resulting controllable diffusion processes and prove non-asymptotic convergence guarantees for the generated distributions in the Wasserstein-2 distance. Finally, we show that variationally stable guidance estimators are adaptive to unknown low dimensionality, effectively mitigating the curse of dimensionality under low-dimensional linear subspace assumptions. Numerical experiments demonstrate the effectiveness of our proposed method and show the advantages compared to the baselines.

stat.ML · cs.LG · math.NA · math.OC · math.ST

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2501.19214

A SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization

Wei Liu, Yangyang Xu

原文摘要

Many real-world problems, such as those with fairness constraints, involve complex expectation constraints and large datasets, necessitating the design of efficient stochastic methods to solve them. Most existing research focuses on cases with no {constraint} or easy-to-project constraints or deterministic constraints. In this paper, we consider nonconvex nonsmooth stochastic optimization problems with expectation constraints, for which we build a novel exact penalty model. We first show the relationship between the penalty model and the original problem. Then on solving the penalty problem, we present a single-loop SPIDER-type stochastic subgradient method, which utilizes the subgradients of both the objective and constraint functions, as well as the constraint function value at each iteration. Under certain regularity conditions (weaker than Slater-type constraint qualification or strong feasibility assumed in existing works), we establish an iteration complexity result of $O(ε^{-4})$ to reach a near-$ε$ stationary point of the penalized problem in expectation, matching the lower bound for such tasks. Building on the exact penalization, an $(ε,ε)$-KKT point of the original problem is obtained. For a few scenarios, our complexity of either the {objective} sample subgradient or the constraint sample function values can be lower than the state-of-the-art results by a factor of $ε^{-2}$. Moreover, on solving two fairness-constrained problems and a multi-class Neyman-Pearson classification problem, our method is significantly (up to 466 times) faster than the state-of-the-art algorithms, including switching subgradient method and inexact proximal point methods.

math.OC · cs.CC · cs.LG · math.NA

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
版本更新 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
版本更新 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
版本更新 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
版本更新 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
版本更新 · 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

查看论文
arXiv ↗PDF ↗
版本更新 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
版本更新 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗
新论文 · 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

查看论文
arXiv ↗PDF ↗