{"ID":2851992,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.18218","arxiv_id":"2510.18218","title":"DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing","abstract":"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.","short_abstract":"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 encour...","url_abs":"https://arxiv.org/abs/2510.18218","url_pdf":"https://arxiv.org/pdf/2510.18218v2","authors":"[\"Luxuan Li\",\"Xiao Wang\",\"Chunfeng Cui\"]","published":"2025-10-21T01:52:46Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.CV\"]","methods":"[]","has_code":false}