BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Jason M. Altschuler

Jason M. Altschuler contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.OCData Structures and AlgorithmsMachine LearningComputational ComplexityInformation Theorymath.APmath.CAmath.FAmath.ITmath.NAmath.PRmath.STNumerical AnalysisStatistics Theory

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
14topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2023arXiv

Shifted Composition II: Shift Harnack Inequalities and Curvature Upper Bounds

We apply the shifted composition rule -- an information-theoretic principle introduced in our earlier work [AC23] -- to establish shift Harnack inequalities for the Langevin diffusion. We obtain sharp constants for these inequalities for the first time, allowing us to investigate their relationship with other properties of the diffusion. Namely, we show that they are equivalent to a sharp "local gradient-entropy" bound, and that they imply curvature upper bounds in a compelling reflection of the Bakry-Emery theory of curvature lower bounds. Finally, we show that the local gradient-entropy inequality implies optimal concentration of the score, a.k.a. the logarithmic gradient of the density.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure

Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k and their support sizes n. This paper develops a general theory about what "structure" makes MOT solvable in poly(n,k) time. We develop a unified algorithmic framework for solving MOT in poly(n,k) time by characterizing the "structure" that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in poly(n,k) time. Second, our framework makes it much simpler to develop poly(n,k) time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle -- which is much more amenable to standard algorithmic techniques. We illustrate this ease-of-use by developing poly(n,k) time algorithms for three general classes of MOT cost structures: (1) graphical structure; (2) set-optimization structure; and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has poly(n,k) runtime; moreover, we provide the first poly(n,k) time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first poly(n,k) time algorithms, even for approximate computation. Together, these three structures encompass many -- if not most -- current applications of MOT.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Asymptotics for semi-discrete entropic optimal transport

We compute exact second-order asymptotics for the cost of an optimal solution to the entropic optimal transport problem in the continuous-to-discrete, or semi-discrete, setting. In contrast to the discrete-discrete or continuous-continuous case, we show that the first-order term in this expansion vanishes but the second-order term does not, so that in the semi-discrete setting the difference in cost between the unregularized and regularized solution is quadratic in the inverse regularization parameter, with a leading constant that depends explicitly on the value of the density at the points of discontinuity of the optimal unregularized map between the measures. We develop these results by proving new pointwise convergence rates of the solutions to the dual problem, which may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Wasserstein barycenters are NP-hard to compute

Computing Wasserstein barycenters (a.k.a. Optimal Transport barycenters) is a fundamental problem in geometry which has recently attracted considerable attention due to many applications in data science. While there exist polynomial-time algorithms in any fixed dimension, all known running times suffer exponentially in the dimension. It is an open question whether this exponential dependence is improvable to a polynomial dependence. This paper proves that unless P=NP, the answer is no. This uncovers a "curse of dimensionality" for Wasserstein barycenter computation which does not occur for Optimal Transport computation. Moreover, our hardness results for computing Wasserstein barycenters extend to approximate computation, to seemingly simple cases of the problem, and to averaging probability distributions in other Optimal Transport metrics.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Lyapunov Exponent of Rank One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution

The Lyapunov exponent corresponding to a set of square matrices $\mathcal{A} = \{A_1, \dots, A_n \}$ and a probability distribution $p$ over $\{1, \dots, n\}$ is $λ(\mathcal{A},p) := \lim_{k \to \infty} \frac{1}{k} \,\mathbb{E} \log \|A_{σ_k} \cdots A_{σ_2}A_{σ_1}\|$, where $σ_i$ are i.i.d. according to $p$. This quantity is of fundamental importance to control theory since it determines the asymptotic convergence rate $e^{λ(\mathcal{A},p)}$ of the stochastic linear dynamical system $x_{k+1} = A_{σ_k} x_k$. This paper investigates the following &#34;design problem&#34;: given $\mathcal{A}$, compute the distribution $p$ minimizing $λ(\mathcal{A},p)$. Our main result is that it is NP-hard to decide whether there exists a distribution $p$ for which $λ(\mathcal{A},p)< 0$, i.e. it is NP-hard to decide whether this dynamical system can be stabilized. This hardness result holds even in the &#34;simple&#34;&#39; case where $\mathcal{A}$ contains only rank-one matrices. Somewhat surprisingly, this is in stark contrast to the Joint Spectral Radius -- the deterministic kindred of the Lyapunov exponent -- for which the analogous optimization problem for rank-one matrices is known to be exactly computable in polynomial time. To prove this hardness result, we first observe via Birkhoff&#39;s Ergodic Theorem that the Lyapunov exponent of rank-one matrices admits a simple formula and in fact is a quadratic form in $p$. Hardness of the design problem is shown through a reduction from the Independent Set problem. Along the way, simple examples are given illustrating that $p \mapsto λ(\mathcal{A},p)$ is neither convex nor concave in general. We conclude with extensions to continuous distributions, exchangeable processes, Markov processes, and stationary ergodic processes.

0 citations0 reviewsNo code linkedOpen access