Memory-Constrained Algorithms for Convex Optimization
Authors: Moise Blanchard, Junhui Zhang, Patrick Jaillet
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | 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 moiseb@mit.edu; Junhui Zhang Operations Research Center MIT Cambridge, MA 02139 junhuiz@mit.edu; Patrick Jaillet Department of Electrical Engineering and Computer Science MIT Cambridge, MA 02139 jaillet@mit.edu |
| 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. |