PaperlayerView exact revision on arXiv

Source-linked AI summary

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong

arXiv:1508.04874v2cs.DScs.DMmath.NAmath.OC

TL;DR

The paper addresses how to reduce the computational overhead of cutting-plane methods for separation-oracle feasibility and related optimization problems. It introduces a faster cutting-plane approach, together with general reductions and problem-specific analyses, and reports improved runtimes across convex and combinatorial optimization. The results include the stated feasibility improvement and faster algorithms for submodular minimization, matroid intersection, submodular flow, and semidefinite programming.

  • Problem

    The paper studies how to improve long-stagnant running times for cutting-plane methods and their applications to convex and combinatorial optimization.

  • Method

    The paper combines a faster cutting-plane method with reductions, duality-based dimension reduction, direct potential-function analysis, and problem-specific structure.

  • Results

    The feasibility problem is solved in O(nSO log(nR/ϵ) + n^3 log^O(1)(nR/ϵ)) time, while applications receive improved runtimes across submodular minimization, matroid intersection, submodular flow, and semidefinite programming.

  • Takeaways & Limitations

    The results show that cutting-plane methods can still improve runtimes for classic optimization problems and may support further methods in practice.

  • Takeaways & Limitations

    A direct near-optimal analysis of weighted analytic centers for the feasibility problem remains an open question.

Abstract

from arXiv · show

We improve upon the running time for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set $K\subset \mathbb{R}^n$ contained in a box of radius $R$, we show how to either find a point in $K$ or prove that $K$ does not contain a ball of radius $ε$ using an expected $O(n\log(nR/ε))$ oracle evaluations and additional time $O(n^3\log^{O(1)}(nR/ε))$. This matches the oracle complexity and improves upon the $O(n^{ω+1}\log(nR/ε))$ additional time of the previous fastest algorithm achieved over 25 years ago by Vaidya for the current matrix multiplication constant $ω<2.373$ when $R/ε=n^{O(1)}$. Using a mix of standard reductions and new techniques, our algorithm yields improved runtimes for solving classic problems in continuous and combinatorial optimization: Submodular Minimization: Our weakly and strongly polynomial time algorithms have runtimes of $O(n^2\log nM\cdot\text{EO}+n^3\log^{O(1)}nM)$ and $O(n^3\log^2 n\cdot\text{EO}+n^4\log^{O(1)}n)$, improving upon the previous best of $O((n^4\text{EO}+n^5)\log M)$ and $O(n^5\text{EO}+n^6)$. Matroid Intersection: Our runtimes are $O(nrT_{\text{rank}}\log n\log (nM) +n^3\log^{O(1)}(nM))$ and $O(n^2\log (nM) T_{\text{ind}}+n^3 \log^{O(1)} (nM))$, achieving the first quadratic bound on the query complexity for the independence and rank oracles. In the unweighted case, this is the first improvement since 1986 for independence oracle. Submodular Flow: Our runtime is $O(n^2\log nCU\cdot\text{EO}+n^3\log^{O(1)}nCU)$, improving upon the previous bests from 15 years ago roughly by a factor of $O(n^4)$. Semidefinite Programming: Our runtime is $\tilde{O}(n(n^2+m^ω+S))$, improving upon the previous best of $\tilde{O}(n(n^ω+m^ω+S))$ for the regime where the number of nonzeros $S$ is small.

Part Overview

The paper develops a faster cutting plane method and applies it through general and problem-specific frameworks to improve runtimes across convex and combinatorial optimization.

  • Motivation: Cutting plane methods are central to convex and combinatorial optimization, but theoretical and application-specific runtime progress had largely stagnated.The paper focuses on polynomial-time convex optimization with linear separation oracles, not integer programming.
  • Paper organization: The paper improves cutting plane runtimes, develops application frameworks, and combines them with problem structure for faster optimization algorithms.The presentation is organized into three parts: a new cutting plane method, general application frameworks, and submodular minimization algorithms.
  • Part I: Cutting plane method: O(nSO log(nR/ϵ) + n^3 log^O(1)(nR/ϵ)) time solves the separation-oracle feasibility problem, improving on the previous best under R/ϵ = O(poly(n)).The algorithm either finds a point in K or proves that K does not contain a ball of radius ϵ.
  • Part I: Cutting plane method: A new technique provides low-variance unbiased estimates for changes in leverage scores, reducing the previous algorithm’s matrix-computation overhead.The technique is combined with ideas from prior cutting plane and slowly changing linear-system algorithms.
  • Part II: Applications: Part II uses dimension reduction through duality and a direct potential-function analysis to apply cutting plane methods efficiently to semidefinite programming, matroid intersection, and submodular flow.The second technique avoids the typical separation-to-optimization reduction when minimizing a linear function over an intersection of convex sets.
  • Part III: Submodular minimization: Part III improves weakly and strongly polynomial submodular minimization by combining cutting-plane guarantees with primal-dual and combinatorial structure.The paper also gives an intermediate O(n^3 log n · EO) oracle-call result with exponential running time before obtaining the fully improved strongly polynomial algorithm.

4 Introduction

Part I studies feasibility over a convex set accessed through a separation oracle and develops a faster cutting-plane method. The approach combines noise-tolerant iterations, efficient numerical techniques, and unbiased leverage-score-change estimates to improve prior running times.

  • The feasibility problem asks whether to find a point in K or prove that K contains no ball of radius ε, given a separation oracle and bounding box radius R.
  • Vaidya’s previous best algorithm required eO(n·SO·log(nR/ε)+n^ω+1 log(nR/ε)) time, and theoretical guarantees had not improved for over 25 years.
  • O(n·SO·log(nR/ε)+n^3 log^O(1)(nR/ε)) expected time improves Vaidya’s bound when R/ε=O(poly(n)).
  • Our approach: The method modifies Vaidya- and Atkinson-style iterations to tolerate random computational noise and implements relaxed iterations using numerical machinery and new techniques.
  • Implications: The algorithm maintains a polytope containing K and provides a proof when K lacks an ε-radius ball, enabling runtime improvements for strongly polynomial submodular minimization.

5 Preliminaries

The preliminaries introduce leverage scores, linear-system solvers, and the hybrid barrier used by the cutting-plane method. Approximate leverage scores and weighted quantities support efficient maintenance of the algorithm’s barrier representation.

  • Leverage scores measure the importance of matrix rows and are denoted by σ for a matrix A.
  • A linear-system solver for a positive-definite matrix returns an approximate solution S(b,ε) in time O(L_O·log(ε^-1)) with high probability.
  • Given such a solver for A^T A, leverage scores can be approximated multiplicatively within (1±ε) in eO((nnz(A)+L_O)ε^-2 log(ε^-1)) time.
  • The cutting-plane method maintains a polytope P={x:Ax≥b} containing K and a minimizer of a hybrid barrier function.
  • The slack vector is s(x)=Ax−b, with S_x=diag(s(x)); the method maintains an approximate leverage-score vector τ rather than explicitly maintaining e.
  • The modified quantity ψ(x) uses an ℓ2 term and λI inside the log determinant and leverage-score definitions to reflect the altered Hessian.

6 Our Cutting Plane Method

The section develops a cutting-plane method by maintaining approximate centers of a hybrid barrier while updating leverage-score estimates and handling changing constraints. It proves termination, geometric progress, and the resulting oracle and running-time guarantees.

  • Method: The method maintains a center of a hybrid barrier function and analyzes approximate hybrid centers for the current polytope.The presentation separately treats center maintenance, constraint changes, approximate centers, and the cutting-plane procedure.
  • Method: Gradient and Hessian bounds, slack stability, and gradient-descent facts support efficient centering steps.The analysis bounds derivatives, controls slack changes near central points, and applies gradient descent under Hessian bounds.
  • Algorithm: The algorithm updates leverage-score estimates using stochastic changes while maintaining the hybrid-barrier parameters.Each iteration updates τ by an estimated change and recomputes e from the updated estimate and point.
  • Guarantees: With high probability in n, Centering outputs iterates satisfying the stated centering and estimation guarantees under the listed parameter assumptions.The guarantee applies for positive iteration counts with bounded estimator accuracy and initial centrality error.
  • Main result: Theorem 31 gives expected time O(nSO_{Ω(ε/√n)}(K) log(nR/ε) + n^3 log^{O(1)}(nR/ε)) to find a point in K or produce a containing polytope with a certified small-width direction.The output polytope contains K, uses approximate separating constraints, and has width O(nε ln(R/ε)) in a specified direction.

7 Technical Tools

The section introduces technical tools for efficiently estimating leverage-score changes and controlling stochastic coordinate updates. These tools support the cutting-plane method’s maintained estimates and bounded-error behavior.

  • 7.1 Estimating Changes in Leverage Scores: The technical toolkit estimates changes in leverage scores using dimension reduction and access to a linear-system solver.The section targets accurate changes because direct dimension-reduction estimates of leverage scores can incur too much error inside the cutting-plane method.
  • 7.1 Estimating Changes in Leverage Scores: Algorithm 3 produces an unbiased estimator of σ(w) − σ(v) with high-probability ℓ2 error O(αε) and expected time Õ((nnz(A) + LO)/ε^2).The estimator decomposes leverage-score differences into norms of small vectors and applies Johnson–Lindenstrauss dimension reduction.
  • 7.1 Estimating Changes in Leverage Scores: The estimator’s leverage-score components are individually controlled with high probability, enabling the stated aggregate difference guarantee.The analysis establishes multiplicative concentration for estimated components before combining them into the final estimator.
  • 7.2 The Stochastic Chasing 0 Game: The Stochastic Chasing 0 Game models maintaining a vector near 0 in ℓ∞ norm while random bounded updates occur and only an approximate state is observed.The player may reset one coordinate and modify the others based on the observed approximate vector.
  • 7.2 The Stochastic Chasing 0 Game: The paper shows that a simple strategy performs well: repeatedly select the largest coordinate and set it to 0.This strategy is the central constructive response to the stochastic chasing problem.

8 Introduction

The paper develops general techniques for applying cutting plane methods efficiently, addressing their perceived inefficiency and extending them to classic continuous and combinatorial optimization problems. It uses duality, direct optimization-oracle techniques, and problem-specific analyses to obtain improved algorithms for semidefinite programming, matroid intersection, submodular flow, and submodular minimization.

  • 8.2 Applications: The paper provides techniques for applying cutting plane methods efficiently to multiple optimization problems, including semidefinite programming, matroid intersection, and submodular flow.These applications illustrate the efficacy and versatility of the techniques.
  • Technique 1: Dimension Reduction through Duality: The authors use duality to reduce the number of dimensions, applying cutting planes in the primal or dual space with fewer variables while still solving the original problem.For semidefinite programming, they use maintained cutting planes to improve runtimes for finding both primal and dual solutions.
  • Technique 2: Using Optimization Oracles Directly: A general optimization-oracle technique regularizes an intersection problem so optimization over K1 and K2 immediately yields a separation oracle, allowing one cutting-plane invocation instead of an iterative reduction.The approach can save O(poly(n)) factors in running times.
  • Minimum-Cost Submodular Flow: The intersection reduction improves running times for matroid intersection and yields a substantial polynomial improvement for submodular flow.The intersection problem generalizes matroid intersection, and the technique targets problems where K = K1 ∩ K2.
  • Matroid Intersection: Matroid-intersection algorithms achieve quadratic oracle-query bounds of ˜O(n2) for independence oracles and ˜O(nr) for rank oracles.The algorithms outperform previous ones in regimes where r is close to n or oracle queries are relatively expensive.
  • Minimum-Cost Submodular Flow: ˜O(n2EO + n3) is the weakly polynomial running time obtained for submodular flow, roughly ˜O(n4) faster than previous weakly polynomial algorithms.The strongly polynomial result does not yield a speedup, while the strongly polynomial submodular-minimization algorithm improves prior algorithms by ˜O(n2) as a corollary.

9 Preliminaries

This section introduces convexity, approximate subgradients, and optimization oracles used to construct separation oracles. It establishes reductions between these oracle models for convex optimization.

  • Approximate subgradients extend ordinary subgradients by permitting an additive error δ in the supporting inequality.
  • The section also records standard closure and monotonicity properties of subgradients, including the gradient inclusion for differentiable convex functions.
  • An optimization oracle for a convex set returns an approximately optimal point for any queried linear objective.
  • An ε-optimization oracle for K yields an ε-subgradient oracle for the support function associated with K.
  • Combining the oracle reductions gives an O(Dε)-separation oracle for max_x∈K ⟨c,x⟩ when K lies in a ball of radius D.

10 Convex Optimization

This section applies the cutting plane method to convex minimization and semidefinite programming. It converts small-width output into approximate minimizers and uses maintained primal information to recover both primal and dual SDP solutions.

  • 10.1 From Feasibility to Optimization: An approximate minimizer can be found using a noisy separation or subgradient oracle, with expected time O(nSOη,δ(f) log(nR/ε) + n^3 log^O(1)(nR/ε)).
  • 10.1 From Feasibility to Optimization: The parameter κ is defined as R/MinWidth(Ω), and a linear transformation based on John’s ellipsoid can make κ effectively O(n^3/2).
  • 10.1 From Feasibility to Optimization: The method only requires Ω⊆B∞(R) and does not guarantee that its output lies in Ω.
  • 10.2 Duality and Semidefinite Programming: The SDP approach uses cutting-plane-maintained primal feasible points and minimax duality to obtain approximate primal solutions in conv(X_i).
  • 10.2 Duality and Semidefinite Programming: For SDP, the resulting procedure finds primal and dual approximations, including X⪰0, TrX=O(M), constraint error at most ε, and C•X≥OPT−ε.

11 Intersection of Convex Sets

This section develops a regularization-based cutting-plane framework for optimizing over intersections of convex sets using optimization oracles. It applies the framework to matroid intersection and submodular flow, while identifying a limitation on recovering points near arbitrary intersections.

  • 11.1 Intersection Framework: The framework optimizes a linear function over K1∩K2 by applying cutting planes to a suitably regularized problem using optimization oracles for K1 and K2.
  • 11.1 Intersection Framework: The regularization makes the objective strongly concave, producing a unique maximizer that approximates the solution over the intersection.
  • 11.1 Intersection Framework: The method can recover a primal solution from an approximate dual solution through a max-min formulation and minimax reasoning.
  • 11.1 Intersection Framework: The algorithm does not guarantee a point close to K1∩K2; an additional assumption may be needed, such as control of the angle between nearly parallel sets.
  • 11.2 Matroid Intersection: O(n^2 T_ind log(nM)+n^3 log^O(1)(nM)) and O(nr T_rank log n log(nM)+n^3 log^O(1)(nM)) algorithms are obtained for weighted matroid intersection.
  • 11.3 Submodular Flow: Submodular flow is solved in O(n^2 EO log(mCU)+n^3 log^O(1)(mCU)) time after an integral-polytope transformation makes feasibility trivial.

12 Introduction

Submodular function minimization is a fundamental combinatorial optimization problem with broad applications. The paper combines faster cutting-plane methods with Lovász-extension and primal-dual techniques to improve its weakly and strongly polynomial runtimes.

  • SFM models graph cuts, set coverage, and economic utility functions, making it useful across theoretical computer science, operations research, machine learning, and economics.
  • The new weakly and strongly polynomial SFM algorithms run in O(n^2 log nM · EO + n^3 log^O(1) nM) and O(n^3 log^2 n · EO + n^4 log^O(1) n), respectively.These improve the previous fastest runtimes by roughly O(n^2) in both regimes.
  • The strongly polynomial approach combines cutting planes with Iwata, Fleischer, and Fujishige techniques to infer structural information from a narrow feasible strip.
  • The paper leaves open whether its algorithms can be converted into fully combinatorial algorithms using only additions and subtractions.
  • The weakly polynomial algorithm applies cutting planes to the Lovász extension, using its subgradient as a separation oracle.
  • Unlike previous algorithms that maintain convex combinations of O(n) base-polyhedron BFSs and make local changes, the new method selects BFSs globally through the cutting-plane method.

13 Preliminaries

The preliminaries formulate SFM over integer-valued submodular functions and develop the Lovász-extension and base-polyhedron machinery used by the algorithms. They connect separating hyperplanes to basic feasible solutions and identify degenerate cases that solve SFM immediately.

  • SFM minimizes an integer-valued submodular function on subsets of an n-element ground set, with oracle evaluation time EO and value bound M.
  • The Lovász extension is a convex relaxation whose minimization over [0,1]^n corresponds to minimizing the original set function.
  • For a sorted point in [0,1]^n, a separating hyperplane is constructed from consecutive function differences f([i]) − f([i−1]).It can be computed with n oracle calls and time O(n · EO + n^2).
  • The separating-hyperplane coefficients correspond precisely to a basic feasible solution of the base polyhedron.
  • If a base-polyhedron vector is non-negative, the empty set minimizes f; if it is non-positive, the full ground set minimizes f.

14 Improved Weakly Polynomial Algorithms for SFM

The paper obtains a faster weakly polynomial SFM algorithm by applying its cutting-plane method to the Lovász extension with an efficiently computable separation oracle. The method returns an integral threshold set that minimizes the original submodular function.

  • O(n^2 log nM · EO + n^3 log^O(1) nM) is the resulting runtime for weakly polynomial SFM.The bound follows from the cutting-plane method and a separation oracle costing O(n · EO + n^2).
  • The algorithm applies the cutting-plane method to the Lovász extension over the hypercube [0,1]^n.
  • The separation oracle is exact, with η = 0 and δ = 0, so its hyperplanes preserve all minimizers and all points no worse than the queried objective.
  • After O(n log M) cutting-plane iterations, a threshold set derived from the remaining feasible region minimizes f.
  • An alternate argument gives O(n^2 log M · EO + n^O(1) log M) time, while whether the main bound can be improved to use log M remains open.

15 Improved Strongly Polynomial Algorithms for SFM

The section develops faster strongly polynomial algorithms for submodular minimization by combining cutting-plane methods with structural properties of base polyhedra and valid-arc deductions. The resulting approach improves the running time and supports a geometric, rather than purely combinatorial, treatment of the problem.

  • Oracle complexity: O(n^3 log n · EO) oracle calls suffice to minimize submodular functions, although the geometric algorithm has exponential running time.The argument repeatedly reduces the dimension after O(n log n) cutting-plane iterations.
  • Algorithmic design: The algorithm maintains a collection of BFS’s and computes a useful convex combination only after enough cutting-plane iterations.This differs from prior methods that explicitly maintain a convex combination throughout.
  • Constraint deduction: Cutting-plane output is used to deduce valid arcs and constraints such as x_i = 0, x_j = 1, x_i = x_j, or x_i ≤ x_j.These deductions either identify minimizers or reduce the remaining problem.

P B = {⃗x ∈RB : 0 ≤⃗x ≤1, xi ≤xj∀(i, j) ∈A ∩(B × B)}

This section characterizes the projected feasible region through box constraints and order constraints, then uses cutting-plane phases to obtain either structural equalities or many valid arcs. The resulting amortized deductions lead to the stated strongly polynomial runtime.

  • Projected feasible region: P^B equals the set of vectors in R^B satisfying 0 ≤ x ≤ 1 and x_i ≤ x_j for every arc within B.The equality follows because every feasible partial vector has a completion when the arc representation is complete.
  • Phase outcomes: Each cutting-plane phase yields either x_i = 0, x_i = 1, x_i = x_j, or at least b/4 new valid arcs.The alternatives arise from the structural cases in the projected feasible region.
  • Arc identification: A convex combination of the BFS’s can certify that each large element has sufficiently influential coordinates relative to its upper or lower bounds.This is the condition used to identify new valid arcs.
  • Runtime: O(n^3 log^2 n · EO + n^4 log^{O(1)} n) time follows from the phase costs and the fact that only O(n^2) arcs can be added.Case 2 occurs at most n times, while Case 3 has amortized arc cost O(n log^2 n · EO + n^2 log^{O(1)} n).

16 Discussion and Comparison with Previous Algorithms

The discussion contrasts the paper’s geometric use of BFS geometry and leverage scores with earlier convex-combination and combinatorial approaches. It also identifies remaining logarithmic overheads and open questions about optimality.

  • Comparison with previous algorithms: Previous algorithms maintain and iteratively improve a convex combination of BFS’s, whereas these algorithms use the geometry of existing BFS’s to choose the next one.The paper attributes the speedup to weighted influences, called leverage scores.
  • Geometric viewpoint: The algorithms minimize the volume of the feasible region using a potential function without a closed-form expression.This differs from earlier scaling schemes based on explicit functions or parameters.
  • Comparison with previous algorithms: The paper’s geometric approach shares tools with earlier work but employs them differently from mostly combinatorial algorithms.The bucketing scheme groups elements by both upper and lower bound sizes.
  • Open problems: Removing the log n overhead remains an open problem because the method relies on tools whose logarithmic factors appear inevitable.For strongly polynomial SFM, the current algorithm incurs one log n factor from having as many as log n buckets at each step.
  • Open problems: Whether the algorithm is optimal up to polylogarithmic factors remains open; certifying a solution already suggests an Ω(n^2) oracle-call lower scale.The certification argument uses a convex combination of n + 1 BFS’s, with n oracle calls per BFS.
Loading 1508.04874v2…