Author name cluster

Sam Chiu-wai Wong

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

STOC Conference 2020 Conference Paper

An improved cutting plane method for convex optimization, convex-concave games, and its applications

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

Given a separation oracle for a convex set K ⊂ ℝ 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 є. We propose a new cutting plane algorithm that uses an optimal O ( n log(κ)) evaluations of the oracle and an additional O ( n 2 ) time per evaluation, where κ = nR /є. This improves upon Vaidya’s O ( SO · n log(κ) + n ω+1 log(κ)) time algorithm [Vaidya, FOCS 1989a] in terms of polynomial dependence on n , where ω < 2.373 is the exponent of matrix multiplication and SO is the time for oracle evaluation. This improves upon Lee-Sidford-Wong’s O ( SO · n log(κ) + n 3 log O (1) (κ)) time algorithm [Lee, Sidford and Wong, FOCS 2015] in terms of dependence on κ. For many important applications in economics, κ = Ω(exp( n )) and this leads to a significant difference between log(κ) and (log(κ)). 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. Our algorithm not only works for the classical convex optimization setting, but also generalizes to convex-concave games. We apply our algorithm to improve the runtimes of many interesting problems, e.g., Linear Arrow-Debreu Markets, Fisher Markets, and Walrasian equilibrium.

Details

FOCS Conference 2019 Conference Paper

Faster Matroid Intersection

Deeparnab Chakrabarty
Yin Tat Lee
Aaron Sidford
Sahil Singla 0001
Sam Chiu-wai Wong

In this paper we consider the classic matroid intersection problem: given two matroids M 1 = (V, I 1 ) and M 2 = (V, I 2 ) defined over a common ground set V, compute a set S ∈ I 1 ∩ I 2 of largest possible cardinality, denoted by r. We consider this problem both in the setting where each Mi is accessed through an independence oracle, i. e. a routine which returns whether or not a set S ∈ I i in T ind time, and the setting where each Mi is accessed through a rank oracle, i. e. a routine which returns the size of the largest independent subset of S in M i in T rank time. In each setting we provide faster exact and approximate algorithms. Given an independence oracle, we provide an exact O(nr log r · T ind ) time algorithm. This improves upon previous best known running times of O(nr 1. 5 ·T ind ) due to Cunningham O(n 2 ·T ind in 1986 and + n 3 ) due to Lee, Sidford, and Wong in 2015. We also provide two algorithms which compute a (1- ε-approximate solution to matroid intersection running in times O(n 1. 5 /ε 1. 5 · Tind) and O((n 2 r -1 ε -2 + r 1. 5 ε -4. 5 ) · Tind), respectively. These results improve upon the O(nr/ε · T ind )time algorithm of Cunningham (noted recently by Chekuri and Quanrud). Given a rank oracle, we provide algorithms with even better dependence on n and r. We provide an O(n√r log n · T rank )time exact algorithm and an O(nε -1 log n · T rank )-time algorithm which obtains a (1 - 0)-approximation to the matroid intersection problem. The former result improves over the O(nr · T rank + n 3 )-time algorithm by Lee, Sidford, and Wong. The rank oracle is of particular interest as the matroid intersection problem with this oracle is a special case (via Edmond's minimax characterization of matroid intersection) of the submodular function minimization (SFM) problem with an evaluation oracle, and understanding SFM query complexity is an outstanding open question.

Details

SODA Conference 2017 Conference Paper

Computing Walrasian Equilibria: Fast Algorithms and Structural Properties

Renato Paes Leme
Sam Chiu-wai Wong

We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and general buyer valuations having only access to an aggregate demand oracle, i. e. , an oracle that given prices on all goods, returns the aggregated demand over the entire population of buyers. For the important special case of gross substitute valuations, our algorithm queries the aggregate demand oracle Õ ( n ) times and takes Õ ( n 3 ) time, where n is the number of goods. At the heart of our solution is a method for exactly minimizing certain convex functions which cannot be evaluated but for which the subgradients can be computed. We also give the fastest known algorithm for computing Walrasian equilibrium for gross substitute valuations in the value oracle model. Our algorithm has running time Õ (( mn + n 3 ) T V ) where T V is the cost of querying the value oracle. A key technical ingredient is to regularize a convex programming formulation of the problem in a way that subgradients are cheap to compute. En route, we give necessary and sufficient conditions for the existence of robust Walrasian prices, i. e. , prices for which each agent has a unique demanded bundle and the demanded bundles clear the market. When such prices exist, the market can be perfectly coordinated by solely using prices.

Details

STOC Conference 2017 Conference Paper

Subquadratic submodular function minimization

Deeparnab Chakrabarty
Yin Tat Lee
Aaron Sidford
Sam Chiu-wai Wong

Submodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be solved in polynomial time. Owing to applications in computer vision and machine learning, fast SFM algorithms are highly desirable. The current fastest algorithms [Lee, Sidford, Wong, 2015] run in O ( n 2 log nM · EO + n 3 log O (1) nM ) time and O ( n 3 log 2 n · EO + n 4 log O (1) n )time respectively, where M is the largest absolute value of the function (assuming the range is integers) and is the time taken to evaluate the function on any set. Although the best known lower bound on the query complexity is only Ω( n ) [Harvey, 2008], the current shortest non-deterministic proof [Cunningham, 1985] certifying the optimum value of a function requires Ω(n 2 ) function evaluations.

Details

SODA Conference 2017 Conference Paper

Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs

Sam Chiu-wai Wong

In this paper we give a f -approximation algorithm for the minimum unweighted Vertex Cover problem with Hard Capacity constraints (VCHC) on f -hypergraphs. This problem generalizes standard vertex cover for which the best known approximation ratio is also f and cannot be improved assuming the unique game conjecture. Our result is therefore essentially the best possible. This improves over the previous 2. 155 (for f = 2) and 2f approximation algorithms by Cheung, Goemans and Wong (CGW). At the heart of our approach is to apply iterative rounding to a natural LP relaxation that is slightly different from prior works which used (non-iterative) rounding. Our algorithm is significantly simpler and offers an intuitive explanation why f -approximation can be achieved for VCHC. We also present faster implementations of our method based on iteratively rounding the solution to certain CGW-style covering LPs.

Details

ICML Conference 2017 Conference Paper

Tight Bounds for Approximate Carathéodory and Beyond

Vahab Mirrokni
Renato Paes Leme
Adrian Vladu
Sam Chiu-wai Wong

We present a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope’s vertices. Our result provides a constructive proof for the Approximate Carathéodory Problem, which states that any point inside a polytope contained in the $\ell_p$ ball of radius $D$ can be approximated to within $\epsilon$ in $\ell_p$ norm by a convex combination of $O\left(D^2 p/\epsilon^2\right)$ vertices of the polytope for $p \geq 2$. While for the particular case of $p=2$, this can be achieved by the well-known Perceptron algorithm, we follow a more principled approach which generalizes to arbitrary $p\geq 2$; furthermore, this naturally extends to domains with more complicated geometry, as it is the case for providing an approximate Birkhoff-von Neumann decomposition. Secondly, we show that the sparsity bound is tight for $\ell_p$ norms, using an argument based on anti-concentration for the binomial distribution, thus resolving an open question posed by Barman. Experimentally, we verify that our deterministic optimization-based algorithms achieve in practice much better sparsity than previously known sampling-based algorithms. We also show how to apply our techniques to SVM training and rounding fractional points in matroid and flow polytopes.

Details

FOCS Conference 2015 Conference Paper

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

Yin Tat Lee
Aaron Sidford
Sam Chiu-wai Wong

In this paper 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 ⊂ R n that is contained in a box of radius R we show how to either compute a point in K or prove that K does not contain a ball of radius ϵ using an expected O(n log(nR/ϵ)) evaluations of the oracle 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 [91] for the current value of the matrix multiplication constant w 2 log nM · EO + n 3 log O(1) nM) and O(n 3 log 2 n · EO + n 4 log O(1) n), improving upon the previous best of O((n 4 · EO + n 5 )logM) and O(n 5 · EO + n 6 ) respectively. · Submodular Flow: n = |V|, m = |E|, C is the maximum edge cost in absolute value and U is maximum edge capacity in absolute value. We obtain a faster weakly polynomial running time of O(n 2 log nCU · EO + n 3 logO(1) nCU), improving upon the previous best of O(mn 5 log nU · EO) and O (n 4 h min {log C, log U}) from 15 years ago by a factor of Õ(n 4 ). We also achieve faster strongly polynomial time algorithms as a consequence of our result on submodular minimization. · Matroid Intersection: n is the size of the ground set, r is the maximum size of independent sets, M is the maximum absolute value of element weight, T rank and T ind are the time for each rank and independence oracle query. We obtain a running time of O((nr log 2 nT rank +n 3 log O(1) n) log nM) and O((n 2 log nT ind +n 3 log O(1) n) log 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. · Semidefinite Programming: n is the number of constraints, m is the number of dimensions and S is the total number of non-zeros in the constraint matrices. We obtain a running time of O(n(n 2 + m ω + S)), improving upon the previous best of Õ(n(n ω + m ω + S)) for the regime S is small.

Details

SODA Conference 2014 Conference Paper

Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs

Wang Chi Cheung
Michel X. Goemans
Sam Chiu-wai Wong

In this paper, we consider the minimum unweighted Vertex Cover problem with Hard Capacity constraints (VCHC) on multigraphs and hypergraphs. Given a graph, the objective of VCHC is to find a smallest multiset of vertices that cover all edges, under the constraints that each vertex can only cover a limited number of incident edges, and the number of available copies of each vertex is bounded. This problem generalizes the classical unweighted vertex cover problem. Here we restrict our attention to unweighted instances, since the weighted version of VCHC is as hard as the set cover problem, as shown by Chuzhoy and Naor (FOCS 2002). We obtain improved approximation algorithms for VCHC on multigraphs and hypergraphs. This problem has first been studied by Saha and Khuller (ICALP 2012). They proposed a 38-approximation for multigraphs, and a max {6 f, 65}-approximation for hypergraphs, where f is the size of the largest hyperedge. In this paper, we significantly improve these approximation ratios to and 2 f respectively. In the case of multigraphs, our approximation ratio is very close to the longstanding bound of 2 for the classical vertex cover problem. Our algorithms consist of a two-step process, each based on rounding an appropriate linear program. In particular, for multigraphs, the analysis in the second step relies on identifying a matching structure within any extreme point solution. Furthermore, we consider the partial VCHC problem in which one only needs to cover all but ℓ edges. We propose a generic reduction from partial VCHC on f -hypergraphs to VCHC on ( f + 1)-hypergraphs, with a small loss in the approximation factor. In particular, we present a (2 f + 2)(1 + ∊)-approximation algorithm for partial VCHC on f -hypergraphs.

Details