acceptodds
Desk rejected at ICLR 2027

Sharp Root-Exponential Rates for Smooth Convex Optimization in a Serial Finite-Bit Model

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

We establish the sharp convergence rate of deterministic smooth convex optimization under simultaneous limits on bit computation and live memory, providing a concrete benchmark for first-order algorithm design with finite resources. In fixed dimension , we consider a finite-bit model in which useful numerical replies must be fully consumed in sequence. Each round includes one oracle call and permits at most bit actions; live storage is bounded by bits, where is the input bit length and is the current numerical precision scale. We construct a single uniform algorithm with increasing precision whose reported point satisfies at every sufficiently late round, uniformly over admissible rounding errors. The algorithm requires no prior knowledge of the smoothness constant, minimizer distance, target accuracy, or horizon. Conversely, for every deterministic program obeying the bit-work budget and reply protocol, even with unrestricted memory, we construct one fixed smooth convex objective whose run under a fixed nearest-grid oracle satisfies along an unbounded subsequence of rounds. Together, these bounds establish as the sharp asymptotic order of eventual every-round guarantees in this protocol. With bit actions per round and serial reply consumption, the same root-exponential order holds in total charged bit work.

Primary area:
optimization
Keywords:
convex optimization, first-order methods, finite-precision oracles, bit complexity, memory-constrained optimization, convergence lower bounds

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_o3SQOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper establishes the convergence rate of deterministic smooth convex optimization under limits of computation and live memory. It proposes an anytime finite-precision algorithm that achieves an objective gap exp⁡(−Ω(n))\exp(-\Omega(\sqrt{n})) without requirements on the smoothness, target accuracy and horizon. It also proves that the lower bound of the proposed algorithm. These bounds establish exp⁡(−Θ(n))\exp(-\Theta(\sqrt{n})) the sharp asymptotic order guarantee of the proposed model.

Critical strengths

This paper constructs a uniform algorithm requiring no prior knowledge of the smoothness constant, target accuracy, and horizon. They also provide the upper bound for this algorithm and lower bound for all deterministic algorithms in the proposed model. The theoretical analysis show that the root-exponential rate is a sharp rates with the protocol.

Critical weaknesses
  1. This paper assume that the next useful reply can only arrive after the current reply has been fully scanned. However, this does not necessarily hold in the practical systems.
  2. The constants in the theoretical bounds depend strongly on the dimension d. In the analysis, d is treated as fixed. The scalability to higher dimensional problem is not clear.
  3. The abstract is notation-heavy and introduces several symbols without sufficient explanation. For example, the precise meaning of the reported point and n_0 are not clearly defined, making the paper a little difficult to understand.
Questions for authors

Please refer to the weakness part.

3 comments
AuthorsOpenReview ↗

Response to Reviewer o3SQ (1)

Thank you for your helpful review. We appreciate your recognition that the same algorithm applies without prior knowledge of the smoothness constant, target accuracy, or horizon, and that we provide its upper bound together with a matching lower bound for all deterministic algorithms under the stated model. Your comments on practical interfaces, dimension dependence, and the abstract have helped us clarify the scope of the results and improve our paper. We respond to each point below.

  • W1: Full reply consumption and practical systems

This paper assume that the next useful reply can only arrive after the current reply has been fully scanned. However, this does not necessarily hold in the practical systems.

Thank you for pointing out this limitation. We agree that not all practical systems require full reply consumption.

Our main motivation is to account for the communication reception cost of higher precision through the same bit operations used by our serial Turing machine. Requiring replies to be read in full is one simplified way to do this, but it is not the only choice. Allowing the host to specify which oracle bits it wishes to receive may lead to different sharp convergence rates. We have added the following discussion to the revised manuscript.

Section 3.2 of the revised manuscript (Reply Protocol):

“We adopt this reply protocol to make the computational cost of numerical precision explicit. Counting oracle calls alone assigns the same cost to coarse and arbitrarily precise replies. Charging for complete reply consumption is the approach adopted in this work to account for communication costs in a simplified communication setting.”

Section 7 of the revised manuscript (Discussion and Limitations):

“At the oracle interface, requiring regular numerical replies to be consumed in full and in sequence allows communication reception to be charged through the same bit actions as local computation. This simplified protocol also reflects the cost structure of restricted numerical communication protocols (Tsitsiklis & Luo, 1987). Future work could determine whether allowing the optimizer to choose which bits it receives leads to different sharp convergence rates.”

These changes are marked in blue. Full consumption also has practical examples. Some devices and services use sequential interfaces that require the current message to be read or drained to preserve message boundaries and interaction state. This simplifies buffering and request management. For example:

  1. AMD/Xilinx AXI4-Stream FIFO. The receive procedure requires the processor to read the current packet in full from the FIFO before proceeding to the next packet. Official manual, pp. 29, 42

  2. HTTP/1.1 persistent connections. A client must read the entire response body to reuse the same connection. The drain_conn() method in urllib3 also discards remaining data by reading it. RFC 9112, §9.3, urllib3 documentation

  3. MySQL streaming result interfaces. With mysql_use_result(), the current result must be drained before further queries can proceed on the same connection. The consume_results=True option in Connector/Python also discards remaining results by reading them. C API documentation, Connector/Python documentation

When an optimizer accesses an external numerical service through such an interface, it still incurs the cost of consuming the full reply even if it uses only part of the information.

AuthorsOpenReview ↗

Response to Reviewer o3SQ (2)

  • W2: Dimension dependence and higher dimensional problems

The constants in the theoretical bounds depend strongly on the dimension d. In the analysis, d is treated as fixed. The scalability to higher dimensional problem is not clear.

Thank you for raising this question. Our results apply in every fixed finite dimension and characterize the sharp root exponential order in rounds or cumulative bit operations. The constants in both bounds are conservative choices and have not been specially optimized. The paper therefore does not determine the optimal asymptotic dependence on dd. We consider this a worthwhile direction for future work. We have added the following statement to Section 7 of the revised manuscript:

“Our results apply in every finite dimension and give a sharp asymptotic order in nn for each fixed dd. The constants in both bounds have not been specially optimized. Determining the optimal asymptotic dependence on dd remains an open problem.”

This addition is marked in blue.

  • W3: Notation and definitions in the abstract

The abstract is notation-heavy and introduces several symbols without sufficient explanation. For example, the precise meaning of the reported point and n_0 are not clearly defined, making the paper a little difficult to understand.

Thank you for identifying this issue. We apologize that some notation was not sufficiently explained. We have reduced the detailed notation in the abstract and introduction of the revised manuscript. Its abstract now defines znz_n as the output point at the end of round nn. We have removed the n0n_0 used in the abstract of the original manuscript and now express the scope of the guarantee through the phrase “at every sufficiently late round on each fixed instance.” The revised abstract reads:

“We establish the sharp convergence rate of deterministic smooth convex optimization under simultaneous limits on bit computation and memory in use, providing a concrete benchmark for first-order algorithm design with finite resources. We adopt a simplified serial bit model that requires oracle replies to be read in full. Computation, memory access, addressing, and communication at the receiving interface are charged through the same bit reads, writes, and head movements, while memory use counts all simultaneously allocated bits. Oracle evaluation and delivery remain external. Each round includes one oracle call and permits O(d)O(d) bit actions; memory use is bounded by O!(A+d[p+⌈log⁡2(d+1)⌉])O\\!\left(A+d[p+\lceil\log_2(d+1)\rceil]\right) bits, where dd is the problem dimension, AA is the total number of bits encoding the dimension and the initial point, and pp is the current working precision. We construct a single algorithm with increasing precision that, in every fixed dimension, produces an output point znz_n at the end of round nn satisfying F(zn)−min⁡xF(x)≤exp⁡[−Ωd(n)]F(z_n)-\min_x F(x)\le\exp[-\Omega_d(\sqrt n)] at every sufficiently late round on each fixed instance, uniformly over admissible rounding errors. The algorithm requires no prior knowledge of the smoothness constant, distance from the initial point to a minimizer, target accuracy, or horizon. Conversely, for every deterministic program obeying the budget on bit operations and reply protocol, even with unrestricted memory, we construct one fixed smooth convex objective whose run under an oracle with fixed rounding to the nearest grid point satisfies F(znj)−min⁡xF(x)≥exp⁡[−O(nj)]F(z_{n_j})-\min_x F(x)\ge\exp[-O(\sqrt{n_j})] along an unbounded subsequence of rounds. Together, these bounds establish exp⁡[−Θ(n)]\exp[-\Theta(\sqrt n)] as the sharp asymptotic order of guarantees that hold on every fixed instance at every sufficiently late round in this protocol. With Od(1)O_d(1) bit actions per round and serial reply consumption, the same root-exponential order holds in the total number of counted bit actions.”

These changes are marked in blue in the revised manuscript.

Thank you again for your comments. We hope these explanations and revisions clarify the scope of the model, the limitations of our dimension analysis, and the meaning of the main results.

Dear Reviewer,

Thank you again for your thoughtful review. Since the discussion period ends soon, we’d be grateful to hear whether our response has addressed your concerns. If anything remains unclear, we’d be happy to discuss it further.

Best regards,

The Authors

Reviewer_gsGqOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors establish the complexity of smooth convex optimization in fixed dimension, assuming a serial finite-bit model. The resource accounting charges single-bit reads/writes and one-cell head moves. Memory is limited and accounts for input, oracle queries and replies, history, scratch and reported estimates. The algorithm is required to read the full oracle reply before receiving the next reply. The main results are:

  1. An upper bound (Theorem 1). The authors propose an algorithm that achieves optimality gap C1exp⁡(−c1n)C_1 \exp(-c_1 \sqrt{n}) for every admissible problem instance at every sufficiently late round nn.
  2. A lower bound (Theorem 2). The authors show that for every deterministic algotithm fulfilling the considered bit computation limits, there exists a fixed smooth convex objective for which the optimality gap is bounded below by C2exp⁡(−c2n)C_2 \exp(-c_2\sqrt{n}) along an unbounded subsequence of rounds.

Together, these bounds establish the optimal complexity in the considered model. The upper bound is proved using finite-precision ellipsoid method (and a version of ternary search for d=1d=1), while the lower bound is established through adversarial construction with nested intervals.

Critical strengths

Novelty: finite bit complexity of optimization methods is an important yet relatively underexplored topic.

Sharp convergence rate under strict computational constraints: The authors establish matching upper and lower bounds under strict computational constraints, thus establishing the optimal asymptotic rate in the proposed model. Moreover, the proposed algorithm has the anytime property.

Critical weaknesses

A justification/motivation for the proposed computational model should be provided. In particular, the bounds rely on mandatory reading of the full oracle reply, whereas some existing works consider a more flexible access to the useful information, see, e.g., "Improving the Bit Complexity of Communication for Distributed Convex Optimization" by Ghadiri et al. and "Differentially Quantized Gradient Methods" by Lin et al. Also, consider commenting the decision to charge every head move rather than using a RAM model.

Questions for authors
  1. Please improve readability of the paper. In particular consider defining finite anchor, uniform implementation, resident regions and other terms before the first use.
  2. Literature review is currently centered around complexity bounds. Consider giving more attention to the comparison of various computational models. Moreover, the related work section is currently incomplete. Consider discussing, for example, the following works: "Optimal inexactness schedules for Tunable Oracle based Methods" by Dessel and Glineur, "The Bit Complexity of Efficient Continuous Optimization" by Ghadiri et al., "Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal" by Blanchard et al.
  3. Please comment on the origin or meaning of the constants 2122^{12} and 2202^{20} in the computation and memory budgets.
6 comments
AuthorsOpenReview ↗

Response to Reviewer gsGq (1)

Thank you for your careful review. We appreciate your recognition of the importance of finite bit complexity in optimization, as well as the matching bounds under strict resource constraints and the anytime guarantee. Your specific suggestions on the model, terminology, and related work have helped us improve the paper. We address them below.

  • W1: Motivation for the computational model and the choice of serial access rather than RAM

A justification/motivation for the proposed computational model should be provided. In particular, the bounds rely on mandatory reading of the full oracle reply, whereas some existing works consider a more flexible access to the useful information, see, e.g., "Improving the Bit Complexity of Communication for Distributed Convex Optimization" by Ghadiri et al. and "Differentially Quantized Gradient Methods" by Lin et al. Also, consider commenting the decision to charge every head move rather than using a RAM model.

Thank you for raising this point. Our model combines a serial Turing machine operating on bits with a protocol that requires full reply consumption.

The serial Turing machine is a simplified computer model and differs substantially from modern hardware. We use it to derive the costs of computation, memory access, addressing, and other program operations from one fully specified virtual machine. Stored bits, head positions, and the control state describe the execution state explicitly. This lets us derive execution costs from elementary actions. Introducing RAM would require additional conventions for charging address processing and random access, and for relating those costs to other bit operations.

Full reply consumption is a simplified choice that brings the communication reception cost of higher precision into the same accounting rules. It is not the only choice. Allowing the host to specify which oracle bits it receives may lead to different sharp convergence rates.

The relevant passage in Section 2.1 of the revised manuscript reads:

“We extend the resource accounting of finite-precision computation and storage in Blanchard et al. (2023b) by specifying the execution of the entire optimization program in a serial model based on a Turing machine. Every host operation is implemented through charged bit reads, bit writes, and head moves. We additionally require numerical replies to be consumed in full and charge each bit read, much as the restricted prefix protocols of Tsitsiklis & Luo (1987) charge each transmitted numerical bit. Together, these rules provide uniform accounting for computation, memory, addressing, and communication reception through basic bit operations, with all allocated storage counted in bits. Oracle evaluation and delivery remain external.”

Section 7 of the revised manuscript discusses RAM models as follows:

“The serial Turing machine provides a simplified, concrete virtual machine in which every host operation is implemented through basic bit actions and allocated storage is counted in bits. This gives a common basis for resource accounting, although it omits the random access provided by RAM models. Extending the analysis to those models would clarify how access mechanisms closer to modern hardware affect the convergence guarantees.”

Section 7 of the revised manuscript also discusses the reply protocol:

“At the oracle interface, requiring regular numerical replies to be consumed in full and in sequence allows communication reception to be charged through the same bit actions as local computation. This simplified protocol also reflects the cost structure of restricted numerical communication protocols (Tsitsiklis & Luo, 1987). Future work could determine whether allowing the optimizer to choose which bits it receives leads to different sharp convergence rates.”

These changes are marked in blue. The models of Lin et al. and Ghadiri et al. that you mentioned are also included in Section 2.1 and Appendix A of the revised manuscript, as detailed in our response to Q2 below.

AuthorsOpenReview ↗

Response to Reviewer gsGq (2)

  • Q1: Terminology and readability

Please improve readability of the paper. In particular consider defining finite anchor, uniform implementation, resident regions and other terms before the first use.

Thank you for this suggestion. We have revised the wording and terminology. The three examples you identified now read as follows:

Original termRevised wording
finite anchor“initial point aa whose coordinates have finite binary expansions”
uniform implementation“one fixed program for all dimensions and instances”
resident regions“allocated memory regions”

Section 3.1 of the revised manuscript also states explicitly:

“The same deterministic program is used for all dimensions and precisions. Dimension, precision, and loop counters are stored in memory and included in the resource accounting.”

We have reviewed similar terminology elsewhere and replaced it with common wording or added definitions where it is used. These changes are marked in blue in the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer gsGq (3)

  • Q2: Computational models and additional related work

Literature review is currently centered around complexity bounds. Consider giving more attention to the comparison of various computational models. Moreover, the related work section is currently incomplete. Consider discussing, for example, the following works: "Optimal inexactness schedules for Tunable Oracle based Methods" by Dessel and Glineur, "The Bit Complexity of Efficient Continuous Optimization" by Ghadiri et al., "Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal" by Blanchard et al.

Thank you for recommending these works. We now discuss all three and have added Section 2.1 (Computational Models and Resource Constraints) to the revised manuscript to compare how computation, memory, oracle access, and communication are accounted for. The relevant paragraph reads:

“Computational models used in previous works account for different parts of the optimization process. Van Dessel & Glineur (2023) prescribe oracle costs as a function of accuracy, without specifying host computation or storage. Tsitsiklis & Luo (1987); Lin et al. (2022); Basu et al. (2026) count communicated messages or oracle replies in bits, excluding local computation and storage from these measures. Blanchard et al. (2023a); Menart et al. (2026) use exact real-valued oracles with unrestricted internal computation and temporary memory, while restricting the bits retained between queries. Ghadiri et al. (2023) analyze bit operations and numerical widths on explicit inputs. Ghadiri et al. (2024) analyze communication in distributed optimization and bit operations in centralized least-squares regression. Blanchard et al. (2023b) study two models: one uses exact real-valued oracle replies and limits only memory retained between queries; the other uses finite replies and limits memory throughout computation, with local work bounds for their finite-precision implementation.”

Appendix A.1 of the revised manuscript also contains the comparison table below. Settings with different resource accounting within the same paper appear in separate rows. The additions are marked in blue.

Table 2 of the revised manuscript. Resource accounting in related computational models. ✓ denotes explicit treatment and × denotes no separate treatment of the indicated item.

Work and settingLocal workMemory limitAddress costOracle costMessage bitsFull sequenceMachine model
Van Dessel & Glineur (2023)×××✓×××
Tsitsiklis & Luo (1987), general protocols××××✓××
Tsitsiklis & Luo (1987), numerical prefixes××××✓✓×
Lin et al. (2022)××××✓××
Ghadiri et al. (2024), distributed optimization××××✓××
Ghadiri et al. (2024), centralized least squares✓××××××
Basu et al. (2026), binary replies××××✓××
Blanchard et al. (2023a)×✓×××××
Menart et al. (2026)×✓×××××
Ghadiri et al. (2023)✓××××××
Blanchard et al. (2023b), memory between queries×✓×××××
Blanchard et al. (2023b), memory throughout computation✓✓×××××
This work✓✓✓×✓✓✓

Local work excludes oracle computation; oracle cost covers reply generation beyond call counts. Memory limit bounds storage capacity; address cost covers locating and accessing data. Machine model specifies host execution through elementary bit actions. Full sequence requires reading or transmitting consecutive numerical prefixes or complete fixed-format numerical replies.

  • Q3: Constants in the computation and memory budgets

Please comment on the origin or meaning of the constants 2122^{12} and 2202^{20} in the computation and memory budgets.

Thank you for this question. Our main intended constraints are O(d)O(d) bit actions per round and O(A+d[p+⌈log⁡2(d+1)⌉])O(A+d[p+\lceil\log_2(d+1)\rceil]) bits of memory. The two constants are conservative sufficient choices that leave room for fixed implementation costs independent of dimension and precision. We have not specially optimized them. We have added the following explanation to Section 3.3 of the revised manuscript:

“These resource constraints are intended to enforce O(d)O(d) bit actions per round and O(A+d[p+⌈log⁡2(d+1)⌉])O(A+d[p+\lceil\log_2(d+1)\rceil]) bits of memory. We choose generous constants to accommodate fixed implementation overheads that do not depend on dimension or precision.”

Thank you again for your specific suggestions on the model, presentation, and comparison with prior work. We hope these additions clarify our modeling choices and their scope, and make the paper easier to read and assess.

Reviewer_NnmZOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies smooth convex optimization when the costs of reading, storing, and processing numbers are taken into account. For fixed dimension, the authors propose an algorithm with increasing precision that achieves a root-exponential convergence rate. They also prove a lower bound showing that this rate is optimal in asymptotic order under their computational model.

Critical strengths
  1. The upper and lower bounds has the same root-exponential order for fixed dimension under the stated model.
  2. The upper-bound algorithm does not require prior knowledge of the smoothness constant, the distance to a minimizer and the target accuracy, It also provides a convergence guarantee at every sufficiently late round. I think achieving this while accounting for the finite precision and computational costs is a strength.
Critical weaknesses
  1. I appreciate the detailed proofs and the verification materials provided in the supplement. However, I found it difficult to extract the main intuition from the technical details, particularly the reasoning behind the parameter choices in Algorithm 1. The algorithm introduces several parameters, such as (q_m), (b_m), (P_m), and (K_m), but their roles and how they work together could be explained more clearly in the main text. For a venue that asks whether a result is understandable as well as correct, I consider this a real weakness.
Questions for authors

Questions :

  1. Could you explain the intuition behind the choices of (b_m), (P_m), and (K_m) in Algorithm 1, particularly how the probe size, oracle precision, and number of cuts work together to ensure convergence?
  2. In Section 3.2, the protocol requires the algorithm to read the entire reply, including unused fields, before receiving the next useful reply. Beyond the general motivation given at the end of this section, could you provide a concrete example motivating this requirement?

Suggestions :

  1. A comparison table in Section 2 (related work) would make it clear what this paper adds.
6 comments
AuthorsOpenReview ↗

Response to Reviewer NnmZ (1)

Thank you for your constructive review and for recognizing our matching bounds and anytime guarantee under finite resource constraints. We address your questions below.

  • W1 / Q1: Parameter choices and convergence intuition in Algorithm 1 of the manuscript

Could you explain the intuition behind the choices of (b_m), (P_m), and (K_m) in Algorithm 1, particularly how the probe size, oracle precision, and number of cuts work together to ensure convergence?

Thank you for pointing out that the parameter choices needed a clearer explanation. We have added their meanings to Section 5.1 of the revised manuscript and collected the conditions they jointly satisfy in Appendix C.3 of the revised manuscript. We quote the passage from Section 5.1 of the revised manuscript below; section and appendix references within this quotation refer to that version:

“In Algorithm 1, qmq_m is an auxiliary size parameter combining the input length AA, dimension dd, and epoch index mm. The integer bmb_m specifies the probe step τm=2−bm\tau_m=2^{-b_m} in ellipsoid coordinates, and PmP_m is the oracle query precision and working precision for the epoch. Each component of the quantized direction uu has tdt_d fractional bits. The parameter ρ\rho is the offset of the cutting plane from the center in ellipsoid coordinates, and KmK_m is the maximum number of cuts in the epoch. The parameter values are chosen jointly so that cuts retain the target ball and yield epoch accuracy (Section 5.2), rounded updates preserve containment and volume contraction (Section 5.3), and the algorithm satisfies the resource and convergence bounds (Section 5.4). The required conditions and their verification are summarized in Appendix C.3.”

The main connection is that more cuts require smaller probes to control errors throughout the epoch. Smaller probes produce smaller function value differences, which require more accurate oracle replies. The direction itself only needs precision that depends on dimension.

For the ellipsoid branch with d≥2d\ge2, fix a minimizer x∗x^* and a positive gradient Lipschitz bound LL. Let Tm=x:∣x−x∗∣2≤2−m−2\mathcal T_m=\\{x:\\|x-x^*\\|_2\le2^{-m-2}\\}, let g=BT∇F(c)g=B^T\nabla F(c), and let uu be the stored approximate direction. In all sufficiently large epochs, when the current ellipsoid contains Tm\mathcal T_m and the center has error greater than (L/16)4−m(L/16)4^{-m}, Appendix C.3 of the revised manuscript gives the combined error bound:

\left\\|\frac{u}{\\|u\\|}-\frac{g}{\\|g\\|}\right\\| &\le \underbrace{32\sqrt d\\,2^{-b_m+4m+4K_m}}_{\text{finite-difference error}}\\\\ &\quad+\underbrace{\frac{128\sqrt d}{L}\\,2^{-8P_m+b_m+2m}}_{\text{oracle error}} +\underbrace{4\sqrt d\\,2^{-t_d}}_{\text{direction truncation}}<\rho. \end{aligned}$$ This ensures that the cut retains the target ball. The same section also gives the volume condition: $$\underbrace{e^{K_m/[16(d+1)]}}_{\text{guaranteed volume reduction}} \gt \underbrace{2^{2d(m+1)}}_{\text{initial ellipsoid volume / target ball volume}}.$$ To verify these conditions, Algorithm 1 of the manuscript uses $q_m=A+4d+m+\lceil\log_2(d+1)\rceil+1$ and $$\begin{aligned} b_m &= 2^{12}d^3q_m,\\\\ P_m &= 2^{16}d^4q_m=16d\\,b_m,\\\\ K_m &= 64d(d+1)(m+1),\\\\ t_d &= 16(\lceil\log_2(d+1)\rceil+1),\\\\ \rho &= \frac{1}{32(d+1)}. \end{aligned}$$ Substitution gives $$4m+4K_m\le\frac{b_m}{2},\qquad P_m\ge b_m+2m,\qquad 4\sqrt d\\,2^{-t_d}\le\frac{\rho}{32}.$$ The total direction error is therefore bounded, for all sufficiently large $m$ on each fixed instance, by $$32\sqrt d\\,2^{-b_m/2} +\frac{128\sqrt d}{L}\\,2^{-7P_m} +\frac{\rho}{32}<\rho.$$ The first two terms tend to zero as $m$ increases. For the volume condition, $$\frac{K_m}{16(d+1)} =4d(m+1)>2d(m+1)\log 2,$$ which gives the required inequality after exponentiation. These are conservative sufficient choices and have not been specially optimized. If every queried center were inaccurate, the target ball would survive all cuts, but the final ellipsoid would have smaller volume than the ball. This contradiction guarantees an accurate center. These choices have $b_m,P_m=\Theta_d(A+m)$ and $K_m=O_d(m)$. Completing epoch $m$, including initialization, reply scans, and up to $K_m$ cuts, takes $O_d((A+m)^2)$ rounds and yields an output with error $O(4^{-m})$. The epochs are $m=1,2,4,\ldots$. After absorbing the finite startup, summing their costs bounds the round count $n$ during epoch $m$ by $$n=O_d\\!\left(\sum_{k=0}^{\log_2 m}(2^k)^2\right)=O_d(m^2).$$ The output from epoch $m/2$ remains available with error $O(4^{-m/2})=O(2^{-m})$. Since $m=\Omega_d(\sqrt n)$, this yields $$F(z_n)-\min_x F(x)\le \exp[-\Omega_d(\sqrt n)]$$ at every sufficiently late round. The added explanations are marked in blue in the revised manuscript.
AuthorsOpenReview ↗

Response to Reviewer NnmZ (2)

  • Q2: Concrete examples of full reply consumption

Beyond the general motivation given at the end of this section, could you provide a concrete example motivating this requirement?

Thank you for this question.

Our main motivation is to account for the communication reception cost of higher precision through the same bit operations used by our serial Turing machine. Requiring replies to be read in full is one simplified way to do this, but it is not the only choice. Allowing the host to specify which oracle bits it wishes to receive may lead to different sharp convergence rates. We have added the following discussion to the revised manuscript.

Section 3.2 of the revised manuscript (Reply Protocol):

“We adopt this reply protocol to make the computational cost of numerical precision explicit. Counting oracle calls alone assigns the same cost to coarse and arbitrarily precise replies. Charging for complete reply consumption is the approach adopted in this work to account for communication costs in a simplified communication setting.”

Section 7 of the revised manuscript (Discussion and Limitations):

“At the oracle interface, requiring regular numerical replies to be consumed in full and in sequence allows communication reception to be charged through the same bit actions as local computation. This simplified protocol also reflects the cost structure of restricted numerical communication protocols (Tsitsiklis & Luo, 1987). Future work could determine whether allowing the optimizer to choose which bits it receives leads to different sharp convergence rates.”

These changes are marked in blue. Full consumption also has practical examples. Some devices and services use sequential interfaces that require the current message to be read or drained to preserve message boundaries and interaction state. This simplifies buffering and request management. For example:

  1. AMD/Xilinx AXI4-Stream FIFO. The receive procedure requires the processor to read the current packet in full from the FIFO before proceeding to the next packet. Official manual, pp. 29, 42

  2. HTTP/1.1 persistent connections. A client must read the entire response body to reuse the same connection. The drain_conn() method in urllib3 also discards remaining data by reading it. RFC 9112, §9.3, urllib3 documentation

  3. MySQL streaming result interfaces. With mysql_use_result(), the current result must be drained before further queries can proceed on the same connection. The consume_results=True option in Connector/Python also discards remaining results by reading them. C API documentation, Connector/Python documentation

When an optimizer accesses an external numerical service through such an interface, it still incurs the cost of consuming the full reply even if it uses only part of the information.

AuthorsOpenReview ↗

Response to Reviewer NnmZ (3)

  • S1: Comparison tables for related work

A comparison table in Section 2 (related work) would make it clear what this paper adds.

Thank you for this suggestion. We have added three comparison tables in Appendix A of the revised manuscript and referred to them at the beginning of Section 2 of the revised manuscript. They compare computational models and resource constraints, ingredients of the upper construction, and the error criteria, quantifier order, and information costs of lower bounds. We reproduce their contents below, with the formatting converted to Markdown. The tables and accompanying explanations are marked in blue in the revised manuscript.

Table 2 of the revised manuscript. Resource accounting in related computational models. ✓ denotes explicit treatment and × denotes no separate treatment of the indicated item.

Work and settingLocal workMemory limitAddress costOracle costMessage bitsFull sequenceMachine model
Van Dessel & Glineur (2023)×××✓×××
Tsitsiklis & Luo (1987), general protocols××××✓××
Tsitsiklis & Luo (1987), numerical prefixes××××✓✓×
Lin et al. (2022)××××✓××
Ghadiri et al. (2024), distributed optimization××××✓××
Ghadiri et al. (2024), centralized least squares✓××××××
Basu et al. (2026), binary replies××××✓××
Blanchard et al. (2023a)×✓×××××
Menart et al. (2026)×✓×××××
Ghadiri et al. (2023)✓××××××
Blanchard et al. (2023b), memory between queries×✓×××××
Blanchard et al. (2023b), memory throughout computation✓✓×××××
This work✓✓✓×✓✓✓

Local work excludes oracle computation; oracle cost covers reply generation beyond call counts. Memory limit bounds storage capacity; address cost covers locating and accessing data. Machine model specifies host execution through elementary bit actions. Full sequence requires reading or transmitting consecutive numerical prefixes or complete fixed-format numerical replies.

Table 3 of the revised manuscript. Related ingredients and corresponding features of our upper construction.

WorkRelated ingredientOur construction
Bland et al. (1981), Section 6Ellipsoid factor updates.Short update coefficients applied to long state entries.
Grötschel et al. (1988), Sections 3.2–3.3Rounding that preserves containment and volume decrease.Dimension-dependent coefficient precision, separate from growing state precision.
Karabag et al. (2021), Lemma 1; value probesValue probes for approximate shallow-cut directions.O(log⁡(d+1))O(\log(d+1)) bits per direction component, independent of target accuracy.
This workShort coefficients, controlled rounding, and serial scheduling.Od(b)O_d(b) bit operations per cut; root-exponential error at every sufficiently late round.

Here bb is the bit width of the stored center and matrix entries.

Table 4 of the revised manuscript. Error criteria, fixed-instance quantifiers, and information costs in related lower bounds.

WorkError criterion or taskFixed instanceInformation and cost
Tsitsiklis & Luo (1987), Proposition 3.2Convex objective error×Transmitted bits of consecutive numerical prefixes.
Sikorski & Trojan (1990), Theorem 1.1Distance to the unique zero of a smooth function✓Number of adaptive continuous linear information evaluations.
Plaskota (2023), Theorem 2.3Hausdorff distance to the zero set; the hard function has a unique zero✓Number of exact function and derivative evaluations.
Basu et al. (2026), Theorems 3–4, continuous caseConvex feasibility under an interior-ball promise×Reply bits: individual bits of a separating normal or signs of inner products.
This workObjective error of one smooth convex function✓Mandatory reads of complete numerical replies; rounds and charged bit operations.

A check in the fixed-instance column means that the asymptotic lower bound is established on one fixed function. This function may depend on the algorithm and any proposed rate specified in the result. A cross denotes a worst-case statement at a prescribed accuracy or geometric scale, without a claim that the same instance remains hard as that scale tends to zero.

Thank you again for these suggestions. They have helped us explain the parameter choices, the settings that motivate the model, and the relationship to prior work more clearly. We hope these explanations and revisions address your concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the reviewers for their careful reviews and constructive suggestions. We appreciate the recognition of the novelty of our work and the importance of its relatively underexplored research topic (Reviewer gsGq). We also thank the reviewers for their constructive feedback on the computational model (Reviewers NnmZ, gsGq, and o3SQ). We appreciate their suggestions for improving the writing and notation (Reviewers gsGq and o3SQ) and their recommendations on related work (Reviewers NnmZ and gsGq). We revised the manuscript and supplementary materials, with manuscript changes marked in blue. The main improvements are as follows:

  1. Improving the abstract and exposition. We reduced the number of symbols in the abstract and refined the wording and expressions throughout the manuscript for greater precision and clarity. We thank Reviewers gsGq and o3SQ for their feedback on the writing. For more details, see our responses to these reviewers.

  2. Expanding the explanation of the computational model. Sections 2.1 and 3 of the revised manuscript were expanded to explain the motivation and scope of the resource accounting rules and reply protocol. We also explained the resource bounds and the choice of budget constants in Section 3.3 of the revised manuscript. We thank Reviewers NnmZ, gsGq, and o3SQ for their questions about the computational model. For more details, see our responses to these reviewers.

  3. Expanding the related work and adding three comparison tables. The discussion in Section 2.1 of the revised manuscript was expanded to compare computational models and resource constraints, with additional references. In Appendix A of the revised manuscript, we added Tables 2–4 to compare our work with related studies in terms of resource assumptions, upper bound constructions, and lower bounds. We thank Reviewers gsGq and NnmZ for their suggestions on the literature and comparisons. For more details, see our responses to these reviewers.

  4. Clarifying the parameter choices in Algorithm 1. In Section 5.1 of the revised manuscript, we explained the parameters' roles. Their joint conditions were collected and verified in Appendix C.3. We thank Reviewer NnmZ for the question about the parameter choices in Algorithm 1. For more details, see our response to Reviewer NnmZ.

  5. Revising the discussion of limitations and future directions. The discussion in Section 7 of the revised manuscript was revised to cover dimension dependence, alternative memory access models, and more flexible reply protocols. We thank Reviewers gsGq and o3SQ for their questions about the scope of the results. For more details, see our responses to these reviewers.

  6. Adding a Lean verification section and formalization materials. Appendix F.1 and Table 26 of the revised manuscript were added to describe the verification scope and map the main results to their Lean declarations. We included the corresponding source code and instructions for building and auditing the formalization in the supplementary materials. The formal verification of the main bounds in Lean 4 was also noted in the abstract and introduction. For more details, see Appendix F.1 of the revised manuscript and the supplementary materials.

Summary of responses to reviewers

  • We explained the motivation and scope of the computational model and provided examples of full reply consumption. For more details, see our responses to Reviewers NnmZ, gsGq, and o3SQ.

  • We clarified the roles of the parameters and the reasons for their choices. For more details, see our response to Reviewer NnmZ.

  • We compared our computational model and convergence results with those of related work. For more details, see our responses to Reviewers NnmZ and gsGq.

  • We clarified the resource budgets and the role of their constants. For more details, see our response to Reviewer gsGq.

  • We discussed dimension dependence and extensions to other computational models and reply protocols. For more details, see our responses to Reviewers gsGq and o3SQ.

We thank the reviewers again for the suggestions that helped improve the model explanation, algorithm presentation, and comparison with prior work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.