In this paper, we examine the problem of partial inference in the context of
structured prediction. Using a generative model approach, we consider the task
of maximizing a score function with unary and pairwise potentials in the space
of labels on graphs. Employing a two-stage convex optimization algorithm for
label recovery, we analyze the conditions under which a majority of the labels
can be recovered. We introduce a novel perspective on the Karush-Kuhn-Tucker
(KKT) conditions and primal and dual construction, and provide statistical and
topological requirements for partial recovery with provable guarantees.

本文探讨了结构化预测中的部分推断问题，采用生成模型方法，考虑在图形标签空间中最大化一种包括一元和成对潜势的评分函数，采用两阶段凸优化算法进行标签恢复，并提供了可证明保证部分恢复的统计和拓扑要求。

结构化预测中的部分推断

Partial Inference in Structured Prediction

We study the framework of universal dynamic regret minimization with strongly
convex losses. We answer an open problem in Baby and Wang 2021 by showing that
in a proper learning setup, Strongly Adaptive algorithms can achieve the near
optimal dynamic regret of $\tilde O(d^{1/3} n^{1/3}\text{TV}[u_{1:n}]^{2/3}
\vee d)$ against any comparator sequence $u_1,\ldots,u_n$ simultaneously, where
$n$ is the time horizon and $\text{TV}[u_{1:n}]$ is the Total Variation of
comparator. These results are facilitated by exploiting a number of new
structures imposed by the KKT conditions that were not considered in Baby and
Wang 2021 which also lead to other improvements over their results such as: (a)
handling non-smooth losses and (b) improving the dimension dependence on
regret. Further, we also derive near optimal dynamic regret rates for the
special case of proper online learning with exp-concave losses and an
$L_\infty$ constrained decision set.

本文研究了强凸损失函数下的动态遗憾最小化框架，通过利用 KKT 条件所施加的许多新约束条件，我们回答了 Baby 和 Wang 2021 年提出的一个开放性问题，并展示了强适应算法在适当的学习设置下可以同时针对任何比较序列达到几乎最优的动态遗憾。此外，在处理非平滑损失和改善回避维度依赖性等方面，我们还取得了 Baby 和 Wang 2021 年工作的其他改进，并针对 exp-concave 损失和一个 L∞受限决策集的特殊情况导出了几乎最优的动态遗憾率。

强凸损失理论在适当在线学习中的最优动态遗憾及其扩展

Optimal Dynamic Regret in Proper Online Learning with Strongly Convex  Losses and Beyond

We consider rules for discarding predictors in lasso regression and related
problems, for computational efficiency. El Ghaoui et al (2010) propose "SAFE"
rules that guarantee that a coefficient will be zero in the solution, based on
the inner products of each predictor with the outcome. In this paper we propose
strong rules that are not foolproof but rarely fail in practice. These can be
complemented with simple checks of the Karush- Kuhn-Tucker (KKT) conditions to
provide safe rules that offer substantial speed and space savings in a variety
of statistical convex optimization problems.

本文提出了一种强效的规则来舍弃 lasso 回归及相关问题中的预测变量，可以通过简单的 KKT 条件检查来提供安全规则，从而在各种统计凸优化问题中提供实质性的速度和空间节省。