Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Optimal Algorithms in Linear Regression under Covariate Shift: On the Importance of Precondition

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that for ellipsoid-constrained linear regression under covariate shift, the minimax-optimal estimator is a linear transformation of the source least-squares estimator, computed by a convex program, and that SGD with…

desk verdict Novel lower bound and ASGD analysis, but the exact minimax optimality claim is unsupported because the upper and lower bound constants don't match. read the letter →

arxiv 2502.09047 v1 pith:RAZXSSMZ submitted 2025-02-13 stat.ML cs.LG

Yuanshi Liu , Haihan Zhang , Qian Chen , Cong Fang This is my paper · ORCID
classification stat.MLcs.LG MSC 62J0562C2090C25
keywords covariateshiftlinearregressionminimaxoptimalitypreconditioningstochasticgradientdescentacceleratedSGDCramér-Raoboundellipsoidconstraint
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to identify the information-theoretically optimal algorithm for high-dimensional linear regression when training and test distributions differ only in the covariate distribution, and the true parameter lies in an ellipsoid. Its central claim is that the minimax-optimal estimator is a linear transformation of the source least-squares estimator, with the transformation computed by a convex program that trades bias against variance. The lower bound comes from a Bayesian Cramér-Rao inequality, the upper bound from this preconditioned estimator, and a duality identity is presented as matching the two. The same preconditioning view is used to show that SGD and accelerated SGD achieve the minimax rate up to logarithmic factors on r-smooth power-law target classes, with momentum expanding the optimality region. If correct, this reduces optimal transfer learning under covariate shift to a tractable matrix optimization problem.

What carries the argument

The central objects are the preconditioned estimator class ŵ_A = (1/n)$M^{{-1/2}}$$AM^{{1/2}}$$S^{{-1}}$Σ x_i y_i, whose matrix A reweights the source least-squares solution to balance bias and variance in the M-ellipsoid geometry; the multivariate Bayesian Cramér-Rao inequality that bounds any estimator's covariance below by (E I(w)+I(π))^{-1}; and a family of priors supported on ellipsoid-inscribed parallelohedra with cosine-squared densities, whose information matrices range over all F with ||F||_* ≤ 1/π². The matching step is Theorem 3, a duality identity equating the lower-bound supremum to a convex program over A. For the SGD analysis, each eigen-direction of the source covariance is governed by a 2×2 momentum matrix, and the effective dimension k* separates optimized from unoptimized directions; semi-stochastic variance and bias recursions bound the effect of fourth-moment noise.

What would settle it

Take S = M = T = I_d with Gaussian source noise σ². The Theorem 1 lower bound is exactly d/(π²d + n/σ²), while the minimized Theorem 2 bound for the proposed estimator is (2σ²+2ψ)d/(n+(2σ²+2ψ)d). Computing both for, say, n = $10^{4}$, d = 100, σ² = 1, ψ = 3 gives bounds whose ratio is about 8; observing such a gap directly contradicts the claim of exact minimax matching, and a rate-only claim would need the paper's own theorems restated accordingly.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is an exact characterization of the minimax target risk for the class W = {w* : ||w*||²_M ≤ 1}: the lower bound is sup over F ≽ O, ||F||_* ≤ 1/π² of ⟨T',($F^{{-1}}$+nS'/σ²)^{-1}⟩, and the paper proves that this supremum equals the minimum over A of (1/π²)||(I-A)^T T'(I-A)|| + (σ²/n)⟨T',A(S')^{-1}A^T⟩. The estimator it proposes is ŵ_A = (1/n)$M^{{-1/2}}$ A $M^{{1/2}}$ $S^{{-1}}$ Σ x_i y_i, and the paper asserts that choosing A to minimize this dual objective attains the information-theoretic minimax rate for every fixed (S,T). It then identifies the accumulation of ASGD updates as a particular greedy preconditioner and gives sufficient conditions, in terms of power-law source spectra and r-smooth target classes, under which SGD and its accelerated variants are rate-optimal up to logarithmic factors.

Load-bearing premise

The whole conclusion rests on identifying the lower bound's dual objective with the risk actually achieved by the estimator, but the two objectives carry different constants (1/π² and σ²/n versus 1 and (2σ²+2ψ||S'||)/n), and no step in the paper bridges that difference.

Editorial extensions

If this is right

  • For any fixed source-target pair, the optimal preconditioner A is the solution of a convex program, so the minimax-optimal estimator can be computed efficiently once S and T are known.
  • Unlabeled target data suffice to build the optimal estimator, since only the covariate matrix T and source matrix S enter the optimization, matching the semi-supervised paradigm.
  • Under power-law source spectra and r-smooth target classes, SGD with geometrically decaying steps attains the minimax rate up to logarithmic factors, and Nesterov momentum widens the range of ellipsoid exponents s for which this holds.
  • Target tasks concentrated on the top d0 coordinates exhibit an emergent phase transition: excess risk stays essentially flat until n exceeds d0^{a+1} and then drops polynomially.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The duality identity in Theorem 3 is independent of the estimation story and may extend to other inverse-covariance problems, where a spectral-norm-constrained supremum is dual to a pre- and post-conditioned quadratic minimization.
  • Closing the constant gap would require either a lower bound whose information constraint yields the coefficient (2σ²+2ψ||S'||) or an estimator whose bias coefficient is 1/π²; a promising test is whether the parallelohedra prior can be replaced by a smoother prior to tighten the bound.
  • The predicted phase transition in the emergence example at n ≈ d0^{a+1} is directly testable by simulating power-law covariate spectra and measuring target risk on the first d0 coordinates as a function of sample size.
  • The r-smooth class is a whitened similarity condition S^{-1/2}TS^{-1/2} ≼ C S^r; empirical work on real covariate shifts could estimate r for natural distribution pairs and check whether ASGD's measured rates sit in the predicted optimality region.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies high-dimensional linear regression under covariate shift when the true parameter lies in an ellipsoid. It derives a Bayesian Cramér-Rao lower bound (Theorem 1), analyzes a preconditioned linear estimator \hat{w}_A defined in (7), and claims in Section 4 that the estimator obtained by solving the convex program (8) attains the exact information-theoretic minimax risk (Theorems 2 and 3). The rest of the paper analyzes ASGD with geometrically decaying step sizes (Theorem 4) and gives sufficient conditions for rate-optimality of SGD/ASGD for anisotropic target classes (Theorems 5-7), including a discussion of emergent risk curves.

Significance. The paper addresses an important and timely question and contains substantial technical machinery: the multivariate Bayesian Cramér-Rao lower bound with ellipsoid-inscribed priors is an interesting construction, and the ASGD analysis with momentum is detailed and nontrivial. If the exact minimax optimality claim were correct, it would be a strong instance-optimal transfer result. Unfortunately, the central matching argument is not valid: Theorem 3 proves an identity involving the lower bound, while the upper bound in Theorem 2 is a different functional with different constants. For the scalar Gaussian instance the two functionals differ by more than a factor of five, and no linear estimator of the form (7) can attain the lower-bound value. The ASGD rate results may be salvageable as rate-optimality statements, but they do not support the advertised exact optimality.

major comments (3)
  1. [Section 4, Theorems 2 and 3] The claimed minimax optimality of the estimator in (7) is not established. Theorem 2 upper-bounds the worst-case excess risk by min_A ||(I−A)^T T'(I−A)|| + ((2σ^2+2ψ||S'||)/n)<T', A(S')^{-1}A^T>, whereas Theorem 3 proves that the lower bound (6) equals min_A (1/π^2)||(I−A)^T T'(I−A)|| + (σ^2/n)<T', A(S')^{-1}A^T>. These are different functionals: the bias coefficients differ by a factor π^2, the variance coefficients differ by σ^2/(2σ^2+2ψ||S'||), and the minimizers need not coincide. The proof of Theorem 2 does not use Theorem 3, and no step in the paper bridges the two objectives. In the scalar instance S=T=M=I, σ^2=ψ=1, n=10, the Theorem 3 value is 1/(π^2+10) ≈ 0.050, while the Theorem 2 value is 4/14 ≈ 0.286. For that instance, the risk of the estimator in (7) is (1−a)^2 + 3a^2/10 at |w|=1, whose minimum over a is 39/169 ≈ 0.231; the minimizer of the Theorem 3 objective has risk about 0.323. Thus the right-hand side of Theorem 3 is not a risk bound for the estimator, and the exact optimality conclusion in Section 4 does not follow.
  2. [Section 4, after Eq. (8)] There is a structural reason why the gap cannot be closed by adjusting constants in the proof. For any fixed A, the worst-case bias over W = {w: ||w||_M^2 ≤ 1} is exactly ||(I−A)^T T'(I−A)||, because the quadratic form u^T (I−A)^T T'(I−A) u attains its maximum on the unit sphere. Hence no estimator of the form (7) can have worst-case risk equal to the right-hand side of Theorem 3 in general, whose bias term is 1/π^2 times this quantity. An exact matching result would require either a different, nonlinear estimator class or a stronger lower bound.
  3. [Section 5, Theorems 5-7] The rate-optimality analysis for ASGD does not repair the central gap. Its lower-bound comparisons use the functional from Theorem 3 via Lemma 33 and Lemma 35, while the ASGD upper bound in Theorem 4 comes from the same bias-variance decomposition that produced Theorem 2. Matching exponents up to logarithmic factors is weaker than the exact minimax optimality advertised in the abstract and in Section 4. The paper should either prove an upper bound with the same constants as the lower bound or explicitly reframe the contribution as rate-optimality up to constants and logarithmic factors.
minor comments (5)
  1. [Theorem 5] The statement says 'Suppose Assumptions 6 holds'; it should refer to Assumption 5 (or the relevant standing assumptions). In the proof, the second occurrence of 'For the region s ≥ 1 − 1/a' should read 'For the region 1 − 1/a > s > (a−1)^2/(a(2a−1))' to match the stated optimality regions.
  2. [Section 5.3.1] The sentence 'the case where T has a rank-1 structure corresponds to ν = 0' contradicts the proof of Theorem 6 and the remark after Theorem 7, both of which use ν = 1 for the rank-1 structure.
  3. [Theorem 2 and Eq. (7)] The estimator (7) and the objective (8) require S and S' to be invertible, but Theorem 2 states the result for 'any positive semi-definite matrix S and T'. The invertibility condition should be stated explicitly, or the use of S^{-1} should be justified for singular S.
  4. [Lemmas 19 and 20] In the proofs of Lemma 19 and Lemma 20, the third case is printed as 'If λ ∈ I2' but should be 'If λ ∈ I3'.
  5. [Throughout] Several displayed equations contain LaTeX artifacts such as '/bracehtipupleft /bracehtipdownright' in Theorem 4 and around Eq. (47), and 'sinkθ' appears in Lemma 30; these should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower and upper bounds are derived from independent arguments; the mismatch between Theorem 2 and Theorem 3 is a soundness gap, not a definitional or fitted equivalence.

full rationale

The derivation chain is not circular. The minimax lower bound (Theorem 1) is obtained from a Bayesian Cramér–Rao inequality (Lemma 2) applied to explicit cosine priors on ellipsoid-inscribed parallelohedra; it does not assume the estimator class (7) or the upper-bound objective. The upper bound (Theorem 2) is a separate bias–variance calculation for the preconditioned estimator (7), minimizing an excess-risk bound; its coefficients (1, (2σ²+2ψ‖S′‖)/n) are derived from Assumptions 3–4 and the supremum over W. Theorem 3 is a self-contained duality calculation equating the lower-bound supremum over F to a different objective with coefficients (1/π², σ²/n). No parameter in Theorem 1 or Theorem 2 is fitted to the other, and the proof of Theorem 2 never invokes Theorem 3. The self-citation to arXiv:2409.09745 appears only in Related Work and is not used in any proof; the appendix borrows lemmas from Li et al. [2024] and Jain et al. [2018], which are external. The serious problem with the paper is a soundness gap—the claimed exact information-theoretic optimality in Section 4 does not follow because Theorem 3’s objective differs from Theorem 2’s upper bound—but this is a non-sequitur, not a circular reduction.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No parameters are fitted to data; sigma^2, psi, and c are treated as fixed inputs. The rate optimality results rely on power-law spectral assumptions and on the bounded-moment assumptions. No new physical entities or mediators are introduced.

assumptions (6)
  • domain assumption Assumption 1: source and target risk share the same minimizer w*.
    Without a common minimizer, the bias-variance decomposition around w* used in Theorems 2 and 4 would not follow.
  • domain assumption Assumption 2: there exists c > 0 with ||w*||_S^2 <= c for all w* in the ellipsoid.
    Controls initial excess risk and implies ||M^{-1/2} S M^{-1/2}|| <= c, used in the upper bounds.
  • domain assumption Assumption 3: bounded fourth moment E[xx^T A xx^T] <= psi tr(SA) S.
    Used to control the variance of the preconditioned estimator and the noise terms in the ASGD recursion.
  • domain assumption Assumption 4: E[epsilon^2 xx^T] <= sigma^2 S.
    The noise second-moment bound is needed for the variance inequalities in Theorems 2 and 4.
  • domain assumption Assumption 5: power-law source eigenvalues lambda_i ~ i^{-a} and M commuting with S with m_i ~ lambda_i^{1-s}.
    These structural assumptions define the regime in which the SGD/ASGD rate optimality results in Theorem 5 are proved.
  • domain assumption Assumption 6: generalized target conditions with parameters a, s, r, nu.
    Used for the broader optimality analysis in Theorem 7 and the rank-1 target case.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Algorithms in Linear Regression under Covariate Shift: On the Importance of Precondition." pith.science (2026). https://pith.science/paper/RAZXSSMZ

@misc{pith2026250209047,
  author       = {Pith},
  title        = {Pith review of: Optimal Algorithms in Linear Regression under Covariate Shift: On the Importance of Precondition},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RAZXSSMZ}},
  note         = {Machine review of arXiv:2502.09047}
}
read the original abstract

A common pursuit in modern statistical learning is to attain satisfactory generalization out of the source data distribution (OOD). In theory, the challenge remains unsolved even under the canonical setting of covariate shift for the linear model. This paper studies the foundational (high-dimensional) linear regression where the ground truth variables are confined to an ellipse-shape constraint and addresses two fundamental questions in this regime: (i) given the target covariate matrix, what is the min-max \emph{optimal} algorithm under covariate shift? (ii) for what kinds of target classes, the commonly-used SGD-type algorithms achieve optimality? Our analysis starts with establishing a tight lower generalization bound via a Bayesian Cramer-Rao inequality. For (i), we prove that the optimal estimator can be simply a certain linear transformation of the best estimator for the source distribution. Given the source and target matrices, we show that the transformation can be efficiently computed via a convex program. The min-max optimal analysis for SGD leverages the idea that we recognize both the accumulated updates of the applied algorithms and the ideal transformation as preconditions on the learning variables. We provide sufficient conditions when SGD with its acceleration variants attain optimality.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Dimension-adapted Momentum Outscales SGD

    stat.ML 2025-05 conditional novelty 7.0 of 10

    DANA, with dimension- and time-dependent momentum, provably outscales SGD on power-law random features when 2α>1, improving loss exponents and compute-optimal curves.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · cited by 1 Pith paper

  1. [1]

    Select a positive integer ˜κ<d

    work page

  2. [2]

    For any PSD matrix M, we have E [ ˆGt⊗ ˆGt ] ◦ M≼ ψ ⟨[ O O O S ] , M ⟩[ δ2 t S δtqtS δtqtS q2 t S ]

    Suppose Assumption 3 holds. For any PSD matrix M, we have E [ ˆGt⊗ ˆGt ] ◦ M≼ ψ ⟨[ O O O S ] , M ⟩[ δ2 t S δtqtS δtqtS q2 t S ] . (75) Proof. 1. From the definiton of Bt, we have Bt =E [( V− ˆGt ) ⊗ ( V− ˆGt )] a ≼ (V− Gt)⊗ (V− Gt)− Gt⊗ Gt + E [ ˆGt⊗ˆGt ] = ˜Bt + E [ ˆGt⊗ˆGt ] , (76) where a ≼ uses E [ V⊗ ˆGt ] = V⊗ Gt and a ≼ uses E [ ˆGt⊗ V ] = Gt⊗ V. 25

    work page

  3. [3]

    C.1.3 Parameter Choice We select the parameters of ASGD using the following procedu re:

    Apply the partition of ˆGt to M = [ M11 M12 M21 M22 ] , we have E [ ˆGt⊗ ˆGt ] ◦ M =E [ δ2 t xx⊤M22xx⊤ δtqtxx⊤M22xx⊤ δtqtxx⊤M22xx⊤ q2 t xx⊤M22xx⊤ ] = [ δ2 t δtqt δtqt q2 t ] ⊙ E [ xx⊤M22xx⊤ ] a ≼ [ δ2 t δtqt δtqt q2 t ] ⊙ [ ψ ⟨[ O O O S ] , M ⟩ S ] ≼ψ ⟨[ O O O S ] , M ⟩[ δ2 t S δtqtS δtqtS q2 t S ] , (77) where⊙ denotes Kronecker product, and a ≼ holds fo...

    work page

  4. [4]

    Select auxiliary step sizes δ′ and γ′ as δ′≤ 1 ψ tr S, γ ′∈ [ δ′, 1 ψ∑ i>˜κλi ] ; (78)

    work page

  5. [5]

    Select the total number of ASGD iterations n and momentum parameters α and β as β = δ′ 4376ψ˜κγ ′ lnn, α = 1 1 +β, n [1−α(1−β)] log2n lnn ≥ 16; (79)

    work page

  6. [6]

    (80) From the above procedure, we have δ≤ 1 2188ψ lnn tr S, γ ∈ [ δ, 1 2188ψ lnn∑ i>˜κλi ] , β = δ 4376ψ˜κγ lnn

    Select step sizes δ and γ as δ = δ′ 2188 lnn, γ = γ′ 2188 lnn. (80) From the above procedure, we have δ≤ 1 2188ψ lnn tr S, γ ∈ [ δ, 1 2188ψ lnn∑ i>˜κλi ] , β = δ 4376ψ˜κγ lnn. (81) Lemma 5. Recall that c =α(1−β), q =αδ + (1−α)γ and K =n/ log2n. We have the following properties of the parameter choice

    work page

  7. [7]

    We have q−δ 1−c = γ−δ 2 , q−cδ 1−c = γ +δ 2 . (82) 26

    work page

  8. [8]

    (83) Proof

    For i∈ [d], we have δλi≤ 1 2188ψ lnn≤ 1, qλ i≤ 1 +c. (83) Proof. 1. Note that 1 −c = 2(1−α). Thus, we have q−δ 1−c = (1−α)(γ−δ) 1−c = γ−δ 2 , q−cδ 1−c = q−δ 1−c +δ = γ +δ 2 . (84)

    work page

Show all 37 references
  1. [9]

    self- governed

    Since λi≤ tr S, we have δλi≤ λi 2188ψ lnn tr S≤ 1 2188ψ lnn≤ 1. (85) Note that 1−α =αβ and 2α = 1 + c , we have q =αδ + (1−α)γ =αδ +αβγ≤ 2αδ = (1 + c)δ. (86) Therefore, qλi≤ (1 +c)δλi≤ 1 +c. C.2 Proof Outline We express the recursions of E [ η bias t ( η bias t ) ⊤] and E [ η ...

    2016

  2. [10]

    If λ∈I1, by Lemma 16 and assumption, ρ(A(λ)) =|x2|≤ 1− q−cδ 1−c λ≤ 1− 4 lnn 4K . (140) Thus, by Lemma 17, ‖ ‖AK(λ) ‖ ‖≤ √ 6K [ρ(A(λ))]K−1≤ √ 6K (1− 4 lnn)K−1 = √ 6K exp [(K− 1) ln (1− 4 lnn)] a ≤ √ 6K exp [ − 4(K− 1) lnn K ] b ≤ √ 6K exp (−3 lnn) = √ 6 n2 log2n, (141) where a ...

  3. [11]

    If λ∈I2, by Lemma 16 and assumption, ρ(A(λ)) =|x2| = √ c(1−δλ)≤√c. (142) Thus, by Lemma 17, ‖ ‖AK (λ) ‖ ‖≤ √ 6K [ρ(A(λ))]K−1≤ √ 6K (√c ) K−1 = √ 6K exp [ − (K− 1) lnc 2 ] a ≤ √ 6K exp [ − (K− 1)(1−c) 2 ] b ≤ √ 6K exp [ − 8(K− 1) lnn K ] ≤ √ 6K exp (−6 lnn) = √ 6 n5 log2n≤ √ 6 ...

  4. [12]

    If λ∈I2, by Lemma 16 and assumption, ρ(A(λ)) =|x2|≤ cδ q ≤c. (144) Thus, by Lemma 17, ‖ ‖AK (λ) ‖ ‖≤ √ 6K [ρ(A(λ))]K−1≤ √ 6KcK−1 = √ 6K exp [−(K− 1) lnc] a ≤ √ 6K exp [−(K− 1)(1−c)] b ≤ √ 6K exp [ − 16(K− 1) lnn K ] ≤ √ 6K exp (−12 lnn) = √ 6 n11 log2n≤ √ 6 n2 log2n, (145) whe...

  5. [13]

    (148) Since x1x2 =c(1−δλ), we have c≤x1≤x2

    If λ∈I1, by Lemma 16, and δ≤q, we have ak≥ 0, and x1≤x2≤ 1− q−cδ 1−c λ≤ 1−δλ. (148) Since x1x2 =c(1−δλ), we have c≤x1≤x2. Therefore, ak+1−cak≥ak+1−x1ak =xk 2 > 0, ak+1−cak≤ak+1−x1x2ak = k∑ i=0 xi 1xk−i 2 −x1x2 k−1∑ i=0 xi 1xk−1−i 2 = k∑ i=0 xi 1xk−i 2 −x2 k∑ i=1 xi 1xk−i 2 =xk...

  6. [14]

    Let x1,2 =r(cosθ± i sinθ), we have r = √ c(1−δλ)≤ 1 and 0≤θ≤π/2 where 2r cosθ =x1 +x2 = 1 +c−qλ≥ 0 from Lemma 5

    If λ∈I2, by Lemma 16, x1 and x2 are complex and conjugate. Let x1,2 =r(cosθ± i sinθ), we have r = √ c(1−δλ)≤ 1 and 0≤θ≤π/2 where 2r cosθ =x1 +x2 = 1 +c−qλ≥ 0 from Lemma 5. Thus ak+1−cak =rk sin ((k + 1)θ) sinθ − rk−1 sin (kθ) sinθ a=rk−1 ( r coskθ + r cosθ−c sinθ sinkθ ) =rk−1...

  7. [15]

    (151) By triangular inequality, and |sinkθ|≤ 1,|coskθ|≤ 1, ⏐ ⏐tan θ 2 ⏐ ⏐≤ 1 |ak+1−cak|≤rk−1 ( r|coskθ| +|r−c| ⏐ ⏐ ⏐ ⏐ sinkθ sinθ ⏐ ⏐ ⏐ ⏐ ) +rk ⏐ ⏐ ⏐ ⏐tanθ 2 ⏐ ⏐ ⏐ ⏐|sinkθ| a ≤rk−1 (r +k(1−r)) +rk =rk−1 (1 + (k− 1)(1−r)) +rk b ≤2, (152) where a ≤ holds for r2≤c≤ 1 =⇒ |r−c|≤ ma...

  8. [16]

    If λ∈I3, by Lemma 16, and δ≤q, we have ak≥ 0, and x1≤x2≤ cδ q ≤c. (153) Therefore, ak+1−cak≥ak+1−ak = k∑ i=0 xi 1xk−i 2 − k−1∑ i=0 xi 1xk−1−i 2 =xk 1− (1−x2) k−1∑ i=0 xi 1xk−1−i 2 ≥xk 1−k(1−x2)xk−1 2 ≥− xk−1 2 ( 1 + (k− 1)xk 2 ) a ≥− 1, ak+1−cak≤ak+1−x2ak =xk 1≤ 1, (154) where...

    2024

  9. [18]

    [2024], we have ( U(ℓ),i ) 22 = δ(ℓ) 2 + (1 +c)(q(ℓ)−δ(ℓ)) 2 ( 1−c2 +cλi(q(ℓ) +cδ(ℓ)) ) ; (175)

    By Equation (F.9) of Li et al. [2024], we have ( U(ℓ),i ) 22 = δ(ℓ) 2 + (1 +c)(q(ℓ)−δ(ℓ)) 2 ( 1−c2 +cλi(q(ℓ) +cδ(ℓ)) ) ; (175)

    2024

  10. [19]

    We have ( U(ℓ),i ) 22≤ δ 2 + c3 2ψ˜κλi (176)

  11. [20]

    [2018], we have ( U(ℓ),i ) 11 = (1− 2δ(ℓ)λi) ( U(ℓ),i ) 22 +δ2 (ℓ)λi

    By Equation (44) of Jain et al. [2018], we have ( U(ℓ),i ) 11 = (1− 2δ(ℓ)λi) ( U(ℓ),i ) 22 +δ2 (ℓ)λi

    2018

  12. [21]

    We have ( U(ℓ),i ) 11≤ ( U(ℓ),i ) 22, and U(ℓ),i≼ 2 ( U(ℓ),i ) 22 I

  13. [22]

    U(ℓ),i≼ Q(ℓ),i≼ 4 3 U(ℓ),i 42

  14. [23]

    By Equation (56), (61) and (63) of Jain et al. [2018], we have ( U(ℓ),i ) 11 = (1 +c−cδiλi)(q(ℓ)−cδ(ℓ))− 2δ(ℓ)λi(q(ℓ)−cδ(ℓ)) + 2δ2 (ℓ)λi 2(1−c2 +cλi(q(ℓ) +cδ(ℓ))) , ( U(ℓ),i ) 12 = ( 1 +c−λi(q(ℓ) +cδ(ℓ)) ) (q(ℓ)−cδ(ℓ)) +δ(ℓ)λi(q(ℓ) +cδ(ℓ)) 2(1−c2 +cλi(q(ℓ) +cδ(ℓ))) , ( U(ℓ),i ...

    2018

  15. [24]

    We have U(ℓ),i≼ 16U(ℓ+1),i

  16. [25]

    We have Q(ℓ),i≼ 20Q(ℓ+1),i. Proof. For Item 2, For Item 4, from Item 1, we know ( U(ℓ),i ) 22≥δ/2. And from Item 3, ( U(ℓ),i ) 11 = ( U(ℓ),i ) 22− 2δ(ℓ)λi ( U(ℓ),i ) 22 +δ2 (ℓ)λi ≤ ( U(ℓ),i ) 22− 2δ(ℓ)λi· δ(ℓ) 2 +δ2 (ℓ)λi = ( U(ℓ),i ) 22. (178) Thus, we have U(ℓ),i≼ ( tr U(ℓ),...

  17. [26]

    (180) Plugging this into ( 171) completes the proof. For Item 7, from Item 6, we split the numerator of U(ℓ),i into two parts, based on whether the term contains λi, num ( U(ℓ),i ) 11 = (1 +c)(q(ℓ)−cδ(ℓ))/bracehtipupleft/bracehtipdownright/bracehtipdownleft/bracehtipupright M1...

  18. [29]

    We assume λi ≂ i−a, λi/mi ≂ i−b and tii ≲ i−a+κ

    Let tii denote the i-th diagonal element of T. We assume λi ≂ i−a, λi/mi ≂ i−b and tii ≲ i−a+κ. Therefore, tii/mi ≲ i−b+κ

  19. [30]

    Note that distributions in r-smooth class satisfies the above assumption with ν = 0

    We assume that ‖ ‖ ‖M−1/2Ti:∞M−1/2 ‖ ‖ ‖ ≲ i−b+κ+ν, where 0≤ν≤ 1. Note that distributions in r-smooth class satisfies the above assumption with ν = 0. The following lemmas provide the convergence rate of ASGD. Lemma 31. Suppose Assumptions 3, 4 and 7 hold, and κ<b −ν. For the r...

  20. [32]

    Then ri ≂ i−a+κ and ri/mi ≂ i−b+κ

    Recall that R def = cS1/2DS1/2 is diagonal. Then ri ≂ i−a+κ and ri/mi ≂ i−b+κ

  21. [33]

    Then we have tii ≲ i−a+κ and tii/λi ≲ iκ for any integeri∈ [d], where tii denotes the i-th diagonal element of T

    For any Qx∈Q and let T = EQx [ xx⊤] . Then we have tii ≲ i−a+κ and tii/λi ≲ iκ for any integeri∈ [d], where tii denotes the i-th diagonal element of T

  22. [34]

    Then we have ‖ ‖T′ i:∞,i:∞ ‖ ‖ ≲ i−b+κ for any integer i∈ [d]

    For any Qx∈Q and let T′ = M−1/2EQx [ xx⊤] M−1/2. Then we have ‖ ‖T′ i:∞,i:∞ ‖ ‖ ≲ i−b+κ for any integer i∈ [d]. Proof. 1. Note that ri =λi·iκ ≂ i−a+κ and ri/mi ≂ (λi/mi)·iκ ≂ i−b+κ

  23. [35]

    From Definition 2, we have T≼ CS1/2DS1/2≼ C diag{λi·iκ}d i=1, Therefore, tii≤Cλ i·iκ ≲ i−a+κ. (249)

  24. [36]

    From Item 1, we have ‖ ‖T′ i:∞,i:∞ ‖ ‖≤C‖diag{(λi+1/mi+1)· (i + 1)κ,..., (λd/md)·dκ}‖≤ i−b+κ

    Note that T′≼ CM−1/2S1/2DS1/2M−1/2 =C diag{(λi/mi)·iκ}d i=1. From Item 1, we have ‖ ‖T′ i:∞,i:∞ ‖ ‖≤C‖diag{(λi+1/mi+1)· (i + 1)κ,..., (λd/md)·dκ}‖≤ i−b+κ. (250) The following lemma explicitly calculates the lower bound i n terms of σ2 andn given polynomial decaying conditions....

  25. [37]

    Note that Assumption 6 implies Assumption 7

    We set b =sa and κ =−ra. Note that Assumption 6 implies Assumption 7. Therefore, the upper bound part follows from Lemma 31 and Lemma 32. For the lower bound, Lemma 36 provides the case where κ≤− 1. For κ> −1, Lemma 37 shows that inf ˆw sup ˜P ∈P(W,S,T) E ˜P ⊗n×Pξ ‖ ˆw− w∗‖2 T...

  26. [109]

    (221) This form is identical to the recursion of ˜Ct if we replace 4 ‖w∗‖2 S by σ2

    and Lemma 28, we have: B(1) t =Bt◦ B(1) t−1 + E [ ˆGt⊗ ˆGt ] ◦ ˜Bt−1 ≼B t◦ B(1) t−1 + 4‖w∗‖2 S· [ δ2 t S δtqtS δtqtS q2 t S ] . (221) This form is identical to the recursion of ˜Ct if we replace 4 ‖w∗‖2 S by σ2. Therefore, we apply Lemma 7 to obtain ⟨ ˜T, B(1) n ⟩ ≤‖ w0− w∗‖2 ...

  27. [173]

    The following lemma characterizes U(ℓ),i and Q(ℓ),i

    yields the desired result. The following lemma characterizes U(ℓ),i and Q(ℓ),i. Lemma 26. With U(ℓ),i defined in (170), we have

  28. [208]

    (211) Note that T≼ 2T0:k∗ + 2Tk∗:∞

    and ( 208) implies that ([ ξ1 O ]) 2 i ≤ (w0− w∗)2 i 8n2(log2n)4, ([ O ξ2 ]) 2 i ≤ 4(w0− w∗)2 i. (211) Note that T≼ 2T0:k∗ + 2Tk∗:∞. Then we have ⟨ ˜T, ˜Bn ⟩ ≤2 ⟨ T0:k∗, ˜Bn ⟩ + 2 ⟨ Tk∗:∞, ˜Bn ⟩ =2 ‖ ‖ ‖ ‖ [ ξ1 O ] ‖ ‖ ‖ ‖ 2 T0:k∗ + 2 ‖ ‖ ‖ ‖ [ O ξ2 ] ‖ ‖ ‖ ‖ 2 Tk∗:∞ ≤ max w∈S...

  29. [242]

    (244) We can write out the following equivalent form: min ai,τ ≥0 τ 2 π2 + d∑ i=1 σ2a2 iri nλi , s.t.∀i∈ [d], (1−ai)2ri mi ≤τ 2

    is equivalent to min ai max k∈[d] (1−ak)2rk π2mk + d∑ i=1 σ2a2 iri nλi . (244) We can write out the following equivalent form: min ai,τ ≥0 τ 2 π2 + d∑ i=1 σ2a2 iri nλi , s.t.∀i∈ [d], (1−ai)2ri mi ≤τ 2. (245) 57 We first minimize the above program with respect to ai to get ai = ...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.