This paper presents a unified approach for maximizing continuous
DR-submodular functions that encompasses a range of settings and oracle access
types. Our approach includes a Frank-Wolfe type offline algorithm for both
monotone and non-monotone functions, with different restrictions on the general
convex set. We consider settings where the oracle provides access to either the
gradient of the function or only the function value, and where the oracle
access is either deterministic or stochastic. We determine the number of
required oracle accesses in all cases. Our approach gives new/improved results
for nine out of the sixteen considered cases, avoids computationally expensive
projections in two cases, with the proposed framework matching performance of
state-of-the-art approaches in the remaining five cases. Notably, our approach
for the stochastic function value-based oracle enables the first regret bounds
with bandit feedback for stochastic DR-submodular functions.

该论文提出了一种统一的方法来最大化连续 DR-submodular 函数，包括了一系列设置和 oracle 访问类型，并且给出了新的结果和改进的结果，其中包括一些与随机函数值有关的访问，使得其能够实现首个带有绑架反馈的悔恨边界。

最大化连续 DR - 次模函数的统一方法

A Unified Approach for Maximizing Continuous DR-submodular Functions

Submodular functions have applications throughout machine learning, but in
many settings, we do not have direct access to the underlying function $f$. We
focus on stochastic functions that are given as an expectation of functions
over a distribution $P$. In practice, we often have only a limited set of
samples $f_i$ from $P$. The standard approach indirectly optimizes $f$ by
maximizing the sum of $f_i$. However, this ignores generalization to the true
(unknown) distribution. In this paper, we achieve better performance on the
actual underlying function $f$ by directly optimizing a combination of bias and
variance. Algorithmically, we accomplish this by showing how to carry out
distributionally robust optimization (DRO) for submodular functions, providing
efficient algorithms backed by theoretical guarantees which leverage several
novel contributions to the general theory of DRO. We also show compelling
empirical evidence that DRO improves generalization to the unknown stochastic
submodular function.

通过直接优化偏差和方差的组合，该研究通过展示如何进行具有理论保证的高效算法，从而在次模函数中进行分布式鲁棒优化（DRO），从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。

分布鲁棒子模最大化

Distributionally Robust Submodular Maximization

In online convex optimization it is well known that certain subclasses of
objective functions are much easier than arbitrary convex functions. We are
interested in designing adaptive methods that can automatically get fast rates
in as many such subclasses as possible, without any manual tuning. Previous
adaptive methods are able to interpolate between strongly convex and general
convex functions. We present a new method, MetaGrad, that adapts to a much
broader class of functions, including exp-concave and strongly convex
functions, but also various types of stochastic and non-stochastic functions
without any curvature. For instance, MetaGrad can achieve logarithmic regret on
the unregularized hinge loss, even though it has no curvature, if the data come
from a favourable probability distribution. MetaGrad's main feature is that it
simultaneously considers multiple learning rates. Unlike previous methods with
provable regret guarantees, however, its learning rates are not monotonically
decreasing over time and are not tuned based on a theoretically derived bound
on the regret. Instead, they are weighted directly proportional to their
empirical performance on the data using a tilted exponential weights master
algorithm.

介绍了 MetaGrad 方法，它是一种自适应方法，能够在多种凸函数子类中实现快速速率，该方法采用了倾斜指数权重主算法，可以同时考虑多个学习率，适用于指数凹和强凸函数，以及各种类型的随机和非随机函数。