- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Decision-Focused Clustering, which groups instances based on the regret incurred by sharing decisions in linear downstream optimization problems. The authors establish the problem's NP-hardness and develop an alternating optimization algorithm that updates cluster representatives and instance assignments, with theoretical convergence guarantees.
Critical strengths
-
The paper groups instances according to the quality of their shared downstream decisions, directly addressing the mismatch between geometric similarity and decision quality.
-
The alternating procedure admits an optimal mean-based representative update for each fixed cluster, while its assignment step avoids computing individualized optimal decisions for every instance.
-
The paper establishes NP-hardness and proves convergence of the algorithm’s objective values.
Critical weaknesses
- The algorithmic contribution requires a substantially more detailed comparison with prior work.
- Theorems 3 and 4 assume exact global empirical minimization, whereas Algorithm 1 only guarantees monotonic objective descent.
- The experiments compare only with -means. Please include decision-aware baselines, such as greedy decision selection and local search, and report runtime and optimization-oracle calls. The shortest-path experiment has only six feasible paths, making exact optimality-gap evaluation straightforward; larger instances would better demonstrate the method’s effectiveness.
Questions for authors
See weaknesses.
- How does DFC compare with closely related methods, particularly SPO Trees (Elmachtoub et al., 2020) and Bregman-based clustering (Banerjee et al., 2005; Iyer and Bilmes, 2012), in terms of algorithm design, theoretical guarantees, and empirical performance?
4 comments
Author Response (Part 2/3)
2. Exact optimality gaps and decision-aware comparisons
Figure 4 and Appendix D.1 now compare DFC with exact enumeration over the six feasible paths. At , the exact training optima are 0.22668, 0.06704, and 0.01912, whereas mean DFC training regrets are 0.30375, 0.13174, and 0.04402. The exact optimum is reached in 25/35, 16/35, and 21/35 runs, respectively. These results quantify remaining gaps rather than equate monotonicity with optimality.
For the original six-path problem, we enumerate every subset of at most feasible paths and minimize training regret. Appendix D.1, Table 4 reports:
| Exact training optimum | Mean DFC training regret | Optimal runs | |
|---|---|---|---|
| 3 | 0.22668 | 0.30375 | 25/35 |
| 4 | 0.06704 | 0.13174 | 16/35 |
| 5 | 0.01912 | 0.04402 | 21/35 |
| 6 | 0 | 0.00055 | 34/35 |
| 7–10 | 0 | 0 | 35/35 for each |
DFC frequently attains the exact optimum, but the gaps at smaller budgets show that objective descent does not ensure global optimality. The test reference in Figure 4 evaluates the training-optimal shared paths unchanged. On the additional , , and networks in Appendix D.3 and Figure 8, it reaches the exact training optimum in 73/80 runs. Thus, the exact-hit result does not extend to every tested instance.
We added Ward hierarchical clustering throughout the three applications, portfolio local and swap-based local searches in Appendix E.3, and courier search in Appendix G.1. At 2,000 portfolio training observations, the best searches improve training regret by 0–0.79%; the global gap remains unknown. For courier at , search reduces training regret from 0.038200 to 0.029186 and test regret from 0.045837 to 0.038257 minutes per order, using 5.647 additional seconds and 3,000 additional solves.
3. Exact empirical minimization versus the implemented algorithm
We agree that Theorems 4–5 considers exact global empirical minimization. Section 3 now explicitly distinguishes monotonic empirical objective values from exact empirical minimization (Line 318). Theorem 4 applies the finite-decision SAA argument; Theorem 5 bounds statistical estimation error for exact empirical minimizers.
For an algorithmic output , define
Under Theorem 5's assumptions, its proof in Appendix B gives, with probability at least ,
\leq BD\sqrt{\frac{2\{Kd\log(1+2N)+\log(2/\delta)\}}{N}} +\frac{4BD}{N}+\varepsilon_N.$$ Here $B$ bounds the cost norm and $D$ is the feasible-region diameter. This separates statistical error from empirical optimization error. The descent guarantee does not bound $\varepsilon_N$. Section 5.2 also states that the Gaussian-based portfolio experiment and its numerical reference do not directly verify the theorem's bounded-cost and exact-minimization assumptions. **4. Greedy selection and larger networks** The additional experiments accompanying this response compare greedy shared-decision selection with DFC and DFC followed by path replacement on $5\times5$ and $8\times8$ grids. Each setting uses 500 training and 500 test observations, $K=3$, and three matched data repetitions. Under IID costs, test regret is: | Method | $5\times5$ grid | $8\times8$ grid | | --- | ---: | ---: | | $k$-means | 9.21291 ± 0.23864 | 22.63478 ± 0.77896 | | DFC | 9.21291 ± 0.23864 | 22.63478 ± 0.77896 | | Greedy selection | 8.92334 ± 0.49668 | 22.43977 ± 0.26452 | | DFC + path replacement local search | 8.82063 ± 0.30589 | 22.00293 ± 0.51993 | Entries are mean ± sample standard deviation. Greedy selection improves on base DFC in these settings, while DFC followed by path replacement has the lowest reported mean. The small number of repetitions does not establish statistical superiority. Under the additional corridor-mixture costs, all four methods achieve essentially zero regret, so those cases do not distinguish their quality. For the IID cases, algorithm time changes from 0.0199 to 0.0208 seconds on $5\times5$ and from 0.0236 to 0.0610 seconds on $8\times8$ when adding path replacement. These times include the starting DFC fit but exclude shared precomputation. Cached candidates avoid additional downstream solves during replacement, but candidate preparation and search are not cost-free.Author Response (Part 3/3)
5. Runtime and optimization-oracle calls
Appendix I reports both total and algorithm-stage costs. Table 11 includes preprocessing and training: DFC takes 0.59461 seconds for shortest path (), 8.27277 seconds for portfolio (), and 37.1364 seconds for courier (), saving 15.7%, 20.5%, and 14.7% relative to matched individualized optimization. The corresponding solve counts are 3,217.06 versus 4,000, 2,186.5 versus 3,000, and 3,346 versus 4,110.
| Setting: training/test size; | Individualized time (s) | DFC time (s) | Individualized solves | DFC solves | Time saved |
|---|---|---|---|---|---|
| Shortest path: 3200/800; 3 | 0.70567 | 0.59461 | 4,000 | 3,217.06 | 15.7% |
| Portfolio: 2000/1000; 5 | 10.40033 | 8.27277 | 3,000 | 2,186.5 | 20.5% |
| Courier, split-first: 3288/822; 10 | 43.5219 | 37.1364 | 4,110 | 3,346 | 14.7% |
The measured DFC implementation uses solves, including cached individualized training optima. This cache is unnecessary for assignment but is included in the reported implementation costs. Further assignment to learned shared decisions requires no downstream solves.
Tables 12–17 extend the evaluation across decision budgets and sample sizes, retaining cases where DFC is slower and runs reach the iteration cap. For example, the separate 5000/1000 portfolio campaign is 22.7% slower than individualized optimization at . The revised discussion therefore treats runtime as a tradeoff with decision quality and training effort, rather than a uniform improvement over individualized optimization or geometric clustering.
We thank the reviewer again for the constructive feedback and valuable suggestions. We believe that the revised manuscript and additional experiments provide a more comprehensive comparison with existing methods, clarify the scope of our theoretical guarantees, and address the concerns about empirical optimality and computational efficiency. We hope these revisions and results satisfactorily resolve the reviewer's questions and further clarify the contributions of DFC.
Thanks to the authors for taking the time to respond and revise the manuscript. There appears to be a gap between the theoretical guarantees and the algorithm (and the experiments). Some aspects of the presentation also need improvement—for example, the explanatory text in Figure 8. After considering the rebuttal and revisions, I will maintain my score.
Author Response (Part 1/3)
We thank the reviewer for the suggestions on related methods, optimization guarantees, and empirical evaluation. We have revised the theoretical positioning and expanded the comparisons. The response below distinguishes results already included in the manuscript from additional larger-grid results reported here.
0. New Results regarding the linear feasible region
We have added a new result, Theorem 2, in the revised manuscript to exploit the clustering structure induced by the parameter space. Theorem 2 establishes conditions under which instances can be pre-grouped based on their locations in the parameter space, potentially reducing the computational complexity of the clustering algorithm. Note that the instances within the same cone may not be grouped into one cluster. Theorem 2 provides a sufficient condition for this pre-grouping method. We provide the detailed analysis in the newly added Appendix A. This result further distinguishes our work from existing approaches, particularly in the setting of linear optimization.
1. Comparison with SPO trees and Bregman-based clustering
Section 1.1 now discusses SPO trees, classical and generalized Bregman clustering, DMOC, and objective-uncertainty K-adaptability. Table 1 compares their modeled scope, algorithms, statistical guarantees, and use of cost-vector representatives.
†: Finite-case consequence of SAA consistency. DFC's exact identification requires a bounded polyhedron, a vertex-selecting oracle, and exact empirical minimization. SAA's risk bounds concern finite feasible regions.
‡: Algorithmic representation only; DMOC and K-adaptability admit equivalent mean-cost updates for linear objectives.
§: For bounded polyhedra with a vertex-selecting oracle (Theorem 2).
SPO trees. Both methods use the mean cost within a group to obtain a shared decision. SPO trees assign observations through feature-based tree splits when the costs being predicted are unknown. DFC observes the cost vector used for assignment and directly chooses the cheapest shared decision. Thus, the differences concern the available information and the restrictions on assignments, rather than the within-group averaging principle. The current experiments do not include a standalone SPO-tree benchmark; we do not claim empirical superiority over SPO trees.
Generalized Bregman clustering. We now cite both Banerjee et al. (2005) and Iyer and Bilmes (2012). DFC fits within the generalized Bregman framework. To make the relationship explicit, define
F(c)=−minw∈Sc⊤w.
Then −w∗(μ)∈∂F(μ) and
=F(c)-F(\mu)-\langle-w^*(\mu),c-\mu\rangle.$$ The generator is determined by the downstream optimization problem and may be nonsmooth. Nonsmoothness alone is not a distinction from generalized Bregman clustering. With this generator, selected subgradients, and matched update conventions, the corresponding generalized Bregman implementation reproduces DFC's objective and core updates. We therefore emphasize the downstream interpretation and explicit population-risk analysis, rather than claim a new alternating mechanism. The revised discussion similarly acknowledges that the shared-decision objective and core updates overlap with $K$-adaptability and linear DMOC.