跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1085新增论文
+884其中 AI 相关
+130已有论文修订
+59新增 AI 导读

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

统计口径与数据新鲜度

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

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-18 19:45库内论文最新更新时间:2026-11-18 08:00

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

26,870 已收录论文22,374 AI 相关8,156 有修订112 HF 社区发现

浏览论文库

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

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

Settling the Support Complexity of Correlated Equilibria

Ashkan Soleymani, Patrick Jaillet, Gabriele Farina, Akbar Rafiey

原文摘要

We study the support complexity of approximate correlated equilibria (CE) in two-player games, that is, the minimum number of pure action profiles that must be assigned positive probability to approximate a correlated equilibrium of a two-player matrix game. For $\varepsilon$-approximate coarse correlated equilibria, constant approximation is possible with support $O(\log N/\varepsilon^2)$ in $N\times N$ games. For correlated equilibria, the best known upper bound was $O(\log^2 N/\varepsilon^4)$ [Babichenko et al., 2014, 2017], but whether this bound was tight remained open. We establish a matching lower bound, resolving the open question of Ko and Schvartzman [2017]. Specifically, we show that, already for two-player zero-sum games, for every $1\leq k\leq N^{1/2}$ the worst-case correlated-equilibrium gap achievable by a distribution supported on at most $k$ pure profiles is $$ Θ\left( \min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\} \right), $$ which implies a $Θ(\log^2 N/\varepsilon^4)$ worst-case support bound. The proof builds on a probabilistic-method construction based on random sign matrices.

cs.GT · cs.LG

新论文 · v1arXiv:2611.12575

From Likelihood Convergence to Parameter Convergence in POMDPs

Jack Zhang, Saurabh Amin, Jiawei Zhang, Patrick Jaillet

原文摘要

Likelihood-based methods are widely used to learn the parameters of partially observable Markov decision processes (POMDPs). While finite-sample guarantees for policy suboptimality exist for certain POMDP subclasses, analogous guarantees for parameter recovery remain less well understood. For any candidate POMDP parameter, we bound its parameter recovery error in terms of its likelihood gap to the ground truth, the structural conditioning of the observation and transition kernels, and the behavior policy used to collect data. The bound applies in both the undercomplete and overcomplete regimes, with the latter following naturally from the undercomplete analysis. Because the result applies to any sufficiently good candidate, it yields finite-sample guarantees for the maximum-likelihood estimator and any procedure producing a parameter with controlled likelihood gap. This is particularly useful for near-optimal learning in infinite-horizon POMDPs, where existing approaches largely rely on model-based planning with accurate transition and observation kernel estimates. The bound separates the contributions of the behavior policy and model, showing how data-collection choices, including action coverage, and their effects on mixing can accelerate parameter learning.

cs.LG

新论文 · v1arXiv:2611.11877

Tropical Gaussian Anticoncentration: Optimal Instance-Dependent Bounds for Online Learning in Extensive-Form Games

Ashkan Soleymani, Zhiyuan Fan, Lillian J. Ratliff, Patrick Jaillet, Gabriele Farina

原文摘要

We study the minimax regret of full-information online decision making in extensive-form games. For prediction with expert advice, the optimal regret is $Θ(\sqrt{T\log K})$, where $K$ is the number of experts, or equivalently, the number of normal-form actions. For treeplex strategy spaces, existing efficient algorithms, including KOMWU and online mirror descent with the weight-one dilated entropy regularizer, achieve regret $\mathcal{O}(\sqrt{T\log|\mathcal{V}|})$, where $\mathcal{V}$ is the set of reduced normal-form strategies. We prove that this logarithmic dependence is minimax optimal in the worst-case full-information reward model. The main difficulty is that pure plans in a treeplex are not independent experts: their rewards are correlated through the recursive structure of decisions and observations. To capture this correlation, we introduce tropical Gaussian formulae, recursive Gaussian expressions built from maxima and normalized sums which preserve the variance. The index count of such a formula matches the number of reduced normal-form continuation plans in the corresponding subtree. Our main analytic result shows that every log-balanced tropical Gaussian formula with index count $N$ has Gaussian width $Ω(\sqrt{\log N})$. While a direct approach struggles to recover this lower bound, our proof uses a spherical entropy profile to measure scale-dependent separation among the Gaussian directions, and then applies Turán's theorem and Sudakov minoration to obtain the width lower bound. Applying this result to treeplexes gives an oblivious hard distribution with valid transition outcome and Rademacher terminal rewards, establishing a regret lower bound of $Ω(\sqrt{T\log|\mathcal{V}|})$. This matches known upper bounds up to universal constants and shows that the DilEnt/KOMWU dependence on the reduced normal-form complexity is unavoidable.

cs.LG · cs.GT

新论文 · v1arXiv:2611.11693

Homological Barriers to Stable Learning of First-Order Nash Equilibria

Ashkan Soleymani, Gabriele Farina, Patrick Jaillet, Georgios Piliouras

原文摘要

We identify a homological barrier to stable learning of local Nash equilibria, also known as first-order Nash equilibria (FONE), in constrained non-concave differentiable games. We consider continuous deterministic learning dynamics that fix every FONE point and aim to attract all initial conditions to the full FONE set. We show that this convergence guarantee is impossible when the target set has nontrivial positive-degree cohomology, such as that arising from a loop, and the state space is compact and contractible. We exhibit this barrier in a simple non-concave quadratic zero-sum game on a box whose exact FONE set consists of a diagonal six-edge loop and an isolated point. Consequently, no such dynamics can make the full FONE set a stable global attractor. We further show that degree two is the minimal polynomial degree at which this barrier can arise and extend the construction to obtain nontrivial homology in arbitrarily high degrees. Finally, we establish that the barrier persists for sufficiently small approximate-FONE targets under small perturbations, yielding an open, positive-volume family of quadratic zero-sum games with the same homological barrier.

cs.GT · cs.LG

新论文 · 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

新论文 · v1arXiv:2611.08775

On Lipschitz Explosion in Deep Neural Networks with Normalization: Consequences for Optimization and Adversarial Robustness

Ashkan Soleymani, Reyhaneh Hosseinpourkhoshkbari, Hadi Daneshmand, Patrick Jaillet

原文摘要

Can a network look stable at every layer and still be exponentially unstable as a whole? The Lipschitz constant of a neural network is a basic stability quantity appearing in optimization guarantees, generalization bounds, and robustness certificates. Deep networks naturally admit two such notions, input Lipschitzness, measuring sensitivity to data perturbations, and parameter Lipschitzness, measuring sensitivity to weight perturbations. We prove that, for deep networks with normalization layers, with batch normalization as the canonical example, both Lipschitz constants can grow exponentially with depth and hence with parameter dimension, even under strong per-layer norm control such as $\|W_\ell\|_2\le 1$, and already for linear activations. Thus, a mechanism widely used to stabilize training can create severe worst-case instabilities that are invisible locally, i.e., from layerwise norm bounds alone. Parameter-Lipschitz explosion turns Lipschitz-dependent nonsmooth optimization guarantees into exponential-in-dimension bounds for deep normalized networks, while input-Lipschitz explosion makes worst-case Lipschitz-based generalization and robustness certificates vacuous. The latter also yields a concrete rank-separation mechanism for adversarial vulnerability. The theory predicts that perturbations introducing new singular directions should be amplified much more strongly than perturbations at the same noise level that remain within the input's original singular subspace. Experiments on MNIST, Fashion-MNIST, and CIFAR-10 support this prediction, showing that rank-creating perturbations cause substantially sharper drops in accuracy, confidence, and margins than same-subspace perturbations.

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

版本更新 · v2arXiv:2310.07884

候选人数随机的秘书问题:先验分布信息如何发挥作用

Secretary Problems with Random Number of Candidates: How Prior Distributional Information Helps

Junhui Zhang, Patrick Jaillet

AI 速读 基于摘要

研究候选人数 N 为随机变量且已知其分布 p 的秘书问题变体,分析单阈值策略的近似保证与采样设定下的样本复杂度。

cs.DS

查看原文摘要

We study variants of the secretary problem, where $N$, the number of candidates, is a random variable with distribution $\mathbf p$. The decision maker, given prior distributional information about $\mathbf p$, wants to maximize the probability of success -- picking the largest number among the $N$ candidates -- using only the sequentially revealed relative ranks of the candidates. When $\mathbf p$ is fully known (full information setting), we show that single-threshold type of strategies can achieve $1/e$-approximation to the optimal probability of success among all possible strategies. In the sampling setting, we give an algorithm that finds a strategy with additive suboptimality at most $ε$ and provide its sample-complexity guarantee. We also give a sampling lower bound; for small $ε$, the upper and lower bounds match up to a logarithmic factor in $1/ε$.