Compander-Aligned Query Geometry for Quantized Zeroth-Order Optimization

• URL: http://arxiv.org/abs/2605.10673v1
• Date: Mon, 11 May 2026 14:55:20 GMT
• Title: Compander-Aligned Query Geometry for Quantized Zeroth-Order Optimization
• Abstract summary: CAQ-ZO forms one-grid-step Rademacher stencils $z pm r$ in $z = (x)$, maps endpoints back through $-1$, and updates in $z$.<n>Our theory proves the grid-spanarity, decomposes endpoint-rounding estimator residuals, and gives station bounds in which generic off-grid queries retain a $2/2$ residual channel while CAQ-ZO makes the query-time residual exactly zero.
• Score: 12.92201130466754
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Low-bit forward evaluation is an attractive route to memory-efficient zeroth-order (ZO) adaptation: the optimizer needs only scalar losses, and the model can be queried near deployment precision. The obstacle is that a quantized ZO query is not a continuous finite difference followed by harmless storage rounding. The query chooses endpoints, the low-precision engine rounds them, and the loss difference is measured along the rounded chord. For nonuniform companding quantizers, this makes the codebook insufficient to predict ZO behavior: a fixed weight-space radius can collapse in dense cells, over-span sparse cells, or assign a rounded chord to an unrounded update direction. We identify the missing object as query geometry and model scalar nonuniform quantization as $Q = φ^{-1} \circ U \circ φ$. CAQ-ZO (Compander-Aligned Queries for Zeroth-Order Optimization) forms one-grid-step Rademacher stencils $z \pm Δr$ in $z = φ(x)$, maps endpoints back through $φ^{-1}$, and updates in $z$. Our theory proves the grid-span mismatch, decomposes endpoint-rounding estimator residuals, and gives stationarity bounds in which generic off-grid queries retain a $Δ^2/μ^2$ residual channel while CAQ-ZO makes the query-time residual exactly zero. Synthetic experiments isolate this channel, and matched NF4 Qwen/Llama fine-tuning shows that CAQ-ZO improves the trained NF4 baseline under the same quantizer and evaluation budget.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• RoPE attention is an exact forward-pass gradient step with softmax intact [0.0]
  We derive an exact gradient-step representation of the RoPE-softmax forward pass.<n>We prove that a nonconstant finite-cache head cannot admit a globally exact affine query readout.
  arXiv  Detail & Related papers  (2026-09-06T15:53:38Z)
• Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing [0.0]
  We revisit a degree-only arc Hamiltonian for fixed-fleet, homogeneous, uncapacitated vehicle routing.<n>Because its local penalties define only a quadratic cycle cover, ground states may contain customer cycles disconnected from the depot.<n>We prove that every ground-state routing is connected and cost-optimal under explicit penalty assumptions.
  arXiv  Detail & Related papers  (2026-08-27T09:48:35Z)
• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) is a framework that combines overcomplete equal-width tight frames, coordinate subsampling, and privacy-aware quantization.<n>SSTQ achieves mean squared error scaling while using only $lceil log N il + b$ bits per client, where $N = (d)$ is the frame size.<n>We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4b)$ to $O(2b)$.
  arXiv  Detail & Related papers  (2026-08-05T17:51:25Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• When Can Depth Replace Precision? A Resource Theory of Quantized Neural Computation [14.270378035741404]
  Pure schedules approach the relaxed class at rate $O(D-1)$ under bounded-variation time dependence.<n> Execution arithmetic can reverse this conclusion.<n>For coherent depth-$L$ first-order high-precision exponents, accuracy matching requires $D=(L)$.
  arXiv  Detail & Related papers  (2026-07-25T23:29:23Z)
• Exponential Reduction of Mesh Dependence in Quantum Estimation of Parabolic PDE Observables [3.3636842548621275]
  We develop a quantum PDE algorithm that estimates linear and quadratic observables and places fine-coarse cancellation inside the circuit before measurement.<n>We also give a non-Fourier realization based on energyorthogonal dyadic midpoint details in one dimension.
  arXiv  Detail & Related papers  (2026-07-20T16:09:24Z)
• GridProbe: Posterior-Probing for Adaptive Test-Time Compute in Long-Video VLMs [3.9266376632068485]
  GridProbe is an efficient training-free posterior-probing inference paradigm.<n>It scores evidence in answer space using a frozen VLM's own reasoning.<n>It selects question-relevant frames adaptively, resulting in sub-quadratic attention cost with little to no accuracy loss.
  arXiv  Detail & Related papers  (2026-05-11T15:57:46Z)
• Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems [0.0]
  Coherent quantum rollout for sequential decision problems requires a unitary simulator.<n>With branch-dependent valid actions, this mapping is totalized coherent rank-select over an entangled $N-bit mask.<n>We give the first reversible-circuit complexity analysis of this primitive.
  arXiv  Detail & Related papers  (2026-04-28T00:46:37Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Preserve-Then-Quantize: Balancing Rank Budgets for Quantization Error Reconstruction in LLMs [6.571619511143774]
  Quantization Error Reconstruction (QER) reduces accuracy loss in Post-Training Quantization (PTQ) by approximating weights as $mathbfW approx mathbfQ + mathbfLmathbfR$, using a rank-$r$ correction to reconstruct quantization error.<n>We propose Structured Residual Reconstruction (SRR), a rank-allocation framework that preserves the top-$k$ singular subspace of the activation-scaled weight before quantization, quantizes only the residual, and uses the remaining rank $r-
  arXiv  Detail & Related papers  (2026-02-02T12:02:21Z)
• TARG: Training-Free Adaptive Retrieval Gating for Efficient RAG [46.122203287541005]
  Training-free Adaptive Retrieval Gating (TARG) is a single-shot policy that decides when to retrieve using only a short, no-latency draft from the base model.<n>On NQ-Open, TriviaQA, and PopQA, TARG consistently shifts the accuracy-efficiency frontier.
  arXiv  Detail & Related papers  (2025-11-12T23:09:52Z)
• qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices [3.4129039170001314]
  Clustering on NISQ hardware is constrained by data loading and limited qubits.<n>We present qc-kmeans, a hybrid $k$-means that summarizes a dataset with a constant-size Fourier-feature sketch and selects centroids by solving small per-group QUBOs with shallow QAOA circuits.
  arXiv  Detail & Related papers  (2025-10-26T05:44:17Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  We study high-dimensional multi-armed contextual bandits with batched feedback where the $T$ steps of online interactions are divided into $L$ batches. In specific, each batch collects data according to a policy that depends on previous batches and the rewards are revealed only at the end of the batch. Our algorithm achieves regret bounds comparable to those in fully sequential setting with only $mathcalO( log T)$ batches.
  arXiv  Detail & Related papers  (2023-11-22T06:06:54Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  We propose an adaptive variance method, called AdaSpider, for $L$-smooth, non-reduction functions with a finitesum structure. In doing so, we are able to compute an $epsilon-stationary point with $tildeOleft + st/epsilon calls.
  arXiv  Detail & Related papers  (2022-11-03T14:41:46Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• AQD: Towards Accurate Fully-Quantized Object Detection [94.06347866374927]
  We propose an Accurate Quantized object Detection solution, termed AQD, to get rid of floating-point computation. Our AQD achieves comparable or even better performance compared with the full-precision counterpart under extremely low-bit schemes.
  arXiv  Detail & Related papers  (2020-07-14T09:07:29Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  We show that Differentially Quantized Gradient Descent (DQ-GD) attains a linear contraction factor of $maxsigma_mathrmGD, rhon 2-R$. No algorithm within a certain class can converge faster than $maxsigma_mathrmGD, 2-R$.
  arXiv  Detail & Related papers  (2020-02-06T20:40:53Z)

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.