Arrow Research search

Author name cluster

James R. Lee

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.

34 papers
2 author rows

Possible papers

34

STOC Conference 2024 Conference Paper

Sparsifying Generalized Linear Models

  • Arun Jambulapati
  • James R. Lee
  • Yang P. Liu
  • Aaron Sidford

We consider the sparsification of sums F : ℝ n → ℝ + where F ( x ) = f 1 (⟨ a 1 , x ⟩) + ⋯ + f m (⟨ a m , x ⟩) for vectors a 1 ,…, a m ∈ ℝ n and functions f 1 ,…, f m : ℝ → ℝ + . We show that (1+ε)-approximate sparsifiers of F with support size n /ε 2 (log n /ε) O (1) exist whenever the functions f 1 ,…, f m are symmetric, monotone, and satisfy natural growth bounds. Additionally, we give efficient algorithms to compute such a sparsifier assuming each f i can be evaluated efficiently. Our results generalize the classical case of ℓ p sparsification, where f i ( z ) = | z | p , for p ∈ (0, 2], and give the first near-linear size sparsifiers in the well-studied setting of the Huber loss function and its generalizations, e.g., f i ( z ) = min{| z | p , | z | 2 } for 0 < p ≤ 2. Our sparsification algorithm can be applied to give near-optimal reductions for optimizing a variety of generalized linear models including ℓ p regression for p ∈ (1, 2] to high accuracy, via solving (log n ) O (1) sparse regression instances with m ≤ n (log n ) O (1) , plus runtime proportional to the number of nonzero entries in the vectors a 1 , …, a m .

Details

FOCS Conference 2023 Conference Paper

Sparsifying Sums of Norms

  • Arun Jambulapati
  • James R. Lee
  • Yang P. Liu
  • Aaron Sidford

Abstract-For any norms $N_{1}, \ldots, N_{m}$ on $\mathbb{R}^{n}$ and $N(x): = N_{1}(x)+\cdots+N_{m}(x)$, we show there is a sparsified norm $\tilde{N}(x)= w_{1} N_{1}(x)+\cdots+w_{m} N_{m}(x)$ such that $|N(x)-\tilde{N}(x)| \leqslant \varepsilon N(x)$ for all $x \in \mathbb{R}^{n}$, where $w_{1}, \ldots, w_{m}$ are non-negative weights, of which only $O\left(\varepsilon^{-2} n \log (n / \varepsilon)(\log n)^{2. 5}\right)$ are non-zero. Additionally, we show that such weights can be found with high probability in time $O\left(m(\log n)^{O(1)}+\right. $ poly $\left. (n)\right) T$, where T is the time required to evaluate a norm $N_{i}(x)$, assuming that $N(x)$ is poly $(n)$ equivalent to the Euclidean norm. This immediately yields analogous statements for sparsifying sums of symmetric submodular functions. More generally, we show how to sparsify sums of p th powers of norms when the sum is p-uniformly smooth. 1

Details

STOC Conference 2023 Conference Paper

Spectral Hypergraph Sparsification via Chaining

  • James R. Lee

In a hypergraph on n vertices where D is the maximum size of a hyperedge, there is a weighted hypergraph spectral -sparsifier with at most O ( −2 log( D ) · n log n ) hyperedges. This improves over the bound of Kapralov, Krauthgamer, Tardos and Yoshida (2021) who achieve O ( −4 n (log n ) 3 ), as well as the bound O ( −2 D 3 n log n ) obtained by Bansal, Svensson, and Trevisan (2019). The same sparsification result was obtained independently by Jambulapati, Liu, and Sidford (2022).

Details

FOCS Conference 2018 Conference Paper

Fusible HSTs and the Randomized k-Server Conjecture

  • James R. Lee

We exhibit a poly(log k)-competitive randomized algorithm for the k-server problem on any metric space. The best previous result independent of the geometry of the underlying metric space is the 2k-1 competitive ratio established for the deterministic work function algorithm by Koutsoupias and Papadimitriou (1995). Even for the special case when the underlying metric space is the real line, the best known competitive ratio was k. Since deterministic algorithms can do no better than k on any metric space with at least k+1 points, this establishes that for every metric space on which the problem is non-trivial, randomized algorithms give an exponential improvement over deterministic algorithms. Our algorithm maintains an approximation of the underlying metric space by a distribution over HSTs. The granularity and accuracy of the approximation is adjusted dynamically according to the aggregate behavior of the HST algorithms. In short: We try to obtain more accurate approximations at the locations and scales where the "gaction" is happening. Thus a crucial component of our approach is the O((log k) 2 )-competitive randomized algorithm for HSTs obtained in our previous work with Bubeck, Cohen, Lee, and Ma. dry, and its "multiscale information theory" perspective.

Details

STOC Conference 2015 Conference Paper

Lower Bounds on the Size of Semidefinite Programming Relaxations

  • James R. Lee
  • Prasad Raghavendra
  • David Steurer

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than 2 n δ , for some constant δ > 0. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-O(1) sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for max-sat.

Details

FOCS Conference 2015 Conference Paper

Talagrand's Convolution Conjecture on Gaussian Space

  • Ronen Eldan
  • James R. Lee

Smoothing properties of the noise operator on the discrete cube and on Gaussian space have played a pivotal role in many fields. In particular, these smoothing effects have seena broad range of applications in theoretical computer science. We exhibit new regularization properties of the noise operator on Gaussian space. More specifically, we show that the mass on level sets of a probability density decays uniformly under the Ornstein-Uhlenbeck semi group. This confirms positively the Gaussian case of Talagrand's convolution conjecture (1989)on the discrete cube. A major theme is our use of an It o process (the "F"ollmer drift")which can be seen as an entropy-optimal coupling between the Gaussian measure and another given measure on Gaussian space. To analyze this process, we employ stochastic calculus and Girsanov's change of measure formula. The ideas and tools employed here provide a new perspective on hyper contractivity in Gaussian space and the discrete cube. In particular, our work gives a new way of studying "small" sets in product spaces (e. g. , Sets of size 2o(n) in the discrete cube) using a form of regularized online gradient descent.

Details

FOCS Conference 2013 Conference Paper

Approximate Constraint Satisfaction Requires Large LP Relaxations

  • Siu On Chan
  • James R. Lee
  • Prasad Raghavendra
  • David Steurer

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for MAX CUT has an integrality gap of 1/2 and any such linear program for MAX 3-SAT has an integrality gap of 7/8.

Details

STOC Conference 2011 Conference Paper

Cover times, blanket times, and majorizing measures

  • Jian Ding
  • James R. Lee
  • Yuval Peres

We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand's theory of majorizing measures. In particular, we show that the cover time of any graph G is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on G, scaled by the number of edges in G. This allows us to resolve a number of open questions. We give a deterministic polynomial-time algorithm that computes the cover time to within an O(1) factor for any graph, answering a question of Aldous and Fill (1994). We also positively resolve the blanket time conjectures of Winkler and Zuckerman (1996), showing that for any graph, the blanket and cover times are within an O(1) factor. The best previous approximation factor for both these problems was O((log log n) 2 ) for n-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).

Details

FOCS Conference 2009 Conference Paper

Higher Eigenvalues of Graphs

  • Jonathan A. Kelner
  • James R. Lee
  • Gregory N. Price
  • Shang-Hua Teng

We present a general method for proving upper bounds on the eigenvalues of the graph Laplacian. In particular, we show that for any positive integer k, the k th smallest eigenvalue of the Laplacian on a bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for planar grids. We also extend this spectral result to graphs with bounded genus, graphs which forbid fixed minors, and other natural families. Previously, such spectral upper bounds were only known for k = 2, i. e. for the Fiedler value of these graphs. In addition, our result yields a new, combinatorial proof of the celebrated result of Korevaar in differential geometry.

Details

FOCS Conference 2008 Conference Paper

Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows

  • Punyashloka Biswal
  • James R. Lee
  • Satish Rao

We present a new method for upper bounding the second eigenvalue of theLaplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the Rayleigh quotient. Using this, we show that every n-vertex graph of genus g and maximum degree d satisfies lambda 2 (G) = O((g+1) 3 d/n). This recovers the O(d/n) bound of Spielman and Teng for planar graphs, and compares to Kelner's bound of O((g+1)poly(d)/n), but our proof does not make use of conformal mappings or circle packings. We are thus able to extend this to resolve positively a conjecture of Spielman and Teng, by proving that lambda 2 (G) = O(dh 6 log h/n) whenever G is K h -minor free. This shows, in particular, that spectral partitioning can be used to recover O(radicn)-sized separators in bounded degree graphs that exclude a fixed minor. We extend this further by obtaining nearly optimal bounds on lambda 2 for graphs which exclude small-depth minors in the sense of Plotkin, Rao, and Smith. Consequently, we show that spectral algorithms find small separators in a general class of geometric graphs. Moreover, while the standard "sweep'' algorithm applied to the second eigenvector may fail to find good quotient cuts in graphs of unbounded degree, our approach produces a vector that works for arbitrary graphs. This yields an alternate proof of the result of Alon, Seymour, and Thomas that every excluded-minor family of graphs has O(radicn)-node balanced separators.

Details

FOCS Conference 2008 Conference Paper

Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums

  • Amit Chakrabarti
  • Alexander Jaffe
  • James R. Lee
  • Justin Vincent

We study the properties of embeddings, multicommodity flows, and sparse cuts in minor-closed families of graphs which are also closed under 2-sums; this includes planar graphs, graphs of bounded treewidth, and constructions based on recursive edge replacement.

Details

FOCS Conference 2006 Conference Paper

Algorithms on negatively curved spaces

  • Robert Krauthgamer
  • James R. Lee

We initiate the study of approximate algorithms on negatively curved spaces. These spaces have recently become of interest in various domains of computer science including networking and vision. The classical example of such a space is the real-hyperbolic space \mathbb{H}^d for d \geqslant 2, but our approach applies to a more general family of spaces characterized by Gromov's (combinatorial) hyperbolic condition. We give efficient algorithms and data structures for problems like approximate nearest-neighbor search and compact, low-stretch routing on subsets of negatively curved spaces of fixed dimension (including \mathbb{H}^d as a special case). In a different direction, we show that there is a PTAS for the Traveling Salesman Problem when the set of cities lie, for example, in \mathbb{H}^d. This generalizes Arora's results for \mathbb{R}^d. Most of our algorithms use the intrinsic distance geometry of the data set, and only need the existence of an embedding into some negatively curved space in order to function properly. In other words, our algorithms regard the interpoint distance function as a black box, and are independent of the representation of the input points.

Details

FOCS Conference 2006 Conference Paper

Lp metrics on the Heisenberg group and the Goemans-Linial conjecture

  • James R. Lee
  • Assaf Naor

We prove that the function d: \mathbb{R}^3 \times \mathbb{R}^3 \to [0, \infty ) given by d\left( {(x, y, z), (t, u, v)} \right)= \left( {[((t - x)^2 + (u - y)^2 )^2 + (v - z + 2xu - 2yt)^2 ]^{\frac{1} {2}} + (t - x)^2 + (u - y)^2 } \right)^{\frac{1} {2}}. is a metric on \mathbb{R}^3 such that (\mathbb{R}^3, \sqrt d ) is isometric to a subset of Hilbert space, yet (\mathbb{R}^3, d) does not admit a bi-Lipschitz embedding into L_1. This yields a new simple counter example to the Goemans-Linial conjecture on the integrality gap of the semidefinite relaxation of the Sparsest Cut problem. The metric above is doubling, and hence has a padded stochastic decomposition at every scale. We also study the L_p version of this problem, and obtain a counter example to a natural generalization of a classical theorem of Bretagnolle, Dacunha-Castelle and Krivine (of which the Goemans-Linial conjecture is a particular case). Our methods involve Fourier analytic techniques, and a recent breakthrough of Cheeger and Kleiner, together with classical results of Pansu on the differentiability of Lipschitz functions on the Heisenberg group.

Details

STOC Conference 2005 Conference Paper

Euclidean distortion and the sparsest cut

  • Sanjeev Arora
  • James R. Lee
  • Assaf Naor

We prove that every n-point metric space of negative type (in particular, every n-point subset of L 1 ) embeds into a Euclidean space with distortion O(√log n log log n), a result which is tight up to the O(log log n) factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size k, we achieve an approximation ratio of O(√log k log log k).

Details

FOCS Conference 2004 Conference Paper

Measured Descent: A New Embedding Method for Finite Metrics

  • Robert Krauthgamer
  • James R. Lee
  • Manor Mendel
  • Assaf Naor

We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This provides a refined and unified framework for the two primary methods of constructing Frechet embeddings for finite metrics, due to J. Bourgain and S. Rao. We prove that any n-point metric space (X, d) embeds in Hilbert space with distortion O(/spl radic//spl alpha//sub X//spl middot/log n), where /spl alpha//sub X/ is a geometric estimate on the decomposability of X. An an immediate corollary, we obtain an O(/spl radic/log /spl lambda//sub X//spl middot/log n) distortion embedding, where /spl lambda//sub X/ is the doubling constant of X. Since /spl lambda//sub X/ /spl les/ n, this result recovers Bourgain 5 theorem, but when the metric X is, in a sense, "low-dimensional", improved bounds are achieved. Our embeddings are volume-respecting for subsets of arbitrary size. One consequence is the existence of (k, O(log n)) volume-respecting embeddings for all 1 /spl les/ k /spl les/ n, which is the best possible, and answers positively a question posed by U. Feige. Our techniques are also used to answer positively a question of Y. Rabinovich, showing that any weighted n-point planar graph embeds in /spl lscr//sub /spl infin///sup O(log n)/ with O(1) distortion. The O(log n) bound on the dimension is optimal, and improves upon the previously known bound of O(log/sup 2/ n).

Details

FOCS Conference 2003 Conference Paper

Bounded Geometries, Fractals, and Low-Distortion Embeddings

  • Anupam Gupta 0001
  • Robert Krauthgamer
  • James R. Lee

The doubling constant of a metric space (X, d) is the smallest value /spl lambda/ such that every ball in X can be covered by /spl lambda/ balls of half the radius. The doubling dimension of X is then defined as dim (X) = log/sub 2//spl lambda/. A metric (or sequence of metrics) is called doubling precisely when its doubling dimension is bounded. This is a robust class of metric spaces which contains many families of metrics that occur in applied settings. We give tight bounds for embedding doubling metrics into (low-dimensional) normed spaces. We consider both general doubling metrics, as well as more restricted families such as those arising from trees, from graphs excluding a fixed minor, and from snowflaked metrics. Our techniques include decomposition theorems for doubling metrics, and an analysis of a fractal in the plane according to T. J. Laakso (2002). Finally, we discuss some applications and point out a central open question regarding dimensionality reduction in L/sub 2/.

Details

STOC Conference 2003 Conference Paper

The intrinsic dimensionality of graphs

  • Robert Krauthgamer
  • James R. Lee

We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [16]. Let Z ∞ d be the infinite graph whose vertex set is Z d and which has an edge (u,v) whenever ||u-v|| ∞ = 1. Let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of Z ∞ d . The growth rate of G, denoted ρ G , is the minimum ρ such that every ball of radius r > 1 in G contains at most r ρ vertices. By simple volume arguments, dim(G) = Ω(ρ G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ G ) for every graph G.Previously, it was not known whether dim(G) could be upper bounded by any function of ρ G , even in the special case of trees. We show that a weaker form of Levin's conjecture holds by proving that, for every graph G, dim(G) = O(ρ G log ρ G ). We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) =Ω(ρ G log ρ G ). For families of graphs which exclude a fixed minor, we salvage the strong form, showing that dim(G) = O(ρ G ). This holds also for graphs without long induced simple cycles. Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces due to Linial[15].

Details