This paper introduces the notion of upper linearizable/quadratizable
functions, a class that extends concavity and DR-submodularity in various
settings, including monotone and non-monotone cases over different convex sets.
A general meta-algorithm is devised to convert algorithms for linear/quadratic
maximization into ones that optimize upper quadratizable functions, offering a
unified approach to tackling concave and DR-submodular optimization problems.
The paper extends these results to multiple feedback settings, facilitating
conversions between semi-bandit/first-order feedback and bandit/zeroth-order
feedback, as well as between first/zeroth-order feedback and semi-bandit/bandit
feedback. Leveraging this framework, new projection-free algorithms are derived
using Follow The Perturbed Leader (FTPL) and other algorithms as base
algorithms for linear/convex optimization, improving upon state-of-the-art
results in various cases. Dynamic and adaptive regret guarantees are obtained
for DR-submodular maximization, marking the first algorithms to achieve such
guarantees in these settings. Notably, the paper achieves these advancements
with fewer assumptions compared to existing state-of-the-art results,
underscoring its broad applicability and theoretical contributions to
non-convex optimization.

本文介绍了上线性可编码 / 可平方化函数的概念，该类函数扩展了凹性和 DR - 次模性，适用于不同凸集的单调和非单调情况。提出了一种通用的元算法，将线性 / 二次最大化的算法转化为优化上可平方化函数的算法，为处理凹和 DR - 次模优化问题提供了统一方法。将这些结果扩展到多反馈设置，促进了半强盗 / 一阶反馈与盗贼 / 零阶反馈之间，以及一阶 / 零阶反馈与半强盗 / 盗贼反馈之间的转换。利用这个框架，使用跟随扰动领袖（FTPL）算法和其他算法作为线性 / 凸优化的基础算法，得到了新的无投影算法，改善了各种情况下的现有最新结果。在 DR - 次模最大化中获得了动态和自适应的遗憾保证，这是在这些设置中首次实现此类保证的算法。值得注意的是，与现有最新结果相比，本文在较少的假设下实现了这些进展，突显了其对非凸优化的广泛适用性和理论贡献。