其中 1<=q
而 1<=q<=p,1<=p<2 的情形就要复杂很多了。由于 p=2 的情形只有有限个奇异点（如下图左的红点所示），所以只要成功设计出一个能保持损失函数下降性质的算法，则可以保证最多只经过每个奇异点一次并脱离奇异集。但对于 1<=p<2 的情形，奇异集是一个包含无限个点的连续点集合（如下图右的红色虚线及红点所示），所以算法可能重新访问奇异集无限次并最终不会逃离奇异集。
该奇异性问题经常且意外地发生。造成奇异性的初始或中间迭代点可在 d>=2 维实空间中的一个开集中稠密，甚至充满整个 d 维实空间 [4]。更为严重的是，该问题无法依靠简单直观的手段来回避，例如随机扰动迭代点使其离开奇异集，或者重选一个随机初始点，等等。事实上，只要采用本文提出的去奇异性次梯度方法，即可在不增加计算复杂度（与一般梯度法相比）的有利条件下解决该奇异性问题，因此完全不需要再借助其他回避手段。
-
论文标题：De-singularity Subgradient for the q-th-Powered L_p-Norm Weber Location Problem
-
论文链接：http://arxiv.org/abs/2412.15546
-
项目地址：https://github.com/laizhr/qPpNWAWS
本文提出一种解决奇异性问题的直观方法：识别出引发奇异性的数据点及维度，然后把相应的分量去除掉。首先是识别出引发奇异性的数据点及维度，分别用集合 V_t (y) 和 U_i (y) 来表示。
下图是 V_t (y) 和 U_i (y) 的一个直观示意图。
然后使用定义 5 来定义去奇异性次梯度 D_{p,q}(y)。
接着，我们需要验证这个去奇异性次梯度 D_{p,q}(y) 具有与普通梯度类似的良好性质。例如，它要能够刻画最小值点（定理 6）和下降方向（定理 7）。这些刻画的关键技术在于引入 p 范数的共轭范数，即使得 1/r+1/p =1 成立的 r 范数。
基于 q 次方 p 范数的去奇异性 Weiszfeld 算法
获得可行的去奇异性次梯度 D_{p,q}(y) 后，下一步就是建立可行的求解算法。本文基于求解该问题常用的 Weiszfeld 算法 [5][2]，建立一种基于 q 次方 p 范数的去奇异性 Weiszfeld 算法（简记为 qPpNWAWS，如 18 式所示）。它在非奇异性情形下使用 (9) 式的常规 Weiszfeld 更新迭代，在奇异性情形下使用 (17) 式的沿下降方向线性搜索法。
通过这种方式，qPpNWAWS 算法可自由来回多次（甚至包括无限次）游走于非奇异集与奇异集之间或之内，同时保证损失函数随迭代下降，并最终收敛。在 1
我们以 CSI300 数据集 [3] 为例简单介绍实验结果，其他数据集以及详细实验结果请参阅论文。运行实验的机器配置为：Intel Core i9-14900KF 中央处理器 1 个，64-GB DDR5 6000-MHz 内存，带 16-GB 独立显存的 Nvidia RTX 4080 SUPER 显卡 1 张。
该实验用于记录 qPpNWAWS 算法在奇异点需要几次线性搜索才能使损失函数下降。结果表明在绝大多数情形下只需不超过 3 次线性搜索。
该实验用于记录 qPpNWAWS 算法完整运行一次所需的总迭代次数以及总时间。结果表明在绝大多数情形下只需不超过约 15 次迭代以及 0.02 秒的总时间。
该实验用于记录 qPpNWAWS 算法的实际计算收敛率。结果表明在绝大多数情形下收敛率均远小于 1，即达到线性收敛速度。
该实验主要测试不同 (q,p) 情形下使用 qPpNWAWS 算法进行在线资产配置实验 [6][7] 所得到的投资得分 —— 累计财富（CW）和夏普比率（SR）。结果表明一定数目的其他 (q,p) 情形（例如 (q,p)=(1,1.6)）的得分要比原始版本 (q,p)=(1,2) 的得分高。因此解决 1<=q<=p,1<=p<2 情形下的奇异性问题有着非常重要的现实意义。
通用机器学习是一个由多个研究方向有机结合而成的整体领域。其往往需要融会贯通多个数学类和计算机类学科的知识，攻关通用人工智能中最为基础的科学与技术难题。本文属于该领域中的基础模块开发与优化器开发研究方向。以下是近期本课题组在该领域的一些主要论文与主攻方向，欢迎阅读并与我们交流讨论。
-
[a]. Zhao-Rong Lai, Weiwen Wang*, “Invariant Risk Minimization Is A Total Variation Model”, the 41st International Conference on Machine Learning (ICML, main track), 2024.（深度学习框架、分布外泛化）
-
[b]. Yizun Lin, Yangyu Zhang, Zhao-Rong Lai*, Cheng Li,”Autonomous Sparse Mean-CVaR Portfolio Optimization”, the 41st International Conference on Machine Learning (ICML, main track), 2024.（逼近理论、稀疏学习）
-
[c]. Yizun Lin, Zhao-Rong Lai*, Cheng Li,“A Globally Optimal Portfolio for m-Sparse Sharpe Ratio Maximization”, the 38th Annual Conference on Neural Information Processing Systems（NeurIPS, main track), 2024.（优化器开发、稀疏学习）
-
[d]. Zhao-Rong Lai, Xiaotian Wu, Liangda Fang, Ziliang Chen*, “A De-singularity Subgradient Approach for the Extended Weber Location Problem”, the 33rd International Joint Conference on Artificial Intelligence (IJCAI, main track), 2024.（基础模块开发、优化器开发）
[1]. Weber, A. 1909. Uber den Standort der Industrien. Tubingen: Mohr.
[2]. Morris, J. G. 1981. Convergence of the Weiszfeld algorithm for Weber problems using a generalized “distance” function. Operations Research, 29(1): 37–48.
[3]. Lai, Z.-R.; Wu, X.; Fang, L.; and Chen, Z. 2024. A De-singularity Subgradient Approach for the Extended Weber Location Problem. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence.
[4]. Chandrasekaran, R.; and Tamir, A. 1989. Open questions concerning Weiszfeld’s algorithm for the Fermat-Weber location problem. Mathematical Programming, 44: 293–295.
[5]. Weiszfeld, E.. Sur le point pour lequel la somme des distances de n points donnes est minimum. Tohoku Mathematical Journal, 43:355–386, 1937.
[6]. Li, B.; Sahoo, D.; and Hoi, S. C. 2016. OLPS: a toolbox for on-line portfolio selection. Journal of Machine Learning Research, 17(1): 1242–1246.
[7]. Huang, D.; Zhou, J.; Li, B.; Hoi, S. C. H.; and Zhou, S. 2016. Robust Median Reversion Strategy for Online Portfolio Selection. IEEE Transactions on Knowledge and Data Engineering, 28(9): 2480–2493.
