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:

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

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

  1. sample:
  2. evaluation function (target):
  3. acquisition function (generate new sample):

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