提出高效算法解决带期望约束的非凸非光滑优化问题。
A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization
- 设计单循环SPIDER型随机次梯度法，结合目标与约束的次梯度及函数值。
- 在弱正则条件下达到O(ε⁻⁴)迭代复杂度，逼近最优解。
- 适用于公平性约束、分类等场景，速度比现有方法快466倍。
许多现实问题（如公平性约束）涉及复杂的期望约束和大规模数据，亟需高效的随机优化方法。现有研究多集中于无约束或易投影约束情形，而本文针对带有期望约束的非凸非光滑随机优化问题，构建了新的精确罚模型，并建立了该模型与原问题的关系。进一步提出一种单循环SPIDER型随机次梯度方法，利用目标函数与约束函数的次梯度以及每轮迭代中的约束函数值。在弱于传统Slater条件或强可行性假设的正则条件下，证明了达到惩罚问题近ε-驻点的期望迭代复杂度为O(ε⁻⁴)，达到此类任务的下界。基于精确罚理论，可获得原问题的(ε,ε)-KKT点。在部分情形下，目标样本次梯度或约束样本函数值的复杂度较当前最优结果降低ε⁻²倍。在两类公平性约束问题和一个多类Neyman-Pearson分类问题上，本方法比切换次梯度法和不精确邻近点法快达466倍。
原文摘要 · Abstract (English)
Many real-world problems, such as those with fairness constraints, involve complex expectation constraints and large datasets, necessitating the design of efficient stochastic methods to solve them. Most existing research focuses on cases with no {constraint} or easy-to-project constraints or deterministic constraints. In this paper, we consider nonconvex nonsmooth stochastic optimization problems with expectation constraints, for which we build a novel exact penalty model. We first show the relationship between the penalty model and the original problem. Then on solving the penalty problem, we present a single-loop SPIDER-type stochastic subgradient method, which utilizes the subgradients of both the objective and constraint functions, as well as the constraint function value at each iteration. Under certain regularity conditions (weaker than Slater-type constraint qualification or strong feasibility assumed in existing works), we establish an iteration complexity result of $O(ε^{-4})$ to reach a near-$ε$ stationary point of the penalized problem in expectation, matching the lower bound for such tasks. Building on the exact penalization, an $(ε,ε)$-KKT point of the original problem is obtained. For a few scenarios, our complexity of either the {objective} sample subgradient or the constraint sample function values can be lower than the state-of-the-art results by a factor of $ε^{-2}$. Moreover, on solving two fairness-constrained problems and a multi-class Neyman-Pearson classification problem, our method is significantly (up to 466 times) faster than the state-of-the-art algorithms, including switching subgradient method and inexact proximal point methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。