Machine Learning
  • Introduction
  • man
  • Linear model
    • Linear Regression
    • Generalized Linear Models
    • Nonlinear regression
  • bayes
    • bayesian network
    • Variational Bayesian inference
    • Gaussian Process Regression
  • Logistic Regression
    • L1 regularization
    • L2 regularization
    • softmax
    • Overflow and Underflow
  • SVM
    • C-SVM
    • C-SVM求解
  • EM
    • GMM
  • Maximum Entropy
    • IIS
  • HMM
    • viterbi algorithm
  • CRF
  • Random Forest
    • bagging
    • random forest
  • boosting
    • catboost
    • gradient boosting
    • Newton Boosting
    • online boosting
    • gcForest
    • Mixture models
    • XGBoost
    • lightGBM
    • SecureBoost
  • LDA
  • rank
    • RankNet
    • LambdaRank
    • SimRank
  • Factorization Machine
    • Field-aware Factorization Machine
    • xdeepFM
  • Clustering
    • BIRCH
    • Deep Embedding Clustering
  • Kalman filtering
  • word2vec
  • 关联规则挖掘
  • MATH-Mathematical Analysis
    • measure
  • MATH-probability
    • Variational Inference
    • Dirichlet分布
    • Gibbs Sampling
    • Maximum entropy probability distribution
    • Conjugate prior
    • Gaussian Process
    • Markov process
    • Poisson process
    • measure
    • Gumbel
  • MATH-Linear Algebra
    • SVD
    • SVD-推荐
    • PCA
    • Linear Discriminant Analysis
    • Nonnegative Matrix Factorization
  • MATH-Convex optimization
    • 梯度下降
    • 随机梯度下降
    • 牛顿法
    • L-BFGS
    • 最速下降法
    • 坐标下降法
    • OWL-QN
    • 对偶问题
    • 障碍函数法
    • 原对偶内点法
    • ISTA
    • ADMM
    • SAG
  • MATH-碎碎念
    • cost function
    • Learning Theory
    • sampling
    • Entropy
    • variational inference
    • basis function
    • Diffie–Hellman key exchange
    • wavelet transform
    • 图
    • Portfolio
    • 凯利公式
  • ML碎碎念
    • 特征
    • test
    • TF-IDF
    • population stability index
    • Shapley Values
  • 课件
    • xgboost算法演进
  • Time Series
  • PID
  • graph
    • SimRank
    • community detection
    • FRAUDAR
    • Anti-Trust Rank
    • Struc2Vec
    • graph theory
    • GNN
  • Anomaly Detection
    • Isolation Forest
    • Time Series
  • Dimensionality Reduction
    • Deep Embedded Clustering
  • Federated Learning
  • automl
  • Look-alike
  • KNN
  • causal inference
Powered by GitBook
On this page
  • 分块坐标下降###
  • 脑洞大开###

Was this helpful?

  1. MATH-Convex optimization

坐标下降法

不是求整个变量的梯度,然后下降,而是循环的沿着变量的每一维进行单变量优化。

xik+1=arg⁡min⁡ϵ∈Rf(x1k+1,x2k+1,…,xi−1k+1,ϵ,xi+1k,…,xnk)x_i^{k+1} =\arg \min_{\epsilon \in R} f(x_1^{k+1},x_2^{k+1}, \ldots ,x_{i-1}^{k+1},\epsilon,x_{i+1}^{k},\ldots,x_n^k)xik+1​=argϵ∈Rmin​f(x1k+1​,x2k+1​,…,xi−1k+1​,ϵ,xi+1k​,…,xnk​)

此方法收敛性与最速下降法类似。

单变量优化优点:

  • 有可能可以精确直线搜索,或者单维度的牛顿法,等可以得到子问题的最优解。

  • 可并行:将内循环的迭代变成单步并行。不过这点依赖于目标函数的结构,变量之间是否能否解耦。

内循环不一定要按维度下标依次迭代,可以乱序,自适应等。

分块坐标下降###

如果不能全变量解耦,那么希望变量之间能够分块解耦。

f(x)=∑i=1mfi(xi),xi∈XiX=X1⊕X2⊕…Xnf(x) = \sum_{i=1}^m f_i (x_i), \qquad x_i \in X_i X = X_1 \oplus X_2 \oplus \ldots X_nf(x)=i=1∑m​fi​(xi​),xi​∈Xi​X=X1​⊕X2​⊕…Xn​

脑洞大开###

可否在最速下降与坐标下降做折衷,每次迭代只取梯度中最大的top k个分量。 好像一般函数,变化最大的几个分量“都在一起”。而且就那么2~3个变化很快,所以k就取2或3. 缺点:这样就不容易精确直线搜索,或者单维度的牛顿法等。

Previous最速下降法NextOWL-QN

Last updated 5 years ago

Was this helpful?