Di Wang
Di Wang is in the Market Algorithm team, which is part of the broader Algorithms, Theory, Neural networks, and AI (Athena) team under Google Research. Di finished his PhD in Computer Science at UC Berkeley where he was advised by Satish Rao. Before joining Google, Di worked as a postdoc researcher at the Simons Institute (UC Berkeley) and the Algorithms & Randomness Center at Georgia Tech. Di's research interests are in the design of efficient algorithms, especially for large-scale optimization problems and graph problems that arise broadly in applications from machine learning, data analysis and operations research. Di's work draws on a broad range of numerical and discrete tools from combinatorics, optimization and graph theory, which leads to not only stronger theoretical guarantees, but also practical improvements for computational challenges arising in practice.
Authored Publications
Sort By
Preview abstract
We consider the problem of auto-bidding in online advertising from the perspective of a single advertiser. The goal of the advertiser is to maximize their value under the Return-on-Spend (RoS) constraint, with performance measured in terms of \emph{regret} against the optimal offline solution that knows all queries a priori. Importantly, the value of the item is \textit{unknown} to the bidder ahead of time. The goal of the bidder is to quickly identify the optimal bid, while simultaneously satisfying budget and RoS constraints. Using a simple UCB-style algorithm, we provide the first result which achieves optimal regret and constraint violation for this problem.
View details
Preview abstract
We study an auction setting in which bidders bid for placement of their content within
a summary generated by a large language model (LLM), e.g., an ad auction in which the
display is a summary paragraph of multiple ads. This generalizes the classic ad settings such
as position auctions to an LLM generated setting, which allows us to handle general display
formats. We propose a novel factorized framework in which an auction module and an LLM
module work together via a prediction model to provide welfare maximizing summary outputs
in an incentive compatible manner. We provide a theoretical analysis of this framework and
synthetic experiments to demonstrate the feasibility and validity of the system together with
welfare comparisons.
View details
Preview abstract
We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to approximate beyond a factor of e/(e-1), and provide a 4e/(e-1)-approximate offline algorithm. For the online setting, we show that no non-trivial approximations are achievable under adversarial arrivals. Under i.i.d. arrivals, we present a polytime online algorithm that provides a constant approximation of the optimal (computationally-unbounded) online algorithm. In contrast, we show that no constant approximation of the ex-post optimum is achievable by an online algorithm.
View details
A Field Guide for Pacing Budget and ROS Constraints
Haihao (Sean) Lu
ICML (2024)
Preview abstract
Budget pacing has been a standard service offered by major Internet advertising platforms for quite some time now. Budget pacing systems seek to optimize advertiser returns subject to budget constraints, through smooth spending of advertiser budgets. In the past few years, autobidding products that provide value-optimizing real-time bidding subject to return-on-spend (ROS) constraints as a service to advertisers have seen a prominent rise in adoption. The algorithms that govern these two services, namely bidding and budgeting, are not necessarily always a single unified entity that optimizes a global objective. But should these algorithms jointly optimize? How do the separate and joint optimizations compare? Systematically answering these questions, with both theoretical analysis and empirical studies is the focus of this work.
We compare (a) the sequential algorithm that first constructs the advertiser's ROS-pacing bid and then lowers that bid for budget pacing, with (b) the optimal joint algorithm that optimizes advertiser returns subject to both budget and ROS constraints. We establish the superiority of joint optimization both theoretically as well as empirically based on data from a large advertising platform. In the process, we identify a third algorithm that retains the theoretical properties of the joint optimization algorithm, while performing almost as well empirically as the joint optimization algorithm. This algorithm eases the transition from a sequential to a fully joint implementation by minimizing the amount of interaction between the two services.
View details
Auto-bidding and Auctions in Online Advertising: A Survey
Ashwinkumar Badanidiyuru Varadaraja
Christopher Liaw
Haihao (Sean) Lu
Andres Perlroth
Georgios Piliouras
Ariel Schvartzman
Kelly Spendlove
Hanrui Zhang
Mingfei Zhao
ACM SIGecom Exchanges, 22 (2024)
Preview abstract
In this survey, we summarize recent developments in research fueled by the growing adoption of automated bidding strategies in online advertising. We explore the challenges and opportunities that have arisen as markets embrace this autobidding and cover a range of topics in this area, including bidding algorithms, equilibrium analysis and efficiency of common auction formats, and optimal auction design.
View details
Preview abstract
Online advertising has recently become a highly competitive, complex, multi-billion-dollar industry with advertisers bidding for ad slots at large scales and high frequencies. This has resulted in the growing need for efficient ``auto-bidding'' algorithms to determine the bids for incoming queries to maximize advertisers' targets subject to their specified constraints. Our work focuses on designing efficient online algorithms for a single value-maximizing advertiser under a commonly seen constraint: Return-on-Spend (RoS). We quantify the efficiency in terms of \emph{regret} in comparison with the optimal algorithm that knows all the queries a priori.
Our main contribution is an algorithm that achieves near-optimal regret while respecting the specified RoS constraint. We are able to also incorporate our results with the pre-existing work of Balseiro, Lu, and Mirrokni~\cite{BLM20} to achieve near-optimal regret while respecting \emph{both} RoS and fixed budget constraints. Our main technical insight is in leveraging ideas from the literature on (offline) packing linear programs, in addition to the generic structural properties arising from our auction model.
View details
Preview abstract
Motivated by the online advertising industry, we study the non-stationary stochastic budget management problem: An advertiser repeatedly participates in $T$ second-price auctions, where her value and the highest competing bid are drawn from unknown time-varying distributions, with the goal of maximizing her total utility subject to her budget constraint. In the absence of any information about the distributions, it is known that sub-linear regret cannot be achieved. We assume access to historical samples, with the goal of developing algorithms that are robust to discrepancies between the sampling distributions and the true distributions. We show that our Dual Follow-The-Regularized-Leader algorithm is robust and achieves a near-optimal $\tilde O(\sqrt{T})$-regret with just one sample per distribution, drastically improving over the best-known sample-complexity of $T$ samples per distribution.
View details
Minimum Cost Flows, MDPs, and $\ell_1$-Regression in Nearly Linear Time for Dense Instances
Jan van den Brand
Yin Tat Lee
Yang P. Liu
Thatchaphol Saranurak
Aaron Sidford
Zhao Song
The 53rd ACM Symposium on Theory of Computing (STOC) (2021) (to appear)
Preview abstract
In this paper we provide new randomized algorithms with improved runtimes for solving linear programs with two-sided constraints. In the special case of the minimum cost flow problem on $n$-vertex $m$-edge graphs with integer polynomially-bounded costs and capacities we obtain a randomized method which solves the problem in $\tilde{O}(m + n^{1.5})$ time. This improves upon the previous best runtime of $\tilde{O}(m \sqrt{n})$ \cite{ls14} and, in the special case of unit-capacity maximum flow, improves upon the previous best runtimes of $m^{4/3 + o(1)}$ \cite{ls20_focs,kathuria2020potential} and $\tilde{O}(m \sqrt{n})$ \cite{ls14} for sufficiently dense graphs.
In the case of $\ell_1$-regression in a matrix with $n$-columns and $m$-rows we obtain a randomized method which computes an $\epsilon$-approximate solution in $\tilde{O}(mn + n^{2.5})$ time. This yields a randomized method which computes an $\epsilon$-optimal policy of a discounted Markov Decision Process with $S$ states and, $A$ actions per state in time $\tilde{O}(S^2 A + S^{2.5})$. These methods improve upon the previous best runtimes of methods which depend polylogarithmically on problem parameters, which were $\tilde{O}(mn^{1.5})$ \cite{LeeS15} and $\tilde{O}(S^{2.5} A)$ \cite{ls14,SidfordWWY18} respectively.
To obtain this result we introduce two new algorithmic tools of possible independent interest. First, we design a new general interior point method for solving linear programs with two sided constraints which combines techniques from \cite{lsz19} and \cite{BrandLN+20} to obtain a robust stochastic method with iteration count nearly the square root of the smaller dimension. Second, to implement this method we provide dynamic data structures for efficiently maintaining approximations to variants of Lewis-weights, a fundamental importance measure for matrices which generalize leverage scores and effective resistances.
View details
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
Jan van den Brand
Yin-Tat Lee
Danupon Nanongkai
Richard Peng
Thatchaphol Saranurak
Aaron Sidford
Zhao Song
61st Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2020)
Preview abstract
We present an $\tilde O(m+n^{1.5})$-time randomized algorithm for maximum bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, and optimal transport) on $m$-edge and $n$-node graphs. For maximum bipartite matching on moderately dense graphs, i.e. $m = \Omega(n^{1.5})$, our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic $O(m\sqrt{n})$-time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and $\tilde O(n^\omega)$-time algorithms [Ibarra-Moran 1981] (where currently $\omega\approx 2.373$). On sparser graphs, i.e. when $m = n^{9/8 + \delta}$ for any constant $\delta>0$, our result improves upon the recent advances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an $\tilde O(m^{4/3})$ runtime.
We obtain this result by several techniques of independent interest. First, we provide a simple sublinear-time algorithm for detecting high-energy edges in electric flows on expanders. Second, we combine this technique with recent advances in dynamic expander decompositions to provide a data structure for efficiently maintaining the iterates of the interior point method of [v.d.Brand-Lee-Sidford-Song 2020]. Finally, we simplify and improve this method by providing new sampling-based techniques for handling loss of feasibility due to approximate linear system solvers. Combining these results yields our $\tilde O(m+n^{1.5})$-time algorithm.
View details
Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard
Preview
Rasmus Kyng
Peng Zhang
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) (2020)
