- 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 without requirements on the smoothness, target accuracy and horizon. It also proves that the lower bound of the proposed algorithm. These bounds establish 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
- 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.
- 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.
- 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
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 . 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 for each fixed . The constants in both bounds have not been specially optimized. Determining the optimal asymptotic dependence on 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 as the output point at the end of round . We have removed the 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 bit actions; memory use is bounded by bits, where is the problem dimension, is the total number of bits encoding the dimension and the initial point, and is the current working precision. We construct a single algorithm with increasing precision that, in every fixed dimension, produces an output point at the end of round satisfying 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 along an unbounded subsequence of rounds. Together, these bounds establish as the sharp asymptotic order of guarantees that hold on every fixed instance at every sufficiently late round in this protocol. With 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
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.
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):
Section 7 of the revised manuscript (Discussion and Limitations):
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:
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
HTTP/1.1 persistent connections. A client must read the entire response body to reuse the same connection. The
drain_conn()method inurllib3also discards remaining data by reading it. RFC 9112, §9.3, urllib3 documentationMySQL streaming result interfaces. With
mysql_use_result(), the current result must be drained before further queries can proceed on the same connection. Theconsume_results=Trueoption in Connector/Python also discards remaining results by reading them. C API documentation, Connector/Python documentationWhen 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.