# Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes

arXiv: https://arxiv.org/abs/2306.10096 · HTML: https://mlsanity.com/paper/2306.10096/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 53 references that are in the map.
- First posted on arXiv 16 Jun 2023.

## Builds on (most cited first, 24 of 24)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [AIDE: Fast and Communication Efficient Distributed Optimization](https://mlsanity.com/paper/1608.06879/) (2016)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [A geometric alternative to Nesterov's accelerated gradient descent](https://mlsanity.com/paper/1506.08187/) (2015)
- [Memory-Sample Tradeoffs for Linear Regression with Small Error](https://mlsanity.com/paper/1904.08544/) (2019)
- [Detecting Correlations with Little Memory and Communication](https://mlsanity.com/paper/1803.01420/) (2018)
- [Optimized first-order methods for smooth convex minimization](https://mlsanity.com/paper/1406.5468/) (2014)
- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [Space lower bounds for linear prediction in the streaming model](https://mlsanity.com/paper/1902.03498/) (2019)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox](https://mlsanity.com/paper/1702.06269/) (2017)
- [Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory](https://mlsanity.com/paper/1907.00762/) (2019)
- [An optimal gradient method for smooth strongly convex minimization](https://mlsanity.com/paper/2101.09741/) (2021)
- [Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales](https://mlsanity.com/paper/2111.03137/) (2021)
- [An optimal first order method based on optimal quadratic averaging](https://mlsanity.com/paper/1604.06543/) (2016)
- [How to trap a gradient flow](https://mlsanity.com/paper/2001.02968/) (2020)
- [Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal](https://mlsanity.com/paper/2302.04963/) (2023)

## Built on by (most cited first, 3 of 3)

- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024)
- [Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory](https://mlsanity.com/paper/2607.24827/) (2026)

## Abstract (arXiv)

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 mathcal O(fracd2pln frac1ε) bits of memory, and make mathcal O((Cfracdpln frac1ε)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 lnfrac1εggln d. While several works gave lower-bound trade-offs (impossibility results) -- we explicit here their dependence with lnfrac1ε, 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. In the regime ε ≤ d-Omega(d), our algorithm with p=d achieves the information-theoretic optimal memory usage and improves the oracle-complexity of gradient descent.