许多顺序决策问题，包括基于池的主动学习和自适应病毒营销，可以作为适应性的下调性最大化问题。关于自适应下调优化的大多数研究都集中在单调病例或非单调性病例上。具体而言，如果实用程序函数是单调的，并且自适应子管道，则\ cite {golovin2011Adaptive}制定了一种贪婪的策略，该策略可以达到$（1-1/e）$近似值，但要受到基数约束。如果实用程序函数是非单调性的，并且自适应子模块，则\ cite {tang2021beyond}表明，随机贪婪的策略达到了$ 1/e $ $ $的近似比，但受到基数约束。在这项工作中，我们旨在通过研究部分超声酮自适应下调最大化问题来概括上述结果。为此，我们介绍了[0,1] $中自适应单调性比率$ m \的表示法，以测量功能的单调性程度。我们的主要结果是表明，如果实用程序功能为$ M $ - 适应性单调和自适应子管道。值得注意的是，当$ m = 0 $和$ m = 1 $时，此结果将恢复上述$（1-1/e）$和$ 1/e $的近似值。我们进一步扩展了结果，以考虑背包约束。我们表明，如果实用程序功能为$ M $ $ - 适应性单调和自适应子模型，则基于抽样的策略的近似值为$（M+1）/10 $。我们结果的一个重要含义是，即使对于非马可分子实用程序函数，如果此函数与单调函数``clote''，我们仍然可以达到接近$（1-1/e）$的近似值。对于许多机器学习应用程序，其实用程序功能几乎是自适应单调的，这会改善性能界限。

典型的自适应顺序决策问题的目标是根据一些部分观察来设计一个交互策略，该策略根据一些部分观察来顺序选择一组项目，以最大化预期的实用程序。已经表明，许多实际应用的实用功能，包括基于汇集的主动学习和自适应影响最大化，满足自适应子骨科的特性。然而，大多数关于自适应子模块最大化的研究重点关注完全自适应设置，即，必须等待从\ emph {all}过去选择之前的反馈。虽然这种方法可以充分利用过去过去的反馈，但是与非自适应解决方案相比，完成选择过程可能需要更长的时间来完成选择过程，其中在任何观察发生之前发生所有选择。在本文中，我们探讨了部分自适应子模块最大化的问题，其中允许同时在批处理中进行多种选择并一起观察它们的实现。我们的方法享有适应性的好处，同时减少了从过去选择等待观察的时间。据我们所知，没有结果对于非单调自适应子膜最大化问题的部分适应性政策。我们在基数限制和背包约束下研究了这个问题，并对这两种情况制定了有效和高效的解决方案。我们还分析了批量查询复杂性，即策略所需的批量次数，以便在一些额外的假设下完成选择过程。

许多顺序决策问题可以作为自适应的下管最大化问题。但是，该领域中的大多数现有研究都集中在基于池的设置上，在该设置中，人们可以按任何顺序选择项目，而对于基于流的设置，项目以任意顺序到达，并且必须立即确定是否可以立即决定在到达时选择或不选择项目。在本文中，我们介绍了一类新的实用程序功能，即半准时函数。我们开发了一系列有效的算法，以最大程度地提高基于流的设置下的半脉冲下函数。

在本文中，我们研究了经典的少量最大化问题，但在非自适应和适应性环境下都受到群体公平限制。已经表明，许多机器学习应用程序的效用函数，包括数据汇总，影响社交网络中的最大化和个性化建议，都满足了子义的属性。因此，在许多应用程序的核心中可以找到受到各种限制的最大化函数。在高水平上，少量最大化旨在选择一组大多数代表性项目（例如，数据点）。但是，大多数现有算法的设计并未包含公平的约束，从而导致某些特定组的不足或过分代表。这激发了我们研究公平的supsodular最大化问题，我们旨在选择一组项目，以最大化（可能是非单调的）suppodular效用功能，但要受群体公平约束。为此，我们为此问题开发了第一个常数因子近似算法。我们的算法的设计足够强大，可以扩展到更复杂的自适应设置下解决suppodular的最大化问题。此外，我们将研究进一步扩展到整合全球基础性约束。

顺序决策问题的目的是设计一种自适应选择一组项目的交互式策略，每个选择都是基于过去的反馈，以最大程度地提高所选项目的预期效用。已经表明，许多现实世界应用的实用程序功能都是自适应的。但是，大多数关于自适应下调优化的现有研究都集中在平均案例上。不幸的是，在最糟糕的案例实现下，具有良好平均表现的政策可能表现较差。在这项研究中，我们建议研究两种自适应下调优化问题的变体，即最坏情况下的自适应下二一个最大化和鲁棒的下二一个最大化。第一个问题旨在找到一项最大化最坏情况的政策，后者旨在找到一项政策（如果有的话），同时可以同时实现接近最佳的平均效用和最差的效用。我们引入了一类新的随机函数，称为\ emph {worst-case subsodular函数}。对于最严重的自适应性次传导性最大化问题，但要受到$ p $系统约束的约束，我们制定了一种自适应的最坏情况贪婪的贪婪政策，该政策实现了$ \ frac {1} {p+1} $近似值案例实用程序如果效用函数是最差的子模型。对于稳健的自适应下调最大化问题，但受到基数约束（分区矩阵约束），如果效用函数既是最坏情况下的casase subsodular and Adaptive subsodular，否 - \ frac {1} {2}}} $（分别$ 1/3 $）在最坏情况下和平均案例设置下同时。我们还描述了我们的理论结果的几种应用，包括池碱积极学习，随机的下套装覆盖和自适应病毒营销。

在大型和快速增长的数据上运行机器学习算法通常是计算昂贵的，减少数据集大小的一个常见技巧，从而降低了机器学习算法的计算成本，是\ EMPH {概率采样}。它通过从具有已知概率的原始数据集中的每个数据点包括来自原始数据的每个数据点来创建采样的数据集。虽然在减少数据集上运行机器学习算法的好处是显而易见的，但一个主要问题是，在使用完整数据集时，从样本获得的解决方案的性能可能比最佳解决方案的性能更差。在本文中，我们在自适应子骨析最大化的背景下检查由概率采样引起的性能损失。我们考虑一个简单的概率采样方法，它在[0,1] $中选择概率$ r \的每个数据点。如果我们设置采样率$ r = 1 $，我们的问题会减少基于原始完整数据集的解决方案。我们将采样间隙定义为从完整数据集获得的最佳解决方案之间的最大比率和从独立系统获得的样本获得的最佳解决方案。 ％它捕获了由概率采样引起的最佳解决方案的性能损失。我们的主要贡献是表明，如果实用程序函数是policywise子模块，那么对于给定的采样率$ r $，采样差距是上限和下限的1美元/ r $。我们的结果立即含义是，如果我们可以基于采样的数据集找到$ \ alpha $-uppatimation解决方案（以$ r $以$ r $上采样），那么该解决方案实现了$ \ alpha r $近似率使用完整数据集时的最佳解决方案。

在本文中，我们研究了具有国家依赖的成本的受限随机潜水区最大化问题。我们的问题的输入是从已知概率分布中得出的状态（即，项目的边际贡献和项目成本）的一组项目。知道项目的实现状态的唯一方法是选择该项目。我们考虑两个约束，即，\ ich {内}和\ \ ich {super}约束。回想一下，每个项目都有一个状态相关的成本，并且内部约束指出所有所选项目的总\ emph {实现}成本不得超过预算。因此，内部约束是具有国家依赖的。另一方面，外部约束是与状态无关的。它可以表示为无论其状态如何，都可以作为一个向下封闭的选定项目系列。我们的目标是最大限度地提高内部和外部限制的目标函数。在较大的成本表明“效用”较大的假设下，我们向这个问题提出了恒定的近似解决方案。

我们考虑自适应 - 调节功能的最低成本覆盖率的问题，并提供4（ln Q+1） - approximation算法，其中Q是目标值。该结合几乎是最好的，因为该问题不能接受比LN Q更好的近似值（除非p = np）。我们的结果是该问题的第一个O（LN Q） - Approximation算法。以前，o（ln q）近似算法仅假设独立项目或单位成本项目是已知的。此外，我们的结果很容易扩展到想要同时覆盖多个自适应 - 调节函数的设置：我们获得了此概括的第一个近似算法。

在本文中，我们研究了具有国家依赖的成本和拒绝的新随机潜水柱最大化问题。我们的问题的输入是预算约束$ B $，以及一组项目（即项目的边际贡献和项目成本）的一组项目是从已知概率分布中汲取的。知道项目的实现状态的唯一方法是探测该项目。我们允许拒绝，即在探测项目并了解其实际状态后，我们必须立即决定是否将该项目添加到我们的解决方案中。我们的目标是顺序探测/选择最优秀的一组项目，以预算限制在所选项目的总成本上。我们对此问题提出了恒定的近似解决方案。我们表明我们的解决方案可以扩展到在线设置。

在机器学习中最大化的是一项基本任务，在本文中，我们研究了经典的Matroid约束下的删除功能强大版本。在这里，目标是提取数据集的小尺寸摘要，即使在对手删除了一些元素之后，该数据集包含高价值独立集。我们提出了恒定因素近似算法，其空间复杂性取决于矩阵的等级$ k $和已删除元素的数字$ d $。在集中式设置中，我们提出$（4.597+o（\ varepsilon））$ - 近似算法，带有摘要大小$ o（\ frac {k+d} {\ varepsilon^2} \ log \ log \ frac \ frac {k} }）$将$（3.582 + o（\ varepsilon））$（k + \ frac {d} {\ varepsilon^2} \ log \ frac {k} {k} {\ varepsilon}） $摘要大小是单调的。在流设置中，我们提供$（9.435 + o（\ varepsilon））$ - 带有摘要大小和内存$ o的近似算法$（k + \ frac {d} {\ varepsilon^2} \ log \ log \ frac {k} {k} {k} {k} {k} {k} { \ varepsilon}）$;然后，将近似因子提高到单调盒中的$（5.582+o（\ varepsilon））$。

我们研究动态算法，以便在$ N $插入和删除流中最大化单调子模块功能的问题。我们显示任何维护$（0.5+ epsilon）$ - 在基数约束下的近似解决方案的算法，对于任何常数$ \ epsilon> 0 $，必须具有$ \ mathit {polynomial} $的摊销查询复杂性$ n $。此外，需要线性摊销查询复杂性，以维持0.584美元 - 批量的解决方案。这与近期[LMNF + 20，MON20]的最近动态算法相比，达到$（0.5- \ epsilon）$ - 近似值，与$ \ mathsf {poly} \ log（n）$摊销查询复杂性。在正面，当流是仅插入的时候，我们在基数约束下的问题和近似的Matroid约束下提供有效的算法，近似保证$ 1-1 / e-\ epsilon $和摊销查询复杂性$ \ smash {o （\ log（k / \ epsilon）/ \ epsilon ^ 2）} $和$ \ smash {k ^ {\ tilde {o}（1 / \ epsilon ^ 2）} \ log n} $，其中$ k $表示基数参数或Matroid的等级。

Evolutionary algorithms (EAs) are general-purpose optimization algorithms, inspired by natural evolution. Recent theoretical studies have shown that EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization, which have a wide range of applications, such as maximum coverage, sparse regression, influence maximization, document summarization and sensor placement, just to name a few. Though they have provided some theoretical explanation for the general-purpose nature of EAs, the considered submodular objective functions are defined only over sets or multisets. To complement this line of research, this paper studies the problem class of maximizing monotone submodular functions over sequences, where the objective function depends on the order of items. We prove that for each kind of previously studied monotone submodular objective functions over sequences, i.e., prefix monotone submodular functions, weakly monotone and strongly submodular functions, and DAG monotone submodular functions, a simple multi-objective EA, i.e., GSEMO, can always reach or improve the best known approximation guarantee after running polynomial time in expectation. Note that these best-known approximation guarantees can be obtained only by different greedy-style algorithms before. Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO.

我们研究了在线上下文决策问题，并具有资源约束。在每个时间段，决策者首先根据给定上下文向量预测奖励向量和资源消耗矩阵，然后解决下游优化问题以做出决策。决策者的最终目标是最大程度地利用资源消耗的奖励和效用总结，同时满足资源限制。我们提出了一种算法，该算法将基于“智能预测 - 优化（SPO）”方法的预测步骤与基于镜像下降的双重更新步骤。我们证明了遗憾的界限，并证明了我们方法的总体收敛率取决于$ \ Mathcal {o}（t^{ - 1/2}）$在线镜面下降的收敛性以及使用的替代损失功能的风险范围学习预测模型。我们的算法和后悔界限适用于资源约束的一般凸的可行区域，包括硬和软资源约束案例，它们适用于广泛的预测模型，与线性上下文模型或有限策略空间的传统设置相比。我们还进行数值实验，以与传统的仅限预测方法相比，在多维背包和最长的路径实例上，与传统的仅预测方法相比，我们提出的SPO型方法的强度。

在随着时间变化的组合环境中的在线决策激励，我们研究了将离线算法转换为其在线对应物的问题。我们专注于使用贪婪算法对局部错误的贪婪算法进行恒定因子近似的离线组合问题。对于此类问题，我们提供了一个通用框架，该框架可有效地将稳健的贪婪算法转换为使用Blackwell的易近算法。我们证明，在完整信息设置下，由此产生的在线算法具有$ O（\ sqrt {t}）$（近似）遗憾。我们进一步介绍了Blackwell易接近性的强盗扩展，我们称之为Bandit Blackwell的可接近性。我们利用这一概念将贪婪的稳健离线算法转变为匪（t^{2/3}）$（近似）$（近似）的遗憾。展示了我们框架的灵活性，我们将脱机之间的转换应用于收入管理，市场设计和在线优化的几个问题，包括在线平台中的产品排名优化，拍卖中的储备价格优化以及supperular tossodular最大化。 。我们还将还原扩展到连续优化的类似贪婪的一阶方法，例如用于最大化连续强的DR单调下调功能，这些功能受到凸约束的约束。我们表明，当应用于这些应用程序时，我们的转型会导致新的后悔界限或改善当前已知界限。我们通过为我们的两个应用进行数值模拟来补充我们的理论研究，在这两种应用中，我们都观察到，转换的数值性能在实际情况下优于理论保证。

在线广告最近已发展成为一个竞争激烈且复杂的数十亿美元行业，广告商在大型和高频上竞标广告插槽。这导致对有效的“自动招标”算法的需求日益增长，这些算法确定了传入查询的投标，以最大程度地提高广告商的目标，但受其指定的约束。这项工作探讨了在日益流行的约束下，为单个价值最大化广告商提供有效的在线算法：返回式增长（ROS）。相对于最佳算法，我们对遗憾进行了量化效率，该算法知道所有查询所有查询都是先验的。我们贡献了一种简单的在线算法，该算法在期望中实现了近乎最佳的遗憾，同时始终尊重指定的ROS约束，当查询的输入顺序为i.i.d.来自某些分布的样本。我们还将结果与Balseiro，Lu和Mirrokni [BLM20]的先前工作相结合，以实现近乎最佳的遗憾，同时尊重ROS和固定的预算限制。我们的算法遵循原始的二重式框架，并使用在线镜像下降（OMD）进行双重更新。但是，我们需要使用非典型的OMD设置，因此需要使用OMD的经典低rebret保证，该保证是用于在线学习中的对抗性环境的，不再存在。尽管如此，在我们的情况下，在更普遍的情况下，在算法设计中应用低纤维动力学的情况下，OMD遇到的梯度可能远非对抗性，但受我们的算法选择的影响。我们利用这一关键见解来显示我们的OMD设置在我们的算法领域中造成了低落的遗憾。

Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization problems. During the past two decades, promising results on the running time analysis (one essential theoretical aspect) of EAs have been obtained, while most of them focused on isolated combinatorial optimization problems, which do not reflect the general-purpose nature of EAs. To provide a general theoretical explanation of the behavior of EAs, it is desirable to study their performance on general classes of combinatorial optimization problems. To the best of our knowledge, the only result towards this direction is the provably good approximation guarantees of EAs for the problem class of maximizing monotone submodular functions with matroid constraints. The aim of this work is to contribute to this line of research. Considering that many combinatorial optimization problems involve non-monotone or non-submodular objective functions, we study the general problem classes, maximizing submodular functions with/without a size constraint and maximizing monotone approximately submodular functions with a size constraint. We prove that a simple multi-objective EA called GSEMO-C can generally achieve good approximation guarantees in polynomial expected running time.

单调可行的算法的开发，受基数约束（SMCC）的基本最大化产生了两个单独的研究方向：具有低自适应复杂性的集中算法，需要随机访问整个数据集；并分布式MAPREDUCE（MR）模型算法，这些算法使用少量的MR回合计算。目前，众所周知，没有MR Model算法使用均值的自适应回合，从而限制了其实际性能。我们在分布式设置中研究了SMCC问题，并介绍了三种单独的MR模型算法，这些算法在分布式设置中引入了sublinear适应性。我们的主要算法，Dash实现了$ \ frac {1} {2} {2}（1-1/e- \ varepsilon）$的近似值，而使用一个MR圆形，而其多轮变体元数据启用MR模型算法可以在大型上运行。以前不可能的基数约束。使用一个和$（$ \ frac {3} {8} {8} - \ varepsilon $）和（$ 1-1/e- \ varepsilon $）的两种附加算法T-DASH和G-DASH提供了改进的比率为（$ \ frac {3} {8} - \ varepsilon $） 1/\ Varepsilon）$ MR ROUNDS。我们所有提出的算法都具有肌关系的自适应复杂性，我们提供了广泛的经验证据来确定：仪表率是比最先进的分布式算法快的数量级，同时产生了几乎相同的溶液值；并验证仪表板在集中和分布式数据上获得可行解决方案时的多功能性。

在典型的优化问题中，任务是选择成本最低或最高价值的多个选项之一。实际上，这些成本/价值数量通常是通过诸如嘈杂的测量或机器学习等过程来实现的，具有可量化的噪声分布。要考虑到这些噪声分布，一种方法是假设值的先验，使用它来构建后部，然后应用标准随机优化来选择解决方案。但是，在许多实际应用中，此类先前的分布可能没有可用。在本文中，我们使用遗憾最小化模型研究了这种情况。在我们的模型中，任务是在$ n $值中选择最高的一个。这些值是未知的，并由对手选择，但是可以通过嘈杂的通道观察到，在噪声通道中，从已知的分布开始添加噪声。目的是最大程度地减少我们选择的遗憾，该遗憾定义为最高值选择的最高值和所选值之间的预期差异。我们表明，挑选最高观测值的na \“我的算法也对最佳级别的遗憾也后悔，即使$ n = 2 $，并且噪声是公正的。对于任何$ n $的最佳遗憾。我们的算法在概念上是简单的，计算上的效率，并且仅需要对噪声分布的最小知识。

本文展示了如何适应$ k $ -MEANS问题的几种简单和经典的基于采样的算法，以使用离群值设置。最近，Bhaskara等人。 （Neurips 2019）展示了如何将古典$ K $ -MEANS ++算法适应与异常值的设置。但是，他们的算法需要输出$ o（\ log（k）\ cdot z）$ outiers，其中$ z $是true Outliers的数量，以匹配$ o（\ log k）$ - 近似值的$ k的近似保证$ -Means ++。在本文中，我们以他们的想法为基础，并展示了如何适应几个顺序和分布式的$ k $ - 均值算法，但使用离群值来设置，但具有更强的理论保证：我们的算法输出$（1+ \ VAREPSILON）z $ OUTLIERS Z $ OUTLIERS在实现$ o（1 / \ varepsilon）$ - 近似目标函数的同时。在顺序世界中，我们通过改编Lattanzi和Sohler的最新算法来实现这一目标（ICML 2019）。在分布式设置中，我们适应了Guha等人的简单算法。 （IEEE Trans。知道和数据工程2003）以及Bahmani等人的流行$ K $ -Means $ \ | $。 （PVLDB 2012）。我们技术的理论应用是一种具有运行时间$ \ tilde {o}（nk^2/z）$的算法，假设$ k \ ll z \ ll n $。这与Omacle模型中此问题的$ \ Omega（NK^2/z）$的匹配下限相互补。

我们研究了在$ n $均质代理之间分配$ t $依次到达项目的问题，即每个代理必须收到所有项目的预先指定的分数，目的是最大化代理商的总估值，分配给他们的项目的总估值。假定代理在每轮中对该项目的估值为I.I.D。但是它们的分布是中央计划者未知的先验。因此，中央规划师需要从观察到的价值中隐含地学习这些分布，以便选择良好的分配策略。但是，这里的另一个挑战是，代理商是战略性的，并激励他们误导其估值，以便获得更好的分配。这使我们的工作与在线拍卖设计设置不同，这些设置通常假设已知的估值分布和/或涉及付款，也可以从不考虑战略代理的在线学习环境中进行付款。为此，我们的主要贡献是一种基于在线学习的分配机制，大约是贝叶斯激励兼容的，当所有代理人都是真实的时，与最佳离线分配政策相比，在所有代理商的效用中保证了sublinear的遗憾。