Modeling Approaches

When it comes to the design part of a research paper, people usually cannot get away with proposing a procedure to handle the problems with an ”algorithm”. This page records some mathematic and theoretical approaches as the toolbox to model and solve the interested problem.

Integer linear programming §

Linear and multiple restrictions (subjections), analytical target function. Also refer to MILP if some variables are not integers. The canonical form of ILP is defined as:

$${\mathrm{maximize}}_{x\in {\mathbb{Z}}^n}{\mathbf{c}}^{\mathrm{T}}\mathbf{x},$$ $$\mathrm{subject}\mathrm{to}\mathbf{Ax}<\mathbf{b},\mathbf{x}>0.$$

Note that ILP is proven to be NP-hard, and solving ILP usually involves commercial solvers like Gurobi.

Related papers

• [ASPLOS ‘23] Mobius: Fine Tuning Large-Scale Models on Commodity GPU Servers

Bayesian optimization §

BO¹ is suitable for problems whose evaluation (target) function is black-box and costly to compute. It’s modeled as a iterative process:

1. sample: $\mathcal{S}=s({\mathbb{R}}^d,n)$
2. evaluation function (target): $y_{t-1}=f(x_{t-1}),M_t=M_{t-1}\cup x_{t-1}$
3. acquisition function (generate new sample): $x_t=\alpha (M_{t-1})$

BO is widely used in the hyper-parameter searching in ML training process, e.g., AutoML.

Related papers

• [SC ‘23] Scalable Tuning of (OpenMP) GPU Applications via Kernel Record and Replay

Additive increase multiplicative decrease §

AIMD is a feedback-based algorithm used for TCP congestion control.

Footnotes §

1. https://zhuanlan.zhihu.com/p/146633409, https://zhuanlan.zhihu.com/p/53826787 ↩