Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Memory-Constrained Algorithms for Convex Optimization
Authors: Moise Blanchard, Junhui Zhang, Patrick Jaillet
NeurIPS 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose a family of recursive cutting-plane algorithms to solve feasibility problems with constrained memory, which can also be used for first-order convex optimization. Precisely, in order to find a point within a ball of radius ϵ with a separation oracle in dimension d or to minimize 1-Lipschitz convex functions to accuracy ϵ over the unit ball our algorithms use O( d2 ϵ ) bits of memory, and make O((C d ϵ )p) oracle calls, for some universal constant C ≥ 1. The family is parametrized by p ∈ [d] and provides an oracle-complexity/memory trade-off in the sub-polynomial regime ln 1 ϵ ≪ ln d. While several works gave lower-bound trade-offs (impossibility results) [31, 5] we explicit here their dependence with ln 1 ϵ , showing that these also hold in any sub-polynomial regime—to the best of our knowledge this is the first class of algorithms that provides a positive trade-off between gradient descent and cutting-plane methods in any regime with ϵ ≫ 1/ d. The algorithms divide the d variables into p blocks and optimize over blocks sequentially, with approximate separation vectors constructed using a variant of Vaidya’s method. |
| Researcher Affiliation | Academia | Moïse Blanchard Operations Research Center MIT Cambridge, MA 02139 EMAIL; Junhui Zhang Operations Research Center MIT Cambridge, MA 02139 EMAIL; Patrick Jaillet Department of Electrical Engineering and Computer Science MIT Cambridge, MA 02139 EMAIL |
| Pseudocode | Yes | Algorithm 1: Memory-constrained Vaidya s volumetric method; Algorithm 2: Approx Separation Vectorδ,ξ(Ox, Oy); Algorithm 3: Approx Oracleδ,ξ,OS(i, j, P(1), . . . , P(i)); Algorithm 4: Memory-constrained algorithm for convex optimization; Algorithm 5: x(r) = Centering(x(0), r); Algorithm 6: An efficient cutting-plane method, simplified from [27]; Algorithm 7: Cutting-plane algorithm with certified optimality; Algorithm 8: Approx Separation Vectorδ,ξ(Ox, Oy); Algorithm 9: Approx Oracleδ,ξ,OS(i, j, x(1), . . . , x(i)); Algorithm 10: Memory-constrained algorithm for convex optimization; Algorithm 11: Memory-constrained gradient descent |
| Open Source Code | No | The paper does not provide any statements about open-sourcing code or links to a code repository for the described methodology. |
| Open Datasets | No | This paper is theoretical and focuses on algorithm design and complexity analysis for convex optimization. It does not conduct empirical studies with datasets or provide information about dataset availability for training. |
| Dataset Splits | No | This paper is theoretical and does not report on empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper on algorithms and complexity; it does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | This paper is theoretical and does not report on empirical experiments that would require specific ancillary software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and focuses on algorithm design and complexity analysis. It does not describe an experimental setup with hyperparameters or system-level training settings. |