该工作研究限制了随机函数是凸的，并表示为随机函数的组成。问题是在公平分类，公平回归和排队系统设计的背景下出现的。特别令人感兴趣的是甲骨文提供组成函数的随机梯度的大规模设置，目标是用最小对Oracle的调用来解决问题。由于组成形式，Oracle提供的随机梯度不会产生目标或约束梯度的无偏估计。取而代之的是，我们通过跟踪内部函数评估来构建近似梯度，从而导致准差鞍点算法。我们证明，所提出的算法几乎可以肯定地找到最佳和可行的解决方案。我们进一步确定所提出的算法需要$ \ MATHCAL {O}（1/\ EPSILON^4）$数据样本，以便获得$ \ epsilon $ -Approximate-approximate-apptroximate Pointal点，同时也确保零约束违反。该结果与无约束问题的随机成分梯度下降方法的样品复杂性相匹配，并改善了受约束设置的最著名样品复杂性结果。在公平分类和公平回归问题上测试了所提出的算法的功效。数值结果表明，根据收敛速率，所提出的算法优于最新算法。

本文分析了双模的彼此优化随机算法框架。 Bilevel优化是一类表现出两级结构的问题，其目标是使具有变量的外目标函数最小化，该变量被限制为对（内部）优化问题的最佳解决方案。我们考虑内部问题的情况是不受约束的并且强烈凸起的情况，而外部问题受到约束并具有平滑的目标函数。我们提出了一种用于解决如此偏纤维问题的两次时间尺度随机近似（TTSA）算法。在算法中，使用较大步长的随机梯度更新用于内部问题，而具有较小步长的投影随机梯度更新用于外部问题。我们在各种设置下分析了TTSA算法的收敛速率：当外部问题强烈凸起（RESP。〜弱凸）时，TTSA算法查找$ \ MATHCAL {O}（k ^ { - 2/3}）$ -Optimal（resp。〜$ \ mathcal {o}（k ^ {-2/5}）$ - 静止）解决方案，其中$ k $是总迭代号。作为一个应用程序，我们表明，两个时间尺度的自然演员 - 批评批评近端策略优化算法可以被视为我们的TTSA框架的特殊情况。重要的是，与全球最优政策相比，自然演员批评算法显示以预期折扣奖励的差距，以$ \ mathcal {o}（k ^ { - 1/4}）的速率收敛。

随机成分优化（SCO）引起了人们的关注，因为它在重要的现实问题上的广泛适用性。但是，SCO上的现有作品假设解决方案更新中的投影很简单，对于以期望形式的约束（例如经验性的条件价值危险约束），该预测无法保留。我们研究了一个新型模型，该模型将单层期望值和两级组成约束结合到当前的SCO框架中。我们的模型可以广泛应用于数据驱动的优化和风险管理，包括规避风险的优化和高音阶组合选择，并可以处理多个约束。我们进一步提出了一类Primal-Dual算法，该算法以$ \ co（\ frac {1} {\ sqrt {n}} $的速率生成序列，以$ \ co（\ frac {1}级别组成约束，其中$ n $是迭代计数器，在预期值约束的SCO中建立基准。

尽管学习已成为现代信息处理的核心组成部分，但现在有足够的证据表明它可以导致偏见，不安全和有偏见的系统。因此，对学习要求施加要求至关重要，尤其是在达到社会，工业和医疗领域的关键应用程序时。但是，大多数现代统计问题的非跨性别性只有通过限制引入而加剧。尽管通常可以使用经验风险最小化来学习良好的无约束解决方案，即使获得满足统计约束的模型也可能具有挑战性。更重要的是，一个好。在本文中，我们通过在经验双重领域中学习来克服这个问题，在经验的双重领域中，统计学上的统计学习问题变得不受限制和确定性。我们通过界定经验二元性差距来分析这种方法的概括特性 - 即，我们的近似，可拖动解决方案与原始（非凸）统计问题的解决方案之间的差异 - 并提供实用的约束学习算法。这些结果建立了与经典学习理论的约束，从而可以明确地在学习中使用约束。我们说明了这种理论和算法受到速率受限的学习应用，这是在公平和对抗性鲁棒性中产生的。

本文认为，使用一组不平等凸期望约束最小化凸期望函数的问题。我们提出了一种可计算的随机近似类型算法，即乘数的随机线性近端方法来解决此凸随机优化问题。该算法可以粗略地看作是随机近似和传统的乘数近端方法的混合体。在轻度条件下，我们表明该算法表现出$ o（k^{ - 1/2}）$预期的收敛速率，如果正确选择了算法中的参数，则客观降低和约束违规率，其中$ k $表示$ k $表示的数量表示迭代。此外，我们表明，算法具有$ o（\ log（k）k^{ - 1/2}）$约束违规和$ o（\ log^{3/2}（k）k）^{ - 1/2}）$目标结合。一些初步的数值结果证明了所提出的算法的性能。

随机多变最小化 - 最小化（SMM）是大多数变化最小化的经典原则的在线延伸，这包括采样I.I.D。来自固定数据分布的数据点，并最小化递归定义的主函数的主要替代。在本文中，我们引入了随机块大大化 - 最小化，其中替代品现在只能块多凸，在半径递减内的时间优化单个块。在SMM中的代理人放松标准的强大凸起要求，我们的框架在内提供了更广泛的适用性，包括在线CANDECOMP / PARAFAC（CP）字典学习，并且尤其是当问题尺寸大时产生更大的计算效率。我们对所提出的算法提供广泛的收敛性分析，我们在可能的数据流下派生，放松标准i.i.d。对数据样本的假设。我们表明，所提出的算法几乎肯定会收敛于速率$ O（（\ log n）^ {1+ \ eps} / n ^ {1/2}）$的约束下的非凸起物镜的静止点集合。实证丢失函数和$ O（（\ log n）^ {1+ \ eps} / n ^ {1/4}）$的预期丢失函数，其中$ n $表示处理的数据样本数。在一些额外的假设下，后一趋同率可以提高到$ o（（\ log n）^ {1+ \ eps} / n ^ {1/2}）$。我们的结果为一般马尔维亚数据设置提供了各种在线矩阵和张量分解算法的第一融合率界限。

在本文中，我们研究了平稳的随机多级组成优化问题，其中目标函数是$ T $函数的嵌套组成。我们假设通过随机的一阶Oracle访问函数及其渐变的噪声评估。为了解决这类问题，我们提出了两个使用移动平均随机估计的两种算法，并分析了它们对问题的$ \ epsilon $ -stationary的趋同。我们表明，第一算法，它是\ Cite {gharuswan20}的泛化到$ t $ letch案例，可以通过使用mini-实现$ \ mathcal {o}（1 / \ epsilon ^ 6）$的样本复杂性每次迭代中的样品批次。通过使用函数值的线性化随机估计修改该算法，我们将样本复杂性提高到$ \ mathcal {o}（1 / \ epsilon ^ 4）$。 {\ Color {Black}此修改不仅可以消除在每次迭代中具有迷你样本的要求，还使算法无参数和易于实现}。据我们所知，这是第一次为（UN）约束的多级设置设计的在线算法，在标准假设下获得平滑单级设置的相同样本复杂度（无偏见和界限第二矩）在随机第一阶Oracle上。

We study stochastic monotone inclusion problems, which widely appear in machine learning applications, including robust regression and adversarial learning. We propose novel variants of stochastic Halpern iteration with recursive variance reduction. In the cocoercive -- and more generally Lipschitz-monotone -- setup, our algorithm attains $\epsilon$ norm of the operator with $\mathcal{O}(\frac{1}{\epsilon^3})$ stochastic operator evaluations, which significantly improves over state of the art $\mathcal{O}(\frac{1}{\epsilon^4})$ stochastic operator evaluations required for existing monotone inclusion solvers applied to the same problem classes. We further show how to couple one of the proposed variants of stochastic Halpern iteration with a scheduled restart scheme to solve stochastic monotone inclusion problems with ${\mathcal{O}}(\frac{\log(1/\epsilon)}{\epsilon^2})$ stochastic operator evaluations under additional sharpness or strong monotonicity assumptions.

Many real-world problems not only have complicated nonconvex functional constraints but also use a large number of data points. This motivates the design of efficient stochastic methods on finite-sum or expectation constrained problems. In this paper, we design and analyze stochastic inexact augmented Lagrangian methods (Stoc-iALM) to solve problems involving a nonconvex composite (i.e. smooth+nonsmooth) objective and nonconvex smooth functional constraints. We adopt the standard iALM framework and design a subroutine by using the momentum-based variance-reduced proximal stochastic gradient method (PStorm) and a postprocessing step. Under certain regularity conditions (assumed also in existing works), to reach an $\varepsilon$-KKT point in expectation, we establish an oracle complexity result of $O(\varepsilon^{-5})$, which is better than the best-known $O(\varepsilon^{-6})$ result. Numerical experiments on the fairness constrained problem and the Neyman-Pearson classification problem with real data demonstrate that our proposed method outperforms an existing method with the previously best-known complexity result.

As machine learning being used increasingly in making high-stakes decisions, an arising challenge is to avoid unfair AI systems that lead to discriminatory decisions for protected population. A direct approach for obtaining a fair predictive model is to train the model through optimizing its prediction performance subject to fairness constraints, which achieves Pareto efficiency when trading off performance against fairness. Among various fairness metrics, the ones based on the area under the ROC curve (AUC) are emerging recently because they are threshold-agnostic and effective for unbalanced data. In this work, we formulate the training problem of a fairness-aware machine learning model as an AUC optimization problem subject to a class of AUC-based fairness constraints. This problem can be reformulated as a min-max optimization problem with min-max constraints, which we solve by stochastic first-order methods based on a new Bregman divergence designed for the special structure of the problem. We numerically demonstrate the effectiveness of our approach on real-world data under different fairness metrics.

二重优化发现在现代机器学习问题中发现了广泛的应用，例如超参数优化，神经体系结构搜索，元学习等。而具有独特的内部最小点（例如，内部功能是强烈凸的，都具有唯一的内在最小点）的理解，这是充分理解的，多个内部最小点的问题仍然是具有挑战性和开放的。为此问题设计的现有算法适用于限制情况，并且不能完全保证融合。在本文中，我们采用了双重优化的重新制定来限制优化，并通过原始的双二线优化（PDBO）算法解决了问题。 PDBO不仅解决了多个内部最小挑战，而且还具有完全一阶效率的情况，而无需涉及二阶Hessian和Jacobian计算，而不是大多数现有的基于梯度的二杆算法。我们进一步表征了PDBO的收敛速率，它是与多个内部最小值的双光线优化的第一个已知的非质合收敛保证。我们的实验证明了所提出的方法的预期性能。

强化学习被广泛用于在与环境互动时需要执行顺序决策的应用中。当决策要求包括满足一些安全限制时，问题就变得更加具有挑战性。该问题在数学上是作为约束的马尔可夫决策过程（CMDP）提出的。在文献中，可以通过无模型的方式解决各种算法来解决CMDP问题，以实现$ \ epsilon $ - 最佳的累积奖励，并使用$ \ epsilon $可行的政策。 $ \ epsilon $可行的政策意味着它遭受了违规的限制。这里的一个重要问题是，我们是否可以实现$ \ epsilon $ - 最佳的累积奖励，并违反零约束。为此，我们主张使用随机原始偶对偶方法来解决CMDP问题，并提出保守的随机原始二重算法（CSPDA），该算法（CSPDA）显示出$ \ tilde {\ tilde {\ Mathcal {o}} \ left（1 /\ epsilon^2 \ right）$样本复杂性，以实现$ \ epsilon $ - 最佳累积奖励，违反零约束。在先前的工作中，$ \ epsilon $ - 最佳策略的最佳可用样本复杂性是零约束的策略是$ \ tilde {\ Mathcal {o}}} \ left（1/\ epsilon^5 \ right）$。因此，与最新技术相比，拟议的算法提供了重大改进。

We study distributionally robust optimization (DRO) with Sinkhorn distance -- a variant of Wasserstein distance based on entropic regularization. We provide convex programming dual reformulation for a general nominal distribution. Compared with Wasserstein DRO, it is computationally tractable for a larger class of loss functions, and its worst-case distribution is more reasonable. We propose an efficient first-order algorithm with bisection search to solve the dual reformulation. We demonstrate that our proposed algorithm finds $\delta$-optimal solution of the new DRO formulation with computation cost $\tilde{O}(\delta^{-3})$ and memory cost $\tilde{O}(\delta^{-2})$, and the computation cost further improves to $\tilde{O}(\delta^{-2})$ when the loss function is smooth. Finally, we provide various numerical examples using both synthetic and real data to demonstrate its competitive performance and light computational speed.

非convex受限的优化问题可用于模拟许多机器学习问题，例如多级Neyman-Pearson分类和受限的Markov决策过程。但是，由于目标和约束可能是非概念，因此这些问题都是具有挑战性的，因此很难平衡减少损失价值和减少约束违规行为的平衡。尽管有几种方法可以解决此类问题，但它们都是双环或三环算法，它们需要Oracles来解决某些子问题，通过在每次迭代中调整多个超级参数，以达到某些准确性。在本文中，我们提出了一种新型的梯度下降和扰动的上升（GDPA）算法，以解决一类平滑的非概念不平等的限制问题。 GDPA是一种原始的偶算法，仅利用目标和约束函数的一阶信息，以交替的方式更新原始变量和双重变量。该算法的关键特征是它是一种单循环算法，其中只需要调整两个步骤尺寸。我们表明，在轻度的规律性条件下，GDPA能够找到非convex功能约束问题的Karush-Kuhn-Tucker（KKT）点，并保证了收敛率。据我们所知，这是第一个可以通过非convex不等式约束来解决一般非凸的平滑问题的单循环算法。与最著名的算法相比，数值结果还显示了GDPA的优越性（就平稳性测量和获得的溶液的可行性而言）。

本文重点介绍了静态和时变设置中决策依赖性分布的随机鞍点问题。这些是目标是随机收益函数的预期值，其中随机变量从分布图引起的分布中绘制。对于一般分布地图，即使已知分布是已知的，发现鞍点的问题也是一般的计算繁琐。为了实现易求解的解决方案方法，我们介绍了均衡点的概念 - 这是它们诱导的静止随机最小值问题的马鞍点 - 并为其存在和唯一性提供条件。我们证明，两个类解决方案之间的距离被界定，条件是该目标具有强凸强 - 凹入的收益和Lipschitz连续分布图。我们开发确定性和随机的原始算法，并证明它们对均衡点的收敛性。特别是，通过将来自随机梯度估计器的出现的错误建模为子-Weibull随机变量，我们提供期望的错误界限，并且在每个迭代的高概率中提供的误差;此外，我们向期望和几乎肯定地显示给社区的融合。最后，我们调查了分布地图的条件 - 我们调用相反的混合优势 - 确保目标是强烈的凸强 - 凹陷的。在这种假设下，我们表明原始双算法以类似的方式汇集到鞍座点。

最近，凸嵌套随机复合优化（NSCO）因其在增强学习和规避风险优化方面的应用而受到了极大的关注。当前的NSCO算法通过数量级的随机甲骨文复杂性较差，而没有嵌套结构的简单随机复合优化问题（例如，平滑和非平滑函数的总和）。此外，它们要求所有外层函数都是平滑的，这对某些重要的应用不满足。这些差异促使我们问：``嵌套成分是否使随机优化在甲骨文复杂性的顺序上更加困难？平滑，结构化的非平滑和一般非平滑层函数的任意组成。当所有外层函数平滑时，我们提出了一种随机顺序双重（SSD）方法，以实现$ \ Mathcal {O}的甲骨文复杂性（1）（1 /\ epsilon^2）$（$ \ MATHCAL {o}（1/\ Epsilon）$）当问题不是（强）凸出时。函数，我们提出了一种非平滑随机顺序双重（NSSD）方法，以实现$ \ MATHCAL {O}（1/\ epsilon^2）$的甲骨文复杂性。我们提供了较低的复杂性，以显示后者$ \ MATHCAL {O }（1/\ epsilon^2）$即使在强烈的凸面设置下也无法改善。 XITY结果似乎是文献中的新事物，它们表明凸NSCO问题的甲骨文复杂性与没有嵌套成分的甲骨文复杂性相同，除了强烈的凸面和外部不太平滑问题。

我们提出了一个基于预测校正范式的统一框架，用于在原始和双空间中的预测校正范式。在此框架中，以固定的间隔进行了连续变化的优化问题，并且每个问题都通过原始或双重校正步骤近似解决。通过预测步骤的输出，该解决方案方法是温暖启动的，该步骤的输出可以使用过去的信息解决未来问题的近似。在不同的假设集中研究并比较了预测方法。该框架涵盖的算法的示例是梯度方法的时变版本，分裂方法和著名的乘数交替方向方法（ADMM）。

Two-level stochastic optimization formulations have become instrumental in a number of machine learning contexts such as continual learning, neural architecture search, adversarial learning, and hyperparameter tuning. Practical stochastic bilevel optimization problems become challenging in optimization or learning scenarios where the number of variables is high or there are constraints. In this paper, we introduce a bilevel stochastic gradient method for bilevel problems with lower-level constraints. We also present a comprehensive convergence theory that covers all inexact calculations of the adjoint gradient (also called hypergradient) and addresses both the lower-level unconstrained and constrained cases. To promote the use of bilevel optimization in large-scale learning, we introduce a practical bilevel stochastic gradient method (BSG-1) that does not require second-order derivatives and, in the lower-level unconstrained case, dismisses any system solves and matrix-vector products.

通过在线规范相关性分析的问题，我们提出了\ emph {随机缩放梯度下降}（SSGD）算法，以最小化通用riemannian歧管上的随机功能的期望。 SSGD概括了投影随机梯度下降的思想，允许使用缩放的随机梯度而不是随机梯度。在特殊情况下，球形约束的特殊情况，在广义特征向量问题中产生的，我们建立了$ \ sqrt {1 / t} $的令人反感的有限样本，并表明该速率最佳最佳，直至具有积极的积极因素相关参数。在渐近方面，一种新的轨迹平均争论使我们能够实现局部渐近常态，其速率与鲁普特 - Polyak-Quaditsky平均的速率匹配。我们将这些想法携带在一个在线规范相关分析，从事文献中的第一次获得了最佳的一次性尺度算法，其具有局部渐近融合到正常性的最佳一次性尺度算法。还提供了用于合成数据的规范相关分析的数值研究。

由于在数据稀缺的设置中，交叉验证的性能不佳，我们提出了一个新颖的估计器，以估计数据驱动的优化策略的样本外部性能。我们的方法利用优化问题的灵敏度分析来估计梯度关于数据中噪声量的最佳客观值，并利用估计的梯度将策略的样本中的表现为依据。与交叉验证技术不同，我们的方法避免了为测试集牺牲数据，在训练和因此非常适合数据稀缺的设置时使用所有数据。我们证明了我们估计量的偏见和方差范围，这些问题与不确定的线性目标优化问题，但已知的，可能是非凸的，可行的区域。对于更专业的优化问题，从某种意义上说，可行区域“弱耦合”，我们证明结果更强。具体而言，我们在估算器的错误上提供明确的高概率界限，该估计器在策略类别上均匀地保持，并取决于问题的维度和策略类的复杂性。我们的边界表明，在轻度条件下，随着优化问题的尺寸的增长，我们的估计器的误差也会消失，即使可用数据的量仍然很小且恒定。说不同的是，我们证明我们的估计量在小型数据中的大规模政权中表现良好。最后，我们通过数值将我们提出的方法与最先进的方法进行比较，通过使用真实数据调度紧急医疗响应服务的案例研究。我们的方法提供了更准确的样本外部性能估计，并学习了表现更好的政策。