Accelerating ERM for data-driven algorithm design using output-sensitive techniques

We thank the reviewer for their time and insightful comments. Re experiments, we note that prior empirical work already suggests usefulness of output-sensitive guarantees on typical instances, which we elaborate below.

Experiments: Our work is motivated from prior empirical research (lines 91-104) which indicate that the output cell size on typical problems is empirically much smaller than the worst-case cell size. The missing component is the development of algorithms with theoretical runtime guarantees which are output-sensitive, as previously proposed algorithms scale with the worst-case cell size. We expect implementation of our (LP-based) algorithm to be relatively straightforward, and would like to remark that there are no reasonable baselines known as previous algorithms were intractable.

Beyond linear boundaries: We agree that algebraic boundaries would be the next direction to look at based on our work. One simple way to apply our algorithms to the polynomial boundary case is to use linearization by projecting into a higher dimension corresponding to the monomials (this would work if the polynomials have a small constant degree e.g. Thm 3.1, Lem 4.1 in [1] or Lemma 2 in [2]). A more direct extension which tries to compute cells induced by polynomial boundaries in an output-sensitive way is an interesting direction for future work.

AugmentedClarkson: Clarkson’s Algorithm computes the set of non-redundant hyperplanes in a linear system in an output-sensitive time complexity. Intuitively, our augmentation additionally keeps track of the neighboring cells corresponding to the non-redundant hyperplanes to facilitate the breadth-first search over the cell adjacency graph. This is important as directly applying Clarkson’s and searching for the nearest cell (in a fixed direction) across each bounding hyperplane can add to the runtime complexity.

References

[1] Balcan, Maria-Florina, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. "Structural analysis of branch-and-cut and the learnability of gomory mixed integer cuts." Advances in Neural Information Processing Systems 35 (2022): 33890-33903.

[2] Balcan, Maria-Florina, Travis Dick, and Manuel Lang. "Learning to Link." In International Conference on Learning Representations 2020.

We respectfully disagree with the reviewer that the main result is not strong. Since its inception (around 2016), the field of theoretical guarantees of data driven algorithm design has been focused on sample complexity results. The major direction that has been left open in this field is to also consider the computational efficiency of data-driven algorithms. Our paper is the first to consider this question at some level of generality. We note that one cannot hope for the same level of generality as for the sample complexity of data driven algorithm design since algorithmic consideration have always been much more problem specific even in the classic (non-data driven) scenarios, that is in classic learning theory: even in classic learning theory we have general sample complexity results for ERM, yet the computational complexity of ERM algorithms depend heavily on the class (and even for basic classes we still have major open questions).

Our work contains many subtle aspects, for example:

• We make a novel connection with computational geometry to give beyond worst-case improvements on runtime efficiency. It is a priori not clear which tool to use to advance the state-of-the-art here.
• The execution tree approach for linkage clustering needs several technical lemmas for establishing soundness of the approach (e.g. lemmas I.5 to I.8 in Appendix I).
• The execution DAG approach used in sequence alignment is a completely novel contribution of this paper, and is critical to achieve the desired output-sensitive runtime guarantee.

Applications of our framework (linear boundaries, constant parameters): We show several distinct applications in our work where the linear boundary and constant parameter size is relevant for the data-driven algorithm design problem: linkage clustering - both metric learning and distance function learning; sequence alignment; two-part tariff pricing (App F); item-pricing with anonymous prices (App F). The linear boundary setting appears more frequently than one might initially expect, see e.g. [1] for several applications. Moreover, by a simple linearization argument, our approach yields ERM implementations for polynomial boundaries with small degrees e.g. e.g. Thm 3.1, Lem 4.1 in [2] or Lemma 2 in [3]. Finally, we remark that we initiate a detailed study of computationally efficient implementation of ERM for data-driven algorithm design and tackle the natural first case where we already show significant improvement over previous runtimes (Table 1) provided output size is small.

the most part does not yield improved running times in the worst case, but a different notion of efficiency (output sensitivity) Output-sensitivity is a relevant notion for data-driven algorithm design. We summarize motivation from prior empirical work in lines 91-104, which indicates usefulness of output-sensitivity from a practical perspective. Note that the whole point of data-driven algorithm design is to provide beyond worst-case improvements in algorithm design [4], so it is not unusual to expect a beyond worst-case measure of efficiency (output-sensitivity and fixed parameter tractability).

It tends more to systematically organizing ideas that have appeared in the literature in one form or another and less to introducing new algorithmic insights or techniques We remark that using a computational geometry based technique in the context of learning theory is in itself remarkable and has hardly ever appeared in prior literature. Moreover, a direct application of Clarkson's algorithm itself is not always sufficient. Our “execution DAG” technique proposed for the sequence alignment problem is a novel algorithmic idea not from any previous literature, and is crucial for tracking the partition of the parameter space for each DP sub-problem. In this case the number of alternative alignments (and therefore the number of relevant hyperplanes $t_{LRS}$) for any fixed optimal alignment is exponential, so a direct application of Clarkson’s algorithm would still be exponential runtime.

References

[1] Balcan, Maria-Florina, Tuomas Sandholm, and Ellen Vitercik. "A general theory of sample complexity for multi-item profit maximization." In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 173-174. 2018.

[2] Balcan, Maria-Florina, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. "Structural analysis of branch-and-cut and the learnability of gomory mixed integer cuts." Advances in Neural Information Processing Systems 35 (2022): 33890-33903.

[3] Balcan, Maria-Florina, Travis Dick, and Manuel Lang. "Learning to Link." In International Conference on Learning Representations 2020.

[4] Maria-Florina Balcan. Data-Driven Algorithm Design. In Tim Roughgarden, editor, Beyond Worst Case Analysis of Algorithms. Cambridge University Press, 2020.

We thank the reviewer for their time and useful comments.

Generalizability to other data-driven algorithm design problems: Our approach is applicable to a fairly large number of problems, for example the various mechanism design problems in [1] are (d,t)-delineable which is a special case of Definition 1 (We include a couple examples in Appendix F). Our current approach is useful whenever the loss as a function of the algorithmic parameter on a fixed problem instance can be shown to have a piecewise structure with linear transition boundaries. The execution tree/DAG technique enables output-sensitive runtime complexity when the piecewise structure can be viewed as a refinement of pieces induced in successive algorithmic steps (e.g. see Figure 2), each refinement involving linear decision boundaries in the parameter space, and we expect this to be useful beyond the linkage clustering and sequence alignment problems considered. There is also potential for extending our work beyond linear transition boundaries e.g. to algebraic boundaries which would be relevant for several problems of interest in data-driven algorithm design.

[1] Balcan, Maria-Florina, Tuomas Sandholm, and Ellen Vitercik. "A general theory of sample complexity for multi-item profit maximization." In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 173-174. 2018.