Under individual smoothness, the optimal incremental first-order oracle (IFO) complexity of nonconvex finite-sum optimization has remained open. Known algorithms use $O(n+\sqrt{n}\,ΔL_{\max}/\varepsilon^2)$ calls, while prior lower bounds miss a factor of $\sqrt{n}$. We prove the matching lower bound for randomized IFO algorithms whose component indices and query points may depend on the complete preceding transcript and private randomness. This determines the minimax IFO complexity up to universal constants under both individual and mean-squared smoothness. Under the global Polyak-Lojasiewicz (PL) condition, the standard PAGE guarantee is not tight when $κ_{\mathrm{ms}}<\sqrt{n}$. Restarted PAGE attains $O(n+n\log(Δ/\varepsilon)/(1+\log(\sqrt{n}/κ_{\mathrm{ms}})))$ for $1\leqκ_{\mathrm{ms}}\leq\sqrt{n}$, and $O(n+κ_{\mathrm{ms}}\sqrt{n}\log(Δ/\varepsilon))$ for $κ_{\mathrm{ms}}\geq\sqrt{n}$. We prove matching lower bounds under individual smoothness for every $κ_{\max}\geq 3$; the same hard instances also give the mean-squared lower bounds. In the small-$κ_{\max}$ range, their average objective is globally strongly convex. Our lower bounds use dense weak hiding. A fixed sign table spreads each hidden direction across the components. Each queried row carries little information, while the exact row average preserves the full signal after rescaling. A bounded radial map handles arbitrary query points, and a smooth gate makes unopened links invisible to both function values and gradients. Balancing the rows needed to reveal one stage with the number of stages allowed by individual smoothness yields the missing $\sqrt{n}$ factor.
The Self-Improving Alignment (SAIL) algorithm addresses distribution shift by reducing a bilevel formulation of the problem to an efficient, single-level method. Empirically, SAIL has demonstrated strong performance on this task. However, a formal analysis of its convergence properties has been lacking. We identify a key theoretical challenge: the standard SAIL objective function is not guaranteed to be strongly concave due to unfavorable properties of its Hessian. To address this limitation, we propose a regularized objective, SAIL-RevKL, which incorporates a reverse Kullback-Leibler (KL) divergence penalty to improve the optimization landscape. Our central theoretical contribution is to prove that this regularized objective satisfies the Polyak-Lojasiewicz (PL) condition within a bounded parameter space. We establish global convergence guarantees, achieving a near-linear sample complexity. We further validate the effectiveness and stability of SAIL-RevKL through empirical evaluations, demonstrating that it outperforms the vanilla SAIL on both MuJoCo benchmarks and LLM alignment tasks.