Online Convex Optimization with Stochastic Constraints
This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich's OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d. generated at each round and are disclosed to the decision maker only after the decision is made. This formulation arises naturally when decisions are restricted by stochastic environments or deterministic environments with noisy observations. It also includes many important problems as special case, such as OCO with long term constraints, stochastic constrained convex optimization, and deterministic constrained convex optimization. To solve this problem, this paper proposes a new algorithm that achieves O( p T ) expected regret and constraint violations and O( p T log(T )) high probability regret and constraint violations. Experiments on a real-world data center scheduling problem further verify the performance of the new algorithm.
***Summary***
The paper proposes an algorithm to address a mixed online/stochastic setting where the objective function is a sequence of arbitrary convex functions (with bounded subgradients) under stochastic convex constraints (also with bounded subgradients).
A static regret analysis (both in expectation and high-probability) is carried out. A real-world experiment about the allocation of jobs across servers (so as to minimize electricity cost) illustrates the benefit of the proposed method.
Assessment:
+ Overall good & clear structure and presentation
+ Technically sound and appears as novel
+ Good regret guarantees
- Confusing connection with "Deterministic constrained convex optimization"
- Some confusion with respect to unreferenced previous work [A]
- More details would be needed in the experimental section
More details can be found in the next paragraph.
***Further comments***
-In Sec. 2.2, the rationale of the algorithm is described. In particular, x(t+1) is chosen to minimize the "drift-plus-penalty" expression. Could some intuition be given to explain how the importance of the drift and penalty are traded off (e.g., why is a simple sum, without a tuning weight, sufficient?). 
-Lemma 5: I do not really have the expertise to assess whether Lemma 5 corresponds to "a new drift analysis lemma for stochastic process". In particular, I am not sufficiently versed in the stochastic process literature.
-Could some improvements be obtained by having \alpha and V dependent on t?
-For Lemma 9, it seems to me that the authors could reuse the results from Proposition 34 in [B]
-Comparison with "OCO with long term constraints": It appears that [A] (not referenced) already provide O(sqrt(T)) and O(sqrt(T)) guarantees, using similar algorithmic technique. This related work should be discussed.
-Comparison with "Stochastic constrained convex optimization": Is [16] the only relevant reference here?
-Confusion comparison with "Deterministic constrained convex optimization": In the deterministic constrained setting, we would expected the optimization algorithm to output a feasible solution; why is it acceptable (and why does it make sense) to have a non-feasible solution here? (i.e., constraint violation in O(1/sqrt(T)))
-Experiments:
   - More details about the baselines and the implementation (to make things reproducible, e.g., starting points) should appear in the core article
   - Is the set \mathcal{X_0} = [x_1^min, x_1^max] \times ... \times [x_100^min, x_100^max]? If this is the case, it means that problem (2) has to be solved with box constraints. More details would be in order.
   - Log-scale for unserved jobs (Figure d) may be clearer
   - Bigger figures would improve the clarity as well
   - An assessment of the variability of the results is missing to decide on the significance of the conclusions (e.g., repetitions to display standard errors and means).
   - To gain some space for the experiments, Sec. 4 could be reduced and further relegated to the supplementary material.
-Could the analysis extended to the dynamic regret setting?
***Minor***
-line 52: typo, min -> argmin. I may have missed them in the paper, but under which assumptions does the argmin of the problem reduce to the single x^*? 
-line 204 (a): isn't it an inequality instead of an equality?
[A] Yu, H. & Neely, M. J. A Low Complexity Algorithm with O(sqrt(T)) Regret and Constraint Violations for Online Convex Optimization with Long Term Constraints preprint arXiv:1604.02218, 2016
[B] Tao, T.; Vu, V. Random matrices: universality of local spectral statistics of non-Hermitian matrices The Annals of Probability, 2015, 43, 782-874
==================
post-rebuttal comments
==================
I thank the authors for their rebuttal (discussion about [A] was ignored). I have gone through the other reviews and I maintain my score. I would like to emphasize though, that the authors should clarify the discussion about the stochastic/deterministic constrained convex opt. case (as answered in the rebuttal).