math.OCOct 21, 2025

DualHash: Stochastic Primal-Dual Algorithms for W-Type Regularized Deep Hashing

Authors: Luxuan Li, Xiao Wang, Chunfeng Cui

Organizations: School of Mathematical Sciences, Beihang University, Beijing 100191, China · School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510006, China

Abstract

Deep hashing encodes high-dimensional image features into compact binary codes, enabling efficient similarity search in large-scale content-based image retrieval, a problem akin to semantic-preserving lossy compression under extreme bit-rate constraints. A fundamental challenge in deep hashing stems from the discrete nature of quantization in generating the codes. W-type regularizations, such as z↦∥∣z∣−1∥1z\mapsto\||z|-1\|_1, are widely adopted and empirically effective at pushing network outputs 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, using Fenchel duality, we reformulate the nonconvex W-type regularization term through its convex conjugate, yielding a min-max problem with tractable proximal updates. We show that this min-max problem captures the stationarity of the original deep hashing objective up to the quantization error. Building on this problem, we present a stochastic primal-dual hashing algorithm, referred to as DualHash, with oracle complexity guarantees. We derive two algorithm instances: a momentum-based version with O(ε−4)O(\varepsilon^{-4}) oracle complexity and an improved O(ε−3)O(\varepsilon^{-3}) version using variance reduction, both for ε\varepsilon-KKT points of the min-max problem, which yield near-stationarity guarantees for the original objective. Experiments on three standard datasets demonstrate competitive retrieval accuracy and reduced quantization error, validating the practical value of DualHash for image retrieval problems. Our implementation of DualHash is available at https://github.com/RailLee/DualHash.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Beyond Post-Quantization: Native Hash Learning with a Dedicated HASH Token

    Jul 3, 2026Xinze Liu, Ding Wang, Hengjie Zhu +1Vision TransformerImage Retrieval

  2. Double Down on Defense: Strengthening Deep Perceptual Hashes against Evasion Attacks without Retraining

    Aug 4, 2026Bangjie Sun, Nayoung Kim, Mun Choon Chan +1Image MatchingAdversarial Robustness

  3. DSCH-Loss: A Dynamic Semantic Channel Objective for Deep Semantic Hashing

    Jul 27, 2026Tobias J. Bauer, Christian Riess, Daniel Loebenberger +1Cross-Modal Representation LearningCross-Modal Retrieval