跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+758新增论文
+578其中 AI 相关
+94已有论文修订
+95新增 AI 导读

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

统计口径与数据新鲜度

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

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

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

24,106 已收录论文20,158 AI 相关7,049 有修订112 HF 社区发现

浏览论文库

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

找到 3 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 04:57(北京时间)
版本更新 · v2arXiv:2607.23863

Polynomial-time computation of $\ell_p$-contraction fixed points for even $p$

Constantinos Daskalakis, Gabriele Farina, Brian Hu Zhang

原文摘要

We give a $\text{poly}(d, p, \log(1/ε))$-time algorithm that computes an $ε$-approximate fixed point of any $\ell_p$-nonexpansive map $f : \mathcal{X} \to \mathcal{X}$, where $\mathcal{X} \subset \mathbb R^d$ is a convex compact set and $p$ is an even integer. This is the first algorithm with $\text{poly}(d, \log(1/ε))$ runtime for any fixed $p \ne 2$. Our techniques are based on a computationally efficient version of Sion's theorem for non-compact minmax problems, and extend to more general total search problems that admit low-degree polynomial potentials.

cs.DS

版本更新 · v2arXiv:2501.10884

Smoothed Analysis of Nash Equilibrium and Fixed Point Computation, and Efficiency of the Homotopy Method

Idan Attias, Yuval Dagan, Constantinos Daskalakis, Rui Yao, Manolis Zampetakis

原文摘要

We study, under a smoothed analysis perspective, the complexity of three PPAD-complete problems: computing Nash equilibria, computing fixed points, and solving variational inequalities. We consider a general perturbation model that bounds the probability density of the quantities evaluated by our algorithms. As special cases, it captures worst-case games perturbed by small random per-action costs, and worst-case maps perturbed by a small random affine function. Under these models, we show that classical algorithmic paradigms, cover-based search and homotopy path-following provably outperform the worst-case state-of-the-art. For games with a constant number of players and $n$ strategies per player, a recursive cover-based algorithm computes an $\varepsilon$-Nash equilibrium using $\log(1/\varepsilon)\cdot 2^{O(n)}$ expected payoff-vector computations, compared to the worst-case runtime tradeoffs of $\log(1/\varepsilon)\cdot n^{O(n)}$, $(1/\varepsilon)^{O(n)}$, $2^{O(\log^2 n/\varepsilon^2)}$, and $2^{O(n)}\mathrm{poly}(\log(1/\varepsilon))$. For fixed points and variational inequalities of bounded and Lipschitz maps on the $n$-dimensional $\ell_2$ unit ball, the same approach runs in expected time $\log(1/\varepsilon)\cdot 2^{O(n)}$, compared to the worst-case $(1/\varepsilon)^{O(n)}$; the $2^{Ω(n)}$ factor is necessary by prior work [Rubinstein, 2017]. For general smooth maps, we further analyze the classical predictor--corrector homotopy method, for which only qualitative convergence guarantees were previously known, showing that under perturbations the homotopy path is well conditioned and has length $2^{O(n)}$, so that the method finds an $\varepsilon$-approximate solution in time $2^{O(n)}\cdot\mathrm{poly}(1/p)/\varepsilon$ with probability at least $1-p$.

cs.GT · cs.DS · cs.LG

版本更新 · v2arXiv:2607.14940

Causal Inference for Sequential Settings under Interference and Latent Confounding

Phevos Paschalidis, Constantinos Daskalakis, Devavrat Shah

原文摘要

We study causal inference under outcome interference for sequential, observational settings. Specifically, we consider settings where the binary outcomes over N units are Markovian across T time steps. At each time step, the outcomes of N units have dependencies captured through an Ising model; each outcome is also impacted through an external field capturing the effects of its treatment as well as latent confounders. Similar to panel data literature, these latent confounders are modeled to have a low-rank factor structure. Our data is a single sample from this high-dimensional distribution. To estimate causal quantities of interest, we provide a computationally efficient method based on Maximum Pseudo-Likelihood Estimation (MPLE) for learning the model parameters. Under mild assumptions, we establish non-asymptotic consistency for parameter estimation and show this translates to faithful estimation of causal quantities of interest after sampling from the learned model. We demonstrate the efficacy of the method through synthetic experiments as well as a real-world case-study investigating causal effects of vaccine rates on COVID-19 death rates within US counties nationwide.

cs.LG · math.PR