- Rating
- 2
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2(+1)
Read review
Paper summary
This paper seeks approximate first- and second-order KKT points of nonconvex programs over a nonnegative polyhedron, ( full row rank), where may lack differentiability on the boundary. The baseline Interior-Point Trust-Region (IPTR) method of Haeser et al. (2019) minimizes the log-barrier potential via scaled steps (, , ), but faces two bottlenecks:
-
Computing the orthogonal projector onto requires forming and inverting at every iteration ( time per step across steps).
-
Escaping saddle points to reach an -KKT2 point in Haeser et al. (2019) requires exact Hessians ( cost).
This paper proposes to mitigate these bottlenecks with two mechanisms:
-
Lazy Oblique Projection (Algorithm 1): Maintain a lazy diagonal approximation using a binary-tree coordinate-tracking scheme (
SelectVector, Lee & Vempala, 2021) and replace with an approximate oblique projector that preserves exact linear feasibility while allowing low-rank updates to the projector when only a few coordinates of change. -
First-Order Negative-Curvature Escape (Algorithms 2 & 3): Whenever the first-order IPTR step fails to decrease by (certifying as an -KKT1 point), projected power iteration on with finite-difference gradients approximates products with the scaled Hessian . If a direction of curvature exists, a step of norm decreases by ; since this can happen at most times, exact projections are needed at most times while approximate projections handle the remaining steps.
Numerical experiments for all algorithms are presented on two 3-dimensional toy instances (). Additionally, synthetic nonconvex quartic problems with are presented for Algorithm 1.
Critical strengths
The oblique projector and its one-step perturbation analysis (Lemma 4, Proposition 4) are algebraically clean and preserve strict interior feasibility.
Some numerical experiments were presented to demonstrate the scalability of Algorithm 1 on moderately sized problem instances.
Critical weaknesses
First, the claimed amortized per-step runtime ( total) silently assumes fast matrix multiplication () to absorb an full-recomputation term (see equations (20)-(21) and line 1241), and hides (where typically scales as ) inside an constant (see equation (16) where it is absorbed into ); under practical matrix multiplication (), the amortized per-step cost is , not .
Second, I have issues with the scope of the numerical experiments. The main algorithms (Algorithm 2 & 3) are only evaluated empirically on a 3-variable toy problem (), several hyperparameters are unspecified (e.g., how were , , , , , , or the initial point chosen in practice?), and no other (non-interior-point) efficient algorithms are used as benchmarks (e.g., Augmented Lagrangian methods of Li & Xu, 2021; Kong et al., 2023; or level-constrained methods of Boob et al., 2025). Additionally, despite motivating Problem (1) with sparse regression, multiple kernel learning, and -constrained neural network training in Section 1, the experiments only test a synthetic quartic objective, which remains unconvincing of the general applicability of the proposed methods.
Questions for authors
- Practical vs. fast matrix multiplication ( vs. ): Can you clarify the exact time complexity of Algorithm 1 and Algorithm 3 as a function of without assuming , and explicitly include the dependence on (from ) in Proposition 3 and Theorems 1 & 3?
- Improving
Procedure 1and Proposition 5:- Can you tighten the lower bound on in Eq. (62) (e.g., by normalizing at each step of
Procedure 1and relating to the Rayleigh quotient) so that the finite-difference step size is polynomial in rather than ? - How does
Procedure 1return if is only guaranteed to exist by contradiction? Does the practical implementation simply return the final iterate ?
- Can you tighten the lower bound on in Eq. (62) (e.g., by normalizing at each step of
- Fixing Algorithm 3 after negative-curvature steps: In Algorithm 3, after Line 10 takes a negative-curvature step of size , should Line 12 be replaced by an explicit restart of
SelectVector(setting and recomputing )? - Large-scale evaluation of Algorithm 3 & practical : What values of , , and were actually used in the experiments of Section 5? Can you evaluate Algorithm 2 and Algorithm 3 on large-scale problems crafted so that first-order IPTR gets trapped at a saddle point (requiring negative-curvature escape at scale)?
- Minor corrections:
- Algorithm 1, Line 5 & Algorithm 3, Line 5: Forming the matrix explicitly costs . The pseudocode should state that is maintained and applied to via matrix-vector products.
- Algorithm 2, Line 8 & Algorithm 3, Line 10: Replace with , and handle the case (where dividing by is ) using with .
- Page 5, Lemma 1(i): "for all " "for all ".
- Page 19, line 992: .
7 comments
Response to Reviewer XiDV
2. W2/Q4: Additional experiments and practical parameters.
Additional saddle-point experiments. In Point 2 of our general response, we compare standard first- and second-order IPTR with Algorithms 1–3 on constrained quartic saddle-point problems at and . Algorithms 2 and 3 escape the saddles, while both first-order methods retain negative curvature. Relative to standard second-order IPTR, Algorithms 2 and 3 achieve speedups of and on the first instance, and and on the second, respectively.
The additional experiments in Point 2 use , , , finite-difference radius , and 64 inner negative-curvature iterations. Algorithm 2 uses , while Algorithms 1 and 3 use and .
Parameters for Figs. 1 and 2. Both instances in Fig. 1 use , , , and . Algorithm 2 uses , while Algorithms 1 and 3 use and .
For the original Fig. 2, we use and . We randomly generate the constraints and the spectrum of to obtain nonconvex quartic objectives. All three instances use and , with for Algorithm 1.
Comparison with non-interior-point methods. We compare Algorithm 1 with Li–Xu's HiAPeM [1], Kong et al.'s IPL(A2) [2], and Boob et al.'s LCPG [3] on a smoothed problem with :
\left �0� , \qquad \tau=10^{-3}.$$ Here $w_i$ are positive weights. The constraints are $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ and $\boldsymbol{x}\ge0$, comprising 1,250 constraints that each group of four variables sums to 4 and 2,750 additional linear measurements. All methods start from $\boldsymbol{x}_0=\boldsymbol{e}$. | $(n,m)$ | Method | Time (s) | Objective | KKT1 | KKT2 | | --- | --- | ---: | ---: | ---: | ---: | | $(4000,3000)$ | Algorithm 1 | 507.081227 | 24758.0815 | 0.050000 | 0.072161 | | | Algorithm 2 | 362.179003 | 24916.0354 | 0.050000 | 0.068003 | | | Algorithm 3 | 308.114073 | 24864.6484 | 0.050000 | 0.087486 | | | Li–Xu HiAPeM | 428.410529 | 25391.7915 | 0.007174 | 0.00004767 | | | Kong IPL(A2) | 1720.000689 | 25262.9636 | 0.049978 | 0.024810 | | | Boob LCPG | 2360.035584 | 25422.4349 | 0.049993 | 0.004071 | Algorithm 1 is $3.39\times$ and $4.65\times$ faster than IPL(A2) and LCPG, respectively, and attains the lowest objective value. Algorithms 2 and 3 are $1.40\times$ and $1.65\times$ faster than Algorithm 1, respectively, and both are faster than all three baselines. We use $\varepsilon=0.025$, $l\approx3.1494$, and $\beta=\delta\approx0.00480824$ for Algorithm 1. **Other methods and objective functions.** **Point 1 of our general response** reports larger-scale quartic and Cauchy-loss experiments, up to $(n,m)=(30000,25000)$. **Point 3** compares Algorithm 1 with standard IPTR using CG for projection, with a $5.64\times$ speedup. **Point 4** compares with Hom-PGD on Cauchy-loss problems, with speedups of $2.61\times$ and $5.83\times$. **Point 5** evaluates the nonconvex COOT objective for matching 1,000 MNIST and 1,000 USPS images, where Algorithm 1 is $1.53\times$ faster than standard first-order IPTR. **3. Q2: Finite-difference radius and the returned direction.** **A polynomial finite-difference radius.** We can choose a finite-difference radius polynomial in $\varepsilon$ while retaining the iteration budget in Proposition 5. Let $\mathcal V=\ker(\boldsymbol{A}\boldsymbol{X})$, $k=\dim\mathcal V$, and let $\boldsymbol{P}$ be the orthogonal projector onto $\mathcal V$. Define $$\boldsymbol{H}=\left.\boldsymbol{P}\boldsymbol{X}\nabla^2f(\boldsymbol{x})\boldsymbol{X}\boldsymbol{P}\right\|_{\mathcal V},\qquad \boldsymbol{B}=\boldsymbol{I}_{\mathcal V}-\boldsymbol{H}/l,\qquad s=\frac{\sqrt\varepsilon}{l},\qquad \alpha=\frac{\delta_0}{2\sqrt{k}}.$$ Let $0<\delta_0<1$. Under the premise $\lambda_{\min}(\boldsymbol{H})<-\sqrt\varepsilon$, Assumption 1 gives $\\\|\boldsymbol{H}\\\|\le l$, so $0<s\le1$ and $b_\*:=\\\|\boldsymbol{B}\\\|\ge1+s$. Fix $$\mathcal T= \left\lceil\frac{8l}{\sqrt\varepsilon} \log\\!\left(\frac{8l}{\delta_0}\sqrt{\frac{n}{\pi\varepsilon}}\right)\right\rceil, \qquad r=\min\left\\{\gamma,\frac12, \frac{\alpha\sqrt\varepsilon}{16\rho\mathcal T}\right\\}.$$ Initialize $\boldsymbol{y}_0$ as a uniformly random unit vector in $\mathcal V$. Each update may be normalized: the update map is positively homogeneous, so this preserves the direction sequence. We analyze the corresponding unnormalized iterates below.Response to Reviewer XiDV
The integral form of Taylor's theorem and Assumption 2 give
\\\|\Delta_t\\\|\le\eta\\\|\boldsymbol{y}_t\\\|,\qquad \eta=\frac{\rho r}{2l}.$$ Compare this sequence with the exact power iteration $\boldsymbol{z}_t=\boldsymbol{B}^t\boldsymbol{y}_0$. Since $\\\|\boldsymbol{y}_t\\\|\le(b_\*+\eta)^t$, expanding the error recurrence yields $$\begin{aligned} \\\|\boldsymbol{y}_t-\boldsymbol{z}_t\\\| &\le\eta\sum_{j=0}^{t-1}b_\*^{t-1-j}(b_\*+\eta)^j\\\\ &=(b_\*+\eta)^t-b_\*^t. \end{aligned}$$ Our choice of $r$ ensures $\eta\mathcal T\le\alpha s/32$. Thus, for every $t\le\mathcal T$, $$\frac{\\\|\boldsymbol{y}_t-\boldsymbol{z}_t\\\|}{b_\*^t} \le e^{\eta t/b_\*}-1 \le2\eta t \le\frac{\alpha s}{16}.$$ The error and the leading component of the exact power iteration have the same growth factor $b_\*^t$. Their relative error therefore depends on $r\mathcal T$, without an exponential dependence on $\mathcal T$. Apart from the fixed upper bounds $\gamma$ and $1/2$, the radius above has order $$\frac{\delta_0\varepsilon} {\rho l\sqrt{k}\log\\!\left(l\sqrt n/(\delta_0\sqrt\varepsilon)\right)}.$$ **Returning the final direction.** We can also prove that after $\mathcal T$ updates, Procedure 1 can directly return $\widehat{\boldsymbol{e}}=\boldsymbol{y}_{\mathcal T}/\\\|\boldsymbol{y}_{\mathcal T}\\\|$ with the guarantee in Proposition 5. To prove this, let $\boldsymbol{u}_1$ be a unit eigenvector of $\boldsymbol{H}$ associated with its minimum eigenvalue. The spherical small-ball bound gives $$\mathbb P\bigl(\|\boldsymbol{u}_1^\top \boldsymbol{y}_0\|<\alpha\bigr) \le2\alpha\sqrt{k}=\delta_0.$$ Condition on the complementary event. Then $\\\|\boldsymbol{z}_t\\\|\ge\alpha b_\*^t$, and the preceding error bound implies $$\\\|\boldsymbol{y}_t\\\|\ge\alpha b_\*^t(1-s/16)\>0.$$ Let $\mathcal S_{\perp'}$ denote the span of the eigenvectors of $\boldsymbol{H}$ with eigenvalues greater than $-\sqrt\varepsilon/2$. On this subspace, $\boldsymbol{B}$ has norm at most $1+s/2$, so $$\\\|\boldsymbol{z}_{\mathcal T,\perp'}\\\|\le(1+s/2)^{\mathcal T}.$$ For $0<s\le1$, $$\log\frac{1+s}{1+s/2}\ge\frac{s}{4}.$$ Moreover, $k\le n$ and $\delta_0s\le1$ imply that the prescribed budget satisfies $$\mathcal T\ge\frac4s\log\frac8{\alpha s}.$$ Consequently, $$\frac{\\\|\boldsymbol{z}_{\mathcal T,\perp'}\\\|}{b_\*^{\mathcal T}} \le\left(\frac{1+s/2}{1+s}\right)^{\mathcal T} \le\frac{\alpha s}{8}.$$ Combining this estimate with the error bound gives $$\frac{\\\|\boldsymbol{y}_{\mathcal T,\perp'}\\\|}{\\\|\boldsymbol{y}_{\mathcal T}\\\|} \le\frac{s/8+s/16}{1-s/16} \le\frac{s}{5} \le\frac{s}{4}.$$ The spectral decomposition therefore yields $$\begin{aligned} \widehat{\boldsymbol{e}}^\top \boldsymbol{X}\nabla^2f(\boldsymbol{x})\boldsymbol{X}\widehat{\boldsymbol{e}} &\le-\frac{\sqrt\varepsilon}{2} +\left(l+\frac{\sqrt\varepsilon}{2}\right) \frac{\varepsilon}{16l^2}\\\\ &\le-\frac{13\sqrt\varepsilon}{32} <-\frac{\sqrt\varepsilon}{4}. \end{aligned}$$ Thus, whenever $\lambda_{\min}(\boldsymbol{H})<-\sqrt\varepsilon$, the final direction satisfies the required negative-curvature bound with probability at least $1-\delta_0$. The iteration and asymptotic time bounds remain unchanged. **An optional stopping condition.** The procedure can also stop earlier using a gradient-based curvature estimate. For $\widehat{\boldsymbol{e}}_t=\boldsymbol{y}_t/\\\|\boldsymbol{y}_t\\\|$, define $$\widehat\lambda_t= \frac{\widehat{\boldsymbol{e}}_t^\top \boldsymbol{X} \left �0� }{r}.$$ Assumption 2 gives $$\left\|\widehat\lambda_t- \widehat{\boldsymbol{e}}_t^\top \boldsymbol{X}\nabla^2f(\boldsymbol{x})\boldsymbol{X}\widehat{\boldsymbol{e}}_t\right\| \le\frac{\rho r}{2}.$$ Hence, the condition $$\widehat\lambda_t+\frac{\rho r}{2} \le-\frac{\sqrt\varepsilon}{4}$$ certifies that $\widehat{\boldsymbol{e}}_t$ can be returned. This check uses the gradient difference already computed for the update. We will include the radius choice, final-iterate proof, and stopping condition in the rebuttal version.
Response to Reviewer XiDV
Thank you for your careful review and constructive suggestions. We address your concerns below, referring to the additional experiments in our general response.
1. W1/Q1: Removing the dependence on Lϕ and clarifying the complexity.
The dependence on Lϕ can be removed by adding a simple diagonal scaling. Define Mt=Xt−1Xt2Xt−1 and replace the direction in Algorithms 1 and 3 by
{\\\|\boldsymbol{R}_t\boldsymbol{M}_t\boldsymbol{X}_t\nabla\phi(\boldsymbol{x}_t)\\\|}, \qquad \beta=\frac{\varepsilon}{l+2\varepsilon+2}, \qquad \delta=\frac{\beta}{4}.$$ We set $\widetilde{\boldsymbol{d}}_t=0$ when the numerator vanishes. Since $e^{-\delta}\boldsymbol{x}_t\le\overline{\boldsymbol{x}}_t\le e^\delta \boldsymbol{x}_t$, we have $e^{-2\delta}\boldsymbol{I}\preceq \boldsymbol{M}_t\preceq e^{2\delta}\boldsymbol{I}$. This scaling adds only $O(n)$ work per iteration. **Feasibility, KKT residual, and descent.** Fix an iteration and suppress the subscript $t$. Set $$\boldsymbol{B}=\boldsymbol{A}\boldsymbol{X},\qquad \boldsymbol{g}=\boldsymbol{X}\nabla\phi(\boldsymbol{x}),\qquad \boldsymbol{K}=\boldsymbol{B}\boldsymbol{M}\boldsymbol{B}^\top=\boldsymbol{A}\overline{\boldsymbol{X}}^2\boldsymbol{A}^\top,$$ and define $$\boldsymbol{v}=-\boldsymbol{K}^{-1}\boldsymbol{B}\boldsymbol{M}\boldsymbol{g},\qquad \boldsymbol{h}=\boldsymbol{g}+\boldsymbol{B}^\top \boldsymbol{v},\qquad \boldsymbol{u}=\boldsymbol{R}\boldsymbol{M}\boldsymbol{g}=\boldsymbol{M}\boldsymbol{h}.$$ The matrix $\boldsymbol{K}$ is positive definite because $\boldsymbol{A}$ has full row rank and $\overline{\boldsymbol{x}}\>0$. Since $\boldsymbol{R}=\boldsymbol{I}-\boldsymbol{M}\boldsymbol{B}^\top \boldsymbol{K}^{-1}\boldsymbol{B}$, $$\boldsymbol{B}\boldsymbol{u}=\boldsymbol{B}\boldsymbol{M}\boldsymbol{g}-\boldsymbol{B}\boldsymbol{M}\boldsymbol{B}^\top \boldsymbol{K}^{-1}\boldsymbol{B}\boldsymbol{M}\boldsymbol{g}=0.$$ Thus the direction lies in $\ker(\boldsymbol{A}\boldsymbol{X})$. Moreover, $$\boldsymbol{X}(\nabla f(\boldsymbol{x})+\boldsymbol{A}^\top \boldsymbol{v})=\varepsilon \boldsymbol{e}+\boldsymbol{h}.$$ If $\\\|\boldsymbol{h}\\\|<\varepsilon$, the right-hand side lies coordinatewise between $0$ and $2\varepsilon$, so $\boldsymbol{x}$ is a $2\varepsilon$-KKT point. Otherwise, $\boldsymbol{u}\ne0$ and $$\boldsymbol{g}^\top \boldsymbol{u}=(\boldsymbol{h}-\boldsymbol{B}^\top \boldsymbol{v})^\top \boldsymbol{u}=\boldsymbol{h}^\top \boldsymbol{M}\boldsymbol{h}, \qquad \frac{\boldsymbol{g}^\top \boldsymbol{u}}{\\\|\boldsymbol{u}\\\|} \ge e^{-4\delta}\\\|\boldsymbol{h}\\\| \ge e^{-4\delta}\varepsilon.$$ For $0<\varepsilon\le\min\\{\gamma,1/2\\}$, the step $\widetilde{\boldsymbol{d}}=-\beta \boldsymbol{u}/\\\|\boldsymbol{u}\\\|$ has norm $\beta\le\min\\{\gamma,1/2\\}$, so $\boldsymbol{x}^+=\boldsymbol{X}(\boldsymbol{e}+\widetilde{\boldsymbol{d}})\>0$ and $\boldsymbol{A}\boldsymbol{x}^+=\boldsymbol{b}$. Assumption 1 and $-\log(1+s)\le-s+s^2$ for $\|s\|\le1/2$ give $$\begin{aligned} \phi(\boldsymbol{x}^+)-\phi(\boldsymbol{x}) &\le \boldsymbol{g}^\top\widetilde{\boldsymbol{d}}+\left(\frac l2+\varepsilon\right)\beta^2\\\\ &\le-\beta\varepsilon e^{-4\delta} +\left(\frac l2+\varepsilon\right)\beta^2\\\\ &\le-\beta\varepsilon+\left(\frac l2+2\varepsilon\right)\beta^2\\\\ &=-\frac{\varepsilon^2}{2l+4\varepsilon+4} -(1-\varepsilon)\beta^2\\\\ &\le-\frac{\varepsilon^2}{2l+4\varepsilon+4}. \end{aligned}$$ Here the third inequality uses $4\delta=\beta$ and $e^{-\beta}\ge1-\beta$. This proves the sufficient-decrease guarantee in Proposition 4 without Assumption 3, which can therefore be removed from Theorems 1 and 3. **Complexity for general $\omega$.** With $\delta=\beta/4$, the constant $C$ in Eq. (16) is independent of $L_\phi$. Retaining the $\omega$-dependent terms in the proof of Proposition 3 gives the following total bounds for $\omega\in[2,3]$. | Method | Total time complexity | | --- | --- | | Algorithm 1 | $\widetilde O\\!\left(nm^{\omega-1}+\dfrac{nm+nm^{\omega-3/2}}{\varepsilon^2}\right)$ | | Algorithm 3 | $\widetilde O\\!\left(\dfrac{nm^{\omega-1}}{\varepsilon^{3/2}}+\dfrac{nm+nm^{\omega-3/2}}{\varepsilon^2}\right)$ | The hidden constants depend on $l$, $\rho$, $f(\boldsymbol{x}_0)-f(\boldsymbol{x}^*)$, and $C_0$, but not on $L_\phi$. The $\widetilde O$ notation suppresses logarithmic factors in $n$, $1/\varepsilon$, and the inverse failure probability.