跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

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

统计口径与数据新鲜度

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

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

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

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

浏览论文库

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

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

找到 346 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-15 10:50（北京时间）
版本更新 · v2arXiv:2611.02267

Overcoming Demand Censoring through Randomization for Risk-Sensitive Newsvendor Learning

Zhengchao Wang, Nam Ho-Nguyen

原文摘要

We study online newsvendor learning with bounded demand, censored observations, and convex nonlinear shortage costs. Because stockouts can conceal the shortage magnitudes needed by gradient-based algorithms, we use randomized ordering to construct unbiased subgradient estimates. We characterize admissible randomization distributions within this framework and develop an online inventory policy that combines the resulting subgradient estimates with gradient-based updates. Our regret analysis quantifies the cost of randomization via the estimation variance and an additional loss term. We characterize the randomization distributions that minimize this objective. For piecewise-linear shortage costs, the optimal distribution is computed through a linear-time recursion; for costs with bounded curvature density, it is characterized by a scalar ordinary differential equation. The policy achieves expected regret of $O(T^{2/3})$ against the best fixed order in hindsight over $T$ periods. Under independent demand and suitable curvature of expected losses, the bound improves to $O(\sqrt{T})$. Matching minimax lower bounds establish rate optimality over the corresponding classes with a fixed marginal-cost bound. Both rates extend to nonperishable inventory under uniformly positive conditional expected demand. Numerical experiments on synthetic and retail data show improvements over alternative policies using censored observations.

cs.LG · math.OC

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

Resolvent Ellipsoid for Minty Set Inclusions

Ashkan Soleymani, Gabriele Farina, Patrick Jaillet

原文摘要

We study Minty set inclusion on a compact convex set $\mathcal{X} \subseteq \mathbb{R}^d$ with a set-valued operator $A : \mathcal{X} \rightrightarrows \mathbb{R}^d$. Under the Minty promise, the goal is to compute $x \in \mathcal{X}$ and $u \in A(x)$ such that $\sup_{y \in \mathcal{X}} \langle u, x - y \rangle \le \varepsilon$. Our approach is geometric and we work in the fixed-scale constrained-resolvent oracle model, where a query at anchor $a$ is assumed to return a resolvent point $x^+$ together with the Yosida vector $g_η(a) = (a - x^+)/η$. We prove that each oracle response yields a sharp dichotomy: either the returned point provides an $\varepsilon$-SVI certificate, or the Yosida vector defines a strict separating normal for the Minty set. Thus, a single black-box resolvent query supplies either a certified candidate solution or a valid geometric cut. Combining this separation principle with the ellipsoid method, we obtain RESOLVENT-ELLIPSOID, an algorithm that computes an $\varepsilon$-SVI in $\mathcal{O}\!\left(\operatorname{poly}(d, \log(1/\varepsilon))\right)$ black-box oracle calls to the fixed-scale constrained resolvent. For monotone inclusions, our algorithm gives, to our knowledge, the first $\mathcal{O}\!\left(\mathrm{poly}(d, \log(1/\varepsilon))\right)$ black-box guarantee in the fixed-scale resolvent model.

cs.LG · math.OC

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2602.20398

Competition Versus Complexity in Multiple-Selection Prophet Inequalities

Eugenio Cruz-Ossa, Sebastian Perez-Salazar, Victor Verdugo

原文摘要

Competition complexity formalizes a compelling intuition: rather than refining the mechanism, how much additional competition is sufficient for a simple mechanism to compete with an optimal one? We begin the study of this question in multi-unit pricing for welfare maximization using prophet inequalities. An online decision-maker observes $m \geq k$ nonnegative values drawn independently from a known distribution, may select up to $k$ of them, and aims to maximize the expected sum of selected values. The benchmark is a prophet who observes a sequence of length $n \geq k$ and selects the $k$ largest values. We focus on the widely adopted class of single-threshold algorithms and fully characterize their $(1-\varepsilon)$-competition complexity. Notably, our results reveal a sharp competition-induced phase transition: in the absence of competition, single-threshold algorithms are fundamentally limited to a $1-1/\sqrt{2kπ}$ fraction of the prophet value, whereas even a $1\%$ multiplicative increase beyond $n$ observations suffices to achieve a $1-\exp(-Θ(k))$ fraction. Another notable result happens when $k=1$: we show that the $(1-\varepsilon)$-competition complexity is exactly $\ln(1/\varepsilon)$, fully resolving an open question by Brustle et al. [Math. Oper. Res. 2024]. Our analysis is based on infinite-dimensional linear programming and duality arguments.

cs.GT · math.OC

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

Recursive Pricing and Incumbent Subtree Column Generation for Solving Optimal Classification Trees

Tengmu Hu, Chen Chen, Theodore T. Allen

原文摘要

Solving optimal classification tree (OCT) problems is computationally challenging because branching, routing, and leaf-assignment decisions must be optimized jointly. We develop an incumbent subtree column generation algorithm (ISCG-OCT) that exploits the recursive structure of classification trees. We first introduce a mixed set-packing and set-partitioning formulation (MSSF). We then construct a restricted master problem whose columns represent feasible subtree patterns. Unlike conventional dual-based column generation, our incumbent-centered pricing evaluates objective improvements relative to the current solution. We establish a recursive decomposition in which fixing a branching decision separates the remaining pricing problem into independent subtree subproblems, enabling exact dynamic programming. We also develop threshold-based variants that trade optimality guarantees for computational efficiency. Computational experiments on 27 benchmark datasets demonstrate competitive training and testing accuracy and substantial reductions in solution time on many instances. When initialized with a CART solution, ISCG-OCT can certify global optimality faster than warm-started mixed-integer programming solvers on selected instances. These results demonstrate how recursive pricing and structured subtree optimization can improve the computational efficiency of exact classification tree methods.

math.OC · cs.LG

查看论文
arXiv ↗PDF ↗
版本更新 · v5arXiv:2410.02583

Sample-Efficient Quantum State Tomography for Structured Quantum States in One Dimension

Zhen Qin, Casey Jameson, Alireza Goldar, Michael B. Wakin, Zhexuan Gong, Zhihui Zhu

原文摘要

In this paper, we answer this fundamental question affirmatively by using a class of informationally complete positive operator-valued measures (IC-POVMs), including symmetric IC-POVMs (SIC-POVMs) and spherical $t$-designs, focusing on sample complexity while not accounting for the implementation complexity of the measurement settings. For SIC-POVMs and spherical 2-designs, we show that the number of state copies to guarantee bounded recovery error of an MPO state with a constrained least-squares estimator depends on the probability distribution of the MPO under the POVM but scales only linearly with $n$ when the distribution is approximately uniform. For general spherical $t$-designs with a sufficiently large $t$, we prove that only a number of state copies proportional to the number of independent parameters in the MPO is sufficient for a guaranteed recovery of any state represented by an MPO. In addition, we establish a sample complexity lower bound based on the Cramer-Rao bound, showing that, for strictly positive definite MPO states and unbiased estimators, a number of state copies proportional to the number of independent parameters in the MPO is also necessary, although the upper and lower bounds do not yet match in their dependence on the target accuracy. Furthermore, we propose a spectral method and a projected gradient descent (PGD) algorithm to solve the constrained least-squares problem, both equipped with rigorous recovery error guarantees.

quant-ph · cs.IT · eess.SP · math.OC

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

A Stability Analysis of AdamW: Unstable Equilibria and Non-Convergence

Baiyu Su, Lizhang Chen, Qiang Liu

原文摘要

AdamW is ubiquitous in deep learning, yet its behavior remains poorly understood. We analyze its dynamics through the lens of dynamical systems and show that AdamW admits an implicit fixed-point objective: its fixed points coincide with the stationary points of a constrained and regularized optimization problem. However, not all of these fixed points are stable under AdamW's dynamics, and stability depends sensitively on curvature, weight decay, and momentum parameters. Even in one-dimensional settings, equilibria may be unstable, and trajectories can exhibit persistent oscillations rather than convergence to them. We further extend the analysis to higher dimensions, deriving sufficient conditions for local stability of the continuous-time dynamics, and propose a convergent modification that preserves AdamW's fixed points. These results clarify what optimization problem AdamW is associated with, when its convergence can be expected, and how its dynamics could inspire more reliable optimizers.

cs.LG · math.OC · stat.ML

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2609.30212

Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

Ruichen Jiang, TaeHo Yoon

原文摘要

We characterize, up to logarithmic factors, the optimal higher-order oracle complexity of finding approximate solutions to composite monotone inclusion problems, formed by the sum of a smooth single-valued monotone operator and a maximal monotone set-valued operator. We introduce the Anchored Extra-Proximal (AEP) framework, which combines an anchored extrapolation step with an inexact anchored proximal update satisfying a relative-error condition. This framework recovers the composite Fast Extragradient method in the first-order setting and yields natural higher-order extensions through Taylor approximations of the smooth operator at the extrapolated point. For every $p\geq 2$, assuming that the $(p-1)$th derivative of the single-valued operator is $L_p$-Lipschitz continuous and the initial distance to a solution is at most $R$, we combine AEP with a bisection line search to obtain a $p$th-order method that attains a tangent residual of at most $\varepsilon$ in $\widetilde{O}((L_p R^{p}/\varepsilon)^{\frac{2}{3p-1}})$ oracle calls. We complement this result with a worst-case lower bound of $Ω((L_p R^p/\varepsilon)^{\frac{2}{3p-1}})$ for every deterministic algorithm in the $p$th-order oracle model, without imposing any prescribed update structure. For the subclass of smooth nonexpansive fixed-point problems, we further establish a lower bound of $Ω(\min\{R/\varepsilon, {(L_p R^{p}/\varepsilon)}^{\frac{2}{3p-1}}\})$. By choosing between AEP and Halpern iteration, we match this lower bound up to logarithmic factors, thereby also settling the deterministic oracle complexity of smooth nonexpansive fixed-point problems.

math.OC · cs.LG · stat.ML

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.41558

A complete analytical characterization of optimal collision-free motion for two robots

Jan Kamm, Antonio Terpin, Raffaello D'Andrea

原文摘要

Collision-free motion planning for multi-agent robotic systems remains an active research area because of the complexity of coordinating robot trajectories, with applications ranging from coordinated drone shows to autonomous operations on land, in the air, and on water. Importantly, the analytical difficulty of nonconvex collision-avoidance constraints has so far driven the development of exclusively numerical methods. We derive a complete analytical characterization of the optimal trajectories for two robots with zero initial and final velocities, under double-integrator dynamics and a squared-acceleration objective. We prove that these trajectories belong to eight distinct contact families and determine which family applies for each configuration of initial and final positions. We analyze the geometrical properties of the optimal trajectories and provide a numerical algorithm for computing them. These insights have already been adopted to improve the performance of numerical methods for multi-agent motion planning by several orders of magnitude.

cs.RO · eess.SY · math.OC

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

Orthogonal Updates for the Win: Towards Accelerated Adaptive Minimax Optimization

Zhiwei Zhai, Xinyu Wang, Wenjing Yan, Lei Ding, Ying-Jun Angela Zhang

原文摘要

Single-loop minimax methods are appealing for modern machine learning, but standard stochastic gradient updates can be unstable and oscillatory under tightly coupled primal-dual dynamics, making performance notoriously sensitive to stepsizes. To fundamentally improve stability, we develop an orthogonal update framework tailored to minimax optimization, which applies updates along orthogonalized directions to reduce update anisotropy. However, orthogonalization reshapes the optimization geometry and makes coordinating primal-dual stepsizes even more delicate. To overcome this challenge, we develop AdaSGDA, which equips orthogonal updates with an adaptive stepsize rule driven by accumulated gradient norms. This mechanism automatically balances coupled primal-dual progress under orthogonalization, yielding an effectively parameter-free method for nonconvex-strongly-concave minimax optimization. We prove that AdaSGDA avoids problem-dependent tuning while attaining the state-of-the-art $\mathcal{O}\left(T^{-1/4}\right)$ convergence rate. We further propose AdaSGDA-VR, which incorporates a carefully designed variance reduction scheme and achieves the faster $\mathcal{O}\left(T^{-1/3}\right)$ rate. Extensive experiments demonstrate that our methods deliver competitive performance compared to existing minimax optimization methods.

cs.LG · math.OC · stat.ML

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

Linear Objective Problems: A Complexity Framework for Bilevel Optimization

Christoph Grüne, James B. Orlin, Lasse Wulf

原文摘要

Many bilevel and robust optimization problems are complete for the second level of the polynomial hierarchy, but such results are usually proven one problem at a time with problem-specific reductions. A recurring obstacle is that the lower level must select an optimal solution rather than merely a feasible one, whereas standard reductions preserve only whether a solution exists, not which solutions are optimal. We introduce linear objective problems (LOP), a framework for optimization problems whose solutions are explicit subsets of a ground set and whose objective is linear in these elements. We define tight solution-embedding reductions, which map the optimal solutions of one problem element by element onto the optimal solutions of another, without having to recognize optimal solutions, which is coNP-hard in general. This gives a notion of LOP-completeness, with Satisfiability as the canonical complete problem, even with unit weights. We show that many classical problems are LOP-complete, including Vertex Cover, Dominating Set, TSP, Knapsack, and Steiner Tree, and we introduce a duality that transfers LOP-completeness between minimization and maximization problems. As our main application, we prove a meta-theorem for min-max regret optimization under interval uncertainty: for every LOP-complete problem, the min-max regret version is $Σ_2^p$-complete. Instead of a separate proof for each nominal problem, it suffices to show that the nominal problem is LOP-complete. This recovers known results for the interval min-max regret versions of Knapsack and Maximum Benefit Set Cover and yields completeness for over 50 further problems.

cs.CC · cs.DM · math.CO · math.OC

查看论文
arXiv ↗PDF ↗
版本更新 · v4arXiv:2512.17473

Alternating Direction Method of Multipliers for Nonlinear Matrix Decompositions

Atharva Awari, Nicolas Gillis, Arnaud Vandaele

原文摘要

We present an algorithm based on the alternating direction method of multipliers (ADMM) for solving nonlinear matrix decompositions (NMD). Given an input matrix $X \in \mathbb{R}^{m \times n}$ and a factorization rank $r \ll \min(m, n)$, NMD seeks matrices $W \in \mathbb{R}^{m \times r}$ and $H \in \mathbb{R}^{r \times n}$ such that $X \approx f(WH)$, where $f$ is an element-wise nonlinear function. We evaluate our method on several representative nonlinear models: the rectified linear unit activation $f(x) = \max(0, x)$, suitable for nonnegative sparse data approximation, the component-wise square $f(x) = x^2$, applicable to probabilistic circuit representation, and the MinMax transform $f(x) = \min(b, \max(a, x))$, relevant for recommender systems. The proposed framework flexibly supports diverse loss functions, including least squares, $\ell_1$ norm, and the Kullback-Leibler divergence, and can be readily extended to other nonlinearities and metrics. We illustrate the applicability, efficiency, and adaptability of the approach on real-world datasets, highlighting its potential for a broad range of applications.

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

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

CVaR Deep Optimal Stopping

Yechan Jeong, Youngjoon Hong

原文摘要

Risk-sensitive optimal stopping is useful when poor stopping outcomes carry substantial costs, as in option exercise, sequential medical treatment, and safety-critical control. A natural objective is Conditional Value at Risk (CVaR) of the stopped reward. We develop a theoretical framework and algorithm for CVaR deep optimal stopping. The framework and algorithm address four difficulties in applying risk-sensitive reinforcement learning to optimal stopping: state augmentation, score-function pathology, blindness to success, and dependence on auxiliary networks. We isolate three structural properties of optimal stopping: single-point reward, action-independent dynamics, and sum-zero gradient. We exploit these properties to establish Markov optimality without state augmentation and derive a pathwise gradient estimator. Under bounded policy derivatives, the pathwise estimator has bounded second moments near deterministic policies, avoiding the divergence that can occur with score-function estimators. Building on this framework, we propose DIOS (Distribution-Informed Optimal Stopping) to address the remaining two difficulties. A per-time-step soft penalty combined with tail-level annealing mitigates blindness to success. Estimating the reward quantile directly from each batch removes the need for an auxiliary critic. For a fixed tail level, we establish a finite-time stationarity guarantee under regularity assumptions along the training iterates. Across the 24 main Bermudan max-call configurations, DIOS achieves the highest mean CVaR and the shortest recorded training time among the tested CVaR baselines.

math.OC · cs.LG

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2601.20983

Monotone Optimisation with Learned Projections

Ahmed Rashwan, Keith Briggs, Chris Budd, Lisa Kreusser

原文摘要

Optimisation algorithms typically assume oracle access to objectives and constraints, yet in many applications these functions are available only through data. To recover them, a common approach learns a surrogate for each function and optimises over it, but this can be unnecessarily expensive and may fail to preserve the structure required by the optimisation algorithm. We study this problem for monotone optimisation, a class of non-convex problems which can be solved globally using the Polyblock Outer Approximation (POA) algorithm. Our key observation is that POA does not require the constraint functions themselves, but only a scalar quantity we call the radial inverse. Learning this quantity directly replaces POA's inner bisection loop over a learned constraint with a single radial inverse evaluation. We characterise exactly which maps arise as radial inverses of monotone constraints, and relate their approximation error to perturbations of the feasible set and optimal objective value. Building on these results, we introduce Homogeneous-Monotone Radial Inverse (HM-RI) networks, structured min-max models that enforce the monotonicity and positive-homogeneity of radial inverses by construction. Across synthetic monotone optimisation problems and a cellular transmit-power application, HM-RI improves solution quality over direct constraint surrogates and local optimisation baselines by up to 58.6 percentage points relative to the Oracle reference objective, while achieving a 3.0-4.7x speed-up over bisection-based POA with learned constraint surrogates, with the largest solution-quality gains occurring in data-limited and piecewise-constant settings.

cs.LG · math.OC

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2609.09108

Distributed Linear Programming on GPU Clusters at Extreme Scale

Arnaud Deza, Santanu S. Dey, Pascal Van Hentenryck

原文摘要

Large linear programs can exceed the memory of a single compute node. Although first-order methods replace sparse factorizations with GPU-suited matrix-vector products, other solver phases can reintroduce a single-node memory limit. We present SHARDLP, a distributed GPU LP solver that keeps the matrix and primal-dual state partitioned from sharded input through solution output. On the Google PDLP benchmark, SHARDLP solves ten of eleven instances, compared with eight in the published CPU PDLP study. On the largest benchmark, eight H200 GPUs solve a 1.185-billion-variable, 6.338-billion-nonzero LP in 9.9 minutes; the published CPU experiment reports 21.06 hours on different hardware. Beyond this benchmark, separately checked multi-node solves reach up to 13.604 billion variables and 40.807 billion nonzeros, while validated executions span up to 76 GPUs across 29 compute nodes. For column-partitioned solves, support-aware communication skips GPUs that store no coefficients for a row; on an LP with 2.76 billion nonzeros, it cuts modelled communication by 92.97% and improves solver time by 1.27x-1.52x. The code for SHARDLP is available at https://github.com/ArnaudDeza/ShardLP.

math.OC · cs.DC

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

Variance-Reduced Stochastic Hessian-Driven Nesterov Acceleration with Adam-Style Preconditioning

Yaxin Yu, Long Chen, Minfu Feng

原文摘要

Stochastic first-order methods use sampled gradients to reduce per-iteration costs, but estimation errors can slow convergence and, in some settings, cause divergence. To improve gradient accuracy while retaining acceleration, we develop scalar and diagonal versions of VR-Adam-SHANG for smooth stochastic convex optimization. The methods combine STORM-type recursive estimation, Adam-style preconditioning, and SHANG's accelerated interpolation and correction, using at most two stochastic gradient evaluations per iteration without full-gradient refreshes. Under unbiased sampling, bounded variance, and mean-square smoothness of gradient noise, polynomial steps with prescribed initialization yield $O(1/K)$ mean-square gradient-estimation error and expected objective-gap bounds combining $O(1/K^2)$ initial-energy decay with an $O(1/\sqrt K)$ stochastic term after $K$ iterations. These guarantees require neither monotonicity of the preconditioner nor a uniform positive lower bound on its eigenvalues. The analysis also establishes polynomial-step convergence of projected nonrecursive Adam-SHANG-s, filling a gap in its original theory. Experiments compare the methods at matched sample-gradient budgets. In every tested setting, at least one of the two versions achieves the lowest mean terminal objective gap among all compared methods.

math.OC · cs.LG · math.NA

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

Chatter Attack: Resource Consumption Attack for Large Language Models

Yibo Miao, Yichuan Cao, Xiao-Shan Gao, Yinpeng Dong

原文摘要

LLMs are powerful but incur substantial inference cost, which can be exploited by malicious users to induce overly long outputs, increasing latency and operational expense. Prior resource consumption attacks either coerce repetition or suppress the end-of-sequence token by lowering its logit value. However, with autoregressive, sampling-based generation, the search space grows exponentially with length and small deviations or unstable trajectories can derail optimization, limiting attack effectiveness and stability. To address this issue, we introduce Chatter Attack, a novel class of resource consumption attacks that optimize adversarial prompts to induce predefined short target phrases, thereby avoiding search-space explosion while still eliciting long responses. Specifically, Chatter Attack triggers self-doubt using short doubt-inducing phrases as the target, and sustains this state throughout generation via inference attention loss and global entropy loss. To extend to black-box settings, we further propose a novel Bayesian Prompt Optimization (BPO) method, which models the objective function globally by constructing a discrete token kernel, efficiently exploring the entire search space using prior information. Extensive experiments across multiple models and datasets show that our method outperforms baselines, with maximum response length increases to 31.5$\times$, and revealing practical resource-depletion risks for real-world LLM inference services.

cs.LG · cs.AI · cs.CR · cs.CV · math.OC

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2605.26373

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos, Ioannis Panageas, Antonios Varvitsiotis

原文摘要

We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding $\mathcal{O}(T^{2/3})$ regret. They left open whether the optimal $Θ(\sqrt{T})$ regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves $\mathcal{O}(\sqrt{T})$ regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu and Hazan (2022) by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that OGD suffers $Ω(T)$ regret even with a stepsize of order $1/\sqrt{T}$, for a smooth Hessian incompatible reparameterization between convex domains and an adversarial sequence of hidden-convex losses. Finally, we extend our analysis to one-point bandit feedback and prove a $\mathcal{O}(T^{3/4})$ expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.

cs.LG · math.OC · stat.ML

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

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses

Yuhan Ye

原文摘要

We study the parameterized complexity of testing approximate first-order stationarity at a prescribed point for continuous piecewise-affine (PA) functions, a basic task in nonsmooth optimization. PA functions form a canonical model for nonsmooth stationarity testing and capture the local polyhedral geometry that appears in ReLU-type training losses. Recent work of Tian and So (2025) shows that testing approximate stationarity notions for PA functions is computationally intractable in the worst case, and identifies fixed-dimensional tractability as an open direction. We address this direction from the viewpoint of parameterized complexity, with the ambient dimension $d$ as the parameter. In this paper, we give XP algorithms in fixed dimension for the tractable sides, and prove W[1]-hardness for the complementary sides. Moreover, lower bounds under the parameterized $k$-Clique hypothesis rule out deterministic algorithms running in time $ρ(d)s^{o(d)}$ for any computable function $ρ$, where $s$ denotes the total binary encoding length of the instance. As a further consequence, our results yield the corresponding parameterized complexity picture for testing local minimality of continuous PA functions. We also extend our hardness results to a family of shallow ReLU CNN training losses, tested in the trainable weight space. Thus, the same parameterized-complexity picture also appears for simple CNN training losses. Notably, our lower bounds assume that $k$-Clique on $N$-vertex graphs admits no deterministic $ρ(k)N^{o(k)}$-time algorithm for any computable function $ρ$. The recent refutations of the Exponential Time Hypothesis (ETH) (OpenAI, 2026) and the stronger fine-grained $k$-Clique hypothesis (Vassilevska Williams and Zamir, 2026) do not contradict this assumption.

math.OC · cs.CC · cs.LG

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

Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead

Vaneet Aggarwal

原文摘要

Elements arrive one at a time, and after each arrival an algorithm holds a set of at most $k$ arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that $k$ arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of $k$ and of the number $n$ of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is $2-\sqrt{2}\approx0.5858$. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to $1-1/e\approx0.6321$, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds $1-1/e$, even when all elements are available at once. For every $\varepsilon>0$, a deterministic algorithm that sees the next $\lceil\varepsilon k/3\rceil$ arrivals keeps a set of value at least $1-1/e-\varepsilon$ times the optimum at every time, changes $O(\varepsilon^{-3})$ elements per arrival and makes $(n+1)^{O(\varepsilon^{-2})}$ evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with $O(\varepsilon^{-2})$ changes per arrival. A randomized algorithm with the same short lookahead makes $O(n^2k)$ evaluations, changes $O(\varepsilon^{-2})$ elements per arrival, and attains the same ratio in expectation at each fixed time. The main tool is a greedy algorithm with an explicit guarantee for each of its partial solutions combined with each initial segment of the known future arrivals. A second tool moves between two such solutions one element at a time while keeping the value high, and the deterministic algorithm times each move using upper bounds on the optimum from failed searches.

cs.DS · cs.LG · math.OC

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

Scalable Neural Safety Certification via Monotonicity

Amirreza Alavi, Majid Zamani, Saber Jafarpour

原文摘要

Learning-based safety certification offers a promising route for verifying complex dynamical systems when explicit models are unavailable, but existing data-driven methods often scale poorly: they treat the system as a black box, rely on dense discretizations or Lipschitz bounds, and consequently suffer from sample complexity that grows exponentially with dimension. This paper shows that a common structural property of dynamical systems--monotonicity--can be used to break this curse of dimensionality. We develop a data-driven framework for robust safety verification and safe controller synthesis for unknown monotone systems using only simulator queries. Our main theoretical result proves that, for monotone systems with upper-closed unsafe sets, safety is completely characterized by the existence of monotone inductive barrier certificates. This structure reduces certificate verification over continuous state spaces to localized boundary checks over finitely many cells. To learn such certificates, we introduce Max-Monotone Networks, a monotone neural architecture with universal approximation guarantees for monotone functions. We then propose a training and refinement algorithm that, upon successful termination, returns formally valid neural barrier certificates and, under mild partition assumptions, requires only $O(n)$ simulator queries. Across high-dimensional benchmarks, including oscillator networks with up to $13{,}659$ states and traffic networks with $1{,}000$ states, our method certifies safety in regimes where prior approaches either do not converge or exceed memory limits. These results demonstrate that exploiting order structure can make neural safety certification both scalable and formally sound.

eess.SY · cs.LG · math.OC

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

Large-Scale Hierarchical Decision-Making in Robot Control via ADMM

Kai Pfeiffer, Jia Wang, Gordon Owusu Boateng, Yuquan Wang, Vincent Bonnet, Abderrahmane Kheddar

原文摘要

Sparse hierarchical nonlinear programming (SH-NLP) based on the $\ell_0$-norm provides a powerful framework for integrated, efficient hierarchical decision-making in robot kinematic control, for example in the presence of a large set of possible end-effector candidate locations. While Sequential Sparse Hierarchical Quadratic Programming (S-SHQP) with interior-point method based SHQP sub-problem solvers exploit the hierarchical, sparse structure of such problems, they are less amenable to effective warm-starting between subsequent, coherent control steps. In this work, we formulate an Alternating Direction Method of Multipliers (ADMM) to efficiently solve related SHQP sub-problems. We introduce efficient substitutions for auxiliary variables representing $\ell_0$-norm surrogates. The solver efficiently handles separable decision functions by evaluating linear algebra expressions in the appropriate order. Results in large-scale kinematic and dynamic control show reduced computation times of up to 23.5% compared with a structure-exploiting interior-point method in low- to moderate-accuracy regimes. Furthermore, hierarchical decision-making is extended to whole-body dynamic control for humanoid walking, where the need for high-accuracy solutions is highlighted.

cs.RO · math.OC

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.05516

Distributed Learning of $α$-Potential Functions in Strategic Multi-agent Systems

Yifei Chen, Chinmay Maheshwari

原文摘要

We study the problem of computing the tightest \(α\)-potential approximation of a general-sum game over continuous action spaces, within a prescribed class of potential functions and when each player has access only to its own utility function. The difficulty is twofold: the approximation error involves a worst-case search over an infinite set of unilateral deviations, and the required utility information is distributed across players. For a linear-in-parameters potential class, we use an exact finite-tuple reformulation that separates the problem into a global outer search over deviation tuples and distributed convex inner problems. We develop a primal--dual inner oracle tailored to this structure and establish a uniform one-sided accuracy guarantee. This oracle can be combined with global outer search to obtain an end-to-end guarantee on the outer optimization error. We also develop a projected zeroth-order outer method as a computationally lighter alternative for higher-dimensional problems. Numerical experiments illustrate the accuracy--computation tradeoff between the two outer-search methods and show that the proposed optimization framework can improve upon analytical \(α\)-potential constructions.

cs.MA · cs.GT · eess.SY · math.OC

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

Parametrize Integer Programming by Packing Imbalanced Circuits

Yuheng Shi

原文摘要

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

math.OC · cs.DS

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2510.00569

Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifold

Ke Xu, Yuefeng Han

原文摘要

Recovering a low-CP-rank tensor from noisy linear measurements is a central challenge in high-dimensional data analysis, with applications spanning tensor PCA, scalar-on-tensor regression, tensor-on-tensor regression, and beyond. We exploit the intrinsic geometry of rank-one tensors by casting the recovery task as an optimization problem over the Segre manifold, the smooth Riemannian manifold of rank-one tensors. This geometric viewpoint yields two powerful algorithms: Riemannian Gradient Descent (RGD) and Riemannian Gauss-Newton (RGN), each of which preserves feasibility at every iteration. Under mild noise assumptions, we prove that RGD converges at a local linear rate, while RGN exhibits an initial local quadratic phase followed by linear refinement to the statistical error. Extensive synthetic experiments validate these convergence guarantees and demonstrate the practical effectiveness of our methods.

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

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2609.24593

Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

Michel Grabisch and. Hans Raj Tiwary

原文摘要

We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

cs.GT · cs.CC · math.CO · math.OC

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

Optimal Byzantine-resilient Federated Learning with User-level Differential Privacy

Ming Xiang, Stratis Ioannidis, Edmund Yeh, Carlee Joe-Wong, Lili Su

原文摘要

Real-world deployment of federated learning (FL) requires resilience against adversarial clients and data privacy. Byzantine fault captures the worst-case behavior of adversarial clients, while differential privacy (DP) provides statistical guarantees against privacy loss. In particular, user-level DP guards a client's entire contribution and provides more realistic protection against information leakage. Despite intensive efforts, the minimax-optimal convergence bound of Byzantine-resilient FL with user-level DP remains open. We establish an information-theoretic lower bound for any Byzantine-resilient empirical risk minimization problem under user-level DP and heterogeneous clients. We propose ByzULDP, a central DP algorithm featuring a two-level momentum across the client and server. Client-side momentum mitigates stochastic gradient variance during robust aggregation. Unlike the fault-free case, naively combining non-linear Byzantine-resilient aggregation with central DP noise can be insufficient to guarantee convergence to a bounded neighborhood of a stationary point. Our key contribution is a server-side momentum that leverages a property specific to user-level DP, where privacy sensitivity depends on how client updates are constructed, to empower convergence. ByzULDP achieves the order-optimal convergence bound for strongly-convex objectives, with vanishing error terms decaying at the optimal $O(1/T)$ and $O(1/\sqrt{T})$ rates for strongly-convex and non-convex objectives, respectively. We corroborate our analysis with numerical experiments on real-world datasets across diverse privacy budgets.

cs.LG · cs.DC · math.OC

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

Online Imitation Learning for Stabilizing Vlasov--Poisson Plasmas

Xiaofan Xia, Qin Li, Wenlong Mou

原文摘要

We study the problem of controlling instability in the Vlasov--Poisson plasma systems, a fundamental challenge for nuclear fusion control. Motivated by the partial observability of plasma states in practice, we investigate imitation learning algorithms that learn from a fully-observable expert controller, but operate under macroscopic measurements. We theoretically establish a separation between online and offline imitation learning --- even a small behavior cloning error leads to error compounding that exponentially amplifies instability over time. By way of contrast, the online imitation learning loss can polynomially control the stability of rollout trajectories. We then propose a DAgger-style algorithm that learns the stabilizing controller under partial observability. Simulation results on a 1D Vlasov--Poisson system demonstrate that our algorithm can effectively stabilize plasma instabilities over longer time horizons than behavior cloning.

cs.LG · math.OC · physics.plasm-ph

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2606.13825

Scalable Deep Unfolding of Conic Optimizers

Alex Oshin, Rahul Vodeb Ghosh, Evangelos A. Theodorou

原文摘要

Deep unfolding (DU) accelerates iterative optimizers by training learnable components through unrolled iterations, but extending DU to the large-scale semidefinite programs (SDPs) common in robotics has remained limited. Unrolling a full-update conic solver such as COSMO exposes two obstacles: backpropagating through the per-iteration linear-system solve incurs memory quadratic in the problem size when the coefficient matrix is formed explicitly, and backpropagating through the positive semidefinite (PSD) cone projection is numerically unstable under repeated eigenvalues. We address the first with a matrix-free implicit differentiation rule that reduces memory from $O(n^2)$ to $O(n + \mathrm{nnz}(A))$, and the second with a stable backward rule based on the Dalečkii--Krein representation of the Fréchet derivative. Together, these enable learning lightweight hyperparameter policies and warm starts for COSMO. On standalone SDPs and second-order cone programs, ranging from max-cut and Lovász $\vartheta$ to robust estimation and control, the learned policies outperform tuned COSMO on every problem class, reducing iterations to tolerance by up to 60$\times$, and transfer without retraining to instances up to 10$\times$ larger in the size parameter while retaining 2--5$\times$ speedups. Our matrix-free solver implementation also batches naturally on the GPU, solving 64 Lovász $\vartheta$ SDPs 14$\times$ faster than sequential COSMO.jl. When embedded in sequential convex programming for nonlinear covariance steering, our learned optimizers outperform the interior-point solver Clarabel in terms of both success rate and solve time.

math.OC · cs.LG

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

Zeroth-Order Riemannian Optimization on Fixed-Rank Manifolds for LLM Fine-Tuning

Xinjue Wang, Xiuheng Wang, Yejun Zhang, Sergiy A. Vorobyov, Esa Ollila

原文摘要

Zeroth-order (ZO) optimization estimates descent directions from function values alone, which removes the activation storage required by backpropagation and makes it attractive for memory-efficient fine-tuning of large language models (LLMs). Existing low-rank ZO methods either parameterize the additive update through Euclidean factors with a non-unique representation, or restrict each finite-difference direction to be low-rank. In this work, we propose to constrain each additive update block to a fixed-rank matrix manifold while keeping the pretrained weights frozen, so the learned update remains rank-constrained throughout fine-tuning. On this geometry, we build a Riemannian ZO gradient estimator that projects a random matrix onto the tangent space, normalizes it to correct the scale mismatch induced by projection, and further propose Zeroth-order Riemannian Gradient Descent (ZO-RGD) and its smoothed variant, ZO-RGD-S. We show that the ambient finite difference matches its retracted counterpart, the normalized estimator recovers the Riemannian gradient in expectation, and ZO-RGD converges under trajectory-regularity conditions. Experiments on LLM fine-tuning tasks show that the proposed algorithms are competitive with strong forward-only baselines across model families and tasks, with gains in several settings.

cs.LG · math.OC

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

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

Tianhao Wu, Matthew Zurek, Weina Wang, Qiaomin Xie

原文摘要

We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms $N$. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in $N$. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an $O(1/\sqrt{N})$ optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.

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

查看论文
arXiv ↗PDF ↗