soco 1.0.0

Algorithms for Smoothed Online Convex Optimization
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

---
layout: primer_without_heading
title: Algorithms - Algorithms for Smoothed Online Convex Optimization
---

# Problem Variants

* **Smoothed Convex Optimization (SCO)**
* **Simplified Smoothed Convex Optimization (SSCO)** - decision space is lower bounded by `0`, movement costs are a dimension-dependently scaled Manhattan distance
* **Smoothed Balanced-Load Optimization (SBLO)** - SSCO and hitting costs are computed by _balancing_ incoming loads across all dimensions each of which is described by a convex cost function
* **Smoothed Load Optimization (SLO)** - SSCO and hitting costs are time independent and linear in some incoming load

# Algorithms

## Offline

### Backward-Recurrent Capacity Provisioning [1]

SSCO - Fractional - Uni-Dimensional

Stays within bounds on the optimal solution moving backwards in time.

### Convex Optimization

SCO - Fractional

Finds the minimizer of a convex objective.

### Graph-Based Optimal Algorithm (in one dimension) [5]

SSCO - Integral - Uni-Dimensional

Finds a shortest path in a graph using dynamic programming (in polynomial time).

### Graph-Based Optimal Algorithm [9]

SSCO - Integral

Finds a shortest path in a graph using dynamic programming (**not** in polynomial time).

### Graph-Based Polynomial-Time Approximation Scheme [9]

SSCO - Integral

Extends the graph-based optimal algorithm by only considering a subset of the decision space to achieve a better performance.

### Static Fractional Optimum

SCO - Fractional

Solves a smaller problem than _Convex Optimization_ to obtain an optimal static solution.

### Static Integral Optimum

SCO - Integral

Cycles through _all_ possible configurations to find the optimal static integral solution. Convexity is used to stop the search of the decision space quickly in practice, however, the worst-case runtime is exponential.

## Online

### Lazy Capacity Provisioning [1]

SSCO - Fractional - Uni-Dimensional - `3`-competitive

Lazily stays within fractional bounds on the decision space.

### Lazy Capacity Provisioning [5]

SSCO - Integral - Uni-Dimensional - `3`-competitive (optimal for a deterministic algorithm)

Lazily stays within integral bounds on the decision space.

### Memoryless algorithm [3]

SSCO - Fractional - Uni-Dimensional - `3`-competitive (optimal for a memoryless algorithm)

Moves towards the minimizer of the hitting cost balancing the paid movement cost. Special case of Primal Online Balanced Descent.

### Probabilistic Algorithm [3]

SSCO - Fractional - Uni-Dimensional - `2`-competitive (optimal)

Constructs a probability distribution of well-performing configurations over time.

### Randmoly Biased Greedy [4]

SCO - Fractional - Uni-Dimensional - `2`-competitive (optimal)

Uses a work function to balance hitting and movement costs.

### Randomized Integral Relaxation [5]

SSCO - Integral - Uni-Dimensional - `2`-competitive (optimal)

Randomly rounds solutions of any `2`-competitive fractional algorithm.

### Lazy Budgeting for SLO [8]

SLO - Integral - `2d`-competitive (optimal for a deterministic algorithm)

Keeps servers active for some minimum time delta even when they are not use to balance hitting costs and movement costs.

### Lazy Budgeting for SLO (randomized) [8]

SLO - Integral - `(e / (e - 1))d`-competitive

Keeps servers active for some minimum time delta even when they are not use to balance hitting costs and movement costs.

### Lazy Budgeting for SBLO [9]

SBLO - Integral - `2d + 1 + \epsilon`-competitive

Keeps servers active for some minimum time delta even when they are not use to balance hitting costs and movement costs.

### Online Gradient Descent [4]

SCO - Fractional

Achieves sublinear regret by _learning_ the static offline optimum.

### Primal Online Balanced Descent [6]

SCO - Fractional - `3+\mathcal{O}(1/\alpha)`-competitive for the `\ell_2` norm and locally `\alpha`-polyhedral hitting costs, `\mathcal{O}(\sqrt{d})`-competitive for the `\ell_1` norm; mirror map must be `m`-strongly convex and `M`-Lipschitz smooth in the switching cost norm

Takes a gradient step orthogonal to some landing level set balancing costs in the primal space.

### Dual Online Balanced Descent [6]

SCO - Fractional - mirror map must be `m`-strongly convex and `M`-Lipschitz smooth in the switching cost norm

Takes a gradient step orthogonal to some landing level set balancing costs in the dual space. Achieves sublinear regret.

### Greedy Online Balanced Descent [7]

SCO - Fractional - `\mathcal{O}(1 / \sqrt{m})`-competitive for `m`-quasiconvex hitting costs and `\ell_2`-squared switching costs

Takes a normal OBD-step and then an additional step directly towards the minimizer of the hitting cost depending on the convexity parameter `m`.

### Regularized Online Balanced Descent [7]

SCO - Fractional - `\mathcal{O}(1 / \sqrt{m})`-competitive (optimal) for `m`-strongly convex and differentiable hitting costs and switching costs modeled as the Bregman divergence where the potential function is `\alpha`-strongly convex, `\beta`-strongly smooth, differentiable, and its Fenchel Conjugate is differentiable; `\Omega(1/m)`-competitive for `m`-quasiconvex hitting costs and `\ell_2`-squared switching costs

Using a computationally simpler local view.

### Receding Horizon Control [2]

SSCO - Fractional - `(1 + \Omega(\beta/e_0))`-competitive where `e_0` is the idle cost and `\beta` is the scaling of the Manhattan distance; when uni-dimensional the competitive ratio is `1 + \mathcal{O}(1/w)`

### Averaging Fixed Horizon Control [2]

SSCO - Fractional - `1 + \mathcal{O}(1/w)`-competitive

# References

1. Minghong Lin and Adam Wierman and Lachlan L. H. Andrew and Eno Thereska. _Dynamic right-sizing for power-proportional data centers_. 2011.
2. Minghong Lin and Zhenhua Liu and Adam Wierman and Lachlan L. H. Andrew. _Online Algorithms for Geographical Load Balancing_. 2012.
3. Nikhil Bansal and Anupam Gupta and Ravishankar Krishnaswamy and Kirk Pruhs and Kevin Schewior and Cliff Stein. _A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs_. 2015.
4. Lachlan L. H. Andrew and Siddharth Barman and Katrina Ligett and Minghong Lin and Adam Myerson and Alan Roytman and Adam Wierman. _A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret_. 2015.
5. Susanne Albers and Jens Quedenfeld. _Optimal Algorithms for Right-Sizing Data Centers_. 2018.
6. Niangjun Chen and Gautam Goel and Adam Wierman. _Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent_. 2018.
7. Gautam Goel and Yiheng Lin and Haoyuan Sun and Adam Wierman. _Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization_. 2019.
8. Susanne Albers and Jens Quedenfeld. _Algorithms for Energy Conservation in Heterogeneous Data Centers_. 2021.
9. Susanne Albers and Jens Quedenfeld. _Algorithms for Right-Sizing Heterogeneous Data Centers_. 2021.