This work proposes LoRA-NSGDM, which finds an $\epsilon$-stationary point with $\mathcal{O}(\epsilon^{-8})$ stochastic oracle complexity, and LoRA-STORM, which improves the stochastic oracle complexity to $\mathcal{O}(\epsilon^{-6})$.
Abstract
Low-rank adaptation (LoRA) optimizes $J(B,A)=\mathcal L(W_\mathrm{base}+sBA)$ over two adapters $B \in \mathbb{R}^{m \times r}$ and $A \in \mathbb{R}^{r \times n}$ that form a low-rank update to a frozen pretrained weight matrix $W_\mathrm{base} \in \mathbb{R}^{m \times n}$. The prior analysis shows LoRA-GD takes $\exp\{\mathcal{O}(\epsilon^{-2})\}$ oracle calls to find an $\epsilon$-stationary point such that $\|\nabla J(B,A)\|\leq \epsilon$ in the deterministic setting. We sharpen the analysis and show that $\mathcal{O}(\epsilon^{-4})$ full-gradient evaluations suffice for the same first-order criterion. We further study stochastic LoRA under unbiased gradient estimates and finite variance. We propose LoRA-NSGDM, which finds an $\epsilon$-stationary point with $\mathcal{O}(\epsilon^{-8})$ stochastic oracle complexity. Under the additional mean-square smoothness condition, we use variance reduction strategy and propose LoRA-STORM, which improves the stochastic oracle complexity to $\mathcal{O}(\epsilon^{-6})$.
Let $G\in\mathbb{R}^{M\times N}$ have independent standard Gaussian entries. For a fixed margin $\kappa\in\mathbb{R}$, the asymmetric binary perceptron asks for $\sigma\in\{\pm1\}^N$ such that $G\sigma/\sqrt{N}\ge\kappa\mathbf{1}_M$. We study the online version of this problem, in which the columns of $G$ arrive sequentially and each sign must be chosen irrevocably before future columns are revealed. We determine the exact threshold $\alpha_{\mathrm{on}}(\kappa)$ for every fixed $\kappa$: for $M/N\to\alpha$ with $\alpha<\alpha_{\mathrm{on}}(\kappa)$, there is a deterministic online algorithm, using $O(MN)$ arithmetic operations and polynomial bit complexity, that succeeds with high probability, while for $\alpha>\alpha_{\mathrm{on}}(\kappa)$, no online algorithm succeeds with high probability. The threshold is characterized by a one-dimensional stochastic control problem for Brownian motion. The main difficulty is to upgrade a single-coordinate Brownian limit to simultaneous feasibility of all $M=\Theta(N)$ constraints, which we do with half-line monotonicity and a short final correction block. At zero margin, we give a computer-assisted proof that $0.32747<\alpha_{\mathrm{on}}(0)<0.36664$. In particular, every density below $0.32747$ is achievable online by such an algorithm, more than tripling the best density previously proved attainable by any polynomial-time algorithm, online or offline (the previous bound was $\alpha\le0.1$, due to Li, Schramm, and Zhou). As $\kappa\to+\infty$, the online threshold agrees to first order with the offline storage capacity. As $\kappa\to-\infty$, it has the same asymptotic scale as the best known offline polynomial-time guarantee, while the storage capacity is larger by a factor of order $\kappa^2$.
Let $A=(\xi_{ij})$ be an $n\times n$ random matrix with independent, not necessarily identically distributed, real entries satisfying \[ \mathbb E\xi_{ij}=0,\qquad \mathbb E\xi_{ij}^{2}=1,\qquad \sup_{z\in\mathbb R}\mathbb P(|\xi_{ij}-z|0$ and $b\in(0,1)$. We prove that, for every $\delta\in(0,1)$, there are constants $c,C>0$, depending only on $a,b,\delta$, such that \[ \mathbb P\left( s_{n+1-l}(A)>Ct\frac l{\sqrt n} \right) \le \exp\!\left(-c\min\{tl,n\}\right) \] for every $t\ge1$ and every $1\le l\le(1-\delta)n$. Thus, with no moment assumption beyond variance, all but a fixed proportion of the largest singular values satisfy the optimal upper bound of order $l/\sqrt n$ with an exponential upper-tail estimate. Combined with the lower bound of the rectangular least singular value bound, this gives $s_{n+1-l}(A)\asymp l/\sqrt n$ with failure probability exponentially small in $l$. The same argument gives the rectangular scale $\sqrt{N+1}-\sqrt{n-l+1}$ for $N\times n$ matrices whenever $N-n+l\le(1-\delta)N$.
Manuel Fernández, Achintya Raya Polavarapu· 0 citations
For a family $\mathcal{F}\subseteq\binom{[n]}k$ and $R\in\binom{[n]}r$, let $d_{\mathcal{F}}(R)=|\{F\in\mathcal{F}:R\subseteq F\}|$ and $\ell_{r,p}(\mathcal{F})=\sum_{R\in\binom{[n]}r}d_{\mathcal{F}}(R)^p$; at the codegree level, write $co_p(\mathcal{F})=\ell_{k-1,p}(\mathcal{F})$. We introduce a new convex-transference method for degree-power extremal problems and develop it into a reusable input--transfer--rigidity framework independent of any particular set-system problem. We give three exact applications. First, a full $t$-star maximizes $co_p$ among $t$-intersecting families for every real $p\geq2$ in the sharp range $n\geq(t+1)(k-t+1)$, with all equality cases determined. This extends the Wu--Zhang quadratic theorem to real exponents and answers a problem of Zhou--Yuan throughout the sharp Erd\H{o}s--Ko--Rado range. Second, if $n\geq2k$, a full point-star maximizes $\ell_{r,p}$ for every $1\leq r\leq k-1$ and real $p\geq2$, again with complete equality classification; thus the framework is not confined to codegrees. Third, if $\nu(\mathcal{F})\leq s$ and $n\geq(2s+1)k-s$, then for every real $p\geq1$, $co_p(\mathcal{F})$ is uniquely maximized, up to isomorphism, by all $k$-sets meeting a fixed $s$-set. This removes the integrality restriction on $p$ and replaces previous cubic thresholds or nonexplicit sufficiently-large assumptions with an explicit linear range valid for arbitrary uniformity.
Mengyue Cao, Mei Lu, Haixiang Zhang· 1 citation· ⚡1
We study the near $L^1$ behavior of the maximally quadratically modulated Hilbert transform \[ \mathcal{C}_2f(x) := \sup_{\lambda} \left|\operatorname{p.v.} \int_{\mathbb{R}}f(x-y)e^{2 \pi i \lambda y^2} \frac{\mathrm{d} y }{y} \right| \] and its lacunary counterpart obtained by restricting $\lambda$ to $2^{\mathbb{Z}}.$ We prove that if $\Phi$ is a Young function satisfying $ \Phi(t)=o\bigl(t\log_2t\bigr)$ then $\mathcal{C}_{2,\mathsf{lac}}$, and therefore $\mathcal{C}_2$ as well, does not satisfy a corresponding $\Phi$-modular estimate. In particular, neither the lacunary nor the full quadratic operator is of weak type $(1,1)$. In the positive direction, we establish an $L\log_1 L$ modular estimate for $\mathcal{C}_2$ and a $L (\log_2L)^2 \log_4L$ estimate for $\mathcal{C}_{2,\mathsf{lac}}.$
A. Fragkos, Ben Krause, Michael T. Lacey· 0 citations
An algorithm achieving regret $\widetilde{\mathcal{O}}(T^{7/10})$ is designed, improving over the previous best-known bound of $\widetilde{\mathcal{O}}(T^{3/4})$ and showing that the curse of dimensionality can be at least partially lifted for this class of objectives.
Matteo Castiglioni, Anna Lunghi, A. Marchesi· arXiv.org· 0 citations
We confirm the Kannan--Lov\'asz--Simonovits conjecture for quadratic forms: if $X \sim \mu$ is an isotropic log-concave random vector in $\mathbb{R}^n$, then for any symmetric matrix $M$ one has $$ \operatorname{Var}_{X \sim \mu}(\langle MX,X\rangle) \leq 2\,\mathbb{E}_{X \sim \mu}|\nabla\langle MX,X\rangle|^2. $$ As an application, we apply the above to $M=\mathbb{E}_{X \sim \mu}(\langle X,\theta\rangle X\otimes X)$ for $\theta\in S^{n-1}$ and show that the Kannan--Lov\'asz--Simonovits constant $\psi_n$ satisfies $$ \psi_n\leq C\log^{1/4}n $$ for some absolute constant $C>0$.
B. Letwin· 10 citations· ⚡8
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
