Robust Learning for Smoothed Online Convex Optimization with Feedback Delay

Summary

This paper studies Smoothed Online Convex Optimization (SOCO) problems where the target is to minimize the sum of a per-round hitting cost and a switching cost that penalizes temporal changes in actions. The most significant difference from previous studies is that they assume a delayed hitting cost and a nonlinear multi-step switching cost, which is quite more general than before and thus brings technical difficulties to provide theoretically guaranteed methods. Furthermore, they also want to use ML-based online optimizers to enhance performance. To that end, they developed a meta-algorithm that robustifies a given online optimizer by projecting its suggested action onto a robustified action set computed from a given expert method and historical observations. They provide a worst-case analysis for the cost of the resulting algorithm, based on which, they further establish a robustness guarantee and consistency result in the language of $CR$-competitive (see Definition 4) once a condition is satisfied. In the appendix, they explore the empirical performance of the proposed algorithm using a case study of battery management and validate its robustness.

Strengths

1. The studied setting is general enough and can incorporate popular neural networks as its part. 2. The worst-case theoretical analysis seems new and the proof seems correct. 3. Though put in the appendix, the experiments are well conducted with detailed descriptions of the experiment setup and chosen parameters, and a careful analysis of the experiment results. I appreciate the experiments a lot. 4. The paper is well-written mostly and the analysis is always to the point.

Weaknesses

However, there are some parts not clear enough. 1. The term ``multi-step nonlinear memory’’ appears abruptly in line 38. I think several additional explanations would help readers to digest this concept better for the first time. 2. In line 200, the author didn’t explain the meaning of $\text{cost}(x_{1:T})$. 3. Line 353, it is unclear to me what the notation $\text{Rob}_{\lambda} \left(\tilde{x}_{1: T} \right)$ means.

Questions

1. Intuitively, once establishing the worst-case bound uniformly in Theorem 4.1, one could easily get an average version (because the average case is always no worse than the worst case). Hence, it is unclear to me why the author bothered to introduce another result to bound the average cost in Theorem 4.2. 2. In Appendix D, the author spent much space explaining how to compute $\nabla_W \mathrm{cost}(x_{1:T})$. The reason is that the operator of projecting ML predictions into a robust set cannot be easily differentiated as typical neural network layers. So why bother to use this projection method? Why not use a primal-dual method that provides a projection-free alternative?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

See the weakness part and questions.

Summary

This paper considers the SOCO problem with multi-step nonlinear switching costs and feedback delay. The authors propose the RCL algorithm, which projects the ML predictions on to a robust action set determined by the expert’s predictions. They show that RCL maintain the $(1+\lambda)$-competitiveness against the expert while exploiting the potential of ML predictions. Moreover, they identify a sufficient condition under which the RCL achieves finite robustness and 1-consistency simultaneously. They also give an upper bound of the average cost of RCL, which reveals the advantage of training the ML model in a robustification-aware manner. Finally, they validate the theoretical results using a case study of battery management.

Strengths

- Challenging setup. This paper considers SOCO with hitting cost feedback delay and multi-step nonlinear memory in the switching cost, which is very hard to deal with. - New algorithm design and new proof approach. The intuition behind their algorithm is clearly explained in line 232-240. Theorem 4.1 is proven by considering a new reservation cost, which decouples the dependency of the online action on the history. - Good theorems with adequate explanation. The paragraphs following Theorem 4.1, Corollary 4.1.1 and Theorem 4.2 give comprehensive analysis of the results.

Weaknesses

- Assume known switching cost and smoothness constant. Convexity and smoothness assumptions on the hitting costs and switching costs. - The robustification-aware ML model is hard to be trained using standard back-propagation.

Questions

- Few lines explaining why the cost difference and the switching cost difference can be upper bounded by $H$ and $G$ respectively would help understanding. - How to efficiently compute the robustified action set? If it cannot be efficiently computed, how you learn that set in your experiment?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

The authors have already mentioned in the paper (line 408-417).

Summary

This paper considers the smoothed online convex optimization problem, in which, in addition to the standard hitting cost incurred per step, the algorithm also incurs a switching cost which relates to changes in its chosen action. The paper considers switching costs which are multi-step (relate to the previous p time steps). The paper presents an ML-augmented algorithm for the problem, which given a possibly-inaccurate predictor and a robust expert, is able to utilize the predictions from the predictor to the degree to which they are accurate, while not exceeding the cost of the expert times some small factor. This is done by taking the predictions and projecting them onto a space of possible actions dictated by the expert. The paper also discusses how to adjust the training of an ML model to take into account the fact that the model's predictions are then projected onto the actions allowed by the expert.

Strengths

The model, and the concept underlying the algorithm, are natural. I liked the figure in Appendix A, perhaps it should be part of the main body of the paper.

Weaknesses

In my opinion, the writing of the paper makes it hard to gain an intuitive understanding of the contributions of the paper within the scope of reasonable reviewing. For example, consider Theorem 4.1; excluding the robustness term, it is very hard to understand the significance of this theorem. Perhaps this bound seems simple and intuitive to experts more familiar with this problem.

Questions

none

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

yes

Summary

This paper studies the Smoothed Online Convex Optimization with multi-step nonlinear switching costs and feedback delay. In this setting, they propose Robustness-Constrained Learning (RCL), which combines existing online algorithm with a novel reservation cost to robustify untrusted ML predictions. Theoretically, they provide both worst-case and average-case guarantees for RCL. Finally, they provide some experiments to evaluate RCL.

Strengths

1. The paper is well written and organized. The paper thoroughly explains the challenges of incorporating ML predictions in their setting and emphasizes the importance of developing novel algorithmic techniques to overcome these difficulties. 2. The theoretical results are sound and look rigorous. The worst-case bound of RCL is novel.

Weaknesses

1. The weakness of the paper lies in the design of reservation costs, which may seem somewhat technical for analysis purposes. Additionally, the discussion on the optimization complexity for solving the constrained convex problem is missing, leaving a gap in understanding the practical implications of the proposed approach. 2. The paper's experimental results should be included in the main part to enhance confidence in the efficiency of RCL. Presenting empirical comparisons of RCL with other methods would demonstrate its advantages and substantiate the claims made in the paper. This would provide valuable evidence of the proposed algorithm's performance and practical benefits.

Questions

See Weakness

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

There are no limitations with regards to negative societal impacts.

Summary

This paper studies a problem, namely, Smoothed Online Convex Optimization (SOCO) with feedback delay and multi-step nonlinear memory, proposing a machine learning augmented online algorithm (RCL) with certain theoretical guarantees. This algorithm considers to implicitly hedge the decisions made by online and offline predictors, using a new constraint action set onto which the algorithm projects its decisions. This constraint set requires the decisions within it to achieve a trade-off between the hitting cost and the switching cost. By this design, this work achieves the first worst-case type cost bound for machine learning augmented algorithm under the given setting, and proposes a sufficient condition for the proposed algorithm to attain finite robustness and 1-consistency simultaneously. Moreover, the paper demonstrates that the algorithm RCL benefits from robustification-aware training and offers an average cost guarantee. Comprehensive experiments are executed to support these results.

Strengths

The writing of this paper is good with detailed explanations of the achieved results and the motivation is well substantiated by the experiments. The proposed algorithm is clear and easy to understand. The inherent nature of delayed feedback in the considered problem might pose an obstacle for algorithm design and analysis, and this paper proposes a solution for it.

Weaknesses

I harbor some reservations regarding the applicability and scalability of the theoretical findings presented in this paper. Please refer to the "Questions" section below for further details.

Questions

1. This paper claims that it provides a sufficient condition to achieve the finite robustness and 1-consistency simultaneously (line 63). But Corollary 4.1.1 suggests that this condition might be applicable for the proposed specific algorithm only. Moreover, this condition requires a per round lower bound for the switching cost of the expert algorithm. Does this condition hold for a broad class of expert algorithms? Could the sufficient condition proposed in Corollary 4.1.1 be suitable for a more general ML-augmented algorithm to realize the best-of-both-world guarantee? 2. I am confused about the term "worst-case" used in the discussion about Theorem 4.1. Based on my understanding, the worst-case bound should account for the upper bound of the minimax ratio. It would be beneficial if the authors could discuss about the relationship between the minimax bound and the bound in Theorem 4.1. 3. There are concerns regarding the existence and convexity of $\mathcal{X}_t$. Does the solution of Eq. (1) below line 223 always exist? It appears from Corollary 4.1.1 that the action set $\mathcal{X}$ is finite. If that is the case, then the "robustified" action set defined at line 223 may not exhibit convexity due to its discrete nature. Can the authors answer the above two questions? 4. Would the authors be able to provide further discussion concerning the technical contributions made in addressing the issues related to feedback delay, especially in comparison with previous works?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

Not much.

Summary

This paper studies Smoothed Online Convex Optimization with multi-step nonlinear switching costs and feedback delay. They propose an ML-augmented online algorithm named RCL that combines ML predictions with an expert online algorithm. The authors show that RCL can guarantee $(1 + \lambda)$ competitive ratio against any expert while improving the average-case performance. They show the effectiveness of RCL using battery management as a case study.

Strengths

1. Learning augmented algorithms is an important paradigm for designing more practical algorithms. Incorporating ML-augmented algorithms with multi-step nonlinear switching costs and feedback delay is a new and challenging problem. 2. The algorithm is simple and intuitive to understand. The authors provide a detailed analysis of the algorithm and the proof is rigorous. 3. This paper is well-written and easy to follow. The authors provide a detailed literature review and a clear introduction to the problem setting. The authors also provide a detailed discussion of the experimental results.

Weaknesses

1. The algorithmic contributions of the paper are a bit weak. The idea of constructing reservation costs to hedge against any possible uncertainties and then solving a constrained convex problem to project the ML prediction into a robust action set is quite standard in ML-augmented algorithms. 2. There lacks a lower bound on the trade-offs between robustness and average performance in ML-augmented algorithms.

Questions

Is it possible for the reservation cost design to be overly conservative, resulting in the constrained optimization problem yielding an empty solution set?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

n/a

Thanks for the rebuttal

I have read the rebuttal and the other reviews. And I will keep my score.