Approximating Multiple Robust Optimization Solutions in One Pass via Proximal Point Methods

Authors: Hao Hao, Peter Y Zhang
Primary area: optimization
Keywords: Robust optimization, Robustness-accuracy tradeoff

Abstract:
Robust optimization provides a principled and unified framework to model many problems in modern operations research and computer science applications, such as risk measures minimization and adversarially robust machine learning. To use a robust solution (e.g., to implement an investment portfolio or perform robust machine learning inference), the user has to a priori decide the trade-off between efficiency (nominal performance) and robustness (worst-case performance) of the solution by choosing the uncertainty level hyperparameters.  In many applications, this amounts to solving the problem many times and comparing them, each from a different hyperparameter setting.  This makes robust optimization practically cumbersome or even intractable. We present a novel procedure based on the proximal point method (PPM) to approximate many Pareto-efficient robust solutions using the PPM trajectory.  Compared with the existing method with computation cost $N\times T_{\mathrm{RC}}$, the cost of our method is $T_{\mathrm{RC}} + (N-1)\times T_{\mathrm{\widetilde{PPM}}}$, where $N$ is the number of robust solutions to be generated,  $T_{\mathrm{RC}}$ is the cost of solving a single robust optimization problem, and $T_{\mathrm{\widetilde{PPM}}}$ is cost of a single step of an approximate PPM. We prove exact PPM can produce exact Pareto efficient robust solutions for a class of robust linear optimization problems. For robust optimization problems with nonlinear and differentiable objective functions, compared with the existing method, our method equipped with first-order approximate PPMs is computationally cheaper and generates robust solutions with comparable performance.

Decision: reject
Reviewer scores: 5, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1730688154383

thread_type:
official_review

<thread_object>
creator: reviewer_7fpc

<content>
summary:
The paper proves that for robust LPs with uncertain objective functions under the simplex decision domain and ellipsoidal uncertainty sets, the proximal point trajectory are exactly Pareto efficient robust solutions. For robust LPs with a random polyhedron domain, the paper proves that with high probability, the performances of the Pareto efficient robust solutions are bounded by the performances of two proximal point trajectories. Numerical experiments on portfolio optimization and adversarially robust deep learning are provided.

strengths:
The paper raises the interesting question of computing the efficient frontier that balances robustness and efficiency, and proposes a novel approach to finding this frontier. The paper provides an original proof that with high probability, the performances of the Pareto efficient robust solutions are bounded by the performances of two proximal point trajectories. The paper demonstrates clear structural organization. The visualizations are informative, and both the core ideas and theorems are presented with clarity.

weaknesses:
The paper claims that the computational cost is reduced from N*T to 2*T. However, in each iteration of the proposed proximal point method for portfolio optimization, a quadratic optimization problem needs to be solved. Thus, the total computational cost is not reduced compared to the brute-force method of solving the problem for multiple alphas.

questions:
The paper would benefit from numerical experiments comparing the running time of the proposed method against the brute-force approach. The abstract should explicitly state that mean-variance optimization is the paper's primary focus. Additionally, it would be helpful to acknowledge the existence of a closed-form solution to the Markowitz optimization problem. Regarding Figure 1, the substantial discrepancy between the out-of-sample performance of robust Markowitz++ portfolios, despite their similar in-sample performance, requires further explanation.

Typos: 
Line 157 bracket is misplaced
Line 180 by -> be
Figure 1: Porfolio -> Portfolio
</content>
</thread_object>

</thread>
<thread>
creation date:
1730717733574

thread_type:
official_review

<thread_object>
creator: reviewer_evsu

<content>
summary:
This paper presents a proximal point method based procedure to approximate many Pareto efficient robust solutions. This procedure reduces the computational requirement  by a multiplicity of the number of robust solutions to be generated. They go on to show that this procedure can produce exact Pareto efficient robust solutions for a class of optimization problems.

strengths:
S1 - The paper is generally well written and well presented.

S2 - The technical claims in the paper are generally well explained.

S3 - Experiments are a plus.

S4 - The idea is interesting

weaknesses:
W1 - The literature review is a bit lacking. The comparisons to previous art are inadequate.

W2 - The main novelty is ambiguous. 

W3 - The method seems to be limited in its generation of robust solutions where the radius of the uncertainty sets are not freely selectable.

questions:
Q1 - Although the computational efficiency claim somewhat makes sense. I am not sure how this is equivalent to generating multiple robust solutions and comparing their results. While your proximal point method generates pareto efficient intermediate solutions, how many of them does it generate? Why is the new computational complexity $2\times T$ and does not include $N$ at all. 

Q2 - How comprehensive is the robust solutions generated by your proximal point based procedure?

Q3 - How to read figure 1 and 2, why are not one-to-one? Are these supposed to be the trajectories followed with the gradient steps?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721799429

thread_type:
official_review

<thread_object>
creator: reviewer_f2yb

<content>
summary:
This paper studies approximating the efficient-robust Pareto solutions through proximal point method. It contributes faster computation requirements compared to the literature.

strengths:
**Originality:** 
- Their undertaking of efficient identification of Pareto front seems new.  
- The work is a novel combination of well-known techniques.

**Quality:**
- The methods used seem appropriate.
- This is a complete piece of work, with possible future improvements.
- The authors are careful and honest about evaluating both the strengths and weaknesses of their work.

**Clarity:**
- The submission is clearly written.
- It is well organized.

**Significance:**
- The result seems important from a computational efficiency perspective.
- Others (researchers or practitioners) are likely to use the ideas or build on them.
- It provides unique conclusions about existing approaches.

weaknesses:
**Originality:** 
- It is not exactly clear how this work differs from previous contributions or if the related work is adequately cited, since there is not substantial comparison.

**Quality:**
- A key point is that the submission has certain issues with technically sound, please see Questions. Similarly, some claims need more support.

**Clarity:**
- It occasionally fails to adequately inform the reader.

**Significance:**
- The difficultness of the task the submission addresses is hard to gauge, considering the rather simple approaches. The comparison with previous work is a bit lacking.
- Thus, it is also not easy to conclude if it advances the state of the art in a demonstrable way.

questions:
**Questions:**
- Line 239: in Theorem 1, $\alpha(\omega_k)$ seems to depend on $x$. How does this work?
- Line 247: what are the two passes exactly?
- Line 299: in Proposition 3, again, the existence of such $\alpha(\omega_k)$ needs to be explained. Is the equality with respect to a specific choice of $x$?

**Major Suggestions:**
- Line 231: define $e$ from the simplex domain.
- Line 329: in Corollary 1, $m$ cannot be arbitrarily large, which makes the probability upper-bounded, so this is not exactly a high probability bound.

**Minor Suggestions:**
- Line 34: need cites in this first paragraph.
- Line 46: also need more cites in the second paragraph.
- Line 91: $E$ is not empty but only includes the zero vector.
- Line 173: explain the connection of this central path to the robust optimization problem earlier on.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730942080882

thread_type:
official_review

<thread_object>
creator: reviewer_qiw4

<content>
summary:
This paper studies robust optimization with an uncertainty set, and proposes a more efficient way for computing Pareto efficient robust solutions based on proximal point methods.

strengths:
This paper proposes a novel way for solving robust optimization with an uncertainty set. The idea of applying Proximal point method for computing the Pareto efficient robust solutions seems to be a novel idea that has been explored before. 

Empirical results demonstrate the effectiveness of the proposed methods.

weaknesses:
A limited setting: The algorithms and theoretical guarantees given by the authors seem to only work on a toy example with linear functions and ellipsoidal uncertainty set. The objective function (e.g., in (3)) has a very particular form, and it seems that the analysis is difficult to be generalized to other cases.

One of the main advantage mentioned by the authors is that the total computational cost is reduced from NT to 2T. I wonder can the authors provide more discussion on this point? To be more specific, which papers are we talking here (Line 054)? 

I am not sure how to understand Theorem 1. The algorithm gives a series of x_k, which are PE in terms of  a series of special alpha (i.e., alpha(\omega_k)). What are these alpha(\omega_k)? how do we know this sequence is good enough? That is, how do we know these alpha covers enough possible alphas, and how does alpha(\omega_k) varies with \omega_k?

Line 239:  (alpha(\omega_k)) is such that the equality holds. How do we know such an alpha exist? How do we compute it?

I have some doubts on how to implement the proposed methods. Specifically: Line 234: when computing x_R, \xi\in\Xi(\infty). So how exactly should we compute x_R? What is \mathcal{U} in Line 253 for the linear problem with ellipsoidal uncertainty set?

questions:
See above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732673630698

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
Dear Reviewers: 

We would like to thank the reviewers for their constructive comments on our work. We have addressed all the comments in the `revised manuscript` (with major updates highlighted in blue), as a result, we believe it is now significantly improved. 

Before addressing each reviewer’s comments in detail. For your convenience, we summarized below a global response to the main comments and the major updates we made to address them.    

## **[Q1]: Position in the literature** 

We thank the reviewers for raising these concerns: i) How is this work positioned within the literature beyond robust optimization? ii) What is the unique contribution of this work to these different literatures? We address these questions positively below.   

**A1: Additional literature review and highlighting our contribution**: Given the nature of the problem, this work is positioned at the intersection of three main literatures, our work contributes to each literature in a substantial and novel way, opening up meaningful future research directions. 

**Continuous Optimization**: The field of continuous optimization predominantly focuses on the question of "how to get to the optimal solution fast" [1-6], not "what does the trajectory as a whole represent". This fundamentally deviates from the existing literature.  Consequently, our work has excited researchers in seminar presentations to the continuous optimization community. Another indirect evidence that we are filling an exciting research gap is that one of the key papers we cited [7] is not highly cited despite its interesting discovery about optimization paths. 

**Implicit Gradient Regularization in ML**: People have explained why and how the iterates of gradient methods, when minimizing a loss function alone, could sometimes provide implicit regularization. We show novel proof and new insights into this problem. Different from the literature [13-20], which tends to be descriptive and focused on unconstrained problems, we present a new direct, constructive proof for the **constrained** setting. This could prove to be an important step forward as constraints naturally appear in many high-stakes AI systems: such as safety-constrained reinforcement learning [26-27] for LLM safety alignment [28-30] and autonomous driving [31,32]. Anecdotally, we discovered the connection between our work and this literature after writing our paper. Naturally, the perspectives we take and the tools we invent are completely different from the ones already used in the literature, opening up a new way of generalizing results in implicit regularization, including but not limited to constrained settings. Our work demonstrates that implicit regularization can be studied in its dual perspective [21-25] i.e., via robust optimization. Specifically, our work demonstrates approximate proximal point methods (including gradient methods) when minimizing a loss function alone, generates iterates that are approximate robust solutions (as demonstrated in our adversarially robust deep learning experiment). Our result in Corollary 1 also shows that previous unconstrained results can be generalized to heavily constrained problems with polyhedron constraint sets. 

**Robust Optimization**: The authors have extensive experience publishing and reviewing in robust optimization, beyond our approach, we are not aware of any methods for generating multiple robust solutions other than the naive approach of "solving the problem multiple times" [8-12]. 

 

**Action Taken**: We made major revisions to `Section 1`, with better positioning of our work within multiple literatures, and highlighted our contributions to each literature. 

We want to thank the reviewer again for raising this concern, we believe the work is now well positioned in the literature with clear contributions to the state-of-the-art.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732673781025

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response (Cont'd)

comment:
## **[Q2]: Theoretical Guarantee is on linear objective, simplex constraint set and ellipsoidal uncertainty set. Questions for generalizability.** 

**A2: Generalizability**: We thank the reviewers for bringing up these concerns: i) How generalizable is the theoretical guarantee for robust linear optimization with constraints? ii) How generalizable is the subsequent PPM-based algorithm for approximating multiple robust solutions?  

The problem of robust optimization with linear objective function (in x), polyhedral constraints (in x), and with general convex uncertainty sets (in u) is the central object of study in Robust Optimization [8,9].  Many problems can be formulated exactly as (robust) linear optimization with constraints (e.g., risk-measure minimization [34], robust MDP [35,36] and mechanism design [37]). Linear optimization with constraints poses additional theoretical complexity compared with unconstrained convex optimization problems, due to the combinatorial nature of its polyhedron constraint set (e.g., the simplex algorithm exploits the combinatorial nature of LPs, it is empirically among the most efficient algorithms for solving LPs despite its exponential worst-case complexity, it has been a challenging question explaining its empirical performance).  

Our theoretical results (Corollary 1 and Theorem 1) consider robust linear optimization problems with general polyhedron feasible region and ellipsoidal uncertainty set. Building upon the theoretical results, our result generalizes to general convex uncertainty sets and more general objective functions. Specifically, 

-Our analysis reveals a new insight: there is a correspondence between the shape of the uncertainty set (ellipsoidal uncertainty set) and the distance-generating function in PPM (Mahalanobis distance), this correspondence exists in general and poses a new research direction, and we are actively investigating the co-design of uncertainty set and the distance-generating function building upon this paper. 

-In the adversarially robust deep learning experiment, we show empirically, our method generalized to nonconvex-nonconcave objective functions (our method is 60 times faster than the brute-force method in generating each robust model `[Table 1]`, with comparable model performance `[Figure 2]`).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732673844077

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response (Cont'd)

comment:
## **[Q3]: Computation cost** 

**A3**: We thank the reviewers for raising this important point. We provide a more detailed discussion of the computation cost of our method v.s. the brute-force method. 

First, as discussed in line 260 of the original manuscript, and as correctly pointed out by the review team, in general, an exact PPM update is no easier to solve than the corresponding robust optimization solution. Hence, in practice, we need to compute cheap approximate PPM updates (e.g., gradient methods) that generate approximate robust solutions, trading-off between computation cost v.s. robust solution quality. The major updates expanding on this point are: 

The more precise computation cost of algorithm 1 is: $ T_\mathrm{R} + (N-1)T_{\mathrm{\widetilde{PPM}}}$, where $T_\mathrm{R}$ is the cost of solving the robust optimization problem, $T_{\mathrm{\widetilde{PPM}}}$ is the cost of a single (approximate) PPM update.  

 

The computational cost reduction can be enjoyed under the condition that objective function is nonlinear and (sub)differentiable, for which we can use first-order approximate PPM that is cheaper than solving the robust optimization problem. 

 

The fundamental trade-off in our approach is between computation cost v.s. robust solution quality. Our approach provides a practical lever to adjust this trade-off by adjusting the choice of the approximate PPM. In short, better approximate PPM leads to better robust solution quality but at a higher cost. Cheap first-order methods such as gradient descent, mirror descent and extra-gradient Method can all be considered as approximate PPM with only the first-order information [21].  

 

Such a trade-off is observed empirically in our adversarially robust deep learning experiments. As shown in Figure 2, we obtain better-performing approximate robust models when we use better approximates of PPM for our method. In addition, we show this trade-off is mild in adversarially robust deep learning, our method with the best (highest cost) approximate PPM (full gradient descent) is **60 times faster** than traditional adversarial training for generating robust models **without sacrificing too much model performance**. As shown in Table 1, our method with the Extra-gradient method as approximate PPM takes **15 seconds** to generate one adversarial robust model v.s. traditional adversarial robust training that takes **15 mins** per adversarial robust model. As shown in Figure 2, the performances of our method against traditional adversarial robust training are comparable. 

 

**Action Taken**: Thanks to the reviewers’ comments, we made major revisions to the computation cost of our approach throughout `Sections 1 and 4`, introducing more precisely the computation cost of algorithm 1 and highlighting the fundamental trade-off between the computation cost v.s. robust solution quality and the lever for adjusting this trade-off via the choice of the approximate PPM.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732673900966

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response (Cont'd)

comment:
## **[Q4]: How to control the granularity of the radius of PPM-generated robust solutions? How comprehensive is the robust solutions generated by the PPM procedure?**  

  

**A4**: We thank the reviewers for bringing up these questions. We agree these are important points for the deployment of our method. The main update is a new closed-form solution to the robust solution radius $\alpha_k(\omega_k)$ for Theorem 1. We discuss the potential approach for controlling the granularity of radius $alpha$.  

  

To show the precise relationship between the PPM iterates and their corresponding robust solution radius. We provide in `Appendix E`, a closed-form solution of $\alpha_{k}$ as $\alpha(\omega_{k},x_{k}) = 2 \omega_{k} \Vert \Sigma^{1/2} x_{k} \Vert_{2}$, where $\omega_{k}$ is defined by the learning rate sequence, and $x_{k}$ is the current PPM iterate. The practical implication is: given we have computed the current PPM iterate $x_k$, we know $x_k$ is a robust solution with radius $\alpha_k$ which we can calculate in closed-form as a function of $\omega_k$ and $x_k$.  

 

We are actively working on methods for controlling the robust solution radius sequence $\{\alpha_k\}$ for our next paper. One approach is by controlling the approximate PPM step size, with a smaller step size leading to finer $\alpha_k$ granularity. In practice, we can take initial large approximate PPM steps, and take finer approximate PPM steps once we enter a neighborhood of robust solutions with good efficiency-robustness trade-off for finer robust solution granularity.   

  

**Action taken**: We give a new closed-formed solution to the robust solution radius $\alpha_k(\omega_k)$ for Theorem 1, in `appendix E`. We thank the reviewers for this comment as it opens up an important new research direction we hope to build upon the current paper.
</content>
</thread_object>

</thread>


Metareview:
metareview:
A proximal point method based method is proposed to generate a series of Pareto efficient solutions with computational efficiency. However, the analysis is limited to a particular form of loss functions and is not obvious to the reviewers how to generalize to more general cases. Numerical results do not seem to be very convincing either.