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
Online Bidding under RoS Constraints without Knowing the Value
Sushant Vijayan
Swati Padmanabhan
The Web Conference (2025)
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 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
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
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
Ariel Schvartzman
Hanrui Zhang
Kelly Spendlove
Georgios Piliouras
Haihao (Sean) Lu
Andres Perlroth
Christopher Liaw
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
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
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
Minimum Cost Flows, MDPs, and $\ell_1$-Regression in Nearly Linear Time for Dense Instances
Thatchaphol Saranurak
Yang P. Liu
Yin Tat Lee
Jan van den Brand
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
Preview abstract
We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic $O(m \log^2 n \log\log^2 n)$ time algorithm. This improves on both the best previously known deterministic running time of $O(m \log^{12} n)$ (Kawarabayashi and Thorup [J. ACM, 66 (2018), 4]) and the best previously known randomized running time of $O(m \log^{3} n)$ (Karger [J. ACM, 47 (2000), pp. 46--76]) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow- and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest.
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)
