Lesi Chen (陈乐偲)

Lesi Chen (陈乐偲)

PhD student, IIIS, Tsinghua

Posts by Tags

GRE

GRE写作

1 minute read

Published:

GRE写作部分整理，包括写作词汇和作文模板

GRE同近义词

4 minute read

Published:

GRE同义词、近义词整理

GRE备考指南

less than 1 minute read

Published:

GRE备考指南，总结了笔者的GRE备考经验

GRE熟词僻义

less than 1 minute read

Published:

GRE熟词僻义整理

Transformer理论

GD is Optimal for In-Context Learning

9 minute read

Published:

Paper Reading: One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attention.

优化

Universal Parameter-Free GD

3 minute read

Published:

Paper Reading: DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method.

IAPTT for Bilevel Optimization

4 minute read

Published:

Paper Reading: Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond

BDA for Bilevel Optimization

5 minute read

Published:

Paper Reading: A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton.

BFGS的显式收敛率

5 minute read

Published:

本文主要讨论了关于经典、“贪心”的、随机的BFGS算法在解正定对称系统中的显式超线性收敛率。

Cubic Regularized Newton Method

8 minute read

Published:

三次正则牛顿方法或者称为Cubic Newton方法在非凸函数和凸函数上的全局收敛性分析。

Lower Bound for Smooth (Strongly) Convex Function

3 minute read

Published:

证明了对于连续可微的光滑-凸函数和光滑-强凸函数这两大类函数上一阶优化算法的复杂度下界，据此可以解释为什么Nesterov加速方法被称为最优算法。

Quasi-Newton and BFGS

13 minute read

Published:

整理了伪牛顿法的相关内容，篇幅大部分在于BFGS算法的收敛性和超线性收敛性的证明。

Estimate Sequence and AGD

4 minute read

Published:

Nesterov加速方法中的更细公式宛如神谕，此处记录Yurii Nesterov 在其 Lectures on Convex Optimization 一书中对该更新公式给出的解释，核心思想在于使用一个序列的收敛性替代函数值的收敛性。

FISTA: FAST Iterative Shrinkage-Thresholding Algorithm

4 minute read

Published:

FISTA（FAST Iterative Shrinkage-Thresholding Algorithm）是Nesterov加速算法在近端梯度下降方法上的一个特例，笔者第一次看Nesterov加速算法等的更新公式宛如神谕，可以感受到其神奇的加速过程，但不能理解其奥妙。遂撰写此文，记录FISTA的推导过程。

Sub-Gradient Descent and Proximal Gradient Descent

4 minute read

Published:

次梯度方法和近端梯度方法的入门级介绍，其中次梯度方法多用于不可导的凸优化问题，而近端梯度方法多用于不可导的凸正则问题。

(Conjugate) Gradient Descent

9 minute read

Published:

共轭梯度方法，既是数值算法中的重要内容，也是优化的一类重要算法。本文介绍从梯度方法到共轭梯度方法的分析，着重介绍收敛性对比分析和证明过程。

SVRG

3 minute read

Published:

论文阅读笔记：Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. NIPS 2013.

凸优化

分布式优化

博弈论

Smooth Nash Equilibria

7 minute read

Published:

Paper Reading: Smooth Nash Equilibria: Algorithms and Complexity.

双层优化

IAPTT for Bilevel Optimization

4 minute read

Published:

Paper Reading: Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond

BDA for Bilevel Optimization

5 minute read

Published:

Paper Reading: A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton.

变分不等式

图神经网络

图算法

近似最短路算法

2 minute read

Published:

图上所有结点对最短路的近似算法。

图的动态连通性问题

2 minute read

Published:

图的动态连通性问题。笔者对相关论文的数据结构和算法进行整理，但是只能窥得作者的妙思的一二，很多精髓仍未掌握。但将整理的内容配图放在这里，希望一来加深自己的理解，二来希望对后续读到相关工作的人有所帮助。

最短路算法

less than 1 minute read

Published:

本文总结了最短路的几个经典算法。由于笔者在网上看到的很多文章都对算法流程做了详细的介绍，但笔者发现大部分文章对算法正确性并没有给出证明，而这些证明对于初次接触的人并不是显然的，因此笔者决定撰写该文章也增进自己学习理解。

最大流与二分图

1 minute read

Published:

本文整理了关于最大流，以及其特例二分图最大图匹配的算法、正确性证明、复杂度证明。

最小生成树

less than 1 minute read

Published:

关于最小生成树的经典算法为Prim和Kruskal算法，很多文章都对其算法流程进行了详细的介绍，但对于其算法正确性的证明却常常忽略。笔者最初接触这两个算法的证明来自《算法导论》，但其中关于“安全边”等的繁琐定义和性质让笔者最初感觉不好理解，因此下面主要总结自己的理解。

图遍历算法

less than 1 minute read

Published:

DFS和BFS是最基础的图遍历算法，不论在图算法邻域还是其他各个邻域都极其重要，例如DFS中的搜索思想也是人工智能的基础。很多文章都对于DFS和BFS的直观理解做了很多解释，但对于DFS和BFS的重要性质却不够详细，因此本文主要总结了DFS和BFS的一些重要性质。

图编辑距离

复杂度下界

强化学习

马尔可夫决策过程

3 minute read

Published:

以经典模型展现马尔可夫决策过程的求解，主要包括：

连续状态马尔可夫决策过程：线性二次最优控制

离散状态马尔可夫决策过程：最优停止理论

深度强化学习

1 minute read

Published:

本文主要关注于使用深度学习方法进行强化学习，同样包括了基于值函数和策略函数的方法，再到演员-评论家算法等，并包含了模仿学习、逆向强化学习等的简介。

扩散模型

数值算法

曲线拟合和最佳逼近

3 minute read

Published:

曲线拟合本质上为数值逼近问题，本文将从曲线拟合的算法出发，并且分析最佳平方逼近和最佳一致逼近。

(快速)傅里叶变换

5 minute read

Published:

笔者在算法与数据结构、图像处理等领域都多次接触到傅里叶变换和快速傅里叶变换，但却一直未能窥其全貌，决定趁此机会好好整理。

非线性方程组的解法

3 minute read

Published:

本文包括了二分法及其变种，不动点迭代法，和基于不动点迭代法的Newton迭代法，以及Secant方法、Broyden方法等经典的伪Newton方法。

函数的插值

4 minute read

Published:

多项式插值的基本内容，包括经典的Lagrange,Neville,Newton插值方法，以及多项式重构问题以及Chebyshev插值，Hermite插值于矩阵函数的关系，样条插值以及其性质。

时间序列

时间序列

5 minute read

Published:

主要包括ARIMA的模型构建、识别、预测、估计等时间序列分析的核心内容。对于一般平稳时间序列的预测，从希尔伯特空间投影的角度给出Durbin-Levinson 算法的证明。对于一般的ARIMA模型，给出其长程预测的极限性质和基于递推公式的预测算法。

最大团

机器学习

牛顿法

Cubic Regularized Newton Method

8 minute read

Published:

三次正则牛顿方法或者称为Cubic Newton方法在非凸函数和凸函数上的全局收敛性分析。

Quasi-Newton and BFGS

13 minute read

Published:

整理了伪牛顿法的相关内容，篇幅大部分在于BFGS算法的收敛性和超线性收敛性的证明。

独立集

理论计算机科学

神经网络

线性回归

The Ideal Intepolator

1 minute read

Published:

Paper Reading: Harmless interpolation of noisy data in regression

统计

随机变量的收敛

1 minute read

Published:

随机变量的收敛性，包括几乎处处收敛、依概率收敛、依分布收敛、依范数收敛，以及其相互之间的蕴含关系证明。

概率图模型

1 minute read

Published:

笔者对概率图模型一直充满兴趣，决定趁这个机会好好整理一下。内容主要包括贝叶斯网络、马尔可夫随机场，以及概率图上的推断和学习问题的常见算法。也是对之前学习的MCMC方法、EM算法等的一个综合性理解。

EM算法

less than 1 minute read

Published:

EM算法（Expectation-Maximization Algorithm)是一个十分经典且精妙的统计学习算法，在机器学习领域等具有重要的意义。

极大似然估计的性质

1 minute read

Published:

总结关于极大似然估计（Maximum Likelihood Estimate，MLE）的相关性质证明，包括同变性、一致性、渐进正态性。

蒙特卡罗方法

less than 1 minute read

Published:

蒙特卡罗方法的总结，包括拒绝性采样、重要性采样等，以及马尔可夫链蒙特卡罗方法(MCMC，Markov Chain Monte Carlo), Metropolis-Hastings采样、Gibbs采样等。

常用分布与假设检验

2 minute read

Published:

总结常用的分布和常见的假设检验方法，从特征函数推导经典的概率极限定理，之后根据常见的分布，推导包括Z检验、卡方检验、t检验、F检验、单因素方差分析等。

统计机器学习

一致性，随机树，随机森林

4 minute read

Published:

本文讨论基于划分机制的机器学习算法的贝叶斯一致性，主要以随机决策树和随机森林为例。

代理性，最优性，可学性，一致性

7 minute read

Published:

贝叶斯最优分类器是理论上最优的分类器，但由于其对应的0-1损失函数非凸不连续，难以直接进行优化，在机器学习中常用凸代理损失函数进行优化，本文研究使用代理损失函数是否能够一致地学习到贝叶斯最优分类器，称为算法的一致性。

VC维，复杂度，泛化界

6 minute read

Published:

使用增长函数和VC维衡量假设空间的复杂度，并且介绍常见分类器，如线性分类器、前馈神经网络、多数投票分类器的VC维，并且根据VC维以及概率不等式等给出关于有限维和无限维假设空间的泛化误差上界。

稳定性，泛化性，可学性，正则化

4 minute read

Published:

稳定性衡量机器学习算法对于训练集的扰动的稳健性，本文主要针对于替换稳定性，从替换稳定性的定义出发，推导稳定性和泛化性以及PAC可学性的关系，并且基于支持向量机、岭回归等经典模型推导稳定性和正则化的关系。

方差分析ANOVA

13 minute read

Published:

方差分析（Analysis of Variance，ANOVA）研究自变量的不同水平对于因变量的影响，本文首先从线性回归模型出发，给出单因素ANOVA的基础理论，再从ANOVA本身模型的角度出发，分别推导单变量和双变量的ANOVA包括假设检验等。

回归分析下

10 minute read

Published:

线性回归模型的推广，从多重共线性的解决到岭回归模型的建立，线性自平稳器的留一交叉验证的公式，再生希尔伯特空间（RKHS）与核岭回归模型的建立，以及Box-Cox变换下和对率回归模型（Logistic Regression）的建立。

回归分析上

15 minute read

Published:

线性回归入门级总结，包括线性回归模型的基本性质，假设检验和区间估计，变量选择和准则，以及对于异方差和自相关等现象的解决。

函数型数据分析

3 minute read

Published:

函数型数据分析针对于数据为函数的情况，而函数可以看作无穷维向量，因此函数型数据分析是有限维模型向无限维模型的推广。本文可以作为函数型数据分析的入门级导论，用于展现函数型数据分析的某些特质。

贝叶斯最优分类器

6 minute read

Published:

从贝叶斯最优分类器推导常见的线性分类器，包括朴素贝叶斯，线性判别分析和Fisher判别分析。

Eckart-Young-Mirsky定理及其泛函版本简证

2 minute read

Published:

最佳低秩逼近的结果依赖于Eckart-Young-Mirsky定理，但大多数证明都略显繁琐，本文从优化的角度给出简要证明，并且推广到无限维的泛函版本。

集成学习

3 minute read

Published:

集成学习的思想是采用若干的较弱的分类器集成为一个较强的分类器，本文主要以二分类问题为例，重点介绍AdaBoost算法的推导过程和训练误差上界。

卡尔曼滤波与隐马尔可夫模型

5 minute read

Published:

本文关注在动态场景下或者在序列数据上的经典机器学习模型，包括Bayes滤波、Kalman滤波、隐Markov模型的前向-后向等求解算法。

稀疏优化与低秩优化初步

5 minute read

Published:

矩阵填充是推荐系统中的关键问题，本文以此问题的求解为例说明矩阵次梯度等一些稀疏优化、低秩优化等的基础内容，同时也包括鲁棒PCA的介绍。

主成分分析PCA

8 minute read

Published:

主成分分析PCA相关内容，从最简单的PCA，再到核PCA、概率PCA等。

高斯无向图模型

1 minute read

Published:

高斯无向图模型是一种重要的概率图模型，与多元高斯分布的各种性质也密切相关。

概率不等式

6 minute read

Published:

总结机器学习中常用的概率不等式的证明，包括Chevnoff，Hoeffding，Bennett，Bernstein不等式等，并且介绍次高斯变量相关的不等式和用随机投影进行数据降维的方法。

熵

1 minute read

Published:

熵相关的内容，是机器学习中重要的一部分，例如决策树的特征选择等。包括KL散度、信息熵、条件熵、互信息等。

指数族分布

4 minute read

Published:

介绍指数族分布的常见性质等，从充分统计量出发，到指数族分布的共轭先验分布和其最大熵性质，以及指数族分布在EM算法中的应用。

计算机理论

图的动态连通性问题

2 minute read

Published:

图的动态连通性问题。笔者对相关论文的数据结构和算法进行整理，但是只能窥得作者的妙思的一二，很多精髓仍未掌握。但将整理的内容配图放在这里，希望一来加深自己的理解，二来希望对后续读到相关工作的人有所帮助。

计算机组成

从C程序到计算机组成原理

less than 1 minute read

Published:

从C语言程序出发，理解一个程序如何被计算机所执行，总结计算机组成原理的一些要点。本文同时也标志着折磨笔者长达很久的ICS（Introduction to Computer System）短期内告一段落。

随机优化

Least Square SGD with Tail Average

8 minute read

Published:

Paper Reading: A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)

PAGE

4 minute read

Published:

Paper Reading: PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization.

SVRG

3 minute read

Published:

论文阅读笔记：Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. NIPS 2013.

随机过程

马尔可夫链

1 minute read

Published:

马尔可夫链的相关总结。马尔可夫链通常用于刻画满足马尔可夫性的随机过程，马尔可夫性指的是一个过程未来的状态仅仅与当前的状态有关，而不依赖于历史的状态。马尔可夫链通常可以根据转移概率矩阵$P_{ij}$ 描述。

布朗运动

3 minute read

Published:

布朗运动的相关总结。布朗运动通常用来研究分子的无规律运动，模拟股票市场的波动情况等。本文主要包含了布朗运动的数字特征、样本轨道特征、布朗桥等基于布朗运动的重要随机过程、布朗运动的最大值和首中时等，不包括与随机积分相关的内容。

分支过程

less than 1 minute read

Published:

分支过程是一种特殊的马尔可夫链，但由于其比较特殊且在显示生活中很常见，单独考虑之。分支过程通常用于分析生物繁衍、粒子分裂等问题。

泊松过程

3 minute read

Published:

泊松过程首先是一个计数过程$N(t)$表示$t$时间内某个时间发生的次数，例如顾客访问的次数、灾难的发生次数等。

非凸优化

高等线性代数

特征值不等式和最佳低秩逼近

1 minute read

Published:

从Hermite矩阵的特征值不等式出发，利用奇异值推广到一般矩阵，得到最佳低秩逼近定理，并且介绍主成分分析（PCA）等应用。