Progressively Sampled Equality-Constrained Optimization
This addresses efficiency in large-scale optimization for applications like machine learning, though it appears incremental as it builds on existing progressive sampling methods.
The paper tackles the problem of solving nonlinear-equality-constrained optimization with constraints defined by expectations over large datasets by proposing an algorithm that progressively increases sample sizes, showing it achieves a better worst-case sample complexity bound than using a full sample set.
An algorithm is proposed, analyzed, and tested for solving continuous nonlinear-equality-constrained optimization problems where the constraints are defined by an expectation or an average over a large (finite) number of terms. The main idea of the algorithm is to solve a sequence of equality-constrained problems, each involving a finite sample of constraint-function terms, over which the sample set grows progressively. Under assumptions about the constraint functions and their first- and second-order derivatives that are reasonable in some real-world settings of interest, it is shown that -- with a sufficiently large initial sample -- solving a sequence of problems defined through progressive sampling yields a better worst-case sample complexity bound compared to solving a single problem with a full set of samples. The results of numerical experiments with a set of test problems demonstrate that the proposed approach can be effective in practice.