acceptodds
Under review as a conference paper at ICLR 2027

Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization

Abstract

Computing approximate Karush-Kuhn-Tucker (KKT) points for constrained nonconvex programs is a fundamental problem in mathematical programming. Interior-point trust-region (IPTR) methods are particularly attractive for such problems because they maintain strictly feasible iterates throughout the iterative process and converge to a first-order and second-order KKT solution. Their scalability, however, is limited by the repeated computation of trust-region search directions. In this paper, we propose an approximate first-order IPTR framework that addresses this bottleneck by replacing exact trust-region subproblem solves with an approximate projector maintained through low-rank updates. The resulting method preserves feasibility and the global convergence guarantees of standard IPTR schemes while substantially reducing the per-iteration cost. We further extend the framework to obtain approximate second-order KKT points using only first-order information by integrating a gradient-based negative-curvature routine, thus avoiding explicit Hessian computations. We conduct numerical experiments to demonstrate the scalability of our approximate first-order IPTR framework in large-scale settings, where it achieves up to a speedup over the existing first-order IPTR algorithm.

Primary area:
optimization
Keywords:
nonconvex optimization, constrained optimization, interior-point methods, first-order methods, trust-region methods, Karush–Kuhn–Tucker conditions

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_XiDVOpenReview ↗
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, min⁡xf(x) s.t. Ax=b,x≥0\min_{x} f(x) \text{ s.t. } Ax = b, x \ge 0 (A∈Rm×nA \in \mathbb{R}^{m \times n} full row rank), where ff may lack differentiability on the boundary. The baseline Interior-Point Trust-Region (IPTR) method of Haeser et al. (2019) minimizes the log-barrier potential ϕ(x)=f(x)−ε∑iln⁡xi\phi(x) = f(x) - \varepsilon \sum_i \ln x_i via scaled steps xt+1=Xt(e+dt)x_{t+1} = X_t(e + d_t) (Xt=diag⁡(xt)X_t = \operatorname{diag}(x_t), dt∈ker⁡(AXt)d_t \in \ker(A X_t), ∥dt∥2≤β\|d_t\|_2 \le \beta), but faces two bottlenecks:

  1. Computing the orthogonal projector Pt=I−XtA⊤(AXt2A⊤)−1AXtP_t = I - X_t A^\top (A X_t^2 A^\top)^{-1} A X_t onto ker⁡(AXt)\ker(A X_t) requires forming and inverting AXt2A⊤∈Rm×mA X_t^2 A^\top \in \mathbb{R}^{m \times m} at every iteration (O(nmω−1)\mathcal{O}(n m^{\omega-1}) time per step across O(ε−2)\mathcal{O}(\varepsilon^{-2}) steps).

  2. Escaping saddle points to reach an (O(ε),ε)(\mathcal{O}(\varepsilon), \sqrt{\varepsilon})-KKT2 point in Haeser et al. (2019) requires exact Hessians ∇2f(xt)\nabla^2 f(x_t) (Ω(n2)\Omega(n^2) cost).

This paper proposes to mitigate these bottlenecks with two mechanisms:

  1. Lazy Oblique Projection (Algorithm 1): Maintain a lazy diagonal approximation {‾X}t≈Xt\overline\{X\}_t \approx X_t using a binary-tree coordinate-tracking scheme (SelectVector, Lee & Vempala, 2021) and replace PtP_t with an approximate oblique projector Rt=I−Xt{−1}{‾X}t2A⊤(A{‾X}t2A⊤){−1}AXtR_t = I - X_t^\{-1\} \overline\{X\}_t^2 A^\top (A \overline\{X\}_t^2 A^\top)^\{-1\} A X_t that preserves exact linear feasibility while allowing low-rank updates to the projector when only a few coordinates of {‾X}t\overline\{X\}_t change.

  2. First-Order Negative-Curvature Escape (Algorithms 2 & 3): Whenever the first-order IPTR step fails to decrease ϕ\phi by Ω(ε2)\Omega(\varepsilon^2) (certifying xtx_t as an O(ε)\mathcal{O}(\varepsilon)-KKT1 point), projected power iteration on ker⁡(AXt)\ker(A X_t) with finite-difference gradients approximates products with the scaled Hessian Xt∇2f(xt)XtX_t \nabla^2 f(x_t) X_t. If a direction of curvature ≲−ε\lesssim -\sqrt{\varepsilon} exists, a step of norm Θ(ε)\Theta(\sqrt{\varepsilon}) decreases ϕ\phi by Ω(ε1.5)\Omega(\varepsilon^{1.5}); since this can happen at most O(ε−1.5)\mathcal{O}(\varepsilon^{-1.5}) times, exact projections are needed at most O(ε−1.5)\mathcal{O}(\varepsilon^{-1.5}) times while approximate projections handle the remaining O(ε−2)\mathcal{O}(\varepsilon^{-2}) steps.

Numerical experiments for all algorithms are presented on two 3-dimensional toy instances (n=3,m=1n=3, m=1). Additionally, synthetic nonconvex quartic problems with (n,m)∈{(1000,500),(3000,2000),(5000,4000)}(n,m) \in \{(1000,500), (3000,2000), (5000,4000)\} are presented for Algorithm 1.

Critical strengths

The oblique projector RtR_t 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 O~(mn)\widetilde{\mathcal{O}}(mn) amortized per-step runtime (O~(nmω−1+nm/ε2)\widetilde{\mathcal{O}}(n m^{\omega-1} + nm/\varepsilon^2) total) silently assumes fast matrix multiplication (ω<2.5\omega < 2.5) to absorb an O~(nmω−1.5/ε2)\widetilde{\mathcal{O}}(n m^{\omega-1.5}/\varepsilon^2) full-recomputation term (see equations (20)-(21) and line 1241), and hides (β/δ)2=Θ(Lϕ2)(\beta/\delta)^2 = \Theta(L_\phi^2) (where Lϕ≥∥X∇f(x)−εe∥2L_\phi \ge \|X\nabla f(x) - \varepsilon e\|_2 typically scales as Ω(n)\Omega(\sqrt{n})) inside an O(1)\mathcal{O}(1) constant (see equation (16) where it is absorbed into CC); under practical matrix multiplication (ω=3\omega = 3), the amortized per-step cost is O~(nm1.5)\widetilde{\mathcal{O}}(n m^{1.5}), not O~(mn)\widetilde{\mathcal{O}}(mn).

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 (n=3,m=1n=3, m=1), several hyperparameters are unspecified (e.g., how were β\beta, δ\delta, rr, σ\sigma, QQ, cc, or the initial point x0x_0 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 ℓ∞\ell_\infty-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
  1. Practical vs. fast matrix multiplication (ω=3\omega = 3 vs. ω<2.5\omega < 2.5): Can you clarify the exact time complexity of Algorithm 1 and Algorithm 3 as a function of ω∈[2,3]\omega \in [2, 3] without assuming ω<2.5\omega < 2.5, and explicitly include the dependence on LϕL_\phi (from (β/δ)2=Θ(Lϕ2)(\beta/\delta)^2 = \Theta(L_\phi^2)) in Proposition 3 and Theorems 1 & 3?
  2. Improving Procedure 1 and Proposition 5:
    • Can you tighten the lower bound on ∥yt+1∥/∥yt∥\|y_{t+1}\|/\|y_t\| in Eq. (62) (e.g., by normalizing yty_t at each step of Procedure 1 and relating ∥yt+1∥\|y_{t+1}\| to the Rayleigh quotient) so that the finite-difference step size rr is polynomial in ε\varepsilon rather than 2−Θ~(l/ε)2^{-\widetilde{\Theta}(l/\sqrt{\varepsilon})}?
    • How does Procedure 1 return e^=yt0/∥yt0∥\hat{e} = y_{t_0}/\|y_{t_0}\| if t0<Tt_0 < \mathcal{T} is only guaranteed to exist by contradiction? Does the practical implementation simply return the final iterate yT/∥yT∥y_{\mathcal{T}}/\|y_{\mathcal{T}}\|?
  3. Fixing Algorithm 3 after negative-curvature steps: In Algorithm 3, after Line 10 takes a negative-curvature step of size Θ(ε)\Theta(\sqrt{\varepsilon}), should Line 12 be replaced by an explicit restart of SelectVector (setting {‾x}{t+1}←x{t+1}\overline\{x\}_\{t+1\} \leftarrow x_\{t+1\} and recomputing (A{‾X}{t+1}2A⊤){−1}(A \overline\{X\}_\{t+1\}^2 A^\top)^\{-1\})?
  4. Large-scale evaluation of Algorithm 3 & practical δ\delta: What values of δ\delta, β\beta, and rr 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)?
  5. Minor corrections:
    • Algorithm 1, Line 5 & Algorithm 3, Line 5: Forming the n×nn \times n matrix RtR_t explicitly costs Ω(n2m)\Omega(n^2 m). The pseudocode should state that Kt−1=(AX‾t2A⊤)−1K_t^{-1} = (A \overline{X}_t^2 A^\top)^{-1} is maintained and applied to Xt∇ϕ(xt)X_t \nabla \phi(x_t) via matrix-vector products.
    • Algorithm 2, Line 8 & Algorithm 3, Line 10: Replace ∇ϕ(x)\nabla \phi(x) with ∇ϕ(xt)\nabla \phi(x_t), and handle the case ⟨∇ϕ(xt),Xte^⟩=0\langle \nabla \phi(x_t), X_t \hat{e} \rangle = 0 (where dividing by ∣⟨∇ϕ(xt),Xte^⟩∣|\langle \nabla \phi(x_t), X_t \hat{e} \rangle| is 0/00/0) using sgn⁡(⋅)\operatorname{sgn}(\cdot) with sgn⁡(0)=1\operatorname{sgn}(0) = 1.
    • Page 5, Lemma 1(i): "for all kk" →\to "for all tt".
    • Page 19, line 992: 2δeδ2\delta e^\delta →\to 2δe2δ2\delta e^{2\delta}.
7 comments
AuthorsOpenReview ↗

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ϕL_\phi and clarifying the complexity.

The dependence on LϕL_\phi can be removed by adding a simple diagonal scaling. Define Mt=Xt−1X‾t2Xt−1\boldsymbol{M}_t=\boldsymbol{X}_t^{-1}\overline{\boldsymbol{X}}_t^2\boldsymbol{X}_t^{-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.
AuthorsOpenReview ↗

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 (n,m)=(1000,500)(n,m)=(1000,500) and (2000,1000)(2000,1000). 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 10.64×10.64\times and 52.28×52.28\times on the first instance, and 9.53×9.53\times and 46.32×46.32\times on the second, respectively.

The additional experiments in Point 2 use ε=0.01\varepsilon=0.01, l=3.5l=3.5, ρ=6\rho=6, finite-difference radius r=0.01r=0.01, and 64 inner negative-curvature iterations. Algorithm 2 uses β=1/352\beta=1/352, while Algorithms 1 and 3 use β=1/552\beta=1/552 and δ=β\delta=\beta.

Parameters for Figs. 1 and 2. Both instances in Fig. 1 use ε=0.1\varepsilon=0.1, l=ρ=40l=\rho=40, r=0.1r=0.1, and x0=(0.333,0.333,0.334)⊤\boldsymbol{x}_0=(0.333,0.333,0.334)^\top. Algorithm 2 uses β=1/402\beta=1/402, while Algorithms 1 and 3 use β=1/422\beta=1/422 and δ=1/1600\delta=1/1600.

For the original Fig. 2, we use σ=1\sigma=1 and x0=e\boldsymbol{x}_0=\boldsymbol{e}. We randomly generate the constraints and the spectrum of Q\boldsymbol{Q} to obtain nonconvex quartic objectives. All three instances use ε=0.1\varepsilon=0.1 and l=5l=5, with β=δ=1/72\beta=\delta=1/72 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 ℓ1/2\ell_{1/2} problem with (n,m)=(5000,4000)(n,m)=(5000,4000):

\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.
AuthorsOpenReview ↗

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.
Reviewer_YxGGOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors study a non-linear optimization problem over a polytope Ax=b, x≥0Ax=b,\ x\ge 0, the main idea of the paper is to consider an approximate sparse update at each iteration to be able to solve the interior point subproblem cheaply. The main paper claim is that the method preserves feasibility and the global convergence guarantees of standard IPTR schemes while reducing the per-iteration cost. They also extend the framework to obtain approximate second-order KKT points using only first-order information by integrating a gradient-based negative-curvature routine. More concretly the diagonal matrix XtX_tin the orthogonal matrix

Critical strengths

The paper main result is very intersting and the obtained result could be important when considering large dimensional optimization problems. The theoritical results as well as the numerical results demonstrate an advantage of the proposed method

Critical weaknesses

Although I like the paper and I think it could potentially be accepted I have some major concerns that refrain me for giving the paper a better score for now. My main objection comes from the fact that you do not need to compute the inverse of the matrix A⊤Xt2AA^\top X_t^2A. Indeed you can compute the projection matrix efficiently using conjugate gradient. By separating the case where xx is far away from the boundary and the case where xx is close to x∗x^* I do not think that condition number issues appear. Also, It seems to me that in Lemma 1 arbitrary large value of q_t (and hence arbitrary large rank value for RtR_t) happens when considering enough iterations. I suspect that this might be hidden in the constant that appear in the time complexity estimate

Questions for authors

Could the author provide a more detail computational and memory advantage comparaison ? Could the author compare the two methods in detail when an iterative method such as CG is used to solve the full IPTR subproblem ? Also could the author explain how often large value of q_t appears ? If such large rank value appear every T iterations, it is not clear at all how the proposed method can have a clear theoritical advantage over the standard IPTR method. Can the author test there method on a practical problem related to ML with real data ? Also I think it is important to consider larger dimensional problems when submitting to this kind of conference. I am not asking a lot of new experiment but I do not think the current experiments are enough.

Reviewer_KtyXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper speeds up first-order Interior-Point Trust-Region (IPTR) algorithms for solving nonconvex optimization problems with linear equality and nonnegativity constraints. Standard IPTR methods guarantee that every step stays strictly inside the feasible region, but they are slow on large problems because they recompute an expensive projection matrix from scratch at every iteration. The authors address this bottleneck in two ways. First, an asymmetric projection matrix is used with careful updates of coordinates when their cumulative changes become large. This is interesting and shown to be able to reduce per-iteration complexity while ensuring feasibility in every step. Second, standard IPTR methods need Hessian matrices to escape saddle points and reach second-order KKT solutions. The authors replace Hessian computations with a gradient-based routine involving cheap approximate projection when exact calculation is not needed, so as to reduce the overall runtime. This is practical. Experiments on synthetic test problems up to 5,000 variables and 4,000 constraints show up to a 2.8x runtime speedup over standard first-order IPTR.

Critical strengths
  1. Usually, approximating a projection matrix causes the search direction to drift outside the feasible region. The authors design an asymmetric projector that places the exact scaling on the outside and the sparse approximation inside the matrix inverse. This algebraically cancels out errors along the equality constraints, guaranteeing 100% strict feasibility at every step while allowing fast low-rank inverse updates.

  2. To find second-order KKT points using only gradients, the algorithm needs many regular gradient steps but relatively few saddle-point escape steps. Using fast approximate projections for the frequent gradient steps and reserving expensive exact projections only for the rare saddle-point escape phases is a practical way to lower total runtime.

Critical weaknesses
  1. In the Introduction and appendix, the authors claim that existing first-order feasible methods either require expensive projections at every step (standard Projected Gradient Descent) or rely on linear optimization oracles (Frank-Wolfe). However, recent work has already lowered the per-iteration complexity of first-order projected gradient descent over compact convex sets without using optimization oracles or matrix inversions: C. Liu, E. Liang, and M. Chen, “Fast Projection-Free Approach (without Optimization Oracle) for Optimization over Compact Convex Set,” NeurIPS 2025. The work carries out projected gradient descent in a unit ball homeomorphic to compact convex set to avoid per-iteration projection, while achieving 100% strict feasibility and optimal convergence rates. The authors should update their related work and contribution to discuss how their method compares to this and other recent approaches.

  2. In Algorithm 3 (Lines 10–12), after taking a large negative-curvature step to escape a saddle point, the pseudocode continues feeding the new iterate into the lazy update routine. In contrast, the proof of Theorem 3 in the appendix states that is completely restarted and the projection matrix is recomputed from scratch after each negative-curvature step, which contradicts Line 12 of Algorithm 3.

  3. Procedure 1 (Page 7) runs a power-iteration loop for T\mathcal{T} steps to find negative curvature (the proof of Prop. 5 ensures its existence for some t_0). The pseudocode should make it clear whether the loop will exit/end once such negative curvature is found (using only gradient evaluations?).

Questions for authors
  1. Update Procedure 1 about when to stop and exit the loop using only gradient/function evaluations.
  2. Fix the inconsistence issue between Algorithm 3 and the proof of Theorem 3, and check whether the proof still goes through.
  3. Update the related work and contribution discussion to include Liu, Liang, and Chen (NeurIPS 2025), and compare the approximate IPTR method against their approach theoretically and empirically on bounded polytopes. Note that the equality-constrained setting is not concerning because with A full row rank and any feasible x̄, the standard null-space parameterization x = x̄ + Nz reduces Ax = b, x ≥ 0 to the pure-inequality problem −Nz ≤ x̄ over a full-dimensional polyhedron. This is exactly the regime the Liu-Liang-Chen results operate in.
  4. Can larger scale experiments be carried out to evaluate the runtime results of the algorithms? They can give better idea of how their runtime complexity scale under practical settings.

I am open to adjust my score upon the above concerns being addressed properly.

Reviewer_dd2YOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies first-order interior-point trust-region (IPTR) methods for linearly constrained nonconvex problems min⁡f(x)\min f(x) s.t. Ax=b,x≥0Ax=b, x\geq 0. It makes two contributions:

  1. Algorithm 1 replaces the exact projector Pt=I−XtA⊤(AXt2A⊤)−1AXtP_t = I - X_tA^\top(AX_t^2A^\top)^{-1}AX_t with RtR_t, which is built from a lazily updated diagonal Xˉt\bar X_t, maintained by SelectVector from Lee & Vempala (2021), so (AXˉt2A⊤)−1(A\bar X_t^2A^\top)^{-1} can be updated with low-rank Woodbury corrections. The claimed total time drops from O(nmω−1/ϵ2)O(nm^{\omega-1}/\epsilon^2) to O~(nmω−1+nm/ϵ2)\tilde{O}(nm^{\omega-1} + nm/\epsilon^2).

  2. Procedure 1, a finite-difference projected power iteration in ker(AX)ker(AX), finds negative-curvature directions. Algorithms2 and3 use it to reach (2ϵ,ϵ)(2\epsilon,\sqrt{\epsilon})-KKT2 points with O~(ϵ−2)\tilde{O}(\epsilon^{-2}) gradient queries.

The experiments cover two 3-variable simplex problems (Fig. 1) and synthetic quartic problems up to n=5000n=5000, m=4000m=4000 (Fig. 2). On the largest instance, Algorithm~1 is up to 2.80×2.80\times faster than exact first-order IPTR.

Critical strengths
  1. The problem and the approximate KKT notions are clearly stated. They follow Haeser et al.'s scaled conditions, which handle objectives that are not differentiable on the boundary.

  2. The oblique projector RtR_t affects only the quality of the step, not feasibility: AXtRt=0AX_tR_t = 0 holds exactly (Lemma 4). Together with ∣∣Rt−Pt∣∣≤46δ||R_t - P_t|| \le 46\delta, this keeps the one-step analysis clean.

  3. Full proofs are provided. Remark 2 is candid about when approximate updates help. The experiments report update-sparsity statistics (qt/nq_t/n) as well as wall-clock time, and the code is released.

Critical weaknesses
  1. The headline complexity (Theorem 1, Table 1) hides factors that matter for the comparison in nn and mm. Proposition 3 is proved under δ=Θ(β)\delta = \Theta(\beta), but Algorithm 1 sets δ=β/(92Lϕ)\delta = \beta/(92L_\phi) (the second term of the minimum in line 3 is always the smaller one). Lemma 1(ii) therefore gives qt=O(4lt(184Lϕ)2log⁡2n)q_t = O\big(4^{l_t}(184 L_\phi)^2\log^2 n\big), and Eq. (16) absorbs (184Lϕ)2(184 L_\phi )^2 into CC. If this factor is carried through, Eq. (20) picks up Lϕ2(ω−2){L_\phi}^{2(\omega-2)}, Eq. (21) picks up LϕL_\phi, and the threshold l∗l^* in (19) drops by log⁡2(184Lϕ)\log_2(184{L_\phi}). The authors keep this factor explicit in Prop. 8. However, LϕL_\phi can grow with nn. Since X∇ϕ=X∇f−ϵeX\nabla\phi = X\nabla f - \epsilon e, we have Lϕ≥ϵn−∥X∇f(x)∥L_\phi \geq \epsilon\sqrt{n} - \|X\nabla f(x)\| at every interior point.

On the simplex with ∥∇f∥≤G\| \nabla f \| \leq G, for example, Lϕ≥ϵn−GL_\phi \geq \epsilon \sqrt{n} - G. In that case the Lemma 1 bound is of order ϵ2nlog⁡2n⋅4lt\epsilon^2 n\log^2 n \cdot 4^{l_t} (\times 1842184^2). This exceeds mm already at lt=0l_t = 0 whenever m≲ϵ2nlog⁡2nm \lesssim \epsilon^2 n \log^2 n. Then l∗<0l^* < 0, every iteration takes the full-recompute branch, and the analysis gives no improvement over O(nmω−1/ϵ2)O(nm^{\omega-1}/\epsilon^2). Please state Theorem 1 with explicit dependence on LϕL_\phi and ll, and characterize the regime in which the improvement holds.

  1. Dependence on ω<2.5\omega < 2.5. The geometric sum in (20) and the step nmω−1.5T≤nmTnm^{\omega-1.5}T \le nmT in (21) both require ω<2.5\omega < 2.5. This condition appears only inside the proof of Prop. 8, not in Prop. 3 or Theorem~1. Exponents below 2.52.5 are only reached by some rare, if any, fast matrix multiplication algorithms. So the claim of ``matrix-vector multiplication time'' per iteration describes a purely theoretical regime. With ω=3\omega = 3, which is what a standard implementation achieves, the same argument gives O(m2.5T+nm1.5T)O(m^{2.5}T + nm^{1.5}T). That is a m\sqrt{m} saving over recomputing from scratch, not O(nm)O(nm) per iteration. Please state this explicitly.

  2. Theory versus experiments. With the prescribed δ\delta, even for Lϕ=1L_\phi = 1 and ignoring CC and log factors, (2β/δ)2=1842≈3.4×104(2\beta/\delta)^2 = 184^2 \approx 3.4\times 10^4, which exceeds m=4000m = 4000. So the theoretical parameters cannot account for the 77--96% sparse-update rates in Fig. 2(d). The experiments presumably used a much larger δ\delta, which is not reported. In that case they show that a heuristic variant works well, not that Algorithm 1 as analyzed does. Please report the δ\delta and β\beta that were used.

Questions for authors
  1. What is Theorem 1 with explicit dependence on LϕL_{\phi} and ll? What is LϕL_{\phi} for the quartic instances? In what regime does the improvement survive when Lϕ≳ϵnL_{\phi} \gtrsim \epsilon \sqrt{n}?
  2. What does the analysis give with ω=3\omega = 3, and which regime do the experiments fall into?
  3. Which δ\delta and β\beta were used in Fig. 2, and how do they compare with β/(92Lϕ)\beta/(92L_{\phi})?

Comments on the paper

1 comment
AuthorsOpenReview ↗

Gentle reminder - less than 24 hours left for the author-reviewer discussion

As the author-reviewer discussion period will end in less than 24 hours, we would greatly appreciate it if you could join the discussion and share your thoughts on our response.

Thank you for your time and consideration!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.