PaperlayerView exact revision on arXiv

Source-linked AI summary

An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications

Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong

arXiv:2004.04250v1cs.DScs.LGstat.ML

TL;DR

Cutting-plane applications continue to emerge, but progress on faster methods had stagnated before Lee, Sidford, and Wong. The paper phases Vaidya’s method and adds a layered data structure, achieving O(n log(κ)) oracle evaluations with total runtime O(n · SO log(κ) + n^3 log(κ)).

  • Problem

    Cutting-plane applications continue to emerge, but progress on faster methods had stagnated before Lee, Sidford, and Wong.

    Source: §1 · p. 4

  • Method

    The method runs Vaidya’s algorithm in phases with recomputation between them and uses a layered data structure to implement iterations efficiently.

    Source: §1 · p. 6, §1.4 · p. 9

  • Results

    O(n · SO log(κ) + n^3 log(κ)) is the stated runtime for the cutting-plane method.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Basic matrix operations require O(n^2) time per oracle-call iteration, making the runtime essentially tight unless sparsity can be exploited.

    Source: §1 · p. 6

    The proposed Ω(n^3 log(κ)) lower bound is Conjecture 1.7, so optimal runtime is conjectured rather than established.

    Source: §1.5 · p. 10

Abstract

from arXiv · show

Given a separation oracle for a convex set $K \subset \mathbb{R}^n$ that is contained in a box of radius $R$, the goal is to either compute a point in $K$ or prove that $K$ does not contain a ball of radius $\epsilon$. We propose a new cutting plane algorithm that uses an optimal $O(n \log (\kappa))$ evaluations of the oracle and an additional $O(n^2)$ time per evaluation, where $\kappa = nR/\epsilon$. $\bullet$ This improves upon Vaidya's $O( \text{SO} \cdot n \log (\kappa) + n^{\omega+1} \log (\kappa))$ time algorithm [Vaidya, FOCS 1989a] in terms of polynomial dependence on $n$, where $\omega < 2.373$ is the exponent of matrix multiplication and $\text{SO}$ is the time for oracle evaluation. $\bullet$ This improves upon Lee-Sidford-Wong's $O( \text{SO} \cdot n \log (\kappa) + n^3 \log^{O(1)} (\kappa))$ time algorithm [Lee, Sidford and Wong, FOCS 2015] in terms of dependence on $\kappa$. For many important applications in economics, $\kappa = \Omega(\exp(n))$ and this leads to a significant difference between $\log(\kappa)$ and $\mathrm{poly}(\log (\kappa))$. We also provide evidence that the $n^2$ time per evaluation cannot be improved and thus our running time is optimal. A bottleneck of previous cutting plane methods is to compute leverage scores, a measure of the relative importance of past constraints. Our result is achieved by a novel multi-layered data structure for leverage score maintenance, which is a sophisticated combination of diverse techniques such as random projection, batched low-rank update, inverse maintenance, polynomial interpolation, and fast rectangular matrix multiplication. Interestingly, our method requires a combination of different fast rectangular matrix multiplication algorithms.

1 Introduction

The introduction presents a cutting-plane method and a layered data structure for leverage-score maintenance, with applications to convex optimization, convex-concave games, and market-equilibrium computation. It also situates linear programming within cutting-plane research and distinguishes membership-oracle approaches to convex feasibility.

1.2 Previous works

  • Vaidya’s method [Vai89a] runs in O(n^(ω+1)) time, while LSW [LSW15] lowers dimension dependence at the cost of log^2(κ); both use O(n log(κ)) oracle calls.Here ω < 2.373 is the matrix multiplication exponent.Source: §1 · p. 4

1 Introduction

  • O(n·SO log(κ) + n^3 log(κ)) time achieves the optimal O(n·SO log(κ)) oracle complexity for the feasibility problem.The authors conjecture the runtime is essentially tight because each iteration requires basic matrix operations taking O(n^2) time.Source: §1 · pp. 4, 6

1.1 Applications

  • Convex minimization takes O(T·n log(κ) + n^3 log(κ)) time, while convex-concave games yield a pair with gap at most εLr.The minimization guarantee is within α times the range of f over S; the game guarantee holds with high probability.Source: §1.1 · p. 6
  • Linear exchange and Fisher spending-constraint markets run in O(mn^2 log(nU)) time; general-valuation markets run in O(n^2TAD log(SMn)+n^4 log(SMn)).The applications exploit the improved dependence on κ, which is polynomially large through log(κ) when 1/ε is exponentially large in n.Source: §1.1 · pp. 6–7

1.3 Lee-Sidford-Wong method (LSW)

  • LSW [LSW15] approximates leverage-score changes with Johnson-Lindenstrauss projections, but accumulated projection errors eventually undermine Vaidya’s performance guarantee.The approximation still requires solving linear systems, which LSW handles in amortized eO(n^2) time after an initial O(n^ω) cost.Source: §1.3 · p. 8

1.4 Overview of our approach

  • A layered leverage-score data structure uses faster, less accurate inner layers and invokes slower, more accurate outer layers when accumulated error grows.It batches updates for fast rectangular matrix multiplication and handles potentially exponential weight changes separately in groups of poly log(n) size using low-rank updates.Source: §1.4 · p. 9

1.5 Discussion of optimality

  • The authors conjecture feasibility requires Ω(n^3 log(κ)) time, making their O(n^3 log(κ)) runtime optimal.They argue prior LP maintenance methods cannot delay low-rank updates when cutting-plane constraints are inserted or deleted, and cite n^2 lower bounds for natural matrix-maintenance tasks.Source: §1.5 · pp. 9–10

1.6 Related works

  • Leverage scores connect this method to prior work across graph algorithms, numerical linear algebra, and optimization, including cutting-plane methods.LSW identifies leverage scores as measuring the relative importance of separating hyperplanes.Source: §1.3 · p. 8, §1.6 · p. 10
  • Linear programming is a fundamental convex-optimization problem and a special case for cutting-plane methods, with extensive prior algorithmic work [Dan47, Kha80, Kar84, Vai87, Vai89b, LS14, LS15, Sid15, Lee16, CLS19, LSZ19, Son19, Bra20, BLSS20].Source: §1.6 · p. 10
  • Membership-oracle research addresses convex-feasibility problems; on query x, the oracle reports whether x belongs to K.Source: §1.6 · p. 11

2 Our Techniques

The techniques balance leverage-score accuracy against update cost through coarse and fine approximations, periodic recomputation, and a layered data structure. The layers use different error tolerances so efficient estimates can be refined when needed.

2.1 Efficient approximation of changes in leverage scores

  • The structures address a tradeoff: fine-grained leverage-score changes are accurate but potentially unaffordable, while coarse estimates are efficient but can accumulate excessive error.Exact recomputation every O(n^(ω−2+o(1))) steps makes controlling error across that interval sufficient.Source: §2.1 · p. 11
  • The method combines coarse and fine leverage-score change formulas, trading the coarse formula's single-integral estimate against a more involved fine formula using integrals, matrix inversion, and multiplication.The coarse formula is estimated at one point along the integral; the fine approximation requires numerical tools.Source: §2.1 · p. 11
  • The coarse and fine formulas yield a fast deterministic structure with larger per-step error and a more complex randomized structure with smaller per-step error but higher cost.The simple structure achieves O(n^2) time per step, while the complicated structure achieves ℓ2-error o(1) over O(n^(ω−2+o(1))) steps at amortized O(n^(2+o(1))) time per step.Source: §2.1 · p. 11

2.2 Layered data structure

  • The layered data structure approximates leverage-score changes to ℓ2-error within 1/log^O(1)(n) and handles each iteration in amortized O(n^2) time.Its construction builds on all the fast rectangular matrix multiplication results summarized in Theorem 2.1.Source: §2.2 · pp. 11–12
  • The layered data structure combines inner and middle simple structures with a more accurate outer structure, which is invoked less often as accumulated error rises.Inner layers tolerate more error and run faster; the outer layer produces a finer estimate at greater cost.Source: §2.2 · p. 11

2.3 Batched low-rank update

The section addresses the difficulty of batching leverage-score updates when weights can change exponentially over a sequence. It illustrates numerical tools for controlling the cost and error, and relates faster rectangular matrix multiplication to a deterministic cutting-plane method.

2.3 Batched low-rank update

  • Batched low-rank updates estimate leverage-score changes after splitting long update sequences into pieces of polylogarithmic size, keeping each weight change quasi-polynomially bounded.The method uses a nearby weight vector and a preconditioned Woodbury update; batching polylogarithmically many changes into rectangular matrix multiplication yields O(n^2) time per weight change.Source: §2.3 · p. 13

2.4 Illustration of our analysis

  • The illustration approximates multiple-variable integrals with polylogarithmically many weighted sample points, with an ℓ2 error bounded by poly(n)/2^(2N).The sample count is N = log^O(1)(n).Source: §2.4 · p. 13
  • The numerical illustration uses inverse maintenance to approximate Q(w) and M(w)^-1 as preconditioners for matrix products in leverage-score updates.The data structure needs explicit approximations to these matrices, beyond computing P(vt)u.Source: §2.4 · pp. 13–14
  • Tall JL projection estimates the relevant quantities with variance at most n^-0.51 using c = 0.31 and ε = n^-0.1.The variance is sufficiently small after n^(ω−2+o(1)) steps before the data structure restarts.Source: §2.4 · p. 14

2.5 Much faster rectangular matrix multiplication implies deterministic cutting plane method

  • If Tmat(n, n, n^β) = O(n^2 log^O(1)(n)) for β > 2/3, the paper gives a deterministic cutting-plane method.The algorithm relies on different fast rectangular matrix multiplication results; the paper also poses open questions about β and the dual exponent α.Source: §2.5 · pp. 14–15

3 Preliminaries

The preliminaries introduce notation and operators used in the paper, review running-time and matrix tools, and state interpolation results used to approximate integrals.

3.1 Notations

  • The notation section defines norm, transpose, inverse, trace, and semidefinite-order conventions, along with shorthand for approximate vector and scalar equality.It also defines eO(f) as f times a polylogarithmic factor.Source: §3.1 · p. 23

3.2 Operators

  • The paper introduces leverage-score operators σ and τ, and operators M, Q, and P for a matrix and vector.The supplied definitions identify these operators by name and input type.Source: §3.2 · p. 23

3.3 Different types of running time

  • The running-time section distinguishes pseudo-polynomial, strongly polynomial, and weakly polynomial algorithms by their input-size and numeric-value dependence.Strongly polynomial time additionally bounds arithmetic operations by a polynomial in the number of input rationals and space by a polynomial in input size.Source: §3.3 · p. 23

3.4 Basic results on matrices

  • The matrix preliminaries state the Woodbury matrix identity for an invertible matrix plus a low-rank update.The identity requires the stated auxiliary matrix to be invertible.Source: §3.4 · p. 24

3.5 Fast matrix multiplication

  • The fast-multiplication section defines Tmat(n, n, r) and lists bounds for r = n^0.31, r = n^0.17, and polylogarithmic r.The cited bounds are O(n^2+o(1)), O(n^2 log^2 n), and O(n^2), respectively.Source: §3.5 · p. 24

3.6 Multiple variable polynomial interpolation

  • The interpolation results construct weighted sample points for one-variable and multivariable integrals, with differentiability assumptions stated for the latter.The multivariable argument builds on the one-variable result through recursive functions.Source: §3.6 · pp. 24–25

4 Perturbed Volumetric Center Cutting Plane Method

The section states the separation-oracle feasibility problem and describes how a cutting-plane method iteratively refines its feasible region. It explains that approximate leverage-score maintenance supports the resulting runtime guarantee.

4 Perturbed Volumetric Center Cutting Plane Method

  • A cutting-plane iteration queries the oracle at a point, then either accepts it or uses a separating hyperplane to refine the feasible region and choose the next query.The next query can use the new hyperplane and past information.Source: §4 · p. 27
  • The implementation maintains estimated leverage scores in amortized O(n^2) time, addressing a bottleneck in Vaidya’s method.The paper describes this as the main innovation behind its faster implementation.Source: §4 · p. 27
  • O((n SO + n^3) log(κ)) time suffices to find a point in K or prove K contains no ball of radius ε, where κ = nR/ε.The guarantee applies to a convex set contained in a box of radius R and equipped with a separation oracle.Source: §4 · p. 27

5 Main Data Structure for Leverage Score Maintenance

The main data structure maintains approximate leverage scores through layered updates, achieving amortized O(n^2) time per update. Its inner, middle, and outer phases use different update schedules and refinement stages.

5 Main Data Structure for Leverage Score Maintenance

  • The main leverage-score data structure supports updates in amortized O(n^2) time and yields a cutting-plane runtime of O(n SO log(κ) + n^3 log(κ)).It combines the simpler data structures from Sections 7 and 8.Source: §5 · p. 28
  • The analysis amortizes each phase and restart to O(n^2) time per update.The inner, middle, and outer phases and the restart are each bounded at this amortized rate.Source: §5 · p. 29

Algorithm 1

  • The structure combines inner and middle simple-maintenance phases with an outer complicated-maintenance phase, refining estimates between layers and restarting after the outer phase reaches its limit.Updates may include insertions, deletions, and weight changes; the algorithm also maintains delayed sequences of updates for later phases.Source: Algorithm 1 · p. 30

6 Batched Low Rank Update

This section develops fast leverage-score maintenance for batched low-rank updates, combining polynomial-based matrix inversion with phased update handling. It accumulates estimated leverage-score changes with handling that depends on whether insertions or deletions occurred, bounding approximation error and running time.

6.1 Simple low rank update

  • With explicit M^-1 and A, the preconditioning lemma computes f(M,t)·V for V ∈ R^(n×r) in O(Tmat(n,n,r)·t) time.The lemma applies to PSD matrices satisfying 0 ⪯ M ⪯ A ⪯ κ·M when κ(1 − 1/κ)^(t+1) < 1.Source: §6.1 · p. 31
  • Lemma 6.2 handles leverage-score updates for O(n)-row weight changes with k changed entries and a controlled spectral factor β, including decreasing weights.For decreasing weights, the stated matrix relation is AᵀW_newA ⪰ β^-1 AᵀWA.Source: §6.1 · p. 32

6.2 Batched low rank update

  • The algorithm separates positive and negative changes, moves insertions and positive updates earlier, and processes phases while sparsifying small multiplicative updates.Within phases it merges rank-1 updates; small changes below η = n^-0.08 are ignored.Source: §6.2 · pp. 35, 39
  • The batched method returns v with ∥log v − log w(T)∥∞ ≤ T·n^-0.08 and ∥log v − log w(T)∥2 ≤ 0.01·T.The theorem assumes T ≤ n^0.08 and at most O(n) rows.Source: §6.2 · p. 36
  • The batched update algorithm takes O(n^2T) total time, with O(n^2L) time per phase and L = log^3(n).The summary also accounts for explicit inverse maintenance at O(n^2L) per phase.Source: §6.2 · pp. 37–38
  • Step 4 adds the estimated change in leverage scores.Source: §6.2 · p. 39
  • The algorithm distinguishes updates without insertions or deletions from insert/delete events, estimating the change between consecutive weight vectors with Lemma 6.2 at error 1/n^1000.Source: §6.2 · p. 39

7 Simple Deterministic Leverage Score Maintenance

This section develops a deterministic data structure for maintaining approximate leverage scores, used in the cutting-plane method’s inner and middle phases. It gives update, query, and error guarantees, and derives a faster cutting-plane algorithm under a matrix-multiplication condition.

7 Simple Deterministic Leverage Score Maintenance

  • The data structure serves the inner and middle phases, and its batched-update subprocedure assumes a short update sequence and small changes.The stated sequence-length condition is T ≤ n^0.08, with at most O(n) rows.Source: §7 · p. 40

7.1 Main result

  • Algorithm 4 deterministically approximates leverage scores for positive diagonal weights and supports updates, estimate refinement, and queries.Under Assumption 7.1, Update(acts) makes one pm.update call and takes additional O(n^2 · |acts|) time; refinement and query each take O(n).Source: §7.1 · p. 40
  • If Tmat(n, n, r) = O(n^2 log^O(1)(n)) for r = n^α with α > 2/3, the corollary gives a deterministic O(n^3 log(n/ϵ)) cutting-plane algorithm.The corollary follows from Theorem 7.2 and B.1.Source: §7.1 · p. 41

7.2 Approximate leverage score’s moving

  • The moving-score calculation approximates leverage-score changes between weight vectors, with the relevant matrix-vector product computable in O(n^2) time.The calculation uses the entry-wise square of Q and the difference between the weight vectors.Source: §7.2 · p. 41, Algorithm 4 · p. 43

7.3 ℓ2-error bound

  • Lemma 7.6 bounds the ℓ2 error of the score update when Assumption 7.1 holds and ϵsimp ≤ 0.01.The proof decomposes the error into two terms and invokes separate bounds for each.Source: §7.3 · pp. 43–44

8 Complicated Randomized Leverage Score Maintenance

Section 8 presents a randomized data structure for approximately maintaining leverage scores under matrix and weight updates, using batched low-rank updates and fast matrix multiplication. It analyzes approximation error, including discrete-sampling errors for four leverage-score expressions under εcomp ≤ 0.01 using holomorphic extension and Cauchy estimates.

8.1 Main result

  • The randomized data structure approximately maintains leverage scores for positive diagonal weight matrices through initialization, updates, estimate refinement, and queries.Initialization takes O(n^(ω+o(1))) time; refinement and query each take O(n) time.Source: §8.1 · p. 47

8.2 Leverage score’s moving

  • The update estimates leverage-score changes along interpolated weight paths, using batched low-rank updates and Gaussian random projections to compute sampled terms.The paths connect intermediate weights and projection-maintenance estimates; Algorithm 5 samples independent Gaussian matrices for its projected computations.Source: §8.2 · p. 47, Algorithm 5 · p. 48

8.3 Running time anlaysis

  • Each Update(acts) makes O(N) projection-maintenance calls and takes extra O(n^2 · |acts| + Tmat(n, n, r) · N^3 · log(n)) time under Assumption 7.1.The running-time guarantee assumes ϵcomp ≤ 0.01.Source: §8.3 · p. 51
  • The update’s remaining projected computations use fast matrix multiplication, taking O(Tmat(n, n, r) · log(n)) time for the listed terms.This computation assumes m = O(n) and ϵcomp ≤ 0.01.Source: §8.3 · p. 51

8.5 Variance upper bound for random Gaussian matrices

  • Variance bounds for the Gaussian-projected terms are summarized in Table 7, and bounds for discrete-sampling error are summarized in Table 8.The terms include η, α, β, and γ; the supplied passages do not expose the tables’ numerical bounds.Source: §8.5 · p. 56, Table 7 · p. 56, §8.6 · p. 58

8.6 Error upper bound for discrete sampling

  • The section states error upper bounds for η⊤η, θ⊤θ, α⊤β, and γ⊤γ when εcomp ≤ 0.01.Source: §8.6 · pp. 58–59
  • For η⊤η, the discrete-sampling error is analyzed by applying Theorem 3.9 with N = |S|.Source: §8.6 · p. 58
  • M2N is bounded by (2N)! · poly(n) using Cauchy’s estimates on a holomorphic extension of the rational function.The extension is holomorphic on the unit ball because M(ys,0) is invertible for |s| ≤ 1 when εcomp ≤ 0.01.Source: §8.6 · p. 58

A Perturbed Volumetric Center Cutting Plane Method

The method adapts Vaidya’s volumetric-center cutting-plane approach by using maintained leverage-score estimates. It achieves the stated feasibility runtime, with the iteration count governed by volume reduction.

A Perturbed Volumetric Center Cutting Plane Method

Number of iterations required

  • Vaidya’s volume reduction yields O(n log(nR/ϵ)) iterations to establish that the feasible region contains no ball of radius ϵ.The cited passage gives a volume bound of at most ϵ^O(n) after this many iterations.Source: Number of iterations required · p. 61

A.1 Our faster implementation via leverage score maintenance

The method speeds up Vaidya’s cutting plane algorithm by maintaining approximate leverage scores and controlling their effect on convergence. Its implementation targets amortized O(n^2) work per iteration, including the Newton step and linear solve.

A.1 Our faster implementation via leverage score maintenance

  • O(n^2) amortized maintenance produces estimated leverage scores, and sufficiently small estimation errors preserve Vaidya’s convergence guarantee.With error at most 1/log^O(1)(n), the Newton step still takes O(1) iterations; the convergence guarantee remains intact.Source: §A.1 · pp. 61, 63
  • An additive o(1) perturbation in leverage scores can be absorbed by slightly scaling c1 and δ; constraint addition and removal are adjusted to keep all constraints’ leverage scores Θ(1).Source: §A.1 · p. 64
  • O(n log(κ)) iterations suffice to reduce the feasible polytope’s volume enough to rule out an ε-radius ball.This yields O(n log(κ)) separation-oracle calls.Source: §A.1 · p. 64
  • O(n^2) amortized time per iteration covers the Newton step, leverage-score computation, and solving a linear system.The linear-system solve and leverage-score estimate are each assigned amortized O(n^2) time.Source: §A.1 · p. 64

B Modified Projection Maintenance

  • The modified projection-maintenance construction uses different rectangular matrix-multiplication regimes to address extra polylogarithmic update costs.The section introduces a lemma for matrix multiplication after noting that an earlier version retains extra log^O(1)(m) terms.Source: B Modified Projection Maintenance · pp. 65–66

C Cutting Plane Method for Convex Minimization and Saddle Point Problems

The section extends the cutting plane framework from convex minimization to convex-concave games. It gives a convex-minimization guarantee and develops the saddle-point formulation and its first-order property.

C.2 Convex minimization

  • O(n log(κ)) subgradient-oracle calls and O(n^3 log(κ)) time give a convex-minimization method, improving the previous O(n^3 log^O(1)(κ)) bound.The paper notes that the improvement matters when κ is exponential in some applications.Source: §C.2 · p. 67
  • The method returns x ∈ S whose objective gap is at most an α fraction of the range of f over S, with high probability.The stated setting has a convex set S containing a minimizer and κ = nγ/α, where γ = R/minwidth(S).Source: §C.2 · p. 67

C.3 Convex-concave games

  • A convex-concave game seeks a saddle point, where the function is convex in x and concave in y.The section defines an ε-saddle point while ignoring a small portion of the domain near the boundary because values there are difficult to certify in the black-box setting.Source: §C.3 · pp. 67–68
  • The game’s first-order vector has a convex-concave property that places every saddle point in the half-space it defines.The stated property applies to points in the product domain and interior query points.Source: §C.3 · p. 68

C.4 Applying cutting plane method to convex-concave games

The game algorithm applies cutting planes in the product space of the two players’ variables while retaining a saddle point in the feasible polytope. It constructs the separating half-space using feasibility information or the game’s first-order vector.

C.4 Applying cutting plane method to convex-concave games

  • The algorithm starts with a box containing X × Y and maintains a polytope in R^(n+m) containing a saddle point.The initial polytope is B∞(0, R).Source: §C.4 · p. 69
  • An infeasible query receives a supporting hyperplane, while a feasible query uses the game’s first-order vector to cut without removing any saddle point.The next polytope contains the current polytope intersected with the resulting half-space.Source: §C.4 · p. 69
  • O((n + m)^2T) time suffices to generate the query points and polytopes with high probability.The theorem states this bound for T ≥ n + m.Source: §C.4 · p. 69

C.5 Cutting plane method for convex-concave games: generating solutions

For convex-concave games, the method forms a solution from a convex combination of iterates rather than returning the best individual iterate. The maximum gap decreases at the same rate as in convex minimization, supporting an approximate saddle point.

C.5 Cutting plane method for convex-concave games: generating solutions

  • Convex weights on the cuts attain the maximum gap, providing multipliers used to construct the game solution.The section states that these weights can be found in time O((n + m)^ω+o(1) log((n + m)/η).Source: §C.5 · p. 70
  • A convex combination of feasible iterates yields a feasible candidate, and under the stated condition on β it approximates a saddle point.The condition is β ≥ 3√(n + m) · L.Source: §C.5 · pp. 70–72
  • The maximum gap tends to zero at the same convergence rate as the cutting plane method for convex minimization.A sufficiently small maximum gap permits a convex combination of iterates to approximate a saddle point.Source: §C.5 · p. 72
  • The method finds an approximate saddle point with high probability for Lipschitz functions convex in x and concave in y, when both domains contain a ball of radius r.The theorem’s runtime expression is split across the supplied passages.Source: §C.5 · p. 73

D.1 Linear Arrow-Debreu markets

The paper applies its cutting-plane approach to linear exchange and Fisher markets, formulating both as convex-concave games and giving weakly polynomial algorithms for computing equilibria.

D.1 Linear Arrow-Debreu markets

  • A convex-concave game formulation reduces the linear exchange problem from potentially n^2 variables to O(n) variables.The paper uses this reduced-variable formulation to solve the market-equilibrium convex program more efficiently.Source: §D.1 · pp. 76–77
  • O(mn^2 log(nU)) time computes a market equilibrium in linear exchange markets.The stated algorithm is weakly polynomial.Source: §D.1 · p. 77

D.2 Fisher markets with spending constraint utilities

  • For Fisher markets, the convex program is transformed into a convex-concave saddle point so the cutting-plane method can be applied.The paper reports O(n^2 log(nU)) iterations and O(m) operations per first-order oracle call.Source: Fisher markets with spending… · pp. 78–79
  • O(mn^2 log(nU)) time computes a market equilibrium in Fisher markets with spending constraint utilities.The stated algorithm is weakly polynomial.Source: Fisher markets with spending… · p. 79

D.3 Walrasian equilibrium for general buyer valuations and fixed supply

For fixed-supply Walrasian equilibrium with general buyer valuations, the paper uses its faster cutting-plane method to improve the runtime while retaining an aggregate-demand-oracle setting. The guarantee applies whenever equilibrium prices exist.

D.3 Walrasian equilibrium for general buyer valuations and fixed supply

  • The market is represented by a convex program whose solution can be accessed through aggregate demand rather than separate buyer demand oracles.The aggregate demand oracle supplies the sum of buyers' utility-maximizing bundles at given prices.Source: §D.3 · p. 80
  • The new result replaces a prior eO(n^6) overhead with the improved cutting-plane runtime.The proof follows Paes Leme–Wong's approach but invokes this paper's convex-minimization method instead of LSW's.Source: §D.3 · p. 81
  • O(n^2 TAD log(SMn) + n^4 log(SMn)) time computes Walrasian prices whenever they exist using only an aggregate demand oracle.TAD is the aggregate-demand-oracle runtime.Source: §D.3 · p. 81

Related papers

Loading 2004.04250v1…