PaperlayerView exact revision on arXiv

Source-linked AI summary

I-LAMM for Sparse Learning: Simultaneous Control of Algorithmic Complexity and Statistical Error

Jianqing Fan, Han Liu, Qiang Sun, Tong Zhang

arXiv:1507.01037v3math.STstat.TH

TL;DR

I-LAMM addresses the gap between what is computed for folded-concave penalized models and what existing theory proves. It uses adaptive local linear approximation with a sequence of approximately solved convex programs, and the authors report polynomial-time computation with optimal statistical accuracy.

  • Problem

    For folded-concave penalized models, the computed solution can differ from what has been proved, while convex penalties introduce non-negligible estimation bias.

    Source: §1 · p. 2

  • Method

    I-LAMM applies adaptive local linear approximation to the folded-concave penalty and approximately solves a sequence of convex programs, beginning with an initial estimator for later optimization.

    Source: §1 · p. 3, §2.1 · p. 7, §2.3 · p. 11

  • Results

    I-LAMM computes an estimator within polynomial time and achieves optimal statistical accuracy for that estimator.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Localized analysis eliminates extra ball constraints from prior work, which the authors say require more tuning and are intuitively redundant given the penalty.

    Source: §7 · p. 27

    With λ held fixed and no further structure, the first-stage sublinear rate is the best possible for this procedure.

    Source: §4.3 · p. 19

Abstract

from arXiv · show

We propose a computational framework named iterative local adaptive majorize-minimization (I-LAMM) to simultaneously control algorithmic complexity and statistical error when fitting high dimensional models. I-LAMM is a two-stage algorithmic implementation of the local linear approximation to a family of folded concave penalized quasi-likelihood. The first stage solves a convex program with a crude precision tolerance to obtain a coarse initial estimator, which is further refined in the second stage by iteratively solving a sequence of convex programs with smaller precision tolerances. Theoretically, we establish a phase transition: the first stage has a sublinear iteration complexity, while the second stage achieves an improved linear rate of convergence. Though this framework is completely algorithmic, it provides solutions with optimal statistical performances and controlled algorithmic complexity for a large family of nonconvex optimization problems. The iteration effects on statistical errors are clearly demonstrated via a contraction property. Our theory relies on a localized version of the sparse/restricted eigenvalue condition, which allows us to analyze a large family of loss and penalty functions and provide optimality guarantees under very weak assumptions (For example, I-LAMM requires much weaker minimal signal strength than other procedures). Thorough numerical results are provided to support the obtained theory.

1. Introduction.

High-dimensional nonconvex penalized estimation separates statistical guarantees from practical algorithms; I-LAMM approximately solves a sequence of convex programs using an adaptive local linear approximation. Its computed estimator achieves optimal statistical properties with controlled computation, while convergence shifts from sublinear to linear after entering the contraction region.

1. Introduction.

  • Convex penalties such as Lasso can introduce non-negligible estimation bias, while folded-concave penalties reduce bias but make theoretical analysis harder.Prior work established properties for hypothetical global or local solutions, while heuristic algorithms lacked theoretical guarantees.Source: §1 · p. 2
  • I-LAMM addresses the gap between statistical guarantees for nonconvex estimators and practical algorithms by guaranteeing optimal accuracy for its polynomial-time computed estimator.Unlike existing works, it imposes no constraint depending on the unknown true parameter.Source: §1 · pp. 2–3
  • I-LAMM uses adaptive local linear approximation to solve convex programs: a crude initial estimate is followed by iterative tightening toward the optimal region.Tightening improves accuracy only while estimation error exceeds the statistical error; each refined estimate supplies an adaptive weight for the next step.Source: §1 · pp. 3–4
  • Under mild conditions, only log(λ√n) steps are needed to obtain the optimal statistical rate, and approximate solutions retain the global optimum’s optimal statistical property.Adaptive stopping controls both computational costs and statistical errors.Source: §1 · p. 3
  • The first-stage algorithm converges sublinearly, then linearly after entering the contraction region; later tightening steps converge linearly.Within that region, feasible solutions are sparse and the objective is essentially low-dimensional, restricted strongly convex, and smooth.Source: §1 · pp. 4–5, Figure 2 · p. 5
  • Localized analysis lets I-LAMM avoid extra ball constraints used in and [28], while covering a broad family of losses and folded-concave penalties.The framework encompasses square, logistic, Gaussian graphical model negative log-likelihood, and Huber losses.Source: §1 · pp. 2, 6

2. Methodology.

I-LAMM uses adaptive local linear approximation and locally majorized convex subproblems to solve folded-concave penalized objectives. It first obtains a coarse contraction estimator, then tightens it with more precise solves.

2.1. Local Adaptive Majorize-Minimization.

  • Adaptive local linear approximation replaces a folded-concave penalty with a sequence of convex problems using weights corresponding to the penalty derivative.SCAD and MCP fit the stated tightening function class; the ℓq-penalty case with q < 1 is excluded because its derivative is unbounded at zero.Source: §2.1 · p. 7
  • LAMM locally majorizes the loss with an isotropic quadratic and increases its scale until the local property holds, avoiding a large Hessian and enabling a simple update.The isotropic parameter is inflated geometrically from an initial value until the local condition is satisfied.Source: §2.1 · p. 8

2.2. Stopping Criterion.

  • Each subproblem stops when its suboptimality measure is at most the prefixed optimization error ε, yielding an ε-optimal solution.I-LAMM distinguishes contraction-stage precision εc from tightening-stage precision εt.Source: §2.2 · p. 10, Figure 3 · p. 10

2.3. Tightening After Contraction.

  • The contraction stage starts from an arbitrary initial value and uses a coarse precision to bring the estimator into a contraction region for tightening.The initial estimator is sparse but has a suboptimal statistical rate.Source: §2.3 · p. 11
  • In the tightening stage, successive convex programs refine the estimator; once it reaches the optimal convergence region, further iterations do not improve statistical performance.Because these initial estimators are already in the contraction region, the optimization has a geometric convergence rate and can use smaller optimization error.Source: §2.3 · p. 11

3. New Insights into Existing Methods.

I-LAMM extends local linear approximation to high-dimensional settings where a good unbiased initializer may be unavailable, and uses an isotropic approximation to avoid costly Hessian computations. Its framework connects adaptive Lasso and folded-concave regularization, with iterative refinement and bounded weights addressing limitations of one-step and classical adaptive-Lasso procedures.

3.1. Connection to One-step Local Linear Approximation.

  • Starting from a possibly poor initial value, the contraction stage produces a sparse coarse estimator that subsequent tightening steps refine toward the optimal convergence region.This differs from one-step LLA, whose oracle result relies on maximum-likelihood initialization, unavailable in high dimensions.Source: §3.1 · p. 12
  • The isotropic quadratic approximation avoids computing and storing a high-dimensional Hessian, which the cited local quadratic approach requires.The paper also notes that the Hessian-based approximation does not yield an analytically solvable optimization problem.Source: §3.1 · p. 12

3.2. New Insight into Folded-concave Regularization and Adaptive Lasso.

  • For adaptive Lasso weights in the tightening class, the framework's optimal solution requires tuning only the contraction-stage λ(0), so sequential tuning may be unnecessary.The passage contrasts this with a two-stage cross-validation procedure lacking theoretical guarantees.Source: §3.2 · p. 13
  • The classical adaptive-Lasso weight 1/|βj| is outside the tightening class and can make zero absorbing; bounded weights in the proposed class avoid that behavior.If the first-stage Lasso misses a true positive, it can remain missed in later stages under the classical weight.Source: §3.2 · p. 13
  • With a suitable weight function, adaptive Lasso is a special case of the framework, while taking the iterations to convergence recovers folded-concave penalized regression.For ℓ of order log(λ√n), the proposed estimator has the optimal statistical rate under mild conditions.Source: §3.2 · p. 14

4. Theoretical Results.

The theory uses eigenvalue conditions localized around the true parameters to handle losses whose Hessians vary with the parameters. Under these conditions, I-LAMM’s tightening steps refine statistical error while the two stages have different iteration rates.

4.1. Localized Eigenvalues and Assumptions.

  • For logistic loss, the Hessian can become nearly singular as the parameter norm grows, motivating eigenvalue conditions localized around the true parameter.The paper states that the needed conditions concern neighborhoods of the true parameters rather than all parameter values.Source: §4 · p. 14, §4.1 · p. 14

4.1.1. Localized Sparse Eigenvalue.

  • The localized sparse eigenvalue condition is presented as the weakest condition in the literature, while the localized restricted eigenvalue condition is an alternative for general parameter-dependent Hessians.For quadratic loss, the localized sparse eigenvalues reduce to commonly used sparse eigenvalues; the localized restricted eigenvalue likewise reduces to the usual restricted eigenvalue when the Hessian is parameter-independent.Source: §4.1.1 · p. 15, §4.1.2 · p. 16

4.2. Statistical Theory.

  • Under the stated assumptions, the contraction-stage estimator has error of order λ√s, and the later tightening steps can achieve the oracle rate with optimization error εt ≲ 1/n.For the quadratic-loss corollary, the oracle rate is p(s/n), as if the true support were known in advance.Source: §4.2 · pp. 16–17
  • Each tightening step contracts the influence of the previous estimator’s error by a δ fraction, and suitable optimization precision yields the oracle statistical rate.The contraction-stage estimator has error of order λ√s; achieving the oracle rate requires greater precision in the tightening stage, not both stages.Source: §4.2 · pp. 16–17
  • For sufficiently large iterations and the stated signal and regularity conditions, I-LAMM has a strong oracle property; the oracle estimator is a fixed point of the algorithm.The oracle estimator depends on intrinsic dimension s rather than ambient dimension d, supporting the stated mildness of the max-norm condition.Source: §4.2 · p. 18

4.3. Computational Theory.

  • The contraction stage has sublinear iteration complexity, whereas each tightening subproblem has a geometric rate and needs logarithmically many iterations to reach precision ε.The first-stage sublinear rate reflects the lack of strong convexity before entering the contraction region; the tightening-stage rate follows once sparse strong convexity applies.Source: §4.3 · pp. 18–19
  • With λ√s=o(1), the total-complexity result requires a crude first-stage tolerance and smaller tolerances in later stages; without further structure and with fixed λ, the first-stage sublinear rate is best possible for this procedure.The authors note that a sufficiently good initial value can yield a linear rate, or a path-following method can gradually reduce λ [28].Source: §4.3 · p. 19

5. Proof Strategy for Main Results.

The proof strategy links statistical refinement to a contraction property and computational efficiency to early stopping followed by localized geometric convergence. Sparsity and entry into the contraction region support the tightening-stage analysis.

5.1. Proof Strategy for Statistical Recovery Result in Section 4.2.

  • Each tightening step reduces the influence of the previous estimator’s error by a δ fraction, while the tightening weight separates coefficient effects from prior-step estimation error.When true coefficients exceed the stated threshold, the coefficient-effect term becomes zero; combining the bounds yields a refined statistical rate.Source: §5.1 · pp. 20–21

5.2. Proof Strategy for Computational Result in Section 4.3.

  • Because optimization error decreases at rate 1/k while the contraction-stage statistical rate is only order λ√s, LAMM can stop once the iterate enters the contraction region.The localized analysis then supports the geometric convergence result for each tightening subproblem.Source: §5.2 · p. 22
  • The contraction estimator is s + es sparse and falls in the contraction region, which enables use of the localized sparse eigenvalue condition in the tightening-stage analysis.The proof bounds the entropy-set size by 2s and the contraction-stage error by order λ√s.Source: §5.1 · p. 20, §5.2 · p. 22
  • Each tightening subproblem converges geometrically, described as the fastest possible rate among first-order methods under the blackbox model.This result is used to obtain the iteration-complexity bound for each tightening step.Source: §5.2 · p. 22

5. Proof Strategy for Main Results.

  • The paper evaluates the framework’s statistical performance through numerical experiments covering three examples.The supplied passage does not report the outcomes of those experiments.Source: §6 · p. 23

6. Numerical Examples.

The numerical examples compare I-LAMM with other estimators in linear and logistic regression, including settings with varying dimensions and sample sizes. I-LAMM has the best overall performance in the reported comparisons, while its iteration behavior exhibits the predicted phase transition.

6. Numerical Examples.

  • The simulations include independent, constant-correlation, and autoregressive correlation designs; logistic regression uses independent binary-response observations, while autoregressive linear regression varies d=1000–3500 and n=100–500.Each simulation setting uses 100 datasets; Figure 4 reports median MSE for the varying-dimensions and sample-sizes example.Source: §6 · pp. 23–24, Figure 4 · p. 25
  • I-LAMM achieves small MSE and FP in all reported cases and the best overall performance; Table 1 reports the median metrics for linear and logistic regression.The comparison includes Cases 1–3 for linear regression and logistic regression.Source: Table 1 · p. 24, §6 · p. 25
  • In the strongly correlated linear-regression case, MCP, SCAD, and ALasso miss true positives, while I-LAMM remains best, followed by Lasso.The passage identifies this as Case 3 and attributes its design to strong feature correlation.Source: §6 · pp. 23, 25
  • As dimension increases, SCAD and MCP quickly break down, while I-LAMM's MSE remains flat; with increasing sample size, I-LAMM, SCAD, and MCP perform almost identically.The authors suggest numerical instability from directly solving nonconvex systems as a possible explanation for the dimension-related breakdown.Source: §6 · p. 25
  • The contraction stage moves from sublinear convergence to a geometric rate after entering the contracting region, while the tightening stage converges geometrically.The plotted iteration behavior is reported for Case 2 of Example 6.1 and is said to agree with the asymptotic theory.Source: §6 · pp. 25–26

7. Conclusions and Discussions.

The discussion presents localized analysis and explicit optimization precision as distinguishing features of I-LAMM's theory. It also identifies extensions and distributed-system questions as directions for future work.

7. Conclusions and Discussions.

  • Compared with calibrated CCCP, I-LAMM's analysis handles a broader family of loss functions than the least-squares analysis described for that method.The discussion also contrasts the procedures' minimum-signal-strength requirements, but the supplied text does not give a complete expression for I-LAMM's requirement.Source: §7 · p. 26
  • Localized analysis removes the extra ball constraints used in prior work, which the authors describe as adding tuning effort and being intuitively redundant given the penalty.The discussion contrasts this analysis with work that did not have the localized-analysis notion.Source: §7 · p. 27
  • The statistical results account for explicit computational precision, and the computational results apply to approximate solutions and do not require path-following.The authors state that any algorithm with desired statistical properties may serve as a building block within tightening steps.Source: §7 · p. 27
  • I-LAMM provides a refined oracle statistical rate for obtained approximate solutions, a result the authors say and [28] do not provide.The discussion contrasts this with 's rate achievable using convex Lasso and [28]'s oracle rate for exact local solutions.Source: §7 · p. 27
  • Applications to matrix completion, graphical models, and quantile regression are proposed as future directions, alongside studying distributed-system tradeoffs.The authors frame the listed applications as conjectured and leave communication-versus-time complexity questions for future research.Source: §7 · p. 27

Supplementary Material to “I-LAMM: Simultaneous Control of Algorithmic Complexity and Statistical Error”

The supplementary material collects proofs and technical lemmas, and its general-loss appendix specifies a class of losses and gives examples and an extension strategy.

Supplementary Material to “I-LAMM: Simultaneous Control of Algorithmic Complexity and Statistical Error”

  • The supplementary material contains proofs of several Section 4 results, key Section 5 lemmas, and an application to robust linear regression.It also collects additional technical lemmas.Source: Supplementary Material to “I-LAMM:… · p. 30

APPENDIX A: GENERAL CONVEX LOSS FUNCTIONS

  • Appendix A assumes a convex loss with continuous first derivative that is locally twice differentiable almost everywhere.The stated differentiability conditions apply in a neighborhood of the target parameter.Source: Appendix A · p. 30
  • The appendix lists logistic, Huber, Gaussian graphical-model, least-squares, and locally twice differentiable convex composite likelihood losses as examples in or related to the family.For a nonconvex loss, it proposes separating convex and concave parts and treating the concave part with the penalty, subject to the stated weight-function assumption.Source: Appendix A · pp. 30–31

APPENDIX B: PROOFS OF STATISTICAL THEORY

Appendix B collects proofs and technical lemmas and establishes parallel results under the localized restricted eigenvalue condition.

APPENDIX B: PROOFS OF STATISTICAL THEORY

  • The appendix collects proofs for Corollary 4.3 and Theorem 4.4.Source: Appendix B · p. 31
  • Its key technical lemmas in Section 5.1 are used to prove Theorem 4.2.Source: Appendix B · p. 31
  • The appendix also establishes parallel results under the localized restricted eigenvalue condition.Source: Appendix B · p. 31

B.1. Statistical Theory under LSE Condition.

The proofs establish a strong oracle property under the LSE condition and develop local sparse-eigenvalue bounds used to support the statistical analysis.

B.1. Statistical Theory under LSE Condition.

  • The proof uses a logarithmic number of tightening steps, on the order of log(λ√n), to reach the oracle-rate argument.The surrounding proof invokes Theorem 4.2 to establish the oracle rate.Source: §B.1 · p. 32
  • The estimator enjoys the strong oracle property when the stated signal and tolerance conditions make the remaining inequality sufficiently small.The proof also requires the tightening tolerance εt to be sufficiently small.Source: §B.1 · p. 34

B.2. Key Lemmas.

  • The appendix connects the LSE condition to localized sparse strong convexity and smoothness, tools used in the theoretical analysis.The proof section also notes that a similar oracle-property result holds under the LRE condition.Source: §B.1 · p. 33, §B.2 · p. 35
  • For sparse vectors in a neighborhood of β*, the localized sparse eigenvalues bound the loss divergence above and below by quadratic terms.The proposition states the bound for pairs with at most m differing coordinates.Source: §B.2 · p. 35

B.3. Statistical Theory under LRE Condition.

Under a localized restricted eigenvalue condition, the analysis localizes approximate solutions so the condition can be applied, and establishes an optimal statistical-rate result.

B.3. Statistical Theory under LRE Condition.

  • The proof relates localized restricted eigenvalues to localized restricted strong convexity and smoothness over the specified cone and neighborhood.The proposition bounds the loss divergence using the localized eigenvalue quantities.Source: §B.3 · p. 36
  • Theorem B.6 establishes an optimal statistical rate for tightening-stage εt-optimal solutions under the stated localized restricted-eigenvalue conditions.The supplied theorem passage does not include the rate expression.Source: §B.3 · p. 37
  • The figure caption gives λ√s as the contraction-stage rate and s/n as the tightening-stage rate for the intermediate solution.It states that the approximate solution has the same rate under mild conditions.Source: Figure 5 · p. 38
  • The localization argument constructs an intermediate solution within radius r of β*; the approximate solution then falls in the region where LRE applies.Under mild conditions, the caption says the approximate and intermediate solutions coincide.Source: §B.3 · pp. 38–39, Figure 5 · p. 38

APPENDIX C: COMPUTATIONAL THEORY

  • Appendix C states that its computational-theory proofs cover Propositions 4.5 and 4.6 and Theorem 4.7, with separate quadratic coefficients for the two stages.It denotes the contraction-stage coefficient by φc and the tightening-stage coefficient by φt.Source: Appendix C · p. 41, §C.1 · p. 41

C.1. Proofs of Main Results.

These appendix proofs trace the computational guarantees through descent and stopping arguments, alongside lemmas for the tightening and support analysis.

C.1. Proofs of Main Results.

  • The proof records a nonincreasing sequence of penalized objectives across contraction-stage iterates.The displayed sequence runs from the approximate solution through the iterates to the initial point.Source: §C.1 · p. 42
  • The contraction-stage proof starts from an estimator with ℓ2 error at most 18λ√s and derives a sufficient inner-iteration condition for the stopping tolerance.The sufficient condition itself is not visible in the supplied passage.Source: §C.1 · p. 42

C.2. Key Lemmas.

  • The support lemma bounds the active set by decomposing it into two parts and bounding their sizes separately.The proof then uses that bound to control the estimator's support.Source: §C.2 · p. 44
  • The tightening-stage proof uses majorization of the objective along the segment between successive iterates to bound the update.It invokes convexity of the loss in the argument.Source: §C.2 · pp. 45–46

APPENDIX D: AN APPLICATION TO ROBUST LINEAR REGRESSION

The appendix applies the theory to robust linear regression and develops technical tools for localized covariance and estimation analysis.

APPENDIX D: AN APPLICATION TO ROBUST LINEAR REGRESSION

  • With only finite second moments, the sparse Huber estimator with adaptive cutoff α can perform as well as sparse ordinary least squares under sub-Gaussian errors.The corollary states this comparison under its specified assumptions and probability guarantee.Source: Appendix D · p. 47

APPENDIX E: TECHNICAL LEMMAS

  • The technical lemmas define a localized sparse relative covariance and distinguish it from restricted correlation by measuring covariance relative to set I.The passage says a subsequent result bounds this quantity using sparse eigenvalues.Source: §E.1 · p. 48

E.1. Statistical Theory.

  • The E.1 proof constructs an intermediate estimator no farther than r from β*, then shows it coincides with the approximate estimator.The coincidence follows when the constructed estimator cannot lie on the radius-r boundary.Source: §E.1 · pp. 50, 52

E.2. Computational Theory.

The computational-theory section develops analytic and probabilistic results, linking iterate changes, suboptimality, sparsity, and estimation bounds across the contraction and tightening stages, establishing an ℓ1 cone property for approximate solutions, proving convexity of a pathwise divergence quantity, and stating a Hanson–Wright concentration result for independent sub-Gaussian variables.

E.2. Computational Theory.

  • Contraction-stage lemmas relate suboptimality to the distance between consecutive iterates, a relationship used to analyze iteration complexity.The analysis also characterizes the locality of the solution sequence.Source: §E.2 · pp. 52, 53, 55
  • An ε-optimal solution satisfies the stated ℓ1 estimation bound ∥eβ − β∗∥1 ≤ 90λs/ρ∗ under the conditions of the basic inequality.The bound follows from Lemma E.6 and its proof.Source: §E.2 · p. 56
  • For sparse approximate solutions within the stated localized conditions, tightening-stage lemmas provide parameter-estimation and objective-function bounds.The lemmas impose conditions on sparsity, suboptimality or objective gap, and proximity to β∗.Source: §E.2 · pp. 57–59
  • If es ≥ C0s under Lemma E.13’s conditions, one LAMM step produces a solution with at most es nonzeros outside E.Here C0 = 80γuρ∗/ρ∗max.Source: §E.2 · p. 60

APPENDIX F: PRELIMINARY LEMMAS.

  • Under the stated gradient-and-tolerance condition, an approximate solution’s ℓ1 error outside E is bounded by a factor times its ℓ1 error on E.Lemma F.1 gives the ℓ1 cone property for approximate solutions.Source: Appendix F · pp. 63–64

APPENDIX F: PRELIMINARY LEMMAS

  • The proof establishes convexity along the linear path by combining convexity of the Huber loss with bilinearity of the inner product.The pathwise argument is used in the proof concerning symmetric Bregman divergence.Source: Appendix F · pp. 64–65
  • The appendix states the Hanson–Wright inequality for a random vector with independent sub-Gaussian components and a universal constant independent of the matrix, vector, and dimension.The supplied passage describes the inequality as a general concentration result for quadratic forms; its bound is not visible in the excerpt.Source: Appendix F · p. 65

Related papers

Loading 1507.01037v3…