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:

$maximize_{x∈Z_{n}}c_{T}x,$ $subjecttoAx<b,x>0.$Note that ILP is proven to be NP-hard, and solving ILP usually involves commercial solvers like Gurobi.

Info

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

## Bayesian optimization

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

- sample: $S=s(R_{d},n)$
- evaluation function (target): $y_{t−1}=f(x_{t−1}),M_{t}=M_{t−1}∪x_{t−1}$
- acquisition function (generate new sample): $x_{t}=α(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.