The study of first-order optimization is sensitive to the assumptions made on
the objective functions. These assumptions induce complexity classes which play
a key role in worst-case analysis, including the fundamental concept of
algorithm optimality. Recent work argues that strong convexity and smoothness,
popular assumptions in literature, lead to a pathological definition of the
condition number (Guille-Escuret et al., 2021). Motivated by this result, we
focus on the class of functions satisfying a lower restricted secant inequality
and an upper error bound. On top of being robust to the aforementioned
pathological behavior and including some non-convex functions, this pair of
conditions displays interesting geometrical properties. In particular, the
necessary and sufficient conditions to interpolate a set of points and their
gradients within the class can be separated into simple conditions on each
sampled gradient. This allows the performance estimation problem (PEP, Drori
and Teboulle (2012)) to be solved analytically, leading to a lower bound on the
convergence rate that proves gradient descent to be exactly optimal on this
class of functions among all first-order algorithms.

本研究重点关注函数满足较小限制的割线不等式和较大上限误差的函数类，可以在各采样梯度上分别满足一组简单条件，在所有一阶算法中，通过梯度下降法可以完全优化此类函数，从而导致收敛速率的下限。

梯度下降在较低限制割线不等式和上误差界下是最优的

Gradient Descent Is Optimal Under Lower Restricted Secant Inequality And  Upper Error Bound

We consider (i) the problem of finding a (possibly mixed) Nash equilibrium in
congestion games, and (ii) the problem of finding an (exponential precision)
fixed point of the gradient descent dynamics of a smooth function $f:[0,1]^n
\rightarrow \mathbb{R}$. We prove that these problems are equivalent. Our
result holds for various explicit descriptions of $f$, ranging from (almost
general) arithmetic circuits, to degree-$5$ polynomials. By a very recent
result of [Fearnley, Goldberg, Hollender, Savani '20] this implies that these
problems are PPAD$\cap$PLS-complete. As a corollary, we also obtain the
following equivalence of complexity classes: CCLS = PPAD$\cap$PLS.

在拥堵博弈中找到 (可能的混合) 纳什均衡和在平滑函数的梯度下降动力学中找到指数精度的不动点两问题等价，由此得到复杂性类的等价性 CCLS = PPAD∩PLS。

拓扑博弈中纳什均衡的复杂性问题

Settling the complexity of Nash equilibrium in congestion games

We show that for several variations of partially observable Markov decision
processes, polynomial-time algorithms for finding control policies are unlikely
to or simply don't have guarantees of finding policies within a constant factor
or a constant summand of optimal. Here "unlikely" means "unless some complexity
classes collapse," where the collapses considered are P=NP, P=PSPACE, or P=EXP.
Until or unless these collapses are shown to hold, any control-policy designer
must choose between such performance guarantees and efficient computation.

研究表明，对于部分可观察的马尔可夫决策过程的多种变化形式，寻找控制策略的多项式时间算法难以或没有确保在最优解的常数因子或常数项内找到策略。除非某些复杂度类崩溃，否则任何控制策略设计师都必须在性能保证和有效计算之间做出选择。

部分可观察的马尔可夫决策过程的不逼近性结果

Nonapproximability Results for Partially Observable Markov Decision  Processes

We examine the computational complexity of testing and finding small plans in
probabilistic planning domains with both flat and propositional
representations. The complexity of plan evaluation and existence varies with
the plan type sought; we examine totally ordered plans, acyclic plans, and
looping plans, and partially ordered plans under three natural definitions of
plan value. We show that problems of interest are complete for a variety of
complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the
process of proving that certain planning problems are complete for NP^PP, we
introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the
standard Boolean satisfiability problem to computations involving probabilistic
quantities; our results suggest that the development of good heuristics for
E-MAJSAT could be important for the creation of efficient algorithms for a wide
variety of problems.

研究了具有平面和命题表示的概率规划领域中测试和寻找小规划的计算复杂性，发现问题的复杂性分别属于 PL，P，NP，co-NP，PP，NP^PP，co-NP^PP 和 PSPACE，提出了一个新的基本 NP^PP 完全问题 E-MAJSAT，表明 E-MAJSAT 问题的启发式算法的开发对于广泛问题的高效算法很重要。