深神经网络（DNN）通常被设计为依次级联的可区分块/层，其预测模块仅连接到其最后一层。 DNN可以与沿主链的多个点的预测模块相连，其中推理可以在中间阶段停止而无需通过所有模块。最后一个退出点可能会提供更好的预测错误，但还涉及更多的计算资源和延迟。就预测误差和成本而言，一个“最佳”的出口是可取的。最佳出口点可能取决于任务的潜在分布，并且可能会从一个任务类型变为另一种任务类型。在神经推断期间，实例的基础真理可能无法获得，并且每个出口点的错误率无法估算。因此，人们面临在无监督环境中选择最佳出口的问题。先前的工作在离线监督设置中解决了此问题，假设可以使用足够的标记数据来估计每个出口点的错误率并调整参数以提高准确性。但是，经过预训练的DNN通常被部署在新领域中，可能无法提供大量的地面真相。我们将退出选择的问题建模为无监督的在线学习问题，并使用匪徒理论来识别最佳出口点。具体而言，我们专注于弹性BERT，这是一种预先训练的多EXIT DNN，以证明它“几乎”满足了强大的优势（SD）属性，从而可以在不知道地面真相标签的情况下学习在线设置中的最佳出口。我们开发了名为UEE-UCB的基于上限（UCB）的上限（UCB）算法，该算法可证明在SD属性下实现了子线性后悔。因此，我们的方法提供了一种自适应学习多种exit DNN中特定于域特异性的最佳出口点的方法。我们从IMDB和Yelp数据集上进行了验证算法验证我们的算法。

This thesis considers sequential decision problems, where the loss/reward incurred by selecting an action may not be inferred from observed feedback. A major part of this thesis focuses on the unsupervised sequential selection problem, where one can not infer the loss incurred for selecting an action from observed feedback. We also introduce a new setup named Censored Semi Bandits, where the loss incurred for selecting an action can be observed under certain conditions. Finally, we study the channel selection problem in the communication networks, where the reward for an action is only observed when no other player selects that action to play in the round. These problems find applications in many fields like healthcare, crowd-sourcing, security, adaptive resource allocation, among many others. This thesis aims to address the above-described sequential decision problems by exploiting specific structures these problems exhibit. We develop provably optimal algorithms for each of these setups with weak feedback and validate their empirical performance on different problem instances derived from synthetic and real datasets.

培训深度神经网络（DNNS）每年都会变得越来越多地资源和能源密集型。不幸的是，现有作品主要集中于优化DNN培训以更快完成，而无需考虑对能源效率的影响。在本文中，我们观察到改善训练绩效的常见实践通常会导致能源使用效率低下。更重要的是，我们证明能耗和性能优化之间存在权衡。为此，我们提出了一个优化框架，宙斯，通过自动找到重复出现的DNN培训工作的最佳作业和GPU级配置来导航这种权衡。宙斯与即时的能源分析一起使用了在线探索 - 开发方法，避免了对昂贵的离线测量的需求，同时适应数据随着时间的流逝。我们的评估表明，宙斯可以将DNN培训的能源效率提高15.3％-75.8％，以减少75.8％。

Performance of machine learning algorithms depends critically on identifying a good set of hyperparameters. While recent approaches use Bayesian optimization to adaptively select configurations, we focus on speeding up random search through adaptive resource allocation and early-stopping. We formulate hyperparameter optimization as a pure-exploration nonstochastic infinite-armed bandit problem where a predefined resource like iterations, data samples, or features is allocated to randomly sampled configurations. We introduce a novel algorithm, Hyperband, for this framework and analyze its theoretical properties, providing several desirable guarantees. Furthermore, we compare Hyperband with popular Bayesian optimization methods on a suite of hyperparameter optimization problems. We observe that Hyperband can provide over an order-of-magnitude speedup over our competitor set on a variety of deep-learning and kernel-based learning problems.

诸如智能手机和自治车辆的移动设备越来越依赖深神经网络（DNN）来执行复杂的推理任务，例如图像分类和语音识别等。但是，在移动设备上连续执行整个DNN可以快速消耗其电池。虽然任务卸载到云/边缘服务器可能会降低移动设备的计算负担，但信道质量，网络和边缘服务器负载中的不稳定模式可能导致任务执行的显着延迟。最近，已经提出了基于分割计算（SC）的方法，其中DNN被分成在移动设备上和边缘服务器上执行的头部和尾模型。最终，这可能会降低带宽使用以及能量消耗。另一种叫做早期退出（EE）的方法，列车模型在架构中呈现多个“退出”，每个都提供越来越高的目标准确性。因此，可以根据当前条件或应用需求进行准确性和延迟之间的权衡。在本文中，我们通过呈现最相关方法的比较，对SC和EE策略进行全面的综合调查。我们通过提供一系列引人注目的研究挑战来结束论文。

深神经网络（DNN）已成为许多应用程序域（包括基于Web的服务）的重要组成部分。这些服务需要高吞吐量和（接近）实时功能，例如，对用户的请求做出反应或反应，或者按时处理传入数据流。但是，DNN设计的趋势是朝着具有许多层和参数的较大模型，以实现更准确的结果。尽管这些模型通常是预先训练的，但是在如此大的模型中，计算复杂性仍然相对显着，从而阻碍了低推断潜伏期。实施缓存机制是用于加速服务响应时间的典型系统工程解决方案。但是，传统的缓存通常不适合基于DNN的服务。在本文中，我们提出了一种端到端自动化解决方案，以根据其计算复杂性和推理延迟来提高基于DNN的服务的性能。我们的缓存方法采用了DNN模型和早期出口的自我介绍的思想。提出的解决方案是一种自动化的在线层缓存机制，如果提前出口之一中的高速缓存模型足够有信心，则可以在推理时间提早退出大型模型。本文的主要贡献之一是，我们将该想法实施为在线缓存，这意味着缓存模型不需要访问培训数据，并且仅根据运行时的传入数据执行，使其适用于应用程序使用预训练的模型。我们的实验在两个下游任务（面部和对象分类）上结果表明，平均而言，缓存可以将这些服务的计算复杂性降低到58 \％（就FLOPS计数而言），并将其推断潜伏期提高到46 \％精度低至零至零。

我们通过审查反馈重复进行一定的第一价格拍卖来研究在线学习，在每次拍卖结束时，出价者只观察获胜的出价，学会了适应性地出价，以最大程度地提高她的累积回报。为了实现这一目标，投标人面临着一个具有挑战性的困境：如果她赢得了竞标 - 获得正收益的唯一方法 - 然后她无法观察其他竞标者的最高竞标，我们认为我们认为这是从中汲取的。一个未知的分布。尽管这一困境让人联想到上下文强盗中的探索探索折衷权，但现有的UCB或汤普森采样算法无法直接解决。在本文中，通过利用第一价格拍卖的结构属性，我们开发了第一个实现$ o（\ sqrt {t} \ log^{2.5} t）$ hearry bund的第一个学习算法（\ sqrt {t} \ log^{2.5} t），这是最小值的最低$ $ \ log $因素，当投标人的私人价值随机生成时。我们这样做是通过在一系列问题上提供算法，称为部分有序的上下文匪徒，该算法将图形反馈跨动作，跨环境跨上下文进行结合，以及在上下文中的部分顺序。我们通过表现出一个奇怪的分离来确定该框架的优势和劣势，即在随机环境下几乎可以独立于动作/背景规模的遗憾，但是在对抗性环境下是不可能的。尽管这一通用框架有限制，但我们进一步利用了第一价格拍卖的结构，并开发了一种学习算法，该算法在存在对手生成的私有价值的情况下，在存在的情况下可以有效地运行样本（并有效地计算）。我们建立了一个$ o（\ sqrt {t} \ log^3 t）$遗憾，以此为此算法，因此提供了对第一价格拍卖的最佳学习保证的完整表征。

我们考虑基于嘈杂的强盗反馈优化黑盒功能的问题。内核强盗算法为此问题显示了强大的实证和理论表现。然而，它们严重依赖于模型所指定的模型，并且没有它可能会失败。相反，我们介绍了一个\ emph {isspecified}内塞的强盗设置，其中未知函数可以是$ \ epsilon $ - 在一些再现内核希尔伯特空间（RKHS）中具有界限范数的函数均匀近似。我们设计高效实用的算法，其性能在模型误操作的存在下最微小地降低。具体而言，我们提出了一种基于高斯过程（GP）方法的两种算法：一种乐观的EC-GP-UCB算法，需要了解误操作误差，并相断的GP不确定性采样，消除型算法，可以适应未知模型拼盘。我们在$ \ epsilon $，时间范围和底层内核方面提供累积遗憾的上限，我们表明我们的算法达到了$ \ epsilon $的最佳依赖性，而没有明确的误解知识。此外，在一个随机的上下文设置中，我们表明EC-GP-UCB可以有效地与遗憾的平衡策略有效地结合，尽管不知道$ \ epsilon $尽管不知道，但仍然可以获得类似的遗憾范围。

富达匪徒问题是$ k $的武器问题的变体，其中每个臂的奖励通过提供额外收益的富达奖励来增强，这取决于播放器如何对该臂进行“忠诚”在过去。我们提出了两种忠诚的模型。在忠诚点模型中，额外奖励的数量取决于手臂之前播放的次数。在订阅模型中，额外的奖励取决于手臂的连续绘制的当前数量。我们考虑随机和对抗问题。由于单臂策略在随机问题中并不总是最佳，因此对抗性环境中遗憾的概念需要仔细调整。我们介绍了三个可能的遗憾和调查，这可以是偏执的偏执。我们详细介绍了增加，减少和优惠券的特殊情况（玩家在手臂的每辆M $播放后获得额外的奖励）保真奖励。对于不一定享受载体遗憾的模型，我们提供了最糟糕的下限。对于那些展示Sublinear遗憾的模型，我们提供算法并绑定他们的遗憾。

我们考虑具有未知实用程序参数的多项式logit模型（MNL）下的动态分类优化问题。本文研究的主要问题是$ \ varepsilon $ - 污染模型下的模型错误指定，该模型是强大统计和机器学习中的基本模型。特别是，在整个长度$ t $的销售范围内，我们假设客户根据$（1- \ varepsilon）$ - 时间段的$（1- \ varepsilon）的基础多项式logit选择模型进行购买，并进行任意购买取而代之的是在剩余的$ \ varepsilon $ - 分数中的决策。在此模型中，我们通过主动淘汰策略制定了新的强大在线分类优化政策。我们对遗憾建立上限和下界，并表明当分类能力恒定时，我们的政策是$ t $的最佳对数因素。分类能力具有恒定的上限。我们进一步制定了一种完全自适应策略，该政策不需要任何先验知识，即污染参数$ \ varepsilon $。如果存在最佳和亚最佳产品之间存在的亚临时差距，我们还建立了依赖差距的对数遗憾上限和已知的 - $ \ VAREPSILON $和UNKNOWER-$ \ \ VAREPSILON $案例。我们的仿真研究表明，我们的政策表现优于基于上置信度范围（UCB）和汤普森采样的现有政策。

亚马逊客户服务每年为数百万客户联系提供实时支持。尽管Bot-Resolver有助于自动化一些流量，但我们仍然看到对人类代理商的需求很高，也称为主题专家（SME）。客户在不同域中的问题（返回策略，设备故障排除等）进行宣传。根据他们的培训，并非所有中小型企业都有资格处理所有联系人。与合格的中小型企业的路由联系是一个非平凡的问题，因为中小企业的域名资格受训练质量的影响，并且可以随着时间的推移而改变。为了在同时学习真正的资格状态的同时，我们建议使用非参数上下文的强盗算法（K-Boot）以及资格控制（EC）算法来制定路由问题。 K-Boot模型以$ K $ -NN选择的类似样品和Bootstrap Thompson采样进行探索，并以类似的样本进行奖励。 EC通过最初符合系统的资格过滤武器（SME），并动态验证该信息的可靠性。提出的K-boot是一种通用匪徒算法，EC适用于其他土匪。我们的仿真研究表明，K-boot在最新的匪徒模型上进行性能，并且当存在随机弹性信号时，EC会提高K-Boot性能。

软件通常会产生偏置输出。特别地，已知基于机器学习（ML）软件在处理鉴别的输入时产生错误的预测。这种不公平的计划行为可能是由社会偏见引起的。在过去的几年里，亚马逊，微软和谷歌已经提供了产生不公平产出的软件服务，主要是由于社会偏见（例如性别或比赛）。在此类事件中，开发人员被绑定了进行公平测试的任务。公平性测试是挑战性的;开发人员任务是产生揭示和解释偏见的歧视性投入。我们提出了一种基于语法的公平测试方法（称为Astraea），它利用无与伦比的语法来产生歧视性投入，以揭示软件系统中的公平违规行为。 Astraea使用概率语法，Astraea还通过隔离观察到的软件偏差原因提供故障诊断。 Astraea的诊断有助于改善ML公平性。 Astraea是在18个软件系统上进行评估，提供三种主要的自然语言处理（NLP）服务。在我们的评估中，Astraea产生了公平违规，率达到约18％。 Astraea产生了超过573K的歧视性测试案例，并违反了102k的公平性。此外，Astraea通过模型再培训将软件公平提高〜76％。

标记数据可以是昂贵的任务，因为它通常由域专家手动执行。对于深度学习而言，这是繁琐的，因为它取决于大型标记的数据集。主动学习（AL）是一种范式，旨在通过仅使用二手车型认为最具信息丰富的数据来减少标签努力。在文本分类设置中，在AL上完成了很少的研究，旁边没有涉及最近的最先进的自然语言处理（NLP）模型。在这里，我们介绍了一个实证研究，可以将基于不确定性的基于不确定性的算法与Bert $ _ {base} $相比，作为使用的分类器。我们评估两个NLP分类数据集的算法：斯坦福情绪树木银行和kvk-Front页面。此外，我们探讨了旨在解决不确定性的al的预定问题的启发式;即，它是不可规范的，并且易于选择异常值。此外，我们探讨了查询池大小对al的性能的影响。虽然发现，AL的拟议启发式没有提高AL的表现;我们的结果表明，使用BERT $ _ {Base} $概率使用不确定性的AL。随着查询池大小变大，性能的这种差异可以减少。

我们介绍了一个多臂强盗模型，其中奖励是多个随机变量的总和，每个动作只会改变其中的分布。每次动作之后，代理都会观察所有变量的实现。该模型是由营销活动和推荐系统激励的，在该系统中，变量代表单个客户的结果，例如点击。我们提出了UCB风格的算法，以估计基线上的动作的提升。我们研究了问题的多种变体，包括何时未知基线和受影响的变量，并证明所有这些变量均具有sublrinear后悔界限。我们还提供了较低的界限，以证明我们的建模假设的必要性是合理的。关于合成和现实世界数据集的实验显示了估计不使用这种结构的策略的振奋方法的好处。

我们开发了一种新的原则性算法，用于估计培训数据点对深度学习模型的行为的贡献，例如它做出的特定预测。我们的算法估计了AME，该数量量衡量了将数据点添加到训练数据子集中的预期（平均）边际效应，并从给定的分布中采样。当从均匀分布中采样子集时，AME将还原为众所周知的Shapley值。我们的方法受因果推断和随机实验的启发：我们采样了训练数据的不同子集以训练多个子模型，并评估每个子模型的行为。然后，我们使用套索回归来基于子集组成共同估计每个数据点的AME。在稀疏假设（$ k \ ll n $数据点具有较大的AME）下，我们的估计器仅需要$ O（k \ log n）$随机的子模型培训，从而改善了最佳先前的Shapley值估算器。

本文考虑了使用嵌入式设备来获取和分类图像的设置。由于计算能力有限，嵌入式设备依赖于具有不平衡精度的简约分类模型。当认为本地分类不准确时，设备可以决定使用更准确但资源密集型的模型将图像卸载到边缘服务器。但是，资源限制（例如，网络带宽）需要调节这种传输，以避免交通拥堵和高延迟。当传输调节是通过令牌桶时，该论文调查了此卸载问题，该机制通常用于此类目的。目的是设计一种轻巧的在线卸载策略，该策略在令牌存储桶的限制下优化了特定于应用程序的指标（例如，分类精度）。该论文制定了基于深Q网络（DQN）的政策，并证明了其功效和在嵌入式设备上部署的可行性。值得注意的是，该策略可以处理复杂的输入模式，包括图像到达中的相关性和分类精度。评估是通过使用来自Imagenet图像分类基准生成的合成痕迹对局部测试床进行图像分类进行的。这项工作的实施可在https://github.com/qiujiaming315/edgeml-dqn上获得。

我们考虑了一个特殊的匪徒问题的情况，即批处理匪徒，其中代理在一定时间段内观察批次的响应。与以前的工作不同，我们考虑了一个更实际相关的以批量学习为中心的情况。也就是说，我们提供了政策不足的遗憾分析，并为候选政策的遗憾展示了上和下限。我们的主要理论结果表明，批处理学习的影响是相对于在线行为的遗憾，批处理大小的多重因素。首先，我们研究了随机线性匪徒的两个设置：有限且无限多手臂的土匪。尽管两种设置的遗憾界限都是相同的，但前者的设置结果在温和的假设下保持。另外，我们为2臂匪徒问题作为重要见解提供了更强大的结果。最后，我们通过进行经验实验并反思最佳批量选择来证明理论结果的一致性。

价格歧视，这是指为不同客户群体的不同价格进行规定的策略，已广泛用于在线零售。虽然它有助于提高在线零售商的收入，但它可能会对公平产生严重关切，甚至违反了监管和法律。本文研究了公平限制下动态歧视性定价的问题。特别是，我们考虑一个有限的销售长度$ T $的单一产品，为一组客户提供两组客户。每组客户都有其未知的需求功能，需要学习。对于每个销售期间，卖方确定每组的价格并观察其购买行为。虽然现有文学主要侧重于最大化收入，但在动态定价文学中确保不同客户的公平尚未完全探索。在这项工作中，我们采用了（Cohen等人）的公平概念。对于价格公平性，我们在遗憾方面提出了最佳的动态定价政策，从而强制执行严格的价格公平制约。与标准$ \ sqrt {t} $ - 在线学习中的遗憾遗憾，我们表明我们案例中的最佳遗憾是$ \ tilde {\ theta}（t ^ {4/5}）$。我们进一步将算法扩展到更普遍的公平概念，包括作为一个特例的需求公平。为了处理这一普通类，我们提出了一个柔和的公平约束，并开发了实现$ \ tilde {o}（t ^ {4/5}）$后悔的动态定价政策。

动态治疗方案（DTRS）是个性化的，适应性的，多阶段的治疗计划，可将治疗决策适应个人的初始特征，并在随后的每个阶段中的中级结果和特征，在前阶段受到决策的影响。例子包括对糖尿病，癌症和抑郁症等慢性病的个性化一线和二线治疗，这些治疗适应患者对一线治疗，疾病进展和个人特征的反应。尽管现有文献主要集中于估算离线数据（例如从依次随机试验）中的最佳DTR，但我们研究了以在线方式开发最佳DTR的问题，在线与每个人的互动都会影响我们的累积奖励和我们的数据收集，以供我们的数据收集。未来的学习。我们将其称为DTR匪徒问题。我们提出了一种新颖的算法，通过仔细平衡探索和剥削，可以保证当过渡和奖励模型是线性时，可以实现最佳的遗憾。我们证明了我们的算法及其在合成实验和使用现实世界中对重大抑郁症的适应性治疗的案例研究中的好处。

我们考虑随机多武装强盗（MAB）问题，延迟影响了行动。在我们的环境中，过去采取的行动在随后的未来影响了ARM奖励。在现实世界中，行动的这种延迟影响是普遍的。例如，为某个社会群体中的人员偿还贷款的能力可能历史上历史上批准贷款申请的频率频率。如果银行将贷款申请拒绝拒绝弱势群体，则可以创建反馈循环，进一步损害该群体中获取贷款的机会。在本文中，我们制定了在多武装匪徒的背景下的行动延迟和长期影响。由于在学习期间，我们将强盗设置概括为对这种“偏置”的依赖性进行编码。目标是随着时间的推移最大化收集的公用事业，同时考虑到历史行动延迟影响所产生的动态。我们提出了一种算法，实现了$ \ tilde {\ mathcal {o}}的遗憾，并显示$ \ omega（kt ^ {2/3}）$的匹配遗憾下限，其中$ k $是武器数量，$ t $是学习地平线。我们的结果通过添加技术来补充强盗文献，以处理具有长期影响的行动，并对设计公平算法有影响。