跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

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

统计口径与数据新鲜度

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

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

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

23,827 已收录论文19,941 AI 相关6,921 有修订112 HF 社区发现

浏览论文库

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

找到 4 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-16 01:33(北京时间)
新论文 · v1arXiv:2611.12696

Generalized Adaptive Boosting and the Geometry of Mistakes

Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen

原文摘要

Not all mistakes are alike. For example, in medical diagnosis, false positive and false negative mistakes have a different impact and should not be aggregated. By revisiting the classical theory of boosting through this lens, we introduce the notion of $Z$-learner, which returns weak hypotheses achieving joint false-positive/false-negative guarantees $(\mathrm{FP},\mathrm{FN})$ from some set $Z \subseteq [0,1]^2$. This formulation generalizes the standard notion of $γ$-weak learning--recovered by taking $Z=\{(z_1,z_2): z_1+z_2<1/2-γ\}$--and allows for more flexible notions of weak learnability that account for the impact of the distribution on the achievable learning guarantees. This raises a natural question: which sets $Z$ are boostable? We answer this by giving a complete geometric characterization that unifies, as special cases, both the classical boosting dichotomy and the recent multi-objective extension of Bressan et al. (COLT 2025). We also present an adaptive algorithm for boosting $Z$-learners without relying on the prior knowledge of $Z$, generalizing AdaBoost's ability to handle unknown margin parameters. Finally, we demonstrate that $Z$-learners can achieve confidence amplification. However, the analysis is significantly more involved than in classical boosting and relies on the centerpoint theorem from discrete and computational geometry.

cs.LG · stat.ML

版本更新 · v2arXiv:2610.32740

Strongly Adaptive Online Learning with Time-Varying Movement Costs

Andrew Jacobsen, Emmanuel Esposito, Hao Qiu, Mengxiao Zhang

原文摘要

We study online convex optimization (OCO) with time-varying movement costs, where the learner incurs both a loss and a time-dependent penalty for changing its decisions. While previous work has established dynamic regret guarantees for this setting, obtaining strongly adaptive guarantees that hold simultaneously over arbitrary intervals remains an open challenge. We address this by developing a new algorithm which, for every interval $[a,b]\subseteq[T]$ and arbitrary comparator sequence, achieves a data-dependent regret bound of $ \widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+λ_t\|g_t\|)} \right) $, where $D$ is the diameter of the decision domain, $P_{[a,b]}$ is the path length of the comparator sequence over $[a,b]$, $g_t$ is the gradient of the loss, and $λ_t$ is the movement-cost coefficient at round~$t$. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of our development, we further obtain strongly-adaptive dynamic regret guarantees under arbitrary delayed feedback with a refined dependence on interval-restricted cumulative delays. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.

cs.LG · stat.ML

新论文 · v1arXiv:2611.07773

Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents

Emmanuel Esposito, Andrew Jacobsen, Hao Qiu, Alexander Ryabchenko, Mengxiao Zhang

原文摘要

We study learning in zero-sum games with delayed feedback. We introduce Multi-Anchor Optimistic Online Mirror Descent (MAO-OMD), a single algorithm which obtains optimal fast rates in self-play on smooth games, while simultaneously maintaining minimax optimal guarantees against arbitrary opponents. In particular, in smooth zero-sum games with arbitrary and unknown feedback delays, MAO-OMD obtains $O(σ_{\max}+1)$ social and individual regrets when used by both players, where $σ_{\max}$ denotes the maximum number of outstanding gradients, while also guaranteeing minimax optimal $O(\sqrt{T+d_{\mathrm{tot}}})$ individual regret against arbitrary opponents, where $d_{\mathrm{tot}}$ is the total delay. Moreover, we show that these optimal rates cannot be obtained simultaneously using the standard black-box reduction to the undelayed setting. We also extend our results to multi-player games, and to games with player-dependent delay sequences.

cs.LG · stat.ML

版本更新 · v2arXiv:2606.03851

The Price of Partial Information with Switching Costs: A Complete Characterization for Feedback Graphs

Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Emmanuel Esposito, Federico Fusco, Tomer Koren

原文摘要

We study how switching costs affect minimax regret under partial feedback. Which features of the feedback preserve the $\sqrt T$ rate, and which force the $T^{2/3}$ rate? We address this question in the framework of feedback graphs, which interpolate between full information and bandits: playing an action reveals the losses of its out-neighbors in a known directed graph. Prior work on feedback graphs with switching costs gave algorithms with regret of order $T^{2/3}$, but matching lower bounds only for restricted classes of graphs, leaving the question open. We establish a complete characterization of the minimax regret with switching costs for all feedback graphs: $\widetildeΘ(\sqrt T)$ if the graph is strongly revealing, meaning that every pair of distinct actions has an endpoint that observes the losses of both; $\widetildeΘ(γ^{1/3}T^{2/3})$ for every other observable graph, where $γ$ is the domination number; and linear otherwise. In particular, tournaments, in which every action observes its own loss and each pair of actions is joined by one directed edge, sit at the phase transition: they behave like full information, but deleting the edge of any pair forces the rate $T^{2/3}$. Hence an action that observes all losses is neither necessary nor sufficient for the rate $\sqrt T$. Our algorithm TournamentSteering for the strongly revealing case rests on a new principle: each observed comparison of two actions serves both to estimate losses and to steer play, and the loss reduction from steering pays for the variance of the estimates. For every strongly revealing graph, distributing the comparisons among observing actions keeps this variance, and hence the regret, polylogarithmic in the number of actions, by an argument similar to the greedy construction of logarithmic dominating sets in tournaments.

cs.LG