提出带理论保证的深度哈希算法，提升图像检索效率与精度
DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing
- 利用对偶空间转化非凸正则项，实现可解析求解的近端算子
- 两种版本分别达到O(ε⁻⁴)和O(ε⁻³)的复杂度，收敛有保障
- 适用于需要高效精确检索的大型图像数据库场景
深度哈希将高维特征向量转化为紧凑的二进制编码，实现大规模检索的高效性。深度哈希的核心挑战源于量化生成编码时的离散性。W型正则化（如||z|-1|）已被证明有效，因其能促使变量趋向于二值。然而，现有方法通常直接优化此类正则化，缺乏收敛性保证。虽然近端梯度方法具潜力，但W型正则化与神经网络输出之间的耦合导致复合形式，一般无闭式近端解。本文提出一种随机原始-对偶哈希算法DualHash，提供严格的复杂度界。通过Fenchel对偶，我们将非凸W型正则化优化部分转化为对偶空间，得到具有闭式解的近端算子。推导出两个算法实例：一个带有动量加速的版本复杂度为O(ε⁻⁴)，另一个使用方差缩减的改进版本复杂度为O(ε⁻³)。在三个图像检索数据库上的实验表明，DualHash性能显著优于现有方法。
原文摘要 · Abstract (English)
Deep hashing converts high-dimensional feature vectors into compact binary codes, enabling efficient large-scale retrieval. A fundamental challenge in deep hashing stems from the discrete nature of quantization in generating the codes. W-type regularizations, such as $||z|-1|$, have been proven effective as they encourage variables toward binary values. However, existing methods often directly optimize these regularizations without convergence guarantees. While proximal gradient methods offer a promising solution, the coupling between W-type regularizers and neural network outputs results in composite forms that generally lack closed-form proximal solutions. In this paper, we present a stochastic primal-dual hashing algorithm, referred to as DualHash, that provides rigorous complexity bounds. Using Fenchel duality, we partially transform the nonconvex W-type regularization optimization into the dual space, which results in a proximal operator that admits closed-form solutions. We derive two algorithm instances: a momentum-accelerated version with $\mathcal{O}(\varepsilon^{-4})$ complexity and an improved $\mathcal{O}(\varepsilon^{-3})$ version using variance reduction. Experiments on three image retrieval databases demonstrate the superior performance of DualHash.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。