解决一类复杂非凸非光滑在线优化问题，可高效求解且有理论保证。
Online Optimization of Difference-of-Convex Compositions with Smooth Mappings
- 用平滑映射组合的凸差函数建模损失与约束，设计时间平滑近端线性算法。
- 首次证明近端残差是原问题的一阶驻点度量，固定点即为驻点。
- 适用于需快速迭代、带复杂结构约束的在线学习场景，如动态系统控制。
我们研究一类广泛存在的结构化非凸非光滑在线优化问题，其中每个损失函数为凸差函数与光滑映射的复合，可行域由同类形式的约束函数定义。提出一种时间平滑近端线性算法，并基于近端残差映射定义局部后悔度量。证明该残差是原问题的合适驻点度量：其固定点条件等价于一阶驻点。分析依赖于由复合凸差约束描述的可行域的切锥刻画，该结果本身具有独立意义，使得每次更新可通过凸优化预言机计算，尽管问题整体非凸。建立了局部后悔界和内部凸子问题总数的上界。还推导出一个误差界，将近端残差与到驻点的距离联系起来，提供近似驻点的定量验证。
原文摘要 · Abstract (English)
We study online optimization for a broad class of structured non-convex non-smooth problems where each loss is a composition of a difference-of-convex function with a smooth mapping, and the feasible region is defined by constraint functions of the same kind. We propose a time-smoothed proximal linear algorithm and a local-regret measure based on a proximal residual mapping. We show that this residual is a proper stationarity measure for the original problem: its fixed-point condition implies first-order stationarity. Our analysis relies on a tangent-cone characterization for a feasible region described by composite difference-of-convex constraints, which is of independent interest and allows each update to be computed via a convex optimization oracle, despite the non-convexity of the problem. We establish a local-regret bound and a bound on the total number of inner convex subproblems. We also derive an error bound connecting the proximal residual to the distance to stationarity, providing a quantitative certificate of approximate stationarity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。