TodayNewsResearchFieldsStacksMarketAnalytics
⌘K

Research

New papers ranked by attention, with their code, models and discussion linked. Pick a field on the left.

Research · AI field

Stochastic gradient descent

Found by the topic model: stochastic gradient descent, sample complexity.

Field page: people, tools, topics →
49papers this week−14.0% vs last week227 this month

Papers

Open problems

Rising research topics

Ask the research

Sample
ByteTrail · AI and developer-tools intelligence
NewsResearchStacksAPI
Fields · this week
All fields3775Multimodal594Agents564Frontier LLMs484Inference & serving289Image segmentation192Graph learning182Learning verifiable rewards1763D scene173Evals108Voice AI106Classifier & causal discovery90Flow matching86Forecasting time84Training & fine-tuning64Teacher policy distillation58Stochastic gradient descent49All 32 fields
WeekMonthQuarterAll
NewestMost relevant

Papers

Open problems in Stochastic gradient descent

  • Convergence guarantees for SGD in non-convex settings1 paper raises it · 1 addresses it

    Understanding when and how SGD converges in non-convex problems is critical for training deep neural networks.

    • Convergence of stochastic gradient descent for learning linear neural networksraises · addresses
  • Handling heavy-tailed noise in SGD1 paper raises it · 1 addresses it

    Heavy-tailed noise can break standard convergence guarantees, requiring robust methods like gradient clipping.

    • Weak-$L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tailsraises · addresses
  • Variance reduction with delayed feedback in non-convex optimization1 paper raises it · 1 addresses it

    Delayed feedback in distributed or asynchronous settings introduces variance that degrades convergence.

    • Variance Reduction with Delayed Feedback for Non-Convex Optimizationraises · addresses
  • Efficiency of deterministic vs. randomized zeroth-order methods1 paper raises it · 1 addresses it

    Deterministic methods may require more evaluations than randomized ones in high-dimensional non-convex problems.

    • Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Traceraises · addresses
  • Polyak-Ruppert averaging performance with momentum1 paper raises it · 1 addresses it

    Momentum can improve the convergence rate of tail-averaged SGD in strongly convex settings.

    • When Momentum Helps Polyak--Ruppert Averagingraises · addresses

Named by an AI from these papers' abstracts.

Rising research topics

Coming with more sources: more tagged papers
  • Federated learning51+34.2%
  • Agents564+9.3%
  • Frontier LLMs484+1.9%
  • Character recognition OCR17−5.6%
  • Sensing communication15−6.2%
  • Inference & serving289−6.5%
  • 3D scene173−7.0%
  • Image segmentation192−8.6%

Papers

  • arXiv cs.LGOct 20

    Convergence of stochastic gradient descent for learning linear neural networks

    Gabin Maxime Nguegnang, Bubacarr Bah, Holger Rauhut, Ulrich Terstiege

    Stochastic gradient descent (SGD) is the cornerstone of modern deep learning, yet its theoretical convergence properties remain poorly understood in non-convex settings. To address this gap, we study SGD dynamics in deep linear neural networks - simplified models that retain key non-convex characteristics while remaining analytically tractable. Building on recent results for gradient descent, we extend convergence guarantees to SGD under regularized squared loss. We establish almost sure boundedness of SGD iterates. Using the framework of asymptotic pseudotrajectories from stochastic approximation theory, our analysis establishes then, for both deterministic and adaptive step-size choices, convergence of SGD to the set of critical points under mild conditions (without relying on Lipschitz properties or whitened data). To our knowledge, this is the first work providing almost sure convergence guarantees for SGD in deep linear networks, bridging the gap between theoretical optimization and practical stochastic training.

    PDF
  • arXiv math.OCOct 20

    Variance Reduction with Delayed Feedback for Non-Convex Optimization

    Wei Jiang, Dingzhi Yu, Zechao Li

    We study variance reduction for non-convex optimization when gradient evaluations return with a delay. The server can update the parameter while earlier evaluations remain unfinished. We first analyze an ordered recursive momentum estimator for stochastic optimization. Under average smoothness and bounded variance, its oracle complexity is $O(1+σ^2ε^{-2}+LΔ_f(1+σ/ε+τ)ε^{-2})$, where the target is an expected squared gradient norm of at most $ε^2$ and $τ$ bounds the feedback delay. We next study finite sums with $n$ components and obtain $O(n+LΔ_f(\sqrt n+\min\{τ,n-1\})ε^{-2})$ evaluations. An asynchronous snapshot variant continues updating during full-gradient computations under an explicit bound on their completion time. For the stochastic method, we further replace a maximum-delay bound by a bound on the weighted amount of missing feedback.

    PDF
  • arXiv cs.GTOct 20

    Fixed Sets and the Hardness of Computing Correlated Equilibria

    Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm +1

    We show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, and thus polynomial-time equivalent to finding a Nash equilibrium. This challenges the conventional view in game theory that correlated equilibria are more tractable objects than Nash equilibria. From a conceptual standpoint, we connect correlated equilibria to a natural generalization of fixed points, which we call fixed sets. A fixed set of a continuous function $f$ is a nonempty finite set $S$ such that $S \subseteq \operatorname{conv} f(S)$. Our main technical contribution is to prove that computing a fixed set is PPAD-hard even at inverse polynomial precision.

    PDF
  • arXiv math.OCOct 20

    Weak-$L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails

    Alyona Nekrasova, Makar Sidorov, Savelii Chezhegov, Alexander Gasnikov, Margarita Preobrazhenskaia +2

    Gradient clipping is a key tool for obtaining high-probability convergence guarantees for stochastic first-order methods under heavy-tailed noise. Existing analyses typically assume a bounded central moment of order $α\in(1,2]$, which excludes distributions with tails of order $u^{-α}$ at the critical exponent. In this paper, we consider smooth convex optimization under affine heavy-tailed noise, whose scale may grow with the gradient norm. We derive high-probability convergence guarantees for clipped SGD (Clip-SGD) and its accelerated variant Clip-SSTM under a weak-$L^α$ tail condition, which is strictly weaker than the corresponding moment bound. For $1<α<2$, the clipping bounds have the same powers of the clipping level as in the moment case, and both methods attain the additive stochastic rate $K^{-(α-1)/α}$. The gradient-dependent noise contributes a faster-decaying term of order $K^{-2(α-1)/α}$, up to logarithmic factors. At $α=2$, we characterize the additional logarithmic factor on the Lorentz scale and establish its necessity for the additive error at fixed confidence. We also analyze Clip-SGD with prescribed clipping levels and derive finite-horizon guarantees for…

    PDF
  • arXiv cs.LGOct 20

    When Momentum Helps Polyak--Ruppert Averaging

    Alexandra Suvroikova, Darina Dvinskikh, Yuriy Dorn, Alexander Gasnikov

    Polyak--Ruppert averaging gives SGD and momentum methods the same asymptotic covariance. We characterize how fast finite runs reach it and how far they can be parallelized. For strongly convex quadratics with additive noise, we prove an online--offline bridge: the empirical risk minimizer on the samples of a tail average is one Newton step from the tail-averaged query point of any online procedure. For SGD, heavy ball, and Nesterov's method with constant momentum, this step is a boundary term at the two ends of the tail and splits the gap to the offline estimator into center, covariance, and shape errors. Necessary and sufficient conditions show that, on the least curved direction, the center error sets the pace: SGD needs $m\ggκ^2$ rounds but momentum only $m\ggκ$, where $κ$ is the condition number, so at sample size $N$ the critical batch size grows from $Θ(\sqrt{N}/κ)$ to $Θ(\sqrt{N/κ})$. The covariance error separates the momentum methods: heavy ball has relative variance excess $Θ(κ^{3/2}/m)$ along the stiffest direction, whereas Nesterov has relative error $O(\sqrtκ/m)$ in every direction. The shape error is method-independent by a Berry--Esseen bound uniform in $κ$ and…

    PDF
  • arXiv cs.LGOct 20

    Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

    Yuxing Peng, Zhiqing Tang, Weijia Jia

    Low curvature trace, an effective rank condition, is a common explanation for why randomized zeroth-order methods scale to high-dimensional tasks such as language model fine-tuning. Can deterministic methods achieve the same savings? We show that they cannot. We study finding $\varepsilon$-stationary points of $L$-smooth nonconvex functions on $\mathbb{R}^d$ from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most $LE$; this is the effective rank condition used to explain zeroth-order fine-tuning. When $ET\le d$, the Gaussian two-point method that such fine-tuning uses needs only $O(ET)$ calls if it rejects steps that raise $f$, where $T=LΔ/\varepsilon^2$ is the iteration count of gradient descent from initial gap $Δ$, and we prove that every randomized method needs $Ω(ET)$ calls, so this cost is optimal up to constants. In contrast, every deterministic method needs $\widetildeΩ(d\min\{T,\sqrt{ET}\})$ calls, and adaptive subspace search attains $O(d\min\{T,\sqrt{ET}\})$: a deterministic method pays about $d$ calls per discovered direction, and the trace budget allows about $\sqrt{ET}$ directions. Determinism…

    PDF
  • arXiv stat.MLOct 19

    Communication Complexity of Universal Features

    Lunjia Hu, Anish Jayant, Peter Li, Princewill Okoroafor, Abhishek Shetty

    Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes $X\sim D$ and produces a finite encoding before a task $f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}$ is specified. For each task, a decoder must predict $f(X)$ with error at most $\varepsilon$ under $D$. We construct an encoder that outputs a representation with $O(d^{*}\log(1/\varepsilon))$ bits, where $d^{*}$ is the dual VC dimension of $\mathcal{F}$. Our encoder greedily selects $O((d^{*}/\varepsilon)\log(1/\varepsilon))$ functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every $d^* \ge 1$ and $\varepsilon < 1/4$ up to a universal constant factor, and instance-wise optimal for every family $\mathcal{F}$ up to an…

    PDF
  • arXiv cs.AIOct 19

    Unified Sharp Bounds on Probabilities of Causation

    Xin Shu, Ang Li

    Probabilities of causation (PoCs) have developed steadily, from the binary measures first introduced by Pearl to the non-binary setting recently studied by Shu et al. As the theory has matured, PoCs have found applications in a growing range of areas, including personalized medicine, marketing and legal attribution. Shu et al. proposed closed-form bounds for multi-valued treatments and outcomes and proved them valid, but left their sharpness in high dimensions open. We close this gap with a mathematical proof. We further show that $\PNS$, $\PSub$, $\PRep$ and $\PN$ are all special cases of a single, more general formula. Combined with their equivalence classes, this settles the question of sharp bounds for discrete PoCs from experimental and observational data: in every dimension, they are given in closed form by a single theorem.

    PDF
  • arXiv math.OCOct 19

    Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity

    Youran Dong, Junfeng Yang, Wei Yao, Jin Zhang

    Bilevel optimization provides a framework for machine learning tasks such as hyperparameter optimization, data reweighting, and meta-learning. Existing Newton-based bilevel methods typically rely on the classical hypergradient formula, which is generally unavailable when lower-level solutions are nonunique and the lower-level Hessian is singular. We develop two Newton-based methods beyond lower-level strong convexity by exploiting curvature shared by the lower-level and multiplier updates. Newton-based GALET handles potentially singular lower-level curvature under a positive spectral-gap condition, exploiting its range structure to avoid the squared-Hessian multiplier system used in GALET. Newton-based BAMM uses a strongly convex aggregation model when the lower-level objective is convex and the upper-level objective is strongly convex in the lower-level variable. We establish convergence guarantees and improved complexity bounds relative to GALET and sl-BAMM under the corresponding assumptions. We further introduce GNBO, a generalized Newton-based framework that captures the shared-curvature structure of the proposed methods and several existing Newton and quasi-Newton bilevel…

    PDF
  • arXiv stat.MLOct 19

    Corrected Block Sparse Spectral Optimization: Exact Models, Finite Identification, and Local Dynamics

    Omid Shams Solari

    The block generalized-power method pairs threshold-based support selection with inexpensive Stiefel updates, but the standard block formulation conflates two nonequivalent objectives and leaves inactive components, threshold ties, and post-selection refitting ill-specified. We rebuild the model from the primal. Eliminating each loading column from the normalized loading-ball problem gives a sum of soft-thresholded Euclidean norms (A-SUM); the squared-threshold objective in common use arises from a quadratic lift (A-SQ). We prove both identities, exhibit a two-component instance whose maximizers disagree, and specify explicit conventions for zero-response columns, ties, rank deficiency, and mask-before-refit. For A-SQ we separate the historical full-polar iteration from a safeguarded Riemannian ascent and prove, for the latter, whole-sequence convergence via a sufficient-ascent lemma, a relative-error lemma, and the Kurdyka-Lojasiewicz property, which applies because the soft-threshold objective and the Stiefel constraint are semi-algebraic. A strict threshold margin then forces finite identification of the support and sign pattern. The post-identification map is ordinary power…

    PDF
  • arXiv cs.LGOct 19

    Stochastic Tracking of Drifting Affine Fixed Points

    Sajad Khodadadian

    Linear stochastic approximation (SA) is widely used to estimate fixed points from noisy observations, but most finite-time analyses assume that the underlying operator remains fixed. We study linear SA with time-varying affine operators, where the fixed points change over time and the observation noise may be correlated across rounds. For constant-stepsize updates, we establish a bound on the cumulative expected squared distance between the iterates and the corresponding fixed points. The bound accounts for the initial error, observation noise, and changes in the fixed points over time. We also establish lower bounds for scalar Gaussian models, showing that, under specified conditions, a suitably chosen constant stepsize achieves the smallest possible worst-case cumulative error up to constant factors, even compared with estimators that use future observations. These results further quantify the effect of temporal correlation on estimation accuracy. Since choosing an appropriate stepsize generally requires knowledge of the noise level and how much the fixed points change, we develop an adaptive method that uses an additional bounded, unbiased observation of the fixed point to…

    PDF
  • arXiv cs.CLOct 18

    Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares

    Yuxiang Zhao, Ting Gan

    We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin $δ$. For any fixed Archimedean quadratic module with prescribed generators and any fixed bound on the degree of the objective, we prove a uniform certificate-degree upper bound of $O(δ^{-1/2}\log^2(2/δ))$ for normalized polynomial objectives. We show that this bound is sharp by constructing a matching lower-bound example in three variables, thereby establishing that the dependence on $δ$ is optimal. These matching bounds also yield sharp worst-case convergence rates for the Lasserre hierarchy.

    PDF
  • arXiv cs.LGOct 18

    Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

    Matan Schliserman, Tomer Koren

    We study the last iterate of stochastic gradient descent (SGD) with a constant stepsize on smooth convex objectives in the low-noise and interpolation regimes, where the variance $σ_\star^2$ of the stochastic gradients at the optimum is small or zero. We establish that after $T$ steps of SGD on $β$-smooth convex losses with any constant stepsize $0<η<2/β$, the last iterate attains expected excess risk $\widetilde O\bigl(\tfrac{1}{η(2-βη)^3T}+\tfracη{(2-βη)^4}σ_\star^2\bigr)$, which gives the rate $\smash{\widetilde O(1/T)}$ for every constant stepsize in the interpolation regime ($σ_\star=0$), matching the $Ω(1/T)$ lower bound up to logarithmic factors and improving upon the $O(1/\sqrt T)$ rate of Attia et al. (2026) for $η=1/β$. Our analysis is based on a new technique, which compares the second moments of the stochastic gradients along the SGD trajectory across only logarithmically many time scales. For quadratic losses in the interpolation regime, an adaptation of this technique gives an $O(1/T)$ rate for every constant stepsize, extending the recent optimal rate for the randomized Kaczmarz method of Derezinski and Dong (2026) to stepsizes above the greedy stepsize with an…

    PDF
  • arXiv math.OCOct 18

    When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?

    Qixin Zhang, Shi Fu, Shengminjie Chen, Chao Qian, Dacheng Tao

    Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algorithm is known to attain the tight $(1-e^{-γ})$-approximation guarantee, where $γ$ denotes the submodularity ratio. However, when considering general matroid constraints, \emph{how well standard greedy can perform} has remained a longstanding open question. In this paper, we resolve this question by studying the worst-case approximation guarantee $R_{\mathrm{gr}}(γ,r)$ of standard forward greedy, where $r$ is the rank of matroid. Specifically, our first contribution is the following refined lower bound \begin{equation*} R_{\gr}(γ,r)\ge \max\left\{ \fracγ{r}, \frac{γ^2} {B_γ+\sqrt{γ(r-1)}}, \frac{γ^{r+1}} {2-γ+γ^{r+1}}, \frac{γ^2} {14\left(B_γ+\sqrt{γ(1-γ)(r-1)}\right)} \right\}, \end{equation*} where $B_γ\triangleq2-γ+γ^2$. This lower bound not only strictly improves upon the previous guarantee of $0.4γ^2/(1+\sqrt{γr})$, but also can recover the classical $1/2$-approximation guarantee at $γ=1$. Subsequently, a corresponding upper bound is established for $R_{\mathrm{gr}}(γ,r)$, namely,…

    PDF
  • arXiv cs.LGOct 18

    Sampling and Curvature in First-Exit Comparisons for Momentum SGD

    Haiyi Li

    First-exit prediction for momentum SGD depends on sampling information that pointwise gradient laws omit. Strongly convex finite pools with identical pointwise laws and matched iid momentum dynamics can have different reshuffled exits; even analytic pools with uniformly close pointwise laws can have separated exit probabilities. For persistent sampling in one dimension, we establish an explicit $O(h)$ mean-exit comparison with a finite-rate switching process under nonvanishing component velocities and step-size conditions; iid sampling instead averages to an ODE. Retaining realized minibatches and sampled curvature yields finite-window exit brackets beyond this regime. In 32 trained ridge-logistic runs, 29 meet prespecified targets with rounding-certified brackets; an enclosure control explains most of the width advantage. Exact-real certificates establish finite means at the original tested radii for three ResNet-18 checkpoints and give local finite-mean conditions for tanh and ViT networks; their upper bounds remain loose, and original-radius ViT mean guarantees remain unresolved despite 128 fresh continuation paths. A two-network replication gives 32/32 successful seeds in…

    PDF
  • arXiv cs.DCOct 18

    An Information-Geometric Framework for OCS-Reconfigurable Interconnect Topology in Large-Scale AI Clusters

    Shintaro Yoshizawa

    Optical Circuit Switches (OCS) make inter-pod wiring in AI clusters programmable, posing design questions on wiring choice, symmetry departure, and reconfigurations. We present a unified information-geometric framework to address these issues.A wiring is a point in a probability simplex over circuits within a degree polytope. Departure from a symmetric Fat-Tree prior $\mathbf{q}$ is measured by $\DKL(\cdot \,\|\, \mathbf{q})$. The cost $U$ is the smoothed DAG critical-path length, whose gradient equals path marginals of a Gibbs distribution via forward--backward recursion.For free energy $F_{β_1} = U + β_1^{-1} \DKL(\cdot \,\|\, \mathbf{q})$, we prove well-posedness, monotonic dependence on $β_1$, adaptation bounds via Jeffreys divergence, and a symmetry principle for static optimality. An entropic proximal-gradient method updates multiplicatively with a $|V|$-dim dual KL projection, achieving linear convergence.For time-varying traffic, a threshold policy yields regret $O(\sqrt{ΓC V_1 T})$ against the switching-free optimum. Traffic changes are detected by a multinomial GLR--CUSUM detector with non-asymptotic false-alarm bounds. Multi-job generalized-mean fairness aligns with…

    PDF
  • arXiv math.OCOct 18

    Non-Acceleration of the Heavy-Ball Method in 1D

    Konstantinos Fotopoulos, Michael Helcig, Karl Deck, Jannis Alsbach

    Despite having an asymptotically optimal rate of convergence on convex quadratics, the acceleration of Polyak's heavy-ball method and a characterization of its dynamics within more general settings have remained long standing open problems. Recently, the work of Goujaud et al. [Math. Program. (2025)] made progress regarding acceleration in the context of smooth, strongly convex minimization: for a small enough inverse condition number, either the method does not accelerate on quadratics, or there exists a smooth strongly convex function such that heavy-ball cycles over the roots of unity. The constructed functions have two variables, thus leaving the question of acceleration over univariate functions open. In this work, we use a Fourier-based analysis to i) provide a proof for the non-acceleration of the heavy-ball method over the class of univariate smooth strongly convex functions. We also ii) provide a strict enlargement of the previous root-of-unity cycling region, with insights regarding the "fractional" sets of Goujaud et al. [arXiv:2502.19916], and iii) give a higher dimensional cycling instance which is not covered by root-of-unity cycling.

    PDF
  • arXiv cs.LGOct 18

    The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

    Guangjian Zhang

    Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$, the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$, uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the…

    PDF
  • arXiv stat.MLOct 18

    Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals

    Guangjian Zhang

    Under the quantifier $\exists A\,\forall D$, where the realizable distribution and its marginal are unknown, we determine the finite-class sample-complexity exponent for strict replicability: two independent samples and one shared seed must produce identical functions. For $\varepsilon=δ=ρ=10^{-4}$, the worst case over $|H|\le M$ is $Θ((\log M)^2)$, without iterated logarithms. For $d\ge1$, $0<\varepsilon\le1/16$, and $0<δ,ρ\le10^{-3}$, every randomized, possibly improper learner valid throughout an explicit anchored realizable family requires $Ω(d^2/(\varepsilonρ^2))$ samples. For the full Boolean class $P_d$, $d\ge2$, in the same parameter range, we prove the matching characterization $Θ(d^2/(\varepsilonρ^2)+\varepsilon^{-1}\log(1/δ))$ using a proper Poissonized ball-sampling algorithm. We also give an explicit proper Gibbs upper bound for every finite measurable Boolean class. Our lower bound uses square-root probabilities and volumetric packing; the Gibbs proof builds on established coupling and generalization identities. Finally, we characterize the known-marginal worst case for $P_d$, showing why that interface must be kept distinct.

    PDF
  • arXiv cs.ITOct 17

    Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation

    Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan

    We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $r<w$ bits to estimate $x^\top y$. Both vectors lie in the $d$-dimensional Euclidean unit ball. Protocols may be randomized, and computation is unrestricted. Performance is measured by $d$ times the worst-case mean-squared error over $x,y$, averaged over protocol randomness. First, we show that query-independent reading cannot benefit from extra storage. Any such reader is equivalent to fully reading an $r$-bit message, even when later reads depend on previously returned bits. At fixed positive rates $W=w/d$ and $R=r/d$, the normalized minimax error converges to $1/(4^R-1)$, independent of $W$. The upper bound was already known [Ordentlich and Polyanskiy, 2025]. We prove the matching lower bound for arbitrary scalar decoders, extending the result for unbiased compressors [Safaryan et al., 2020]. Then, we show that query-dependent reading makes extra storage useful. We construct a two-batch protocol using Gaussian projections and random thresholds,…

    PDF
Load more