精读笔记
Problem Setting
这篇论文解决的不是“如何做 BCG”，而是 BCG 中长期被弱化处理的步长问题：在 smooth possibly nonconvex 优化中，如果只更新一个 block，如何在不知道 block Lipschitz 常数、又不评估目标函数的情况下选择步长，并仍然给出全局非渐近 stationarity guarantee。
真正困难点有两个。第一，block 更新只看到局部梯度，但 descent condition 通常由 block curvature 决定；如果不用 Lipschitz 常数或 line-search，就没有显式机制防止过大步长导致函数上升。第二，不同 block selection rule 的分析结构完全不同：UR 可以用期望和 unbiasedness，GS 可以用最大 block norm，cyclic 最麻烦，因为一个 cycle 内梯度会 drift，selected block gradient 与 cycle 起点 full gradient 不再直接对齐。
已有方法卡在两端：一端是理论干净的 BCG，通常需要 Lipschitz 常数或 line-search；另一端是实践中的 adaptive optimizer，虽然 OFFO 且 robust，但在 block-coordinate nonconvex setting 下缺少统一 convergence-rate theory。这篇论文瞄准的就是这个中间空白。
Motivation
作者的核心动机是：BCG 的 block selection 已经被研究得很充分，但 step-size selection 在 nonconvex BCG 理论里仍然相当传统。constant step 需要 curvature knowledge；line-search 需要多次 objective evaluation；两者都不适合 objective expensive 或 noisy 的情况。
关键观察是 AdaGrad 类方法的理论并不依赖函数值搜索，而是依赖历史梯度能量形成自适应 damping。把这个机制嵌入 BCG 后，有可能让每个被访问坐标自己调节步长，避免显式估计 block Lipschitz 常数。
这里缺的不是一个新 optimizer trick，而是一个能同时覆盖 GS、UR、cyclic 三类选择规则的统一 proof template。论文的价值主要在这个 proof template，而不是算法形式本身有多复杂。
Core Idea
核心思想是把 AdaGrad 的“历史梯度能量归一化”改造成 block-coordinate 版本：每次只更新被选中 block 的变量，同时只累积该 block 内坐标的梯度平方；未访问坐标的权重保持不变。于是每个坐标的步长只由它在实际被更新时看到的梯度历史决定。
这改变了 BCG 中步长的建模方式：步长不再来自外部 curvature oracle，也不再通过函数值回溯搜索确定，而是由 optimization trajectory 内生地产生。直觉上，如果某个坐标/block 梯度长期很大，它的权重会快速增大，后续步长变小；如果某个方向较少被激活或梯度较小，则不会被过度 damp。这是一种 memory reuse，而不是 curvature estimation。
和 prior 的本质区别在于：它放弃了每步 sufficient decrease，接受非单调性，然后通过 AdaGrad-style 累积不等式证明总体上 stationarity measure 会下降。也就是说，它不是让每一步安全，而是让“危险项”的总账可控。
Method
关键机制可以压缩为以下几项。
1. Block-local AdaGrad weight：对 selected block 中每个坐标维护 w_i,k = sqrt(ς + selected-gradient-square history)。它解决的是未知步长尺度问题；核心变化是将全局或 block Lipschitz 常数替换为坐标级历史梯度能量。
2. OFFO update：更新为 s_i,k = -g_i,k / w_i,k，仅作用在当前 block。它避免 objective evaluation，因此和 line-search BCG 的信息流完全不同；算法只需要 gradient oracle，适合函数值昂贵或噪声函数值不可靠的场景。
3. Nonmonotone descent lemma：单步函数差被写成一个负的一阶项加一个正的二阶 Lipschitz 项。由于一阶项按 1/w 衰减、二阶项按 1/w^2 衰减，后者的累积可由 log term 控制。这是证明成立的核心 accounting。
4. Block-to-full stationarity conversion：GS 用最大 block gradient 给出 full gradient 上界；UR 用均匀抽样下 selected block norm 的期望连接 full gradient norm；cyclic 则需要额外 global Lipschitz 控制一个 cycle 内未更新 block 的梯度漂移。这部分不是优化机制本身，而是为了把 selected-block progress 转换成标准 stationarity metric。
5. Box constraints：把 gradient norm 换成 projected-gradient residual v = P_C(x-g)-x，并用 max(1, η) 保证可行性。机制上不是新算法，而是把 AdaGrad accounting 迁移到 constrained stationarity measure。
Key Insight / Why It Works
最关键的 insight 是：在 nonconvex smooth setting 下，不必强制每次 block update 都下降；只要正的 curvature penalty 的累计增长慢于负的 adaptive-gradient 累计下降，就能得到 ergodic stationarity。bAdag 的 proof 本质是 AdaGrad 势函数证明在 block-coordinate 轨迹上的重写。
真正有效的原因不是 block selection 本身，而是权重累积带来的自动 damping。早期可能出现 aggressive step 和 nonmonotone behavior；随着某些坐标累计梯度变大，二阶误差项被 1/w^2 快速压低，而一阶下降项仍以 1/w 贡献可控进展。这种线性项与二次项的衰减速率差，是整个理论成立的核心。
最可能的核心贡献是 Lemma 4.1 + Lemma 4.4 + log-bound 的组合：它给出了一个不依赖 function evaluation 的 BCG adaptive-step 证明模板。相比之下，box-constrained extension 更像技术迁移；实验中的 extrapolated bAdag 也更偏 engineering。
需要直接指出：rate 本身并不强。论文证明的是 average gradient norm O(1/sqrt(k))，而很多 fixed-step BCG 文献给的是 min gradient norm squared O(1/k)，换成 norm 也是 O(1/sqrt(k))，但常数通常更好。因此这篇论文不是在复杂度阶上推进 BCG，而是在“未知 Lipschitz + OFFO + 多 selection rules”这个约束组合下给出可证明算法。
实验中的 robustness 很可能主要来自 OFFO 避免 noisy objective line-search，而不是 AdaGrad block weighting 相比其他 OFFO fixed schedule 有决定性优势。文中未充分说明 adaptive accumulation 与 simply using conservative diminishing steps 之间的差异增益。增益归因不完全清楚。
Relation To Prior Work
它最接近两条谱系的交叉：一条是 classical BCG / BCPG 的 nonconvex nonasymptotic analysis，另一条是 AdaGrad / OFFO adaptive first-order methods 的 convergence analysis。
和 Nesterov/Richtárik/Necoara/Nutini/Cai 等 BCG 工作相比，实质差异在步长来源：prior 多数依赖 Lipschitz 常数、matrix upper bound 或 line-search；bAdag 通过历史 gradient norm 生成步长，不需要 objective evaluation。这是信息结构上的差异，不只是参数调法。
和 AdaGrad 相比，算法新意有限：当 block 数 d=1 时基本退化为 AdaGrad-like 方法。真正新增的是 block-coordinate 下只累积 selected block history，并证明这种 partial memory 仍足以控制全局 stationarity，尤其是把 GS/UR/C 放进一个统一框架。
和 stochastic AdaGrad 的关系也很近，但这里的 random block gradient 不是标准无偏全梯度估计，差一个 1/d 的结构，并且算法没有 rescaling。论文强调这一点是合理的。不过 UR 分析仍然严重依赖均匀采样结构；它不是任意 sampling 下的 adaptive BCG theory。
看似新的部分中，box-constrained 版本主要是 projected-gradient residual + AdaGrad accounting 的重组；NMF extrapolation 更明显是已有 NMF acceleration idea 的工程性加入，不属于理论主贡献。
Dataset / Evaluation
实验覆盖了三类场景：convex least squares、nonconvex logistic regression with log-sum penalty、box-constrained robust Huber-NMF。覆盖面足够展示算法可运行，并且包含噪声目标/梯度设置，这与 OFFO claim 对齐。
最能支持论文主张的是 noisy least squares 和 noisy logistic regression：BCG-LS 在函数值/梯度带噪时 line-search 明显不稳定，而 bAdag 由于不看 objective value 更稳。这验证的是“OFFO 在 noisy evaluation 下更 robust”，不是严格验证 bAdag 相对所有 adaptive/diminishing BCG 的优势。
NMF 实验更像应用展示。Huber-NMF 的 objective 不满足全文 cyclic convergence 所需 global Lipschitz gradient，作者也承认这一点，因此该实验不能作为理论 claim 的直接证据。加入 extrapolation 后的 ebAdag 性能接近 MU，但这部分增益来源不清，可能主要来自 NMF 领域已知的 extrapolation trick。
evaluation 没有充分比较其他 objective-free baseline，例如简单 diminishing step BCG、block-wise scalar AdaGrad、non-uniform sampling variants 或 stochastic adaptive BCG。因而实验能说明 bAdag 比 noisy line-search 稳，但不能说明它是 adaptive BCG 中最合理的设计。
Limitation
第一，理论常数偏重。Θ 依赖 N 和 max block Lipschitz，UR/GS/C 又分别带 d、sqrt(d) 或 cycle-level 因子；这些依赖会在大规模高维 block decomposition 下削弱结论。作者也承认 N 可能只是 proof artifact，但文中未解决。
第二，cyclic 结果更弱。它按完整 cycle T 给 rate，并额外需要 global Lipschitz continuity。对许多 matrix factorization 类问题，全局 Lipschitz 不成立；这意味着最常用的 cyclic block update 在实际应用中未必被理论覆盖。
第三，GS 的可扩展性有限。GS 需要每步 full gradient 才能选最大 block，这在许多 BCG 应用中抵消了 block update 的低成本优势。因此 GS 的理论覆盖漂亮，但实际 scalability 依赖问题结构能否廉价获得 full gradient/block scores。
第四，算法本质上把 curvature estimation 问题转移成历史梯度 scaling 问题。AdaGrad 权重能防止长期大梯度方向过激，但不等价于估计局部 Lipschitz；在 ill-conditioned、gradient magnitude 与 curvature 不匹配的情形，adaptive scaling 未必给出好步长。
第五，实验归因不充分。bAdag 相对 BCG-LS 的优势在高噪声下很明显，但这可能主要来自 line-search 被 noisy objective 破坏，而不是 bAdag 特有的 block-coordinate AdaGrad 机制。缺少 OFFO baseline 会让核心增益来源不清。
第六，box-constrained 版本较保守。为了保证可行性使用 max(1, η) 缩放，可能在早期牺牲进展；constrained cyclic bound 的常数也明显更差。
Takeaway
- 1. 这篇论文真正值得记住的是一个 proof pattern：BCG 不必依赖 sufficient decrease；可以用 AdaGrad-style historical normalization + log potential 来控制 nonmonotone block updates。
- 2. 对实际算法设计的启发是：在 objective evaluation 不可信或昂贵时，BCG 的步长选择应优先考虑 OFFO adaptive mechanisms，而不是把 line-search 当默认方案。
- 3. 未来更有价值的问题不是继续换 adaptive optimizer 名字，而是去掉 N/d 常数、支持 non-uniform sampling、处理 composite nonsmooth，并解释 adaptive scaling 相对简单 diminishing schedules 的真实增益。
- 4. 对 cyclic BCG，真正的瓶颈仍是 block interaction / gradient drift 控制；如果能用更细的 block coupling condition 替代 global Lipschitz，会比当前 bound 更有意义。
一句话总结
bAdag 是把 AdaGrad 的历史梯度归一化机制嵌入 BCG、并为 GS/UR/cyclic 三类 block rule 给出 OFFO nonconvex 非渐近理论的一篇方法论论文，贡献主要在统一分析框架而不是复杂度阶或实验性能上的根本突破。