Demystifying and Generalizing BinaryConnect

• URL: http://arxiv.org/abs/2110.13220v1
• Date: Mon, 25 Oct 2021 19:07:38 GMT
• Title: Demystifying and Generalizing BinaryConnect
• Authors: Tim Dockhorn, Yaoliang Yu, Eyy\"ub Sari, Mahdi Zolnouri, Vahid Partovi Nia
• Abstract summary: We show that existing quantization algorithms, including post-training quantization, are surprisingly similar to each other. We argue for proximal maps as a natural family of quantizers that is both easy to design and analyze. We propose ProxConnect (PC) as a generalization of BinaryConnect (BC) and we prove its convergence properties.
• Score: 22.41391997183786
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: BinaryConnect (BC) and its many variations have become the de facto standard for neural network quantization. However, our understanding of the inner workings of BC is still quite limited. We attempt to close this gap in four different aspects: (a) we show that existing quantization algorithms, including post-training quantization, are surprisingly similar to each other; (b) we argue for proximal maps as a natural family of quantizers that is both easy to design and analyze; (c) we refine the observation that BC is a special case of dual averaging, which itself is a special case of the generalized conditional gradient algorithm; (d) consequently, we propose ProxConnect (PC) as a generalization of BC and we prove its convergence properties by exploiting the established connections. We conduct experiments on CIFAR-10 and ImageNet, and verify that PC achieves competitive performance.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Circuit Knitting Faces Exponential Sampling Overhead Scaling Bounded by Entanglement Cost [5.086696108576776]
  We show that the sampling overhead of circuit knitting is exponentially lower bounded by the exact entanglement cost of the target bipartite dynamic. Our work reveals a profound connection between virtual quantum information processing via quasi-probability decomposition and quantum Shannon theory.
  arXiv  Detail & Related papers  (2024-04-04T17:41:13Z)
• Understanding Neural Network Binarization with Forward and Backward Proximal Quantizers [26.27829662433536]
  In neural network binarization, BinaryConnect (BC) and its variants are considered the standard. We aim at shedding some light on these training tricks from the optimization perspective.
  arXiv  Detail & Related papers  (2024-02-27T17:43:51Z)
• Distributed Partial Quantum Consensus of Qubit Networks with Connected Topologies [13.978557505365604]
  Two partial quantum consensus protocols, based on the Lyapunov method for chain graphs and the geometry method for connected graphs, are proposed. The numerical simulation over a qubit network is demonstrated to verify the validity and the effectiveness of the theoretical results.
  arXiv  Detail & Related papers  (2024-02-22T03:44:45Z)
• Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint [6.799314463590596]
  In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits. In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph.
  arXiv  Detail & Related papers  (2024-02-04T08:29:41Z)
• Graph test of controllability in qubit arrays: A systematic way to determine the minimum number of external controls [62.997667081978825]
  We show how to leverage an alternative approach, based on a graph representation of the Hamiltonian, to determine controllability of arrays of coupled qubits. We find that the number of controls can be reduced from five to one for complex qubit-qubit couplings.
  arXiv  Detail & Related papers  (2022-12-09T12:59:44Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage [6.019061613604927]
  We present an efficient classical algorithm that, with 1 GPU within 2s, yields high XEB values, namely 2-12% of those obtained in experiments. By identifying and exploiting several vulnerabilities of the XEB, we achieve high XEB values without full simulation of quantum circuits.
  arXiv  Detail & Related papers  (2021-12-03T00:37:10Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems. Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
  arXiv  Detail & Related papers  (2021-09-06T14:35:15Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.