About

Lorenzo Orecchia is an Assistant Professor in the Computer Science department at the University of Chicago. His research focuses on designing simple and efficient algorithms to address foundational computational challenges across a variety of applications, including Theoretical Computer Science, Machine Learning, and Mathematical Optimization. A central theme in his work is the use of convex optimization and first-order methods as a versatile design framework applicable to both combinatorial and continuous problems. This approach enables the integration of techniques from discrete and continuous mathematics, resulting in faster and more interpretable algorithms.

Research topics

• Computer Science
• Mathematics
• Geometry
• Pure mathematics
• Discrete mathematics
• Combinatorics
• Physics
• Statistics
• Algorithm

Selected publications

• Manifold learning and optimization using tangent space proxies

  ArXiv.org · 2025-01-22

  preprintOpen access

  We present a framework for efficiently approximating differential-geometric primitives on arbitrary manifolds via construction of an atlas graph representation, which leverages the canonical characterization of a manifold as a finite collection, or atlas, of overlapping coordinate charts. We first show the utility of this framework in a setting where the manifold is expressed in closed form, specifically, a runtime advantage, compared with state-of-the-art approaches, for first-order optimization over the Grassmann manifold. Moreover, using point cloud data for which a complex manifold structure was previously established, i.e., high-contrast image patches, we show that an atlas graph with the correct geometry can be directly learned from the point cloud. Finally, we demonstrate that learning an atlas graph enables downstream key machine learning tasks. In particular, we implement a Riemannian generalization of support vector machines that uses the learned atlas graph to approximate complex differential-geometric primitives, including Riemannian logarithms and vector transports. These settings suggest the potential of this framework for even more complex settings, where ambient dimension and noise levels may be much higher.

  PublisherOA PDFDOI

• Atlas-based Manifold Representations for Interpretable Riemannian Machine Learning

  ArXiv.org · 2025-10-20

  preprintOpen accessSenior author

  Despite the popularity of the manifold hypothesis, current manifold-learning methods do not support machine learning directly on the latent $d$-dimensional data manifold, as they primarily aim to perform dimensionality reduction into $\mathbb{R}^D$, losing key manifold features when the embedding dimension $D$ approaches $d$. On the other hand, methods that directly learn the latent manifold as a differentiable atlas have been relatively underexplored. In this paper, we aim to give a proof of concept of the effectiveness and potential of atlas-based methods. To this end, we implement a generic data structure to maintain a differentiable atlas that enables Riemannian optimization over the manifold. We complement this with an unsupervised heuristic that learns a differentiable atlas from point cloud data. We experimentally demonstrate that this approach has advantages in terms of efficiency and accuracy in selected settings. Moreover, in a supervised classification task over the Klein bottle and in RNA velocity analysis of hematopoietic data, we showcase the improved interpretability and robustness of our approach.

  PublisherOA PDFDOI

• Training Binary Neural Networks via Gaussian Variational Inference and Low-Rank Semidefinite Programming

  2024-01-01

  article
  PublisherDOI

• Geometry and Duality of Alternating Markov Chains

  arXiv (Cornell University) · 2024

  Senior authorCorresponding
  • Computer Science
  • Geometry
  • Mathematics

  In this note, we realize the half-steps of a general class of Markov chains as alternating projections with respect to the reverse Kullback-Leibler divergence between convex sets of joint probability distributions. Using this characterization, we provide a geometric proof of an information-theoretic duality between the Markov chains defined by the even and odd half-steps of the alternating projection scheme.

  PublisherOA PDFDOI

• Top-$K$ ranking with a monotone adversary

  arXiv (Cornell University) · 2024-02-12

  preprintOpen access

  In this paper, we address the top-$K$ ranking problem with a monotone adversary. We consider the scenario where a comparison graph is randomly generated and the adversary is allowed to add arbitrary edges. The statistician's goal is then to accurately identify the top-$K$ preferred items based on pairwise comparisons derived from this semi-random comparison graph. The main contribution of this paper is to develop a weighted maximum likelihood estimator (MLE) that achieves near-optimal sample complexity, up to a $\log^2(n)$ factor, where $n$ denotes the number of items under comparison. This is made possible through a combination of analytical and algorithmic innovations. On the analytical front, we provide a refined~$\ell_\infty$ error analysis of the weighted MLE that is more explicit and tighter than existing analyses. It relates the~$\ell_\infty$ error with the spectral properties of the weighted comparison graph. Motivated by this, our algorithmic innovation involves the development of an SDP-based approach to reweight the semi-random graph and meet specified spectral properties. Additionally, we propose a first-order method based on the Matrix Multiplicative Weight Update (MMWU) framework. This method efficiently solves the resulting SDP in nearly-linear time relative to the size of the semi-random comparison graph.

  PublisherOA PDFDOI

• Hypergraph Diffusions and Resolvents for Norm-Based Hypergraph Laplacians

  arXiv (Cornell University) · 2023-07-20

  preprintOpen access

  The development of simple and fast hypergraph spectral methods has been hindered by the lack of numerical algorithms for simulating heat diffusions and computing fundamental objects, such as Personalized PageRank vectors, over hypergraphs. In this paper, we overcome this challenge by designing two novel algorithmic primitives. The first is a simple, easy-to-compute discrete-time heat diffusion that enjoys the same favorable properties as the discrete-time heat diffusion over graphs. This diffusion can be directly applied to speed up existing hypergraph partitioning algorithms. Our second contribution is the novel application of mirror descent to compute resolvents of non-differentiable squared norms, which we believe to be of independent interest beyond hypergraph problems. Based on this new primitive, we derive the first nearly-linear-time algorithm that simulates the discrete-time heat diffusion to approximately compute resolvents of the hypergraph Laplacian operator, which include Personalized PageRank vectors and solutions to the hypergraph analogue of Laplacian systems. Our algorithm runs in time that is linear in the size of the hypergraph and inversely proportional to the hypergraph spectral gap $λ_G$, matching the complexity of analogous diffusion-based algorithms for the graph version of the problem.

  PublisherOA PDFDOI

• Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game

  arXiv (Cornell University) · 2023

  • Computer Science
  • Mathematics
  • Combinatorics

  Despite there being significant work on developing spectral, and metric embedding based approximation algorithms for hypergraph generalizations of conductance, little is known regarding the approximability of hypergraph partitioning objectives beyond this. This work proposes algorithms for a general model of hypergraph partitioning that unifies both undirected and directed versions of many well-studied partitioning objectives. The first contribution of this paper introduces polymatroidal cut functions, a large class of cut functions amenable to approximation algorithms via metric embeddings and routing multicommodity flows. We demonstrate an $O(\sqrt{\log n})$-approximation, where $n$ is the number of vertices in the hypergraph, for these problems by rounding relaxations to metrics of negative-type. The second contribution of this paper generalizes the cut-matching game framework of Khandekar et. al. to tackle polymatroidal cut functions. This yields the first almost-linear time $O(\log n)$-approximation algorithm for standard versions of undirected and directed hypergraph partitioning. A technical consequence of our construction is that a cut-matching game which greatly relaxes the set of allowed actions for both players can be used to partition hypergraphs with negligible impact on the approximation ratio. We believe this to be of independent interest.

  PublisherOA PDFDOI

• Fair Packing and Covering on a Relative Scale

  SIAM Journal on Optimization · 2020-01-01

  preprintOpen accessSenior author

  Fair resource allocation is a fundamental optimization problem with applications in operations research, networking, and economic and game theory. Research in these areas has led to the general acceptance of a class of $\alpha$-fair utility functions parameterized by $\alpha \in [0, \infty]$. We consider $\alpha$-fair packing---the problem of maximizing $\alpha$-fair utilities under positive linear constraints---and provide a simple first-order method for solving it with relative-error guarantees. The method has a significantly lower convergence time than the state of the art, and to analyze it, we leverage the approximate duality gap technique, which provides an intuitive interpretation of the convergence argument. Finally, we introduce a natural counterpart of $\alpha$-fairness for minimization problems and motivate its usage in the context of fair task allocation. This generalization yields $\alpha$-fair covering problems, for which we provide the first near-linear-time solvers with relative-error guarantees.

  PublisherOA PDFDOI

• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods

  SIAM Journal on Optimization · 2019-01-01 · 63 citations

  articleOpen accessSenior author

  We present a general technique for the analysis of first-order methods. The technique relies on the construction of a duality gap for an appropriate approximation of the objective function, where the function approximation improves as the algorithm converges. We show that in continuous time the enforcement of an invariant, which corresponds to the approximate duality gap decreasing at a certain rate, exactly recovers a wide range of first-order continuous-time methods. We characterize the discretization errors incurred by different discretization methods, and show how iteration-complexity-optimal methods for various classes of problems cancel out the discretization error. The techniques are illustrated on various classes of problems---including convex minimization for Lipschitz-continuous objectives, smooth convex minimization, composite minimization, smooth and strongly convex minimization, solving variational inequalities with monotone operators, and convex-concave saddle-point optimization---and naturally extend to other settings.

  PublisherOA PDFDOI

• Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View

  arXiv (Cornell University) · 2019-06-29 · 2 citations

  preprintOpen accessSenior author

  This note provides a novel, simple analysis of the method of conjugate gradients for the minimization of convex quadratic functions. In contrast with standard arguments, our proof is entirely self-contained and does not rely on the existence of Chebyshev polynomials. Another advantage of our development is that it clarifies the relation between the method of conjugate gradients and general accelerated methods for smooth minimization by unifying their analyses within the framework of the Approximate Duality Gap Technique that was introduced by the authors.

  PublisherOA PDFDOI

Recent grants

• AF: Small: New Perspectives on Special Methods for Graph Algorithms

  NSF · $91k · 2015–2016

• CAREER: Next-Generation Design of First-Order Optimization Algorithms by the Calculus of Variations of Self-Dual Functionals

  NSF · $501k · 2020–2025

• AF:Small: Continuous Perspectives on Accelerated Methods for Combinatorial Optimization

  NSF · $498k · 2017–2020

• AF: Small: New Perspectives on Special Methods for Graph Algorithms

  NSF · $177k · 2013–2015

Frequent coauthors

• Zeyuan Allen-Zhu

  21 shared

• Jelena Diakonikolas

  University of Wisconsin–Madison

  17 shared

• Nisheeth K. Vishnoi

  11 shared

• Michael W. Mahoney

  9 shared

• Zeyuan Allen Zhu

  Institute of Computing Technology

  8 shared

• Yin Tat Lee

  7 shared

• Jonathan A. Kelner

  7 shared

• Aaron Sidford

  6 shared

Labs

• Orecchia Research GroupPI

  Designs simple, efficient algorithms for foundational computational challenges in Theoretical Computer Science, Machine Learning, and Mathematical Optimization.

Education

• Ph.D., Computer Science

  UC Berkeley

  2011

• M.S., Applied Mathematics

  MIT

• B.S.

  Unknown

Awards & honors

• 2014 Best Paper Award, co-winner, SODA
• NSF CAREER Award (2020)