We characterize the fresh-gradient oracle complexity of smooth nonconvex-strongly-concave minimax optimization, with matching upper and lower bounds up to logarithmic factors. Let $\Phi(x)=\max_y f(x,y)$, where $f$ is jointly $L$-smooth and $\mu$-strongly concave in $y$ on unconstrained Euclidean domains, and set $\kap...
Wen-Dao Wu, Hai-Han Zhang, Chen-Heng Zhang et al.· 1 citation
We establish matching polynomial query bounds for low-rank approximation from exact matrix--vector products. Given an unknown matrix $A\in\mathbb{R}^{m\times n}$, at each step a randomized algorithm chooses either $v\in\mathbb{R}^n$ and receives $Av$, or $u\in\mathbb{R}^m$ and receives $A^\top u$. The choice may depend...
Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al.· 1 citation
The same accuracy exponent holds beyond tensor update rules, even for randomized queries and arbitrary feasible outputs, for smooth convex--concave minimax optimization.
Yan-Yi Li, Hai-Han Zhang, Chen-Heng Zhang et al.· 0 citations
This work reframe knowledge editing from a manifold perspective, viewing it as a localized displacement of an edit sub-manifold within the global knowledge manifold, and proposes ManiEdit, a novel manifold-aware autoregressive editing framework consisting of two core components: Pivot Localization and Manifold-Aware Pr...
Rui Liu, Chen-Heng Zhang, Hao-Xuan Li et al.· 0 citations
A matching $\Omega_p(Q^{2/(3p-1)})$ lower bound is proved for arbitrary adaptive deterministic algorithms and randomized algorithms with per-instance success probability at least $2/3$, without span or tensor-update restrictions.
A single fixed smooth convex hard instance is constructed using a Moreau-smoothed biased max chain, an exact prefix-shielding mechanism, and batched delayed rotations to preserve consistency with the full adaptive transcript and establish the optimality of the square-root complexity branch for deterministic bounded-que...
Wen-Dao Wu, Hai-Han Zhang, Chen-Heng Zhang et al.· 0 citations
This work proves the first near-optimal lower bound for arbitrary adaptive randomized algorithms throughout both accuracy regimes of exact value Lipschitz convex optimization, and develops a posterior mean energy method for adaptive exact max observations.
Haihan Zhang, Chen-Heng Zhang, Zhiquan Qi et al.· 1 citation
Inspired by the human brain, which balances plasticity and stability through complementary episodic storage and gradual consolidation, UniMem is proposed, a self-routing framework for autonomous memory management that consistently outperforms baselines while maintaining execution fidelity.
