# DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing

arXiv: https://arxiv.org/abs/2510.18218 · HTML: https://mlsanity.com/paper/2510.18218/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 45 of its 84 references that are in the map.
- First posted on arXiv 21 Oct 2025.

## Builds on (most cited first, 30 of 45)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Quantization Networks](https://mlsanity.com/paper/1911.09464/) (2019)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [HashNet: Deep Learning to Hash by Continuation](https://mlsanity.com/paper/1702.00758/) (2017)
- [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020)
- [Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems](https://mlsanity.com/paper/1410.1390/) (2014)
- [Training Neural Networks Without Gradients: A Scalable ADMM Approach](https://mlsanity.com/paper/1605.02026/) (2016)
- [Feature Learning based Deep Supervised Hashing with Pairwise Labels](https://mlsanity.com/paper/1511.03855/) (2015)
- [ProxQuant: Quantized Neural Networks via Proximal Operators](https://mlsanity.com/paper/1810.00861/) (2018)
- [Stochastic Methods for Composite and Weakly Convex Optimization Problems](https://mlsanity.com/paper/1703.08570/) (2017)
- [A Survey on Deep Hashing Methods](https://mlsanity.com/paper/2003.03369/) (2020)
- [Simultaneous Feature Learning and Hash Coding with Deep Neural Networks](https://mlsanity.com/paper/1504.03410/) (2015)
- [One Loss for All: Deep Hashing with a Single Cosine Similarity based Learning Objective](https://mlsanity.com/paper/2109.14449/) (2021)
- [Supervised Discrete Hashing](https://mlsanity.com/paper/1503.01557/) (2015)
- [Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/1702.02505/) (2017)
- [Deep Supervised Discrete Hashing](https://mlsanity.com/paper/1705.10999/) (2017)
- [Deep Supervised Hashing with Triplet Labels](https://mlsanity.com/paper/1612.03900/) (2016)
- [A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1907.03793/) (2019)
- [A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning](https://mlsanity.com/paper/1808.05403/) (2018)
- [Global convergence of splitting methods for nonconvex composite optimization](https://mlsanity.com/paper/1407.0753/) (2014)
- [Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence](https://mlsanity.com/paper/1811.11829/) (2018)
- [Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problems](https://mlsanity.com/paper/1902.07672/) (2019)
- [Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization](https://mlsanity.com/paper/2006.00425/) (2020)

## Abstract (arXiv)

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 O(varepsilon-4) complexity and an improved O(varepsilon-3) version using variance reduction. Experiments on three image retrieval databases demonstrate the superior performance of DualHash.