Huang Zhiyi: A climber who rushes to the highest "rock point" of the "dangerous peak" of algorithms!

Even on days when he is not climbing, Huang Zhiyi, an associate professor at the Department of Computer Science at the University of Hong Kong (HKU), would think about the "rock points" - thinking about how to perfectly mobilize the fingertips, soles of the feet, and the core of the body, and imagine the posture of the movements and the connection between the front and the back. He loves rock climbing, in large part because this sport is similar to his career - the study of optimization problems under uncertain information in the field of theoretical computer science.

Each steep rock wall is like a series of challenging open questions, which require close cooperation between the brain and the body, the appropriate use of tools, prudent planning and summary, and targeted attack on multiple difficulties. Then, in the process of falling and hovering again and again, endure frustration and self-doubt, improve emotional resilience, physical willpower and the sense of belief in reaching the end; under various uncertain information, analyze and test continuously to achieve a delicate balance and optimization, and respond to the real needs of the vast world.

▲Huang Zhiyi

Since joining HKU in 2014, with his unremitting efforts, Huang Zhiyi has successively solved the thirty-year open problems proposed by Turing Award winner Richard Karp (covering applications such as smart travel and organ donation), as well as two more than ten-year open problems in online advertising: display ads and ad keywords. So far, he has published more than 40 papers in top conferences. In 2015, he won the Best Paper Award at the Annual Conference on Parallelism in Algorithms and Architectures (SPAA), becoming the first winner from an Asian institution; in 2020, he won the Best Paper Award at the Annual Conference on Foundations of Computer Science (FOCS), becoming the first winner from an Asian institution in nearly 14 years.

The infinite scenery is on the dangerous peaks, and the infinite scenery is ahead. The climbing journey in the algorithm world has never really ended. For Huang Zhiyi, the beauty of climbing lies in the perfect route that has been found after searching for a long time, the brief joy after climbing, and the fearless courage to continue to move towards the next unknown cliff after going through hardships and touching the highest "rock point", as well as the vigorous vitality that is tempered by constantly broadening horizons and constantly moving forward.

Heading into the uncertain unknown

For theoretical computer scientists, every quiet moment may contain a "brainstorm". Sometimes, sitting on the floor with his children playing games on weekends, Huang Zhiyi's mind wanders to other places without him realizing it, and he recalls a certain algorithm problem. This obsession with theoretical computer science can be traced back to his experience studying in the "Yao Class" of Tsinghua University (abbreviated as "Tsinghua") more than a decade ago.

In 2004, Turing Award winner Academician Yao Qizhi returned to Tsinghua full-time to teach courses in the Department of Computer Science and Technology. During this period, he came up with the idea of ​​establishing the "Tsinghua Academy Computer Science Experimental Class", and the following year he passed the selection exam and officially formed a class of 30 top students in mathematics and computer science. This was the first "Yao Class". Huang Zhiyi was a junior when he entered the first "Yao Class". Earlier, due to his outstanding performance in the high school mathematics competition, he was recommended to the Department of Computer Science at Tsinghua; later, due to his interest in mathematics and physics, he took courses in the college's "Mathematical and Physical Experimental Class". These inadvertently laid a certain foundation for him to be admitted to the "Yao Class".

The "Yao Class" is committed to cultivating top-notch innovative computer science talents who are as competitive as or even more competitive than undergraduates from world-class universities such as MIT and Princeton University. Academician Yao Qizhi specially developed a training program for students in the class, especially the theoretical algorithm course he opened, which was refreshing. At the same time, he also invited researchers from Microsoft Research Asia to teach students courses such as distributed computing and operating systems. The textbooks and exercises were very advanced at the time. With excellent teachers and smart classmates, a warm and learning atmosphere was formed within the "Yao Class". Huang Zhiyi was deeply influenced and gradually became interested in the theoretical computer science studied by Academician Yao Qizhi. Theoretical computer science, that is, the mathematical foundation of computer science, includes the algorithm design of various computing problems and the mathematical analysis of their time complexity, space complexity, etc., which is very consistent with Huang Zhiyi's interests and expertise.

After graduating in 2008, Huang Zhiyi went to the University of Pennsylvania for further doctoral studies. His advisor, Sampath Kannan, is a fellow of the American Computer Association; his other advisor, Aaron Roth, is a Sloan Award winner. Both advisors have made extraordinary achievements in their respective research fields. During this period, Huang Zhiyi actively engaged in academic exchanges, came into contact with many directions in the field of theoretical computer science, and conducted a lot of research on online algorithms and algorithmic game theory, and cooperated with Google Research and Microsoft Research. Not only that, during his doctoral studies, he also proposed a representative result of "a general method for converting algorithms into incentive-compatible mechanisms", and successively won important awards such as the 2012 Simons Theoretical Computer Science Scholarship (a total of 5 winners in the United States) and the 2013 Rabinov Doctoral Dissertation Award.

After obtaining his doctorate, Huang Zhiyi did a one-year postdoctoral research at Stanford University with Tim Roughgarden, a Gödel Prize winner, during which he seriously thought about his next research plan. At that time, theoretical computer science research had just emerged in China. As a student of the first "Yao Class", Huang Zhiyi always hoped to return to China to serve after graduation, just like Academician Yao Qizhi. So in 2014, he chose to return to China and join the University of Hong Kong (hereinafter referred to as "HKU"), which is adjacent to his hometown of Guangdong and has a long history. As soon as he joined the job, he stood out from 359 applicants for the Outstanding Young Scholars Program and became one of the 22 Early Career Award winners awarded by the Hong Kong Research Grants Council in 2014-2015. In the strong academic atmosphere of HKU, Huang Zhiyi started to study optimization problems under uncertain information.

Optimization problems under uncertain information are a different direction from traditional algorithm research. Traditional algorithm research considers how to solve different computing problems under the constraints of computing resources such as time and storage space; while optimization problems under uncertain information are to design algorithms to solve problems under the constraints of insufficient information while considering information itself as a computing resource. Take the problem of matching search requests and advertisers on search engines as an example: on the one hand, when matching a certain search request, the algorithm cannot accurately predict what kind of requests will be in the future, so this type of problem needs to deal with future uncertainties; on the other hand, in order to find a good match, the algorithm wants to know the advertiser's value measurement for different keywords, and this information is only known by the advertiser himself, which is uncertain for the algorithm.

▲Huang Zhiyi (third from left in the front row) attended the Shonan Conference in Japan in 2017 with the theme of "Algorithms and Optimization under Uncertain Information"

According to the types of information uncertainty and practical considerations, Huang Zhiyi mainly conducted in-depth research in the two directions of online algorithms and algorithmic game theory. In these two major algorithm fields, there are countless scientific research peaks, each of which is naturally formed with multiple cliffs. For decades, there have been thorns, clouds and mist, and mystery, attracting "explorers" and "climbers" who love theoretical computer science to come from afar to pay homage, ponder, practice, and seek hope of reaching the top. Huang Zhiyi enthusiastically threw himself into it and officially set out for the uncertain unknown.

Solving problems and promoting applications

In the field of online algorithms, Huang Zhiyi has focused on the online optimization of nonlinear objective functions, traditional online matching, and complete online matching. In the field of algorithmic game theory, he has conducted a series of innovative studies on a research hotspot in recent years: how to design mechanisms in scenarios where there is insufficient information about the probability distribution of buyer value. His papers were published at the flagship conferences of theoretical computer science, the Annual Conference on Theory of Computing (STOC) and the Annual Conference on Foundations of Computer Science (FOCS).

Scheduling and resource allocation are two classic problems for online optimization of nonlinear objective functions. In 2014, Zhiyi Huang studied how to adjust processor speed in real time to achieve the optimal balance between energy consumption and work processing performance. A key point is that energy consumption is often a quadratic or cubic function of processor speed rather than a linear function. In response to this, Zhiyi Huang proposed a set of algorithm design and analysis frameworks based on Fenchel duality, and designed a theoretically optimal algorithm for this problem based on this. In 2015, he further extended the results to a short-sighted model that cannot accurately predict the number of computing resources required to process each job, and proposed a new algorithm under this model to imitate the algorithm decision-making under a non-short-sighted model. The related paper won the Best Paper Award from the Annual Conference on Parallelism in Algorithms and Architectures (SPAA), the top conference in high-performance computing theory. In 2016, Zhiyi Huang extracted a general theoretical method from the Fenchel duality framework, thereby solving the covering and packing problems of a large class of nonlinear objective functions at one time. The 2016 summary of the online algorithm column of the Association for Computing Machinery's Newsletter on Algorithms and Computational Theory (ACM SIGACT News) stated that this paper "unified, simplified, and improved many existing results" and called this paper "the most eye-catching result of this year."

Matching is one of the most basic optimization problems, and its online version is also one of the most popular directions in online algorithms. Traditional online matching models are very common in modeling application scenarios such as organ transplantation and online advertising matching. Since the worst-case analysis framework commonly used in theoretical computer science often cannot well characterize the characteristics of actual problems in these scenarios, one of the hot spots and difficulties of online matching in recent years is to introduce a certain amount of randomness into the model and design algorithms under this premise. In addition, there are some open problems in traditional online matching that have not been broken through after more than 10 years of research. In 2020, after years of accumulation and thinking, Huang Zhiyi proposed a new algorithmic technique called online relevance selection for the advertising keyword problem proposed in 2005 and the display advertising problem proposed in 2009, breaking through the bottlenecks of these two open problems in one fell swoop. It is particularly worth mentioning that his work on solving the display advertising problem won the best paper award at the 2020 Foundations of Computer Science Annual Conference (FOCS), which is the second time in history that scholars from Asian universities have won the award, and it is also the first time in nearly 14 years.

Traditional online matching theory only deals with bipartite graph matching, such as the matching of search requests and advertisers. In some new application scenarios, including ride-hailing and carpooling services, the algorithms often need to deal with online matching of general graphs. Based on actual scenarios, in 2018, Huang Zhiyi proposed a completely online matching model and a corresponding algorithm analysis framework, making it possible to study the online matching theory of general graphs. This is considered to be "the first time that the algorithm proposed by Turing Award winner Richard Capa and others has been extended to general graphs and achieved an approximation ratio better than 0.5." Due to the value of the research, subsequent research groups such as the ride-hailing platform Lyft, MIT, and Stanford University have used this model as a reference.

In addition, in the field of algorithmic game theory, regarding the problem of "how to learn the approximate form of the Bayesian prior probability distribution from the data under the Bayesian model, so as to derive the approximate optimal mechanism for maximizing profits with less data", Huang Zhiyi has produced a series of research results since 2015 targeting the sampling complexity of the algorithm.

-- In 2015, Huang Zhiyi discovered the connection between this problem and statistical machine learning theory and information theory, the former of which can be used to analyze the upper bound of sampling complexity, while the latter can be used to analyze the lower bound of sampling complexity. Based on these tools, he solved the sampling complexity problem in the case of a single buyer and a single item, which attracted widespread attention in the industry.

——In 2016, Huang Zhiyi extended the algorithmic ideas and analysis methods based on statistical machine learning theory to the situation of multiple buyers, thereby improving the upper bound of its sampling complexity.

——In 2017, Huang Zhiyi noticed that algorithms in actual scenarios need to constantly use new data to update the learned mechanisms and pricing, which can be regarded as a kind of online learning. By proposing a new multi-scale online learning theory, he designed a new algorithm and obtained the optimal theoretical results. This new theory was later applied to the model selection problem in traditional machine learning theory.

——In 2018, Huang Zhiyi noticed that previous related studies generally assumed that buyers would not strategically adjust their behavior based on the seller's algorithm, and some subsequent studies pointed out that this assumption oversimplified the problem and proved that the strategic behavior of buyers could significantly reduce the profits of the seller's algorithm. Based on this, he proposed a set of algorithmic tools based on differential privacy, which can effectively reduce the strategic behavior of buyers when the mechanism structure to be learned is relatively simple.

--In 2019, based on previous research, Huang Zhiyi re-proposed a new set of informatics-based methods that were completely different from the previous framework, which completely solved the sampling complexity problem under multiple buyers' circumstances. It was regarded by the academic community as a "breakthrough result" in the direction of sampling complexity.

——In 2020, Huang Zhiyi further applied this series of sampling complexity theories to the more difficult market segmentation problem, and obtained the first polynomial sampling complexity upper bound for this problem.

The above-mentioned related results have been cited by famous scholars including Noam Nisan, Tim Lovegarden, the founder of algorithmic game theory and winner of the Gödel Prize, a high-level award in the field of theoretical computer science, Constantinos Daskalakis, winner of the Nevanlinna Prize, and Yao Qizhi, winner of the Turing Award.

▲Huang Zhiyi gave a lecture on the theme of "Data-driven Auction Mechanism Design" at the China Computer Federation (CCF) Enlightenment Conference

From an ignorant student listening to basic courses under the podium to becoming an academic colleague who talks with teachers and academic predecessors, Huang Zhiyi's growth is visible to the naked eye. "My progress is inseparable from the guidance of Academician Yao, and I have also benefited greatly from my doctoral supervisors Sampath Kannan and Aaron Ross, as well as my postdoctoral supervisor Tim Lovegarden and my internship supervisor Nikhil Devanur at Microsoft Research. Academic predecessors such as Deng Xiaotie, Teng Shanghua, and Sun Xiaoming have also given me valuable advice and guidance many times." Year after year, many real-world problems are condensed in his mind. With repeated complex deductions and problem solving, Huang Zhiyi's journey to climb the dangerous peak of algorithms is getting better and better.

Mingde's exploration of things never stops

The HKU emblem is engraved with the four characters "明德研究物". "明德" means to demonstrate virtue, and "研究物" means to explore the principles of things. In the fast-paced Hong Kong, HKU has created a quiet and comfortable academic paradise for teachers and students, eliminating impetuousness and not blindly pursuing paper output. In his nearly 10 years at HKU, Huang Zhiyi's greatest experience is this dignified academic freedom.

"The output cycle of theoretical computer science research is relatively long, but the college did not issue rigid task indicators across the board, but respected everyone's disciplinary characteristics. The college leaders also pay attention to cultivating young teachers' independent scientific research capabilities, encouraging us to develop our own teams and scientific research directions of interest first, rather than cooperating with senior professors to produce results as soon as possible." It was in this atmosphere that Huang Zhiyi did not follow the trend to choose popular directions, but insisted on his own research interests, gradually led the team onto the right track, and naturally formed a series of influential academic achievements.

At present, Huang Zhiyi's team recruits an average of one doctoral student each year, and the number of doctoral students in the research group is generally 4 to 5. In addition, every summer, he will also guide 2 to 6 undergraduates from home and abroad to do research. After the short-term teacher-student relationship ends, if the mutual inspection is satisfactory, they will continue the cooperative research for a year. Some of these undergraduates are from Tsinghua's "Yao Class". "Yao Class" inherits the academic legacy of Academician Yao Qizhi while collaborating and innovating, and talents emerge in large numbers.

In Huang Zhiyi's view, the research model of theoretical computer science is, in a sense, an apprenticeship system. "I have a cooperative relationship with my students. The difference between us may be that I have more experience and qualifications. In daily research, they will learn my ideas for selecting topics, solving problems, and asking questions through research projects. This research model does not have a complete set of teaching materials, so the instructor needs to teach the students by example."

To this end, Huang Zhiyi put forward several requirements that he thought were the most important to students. First, it is necessary to cultivate the awareness of high-value and high-quality topics. "More than ten years ago, I went to the University of Pennsylvania to study for a doctorate. The dean of the department said a lot at the briefing. The only sentence I remember so far is 'the most important thing in the past few years of studying for a doctorate is to form a taste for research and know whether the topic is good or bad.'" Second, to do theoretical computer science research, you need to have sufficient maturity in the operation of mathematical thinking and the use of mathematical tools, be able to adapt to changes, and find ways to advance research. Third, develop good habits. "I often emphasize to students that they should maintain a good habit of reading papers. In addition to papers in their own small directions, they should also try to understand some cutting-edge academic achievements in other related fields as much as possible to expand their knowledge reserves and academic horizons." As for the publication of papers that many people are concerned about, Huang Zhiyi is relaxed about it. "There is a certain element of luck in the publication of papers. It depends on the students' personal luck. It can't be rushed."

Even though he has been a teacher for many years, Huang Zhiyi always remembers his identity as a student. Among the many suggestions from Academician Yao Qizhi, the sentence "People who do research do not need to prove themselves repeatedly on the same problem" was like a stone thrown into the lake, stirring ripples in Huang Zhiyi's heart. Later, it became his motto to encourage himself from time to time, motivating him to keep trying and challenging himself, and to stop and review and summarize every once in a while. What determines the success of the climb is often the tiny details and the hesitation of a thought. Today, compared with winning the "Best Paper", making novel scientific research explorations and practicing a good scientific research taste are more desirable to Huang Zhiyi.

The problems in online algorithm research are rooted in the uncertainty of what will happen in the future. Algorithmic game theory focuses on problems related to the uncertainty of private information of selfish subjects. In the future, in the broad context of optimization under uncertainty, Huang Zhiyi hopes to continue to explore unresolved challenges in related directions. Learning in a strategic environment, the linear program hierarchy of online optimization, and the integration of online decision-making strategies from different fields... Dangerous peaks and cliffs are also extending a warm invitation to this brave climber.