# Theoretical Foundations

## Machine Learning, Computer Science, Mathematics

• ### The Art of LaTeX: Common Mistakes, and Advice for Typesetting Beautiful, Delightful Proofs

When was the first time you had to use LaTeX? If you are like most people, it was probably suddenly forced upon you during your first math or CS class where you had to start writing proofs, with minimal guidance on how to get started. Unfortunately, this meant that while many people have good operational knowledge of LaTeX, there are still many small mistakes and best practices which are not followed, which are not corrected by TAs as they are either not severe enough to warrant a note, or perhaps even the TAs themselves are not aware of them.

In this post, we cover some common mistakes that are made by LaTeX practitioners (even in heavily cited papers), and how to address them.

• ### A Concise Proof of the Central Limit Theorem, and Its Actually Useful Version, the Berry-Esseen Theorem

The Central Limit Theorem is widely used in statistics and machine learning, as it allows us to assume that given enough samples, the mean of the samples will follow a normal distribution. This holds even if the samples come from a distribution that is not normally distributed. In this post, we prove the Central Limit Theorem, and then take a look at the Berry-Esseen Theorem, which actually provides a quantitative bound on the convergence of the distribution and can therefore be actually used in deriving theoretical bounds.

• ### Reinforcement Learning Policy Optimization: Deriving the Policy Gradient Update

Reinforcement learning algorithms that learn a policy (as opposed to implicit policy methods like $$\epsilon$$-greedy) optimize their policies by updating their policies in the direction of the gradient. However, the precise environment dynamics are not usually known to us, and the state space is usually also too large to enumerate, which means that we still cannot compute the gradient analytically. In this post, we derive the policy gradient update from scratch, and show how it can be approximated by sampling sufficiently many trajectories.

• ### Pseudo-determinism for Graph Streaming Problems

Given a fixed input for a search problem, pseudo-deterministic algorithms produce the same answer over multiple independent runs, with high probability. For example, we can efficiently find a certificate for inequality of multivariate polynomials pseudo-deterministically, but it is not known how to do so deterministically. The same notion can be extended to the streaming model. The problem of finding a nonzero element from a turnstile stream is previously shown to require linear space for both deterministic and pseudo-deterministic algorithms. Another model of streaming problems is that of graphs, where edge insertions and deletions occur along a stream. Some natural problems include connectivity, bipartiteness, and colorability of a graph. While the randomized and deterministic graph streaming algorithms have been mostly well-studied, we investigate pseudo-deterministic space lower bounds and upper bounds for graph theoretic streaming problems.

• ### Graphical Bayesian Networks with Topic Modeling Priors for Predicting Asset Covariances

Covariance matrix prediction is a long-standing challenge in modern portfolio theory and quantitative finance. In this project, we investigate the effectiveness of Bayesian networks in predicting the covariance matrix of financial assets (specifically a subset of the S&P 500), evaluated against Heterogeneous Autoregressive (HAR) models. In particular, we consider both HAR-DRD, based on the DRD decomposition of the covariance matrix, and Graphical HAR (GHAR)-DRD, which is also based on DRD decomposition but also makes use of graphical relationships between the assets. To build the graph representing relationships between the assets, we apply Latent Dirichlet allocation (LDA) on the 10-K filings of each of the companies, and infer edges based on topic overlap.

• ### Analysis of Symmetry and Conventions in Off-Belief Learning (OBL) in Hanabi

Hanabi has been proposed as the new frontier for developing strategies in cooperative AI, currently a very nascent area of AI research. A recent algorithm that has been developed for multi-agent reinforcement learning in a cooperative context is the Off-Belief Learning (OBL) algorithm, which is based on iterated reasoning starting from a base policy. We investigate if policies learnt by agents using the OBL algorithm in the multi-player cooperative game Hanabi in the zero-shot coordination (ZSC) context are invariant across symmetries of the game, and if any conventions formed during training are arbitrary or natural, both of which are desirable properties.

• ### Improving Domain Adaptation of Transformer Models For Generating Reddit Comments

We improve upon the recent success of large language models based on the transformer architecture by investigating and showing several methods that have empirically improved its performance in domain adaptation. We use a pre-trained GPT-2 model and perform fine-tuning on 5 different subreddits, and use different methods of ordering the training data based on our priors about the input to see how this affects the prediction quality of the trained model. We propose a new metric for evaluating causal language modeling tasks called APES (Average Perplexity Evaluation for Sentences) to address the limitations of existing metrics, and apply them to our results. Our results are evaluated against both LSTM and GPT-2 baselines.

• ### Efficient Low Rank Approximation via Affine Embeddings

Suppose you have a $$n \times d$$ matrix $$A$$, where both dimensions are large. This could represent something like a customer-product matrix used in online recommender systems, where each cell $$A_{i,j}$$ denotes how many times customer $$i$$ purchased item $$j$$. Then it is typically the case that $$A$$ can be well-approximated by a low-rank matrix. For instance, using the previous example, there might only be a few dominant patterns that describes purchasing behavior in $$A$$, and the rest of it is just noise. Therefore, if we can find such a low-rank approximation, we can achieve significant space savings, and can also help to make the data more interpretable. In this post, we explore how affine embeddings via the CountSketch matrix allows us to perform low rank approximation in time $$O\left(\nnz{A}+(n+d) \poly \left( \frac{k}{\epsilon} \right)\right)$$.

• ### CMU 15-441/641 Computer Networks Course Review

Computer Networks is one of the lesser-known systems classes at Carnegie Mellon that turned out to be surprisingly fun and informative. In this post I'll talk about the projects and content covered, followed by my own thoughts on the usefulness on the class and who should take it.

• ### Solving Genshin Impact's Ancient Azure Stars quest in Linear Time

It is summer yet again, and miHoYo has blessed us with the Summertime Odyssey event that explores the (often dark and painful) backstories of the cast comprising Kazuha, Xinyan, Fischl, and Mona, back on the setting of the Golden Apple Archipelago. One puzzle that I found interesting from a computational perspective was a major part of Mona's questline Ancient Azure Stars, which is the main topic of this post. In this puzzle, you are given a pattern that resembles a constellation that you need to imitate. The puzzle is interesting because even though its mechanics allows for an exponential search space (and also multiple possible solutions), clever algorithmic techniques can speed up finding a valid solution to almost linear time. This post is meant to be accessible to people with only some exposure to algorithms, and takes things step by step.

• ### Impagliazzo's Five Worlds, or The Computational (Im)Possibilities of The World That We Live In

Most people have probably heard of the P = NP? problem in some shape or form, which asks whether the class of languages decidable in deterministic polynomial time is the same as the class of languages decidable in non-deterministic polynomial time. However, there are also several other interesting classes of intermediate possibilities that can arise if it was the case that P != NP, as this post explores.

• ### The Delightful Consequences of the Graph Minor Theorem

The graph minor theorem, also known as the Robertson–Seymour theorem, is generally regarded as the most important result in graph theory. In this post we introduce the graph minor theorem, provide the necessary background, and discover its delightfully deep algorithmic and philosophical implications.

• ### Universal types, and your type checker doesn't suck as much as you think

Universal types are very useful for performing generic programming, which allows you to use the same code over different types. For instance, the C++ STL (Standard Template Library) allows you to work on things like containers over any arbitrary type. You would surely not want to re-implement the logic for every concrete type that you use. Such a feature is known as parametric polymorphism. It is different from the other kind of polymorphism normally found in object-oriented languages that allows for overloading and run-time dispatch, which is known as ad-hoc polymorphism. In this post, we understand the theoretical foundations underpinning universal types, and conclude with the landmark result that typechecking with universal types is undecidable.

• ### Against Government Scholarships

Over the past few years, I've received numerous questions about studying abroad and whether it is advisable to take a government scholarship to do so from my juniors. Having witnessed firsthand the early career trajectories of many scholars and non-scholars alike, and having heard their different perspectives, I feel like now I have a good understanding of the concerns at hand to answer this question confidently. This post is targeted towards Singaporean junior college students debating whether they should take on a scholarship from the government to pursue a fully-paid education abroad. In this post, I will consider both the pros and cons of taking a scholarship. The relevance of some of the points is highly dependent on your current situation, so ultimately you must still make your value judgment.

• ### Why you can't create a value with the Bottom type (and why it's still useful)

If you've used any sort of object-oriented language, you may be familiar with the notion but not the name of the top-level type $$\top$$. For instance, in Java, the Object class forms the root of the class hierarchy, and similarly, in Python, all objects inherit from object. Analogously, there is also a bottom-level type $$\bot$$, but it cannot be instantiated by any value in any language. This post will explain why.

• ### Quantum physics inaccuracies in Seishun Buta Yaro (Rascal Does Not Dream of Bunny Girl Senpai)

I finished watching Seishun Buta Yaro (Rascal Does Not Dream of Bunny Girl Senpai) recently, and really enjoyed the anime. It explored themes of finding one's identity, and dealing with social anxiety during adolescent years. In the show, students are inflicted by a fictional disease called Adolescence Syndrome when they are severely affected by the things happening around them, whose symptoms depends on the specific reason why a person is mentally distraught. Rio Futaba, the president of the science club in the school, tries to explain the reasons for Adolescence Syndrome using quantum mechanics principles throughout the show. Unfortunately, most of it was poorly applied, and could be harmful in reinforcing misconceptions of quantum mehanics. In this post, I examine each of her claims and describe why they don't really make sense. This post is aimed at a general audience and requires no knowledge of quantum mechanics.

• ### Writing a DPLL SAT Solver

Boolean satisfiability (SAT) solvers have played an important role in software and hardware verification, automatic test pattern generation, planning, scheduling, and solving challenging problems in algebra. In this post, I talk about my experience writing my own SAT solver, its implementation details, designs and algorithms used, some comparisons between using different heuristics for splitting and choosing of variable assignments in the unforced case, challenges faced, and possible future directions.

• ### Playing Atari using Deep Reinforcement Learning

In this post, we study the first deep reinforcement learning model that was successfully able to learn control policies directly from high dimensional sensory inputs, as applied to games on the Atari platform. This is achieved by Deep Q Networks (DQN).

• ### HopSkipJumpAttack: An Efficient Adversarial Attack against Machine Learning Algorithms

Many machine learning algorithms have been shown to be susceptible to adversarial examples. For example, image classification neural networks can wrongly classify an image when a small perturbation, unnoticeable to the human eye, is added to the original image which it has previously correctly classified. The goal of an adversarial attack can thus be rephrased as an optimization problem to compute the "smallest" perturbation needed, such that the perturbed example will be misclassified.