summaries: This paper introduces a supervised neural network predicting a wireframe structure from a 3D point cloud. The network takes a raw unordered 3D point cloud as input, processes it using FCGF architecture, and predicts three types of information: vertex existence in each patch, vertex location, and edge existence for each pair of vertices. In the experiments, the network is evaluated with two datasets, a subset of the ABC dataset and a set of 3D models from Google 3D warehouse. Also, it is compared with the baseline methods using four evaluation metrics, which are created to assess the accuracy of the predicted vertices, edges, and the overall wireframe graph structure. The results demonstrate the outperformance of the proposed method quantitatively and qualitatively.

summaries: This paper presents a deep architecture to extract a wireframe model from a 3D point cloud. This is a problem of high interest, and the author claim that the approach they present is the first one to address this task, which is true to the best of my knowledge. Since both the approach and the evaluation are sound, this alone seem to warrant publication. There are however several weaknesses in the paper, and my accept recommendation is conditional to clear answer on each of them:

summaries: This paper introduces PC2WF, a neural network that turns 3D point clouds into a wireframe model. PC2WF encodes each point into a feature vector and uses them to predict the candidate corners. After that, line proposals are generated by connecting pairs of corners, and the point features along each line are pooled into its confidence value. By pruning the proposed lines, PC2WF generates the final wireframe represesntation.

abstractText: We introduce PC2WF, the first end-to-end trainable deep network architecture to convert a 3D point cloud into a wireframe model. The network takes as input an unordered set of 3D points sampled from the surface of some object, and outputs a wireframe of that object, i.e., a sparse set of corner points linked by line segments. Recovering the wireframe is a challenging task, where the numbers of both vertices and edges are different for every instance, and a-priori unknown. Our architecture gradually builds up the model: It starts by encoding the points into feature vectors. Based on those features, it identifies a pool of candidate vertices, then prunes those candidates to a final set of corner vertices and refines their locations. Next, the corners are linked with an exhaustive set of candidate edges, which is again pruned to obtain the final wireframe. All steps are trainable, and errors can be backpropagated through the entire sequence. We validate the proposed model on a publicly available synthetic dataset, for which the ground truth wireframes are accessible, as well as on a new real-world dataset. Our model produces wireframe abstractions of good quality and outperforms several baselines.

authors:
Syeda Mariam Ahmed
Yan Zhi Tan
Chee Meng Chew
Abdullah Al Mamun
Fook Seng Wong

title: Edge and corner detection for unorganized 3d point clouds with application to robotic welding

venue: In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS),

authors:
Dena Bazazian
Josep R Casas
Javier Ruiz-Hidalgo

title: Fast and robust edge extraction in unorganized point clouds

venue: In Digital Image Computing: Techniques and Applications (DICTA),

authors:
Siheng Chen
Dong Tian
Chen Feng
Anthony Vetro
Jelena Kovačević

title: Fast resampling of threedimensional point clouds via graphs

venue: IEEE Transactions on Signal Processing,

authors:
Otfried Cheong
Joachim Gudmundsson
Hyo-Sil Kim
Daria Schymura
Fabian Stehn

title: Measuring the similarity of geometric graphs

venue: In International Symposium on Experimental Algorithms,

authors:
Christopher Choy
JunYoung Gwak
Silvio Savarese

title: 4d spatio-temporal convnets: Minkowski convolutional neural networks

venue: In IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Christopher Choy
Jaesik Park
Vladlen Koltun

title: Fully convolutional geometric features

venue: In IEEE International Conference on Computer Vision (ICCV),

authors:
Inge Coudron
Steven Puttemans
Toon Goedemé

title: Polygonal reconstruction of building interiors from cluttered pointclouds

venue: In European Conference on Computer Vision (ECCV),

authors:
Kris Demarsin
Denis Vanderstraeten
Tim Volodine
Dirk Roose

title: Detection of closed sharp edges in point clouds using normal estimation and graph theory

venue: Computer-Aided Design,

authors:
Tao Du
Jeevana Priya Inala
Yewen Pu
Andrew Spielberg
Adriana Schulz
Daniela Rus
Armando Solar-Lezama
Wojciech Matusik

title: InverseCSG: Automatic conversion of 3d models to CSG trees

venue: ACM Transactions on Graphics (TOG),

authors:
Alexandre Durupt
Sebastien Remy
Guillaume Ducellier
Benoît Eynard

title: From a 3d point cloud to an engineering CAD model: a knowledge-product-based approach for reverse engineering

venue: Virtual and Physical Prototyping,

authors:
Hao Fang
Florent Lafarge
Mathieu Desbrun

title: Planar shape detection at structural scales

title: Detection of interest points on 3d data: Extending the Harris operator

venue: In Computer Recognition Systems

authors:
Diego Gonzalez-Aguilera
Susana Del Pozo
Gemma Lopez
Pablo

title: Rodriguez-Gonzalvez. From point cloud to CAD models: Laser and optics geotechnology for the design of electrical substations

venue: Optics & Laser Technology,

authors:
Timo Hackel
Jan Dirk Wegner
Konrad Schindler

title: Contour detection in unstructured 3d point clouds

title: Joint classification and contour extraction of large 3d point clouds

venue: ISPRS Journal of Photogrammetry and Remote Sensing,

authors:
Christopher G Harris
Mike Stephens

title: A combined corner and edge detector

venue: In Alvey Vision Conference,

authors:
Kun Huang
Shenghua Gao

title: Wireframe parsing with guidance of distance map

venue: IEEE Access,

authors:
Kun Huang
Yifan Wang
Zihan Zhou
Tianjiao Ding
Shenghua Gao
Yi Ma

title: Learning to parse wireframes in images of man-made environments

authors:
Jaehoon Jung
Sungchul Hong
Sanghyun Yoon
Jeonghyun Kim
Joon Heo

title: Automated 3d wireframe modeling of indoor structures from point clouds using constrained least-squares adjustment for as-built BIM

venue: Journal of Computing in Civil Engineering,

authors:
Sebastian Koch
Albert Matveev
Zhongshi Jiang
Francis Williams
Alexey Artemov
Evgeny Burnaev
Marc Alexa
Denis Zorin
Daniele Panozzo

title: ABC: A big CAD model dataset for geometric deep learning

authors:
Jun Li
Kai Xu
Siddhartha Chaudhuri
Ersin Yumer
Hao Zhang
Leonidas Guibas

title: GRASS: Generative recursive autoencoders for shape structures

authors:
Lingxiao Li
Minhyuk Sung
Anastasia Dubrovina
Li Yi
Leonidas J Guibas

title: Supervised fitting of geometric primitives to 3d point clouds

authors:
Yan-qin Li
Gui-zhong Xie
Fan-nian Meng
De-hai Zhang

title: Using the point cloud data to reconstructing CAD model by 3d geometric modeling method in reverse engineering

venue: In International Conference on Manufacturing Engineering and Intelligent Materials (ICMEIM),

authors:
Hong-Wei Lin
Chiew-Lan Tai
Guo-Jin Wang

title: A mesh reconstruction algorithm driven by an intrinsic property of a point cloud

authors:
Liangliang Nan
Peter Wonka

title: Polyfit: Polygonal surface reconstruction from point clouds

title: From point cloud to surface: the modeling and visualization problem. International Archives of the Photogrammetry

venue: Remote Sensing and Spatial Information Sciences,

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster R-CNN: Towards real-time object detection with region proposal networks

venue: In Advances in Neural Information Processing Systems (NeurIPS),

authors:
Ruwen Schnabel
Roland Wahl
Reinhard Klein

title: Efficient RANSAC for point-cloud shape detection

venue: Computer Graphics Forum,

authors:
Ruwen Schnabel
Raoul Wessel
Roland Wahl
Reinhard Klein

title: Shape recognition in 3d pointclouds

venue: In International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG),

authors:
Gopal Sharma
Rishabh Goyal
Difan Liu
Evangelos Kalogerakis
Subhransu Maji

title: CSGNet: Neural shape parser for constructive solid geometry

authors:
Ivan Sipiran
Benjamin Bustos

title: A robust 3d interest points detector based on harris operator

venue: In Eurographics Conference on 3D Object Retrieval

title: Harris 3d: a robust extension of the Harris operator for interest point detection on 3d meshes

venue: The Visual Computer,

authors:
Stephen M Smith
J Michael Brady

title: SUSAN -— a new approach to low level image processing

venue: International Journal of Computer Vision,

authors:
Shubham Tulsiani
Hao Su
Leonidas J Guibas
Alexei A Efros
Jitendra Malik

title: Learning shape abstractions by assembling volumetric primitives

authors:
Nicolas Walter
Olivier Aubreton
Yohan D Fougerolle
Olivier Laligant. Susan

title: 3d operator, principal saliency degrees and directions extraction and a brief study on the robustness to noise

venue: In IEEE International Conference on Image Processing (ICIP),

authors:
Peng-Shuai Wang
Yang Liu
Yu-Xiao Guo
Chun-Yu Sun
Xin Tong

title: O-CNN: Octree-based convolutional neural networks for 3d shape analysis

authors:
Xiaogang Wang
Yuelang Xu
Kai Xu
Andrea Tagliasacchi
Bin Zhou
Ali Mahdavi-Amiri
Hao Zhang

title: Pie-net: Parametric inference of point cloud

venue: edges. Conference on Neural Information Processing Systems (NeurIPS),

authors:
Shaobo Xia
Ruisheng Wang

title: A fast edge extraction method for mobile LiDAR point clouds

venue: IEEE Geoscience and Remote Sensing Letters,

authors:
Nan Xue
Tianfu Wu
Song Bai
Fu-Dong Wang
Gui-Song Xia
Liangpei Zhang
Philip H.S. Torr

title: Holistically-attracted wireframe parsing

venue: arXiv preprint arXiv:2003.01663,

authors:
Bisheng Yang
Yufu Zang

title: Automated registration of dense terrestrial laser-scanning point clouds using curves

authors:
Lequan Yu
Xianzhi Li
Chi-Wing Fu
Daniel Cohen-Or
Pheng-Ann Heng

title: EC-Net: an edgeaware point set consolidation network

authors:
Yichao Zhou
Haozhi Qi
Yi Ma

title: End-to-end wireframe parsing

authors:
Yichao Zhou
Haozhi Qi
Yuexiang Zhai
Qi Sun
Zhili Chen
Li-Yi Wei
Yi Ma

title: Learning to reconstruct 3d Manhattan wireframes from a single image

authors:
Chuhang Zou
Ersin Yumer
Jimei Yang
Duygu Ceylan
Derek Hoiem

title: 3D-PRNN: Generating shape primitives with recurrent neural networks

authors:
Chuhang Zou
Alex Colburn
Qi Shan
Derek Hoiem

title: LayoutNet: Reconstructing the 3d room layout from a single RGB image

heading: 1 INTRODUCTION

text:
Many practical 3D sensing systems, like stereo cameras or laser scanners, produce unstructured 3D point clouds. That choice of output format is really just a "smallest common denominator", the least committal representation that can be reliably generated with low-level signal processing. Most users would prefer a more efficient and more intuitive representation that describes the scanned object’s geometry as a compact collection of geometric primitives, together with their topological relations. Specifically, many man-made objects are (approximately) polyhedral and can be described by corners, straight edges and/or planar surfaces. Roughly speaking there are two ways to abstract a point cloud into a polyhedral model: either find the planar surfaces and intersect them to find the edges and corners, e.g., Schnabel et al. (2007); Fang et al. (2018); Coudron et al. (2018); or directly find the salient corner and/or edges, e.g., Jung et al. (2016); Hackel et al. (2016).
A wireframe is a graph representation of an object’s shape, where vertices correspond to corner points (with high Gaussian curvature) that are linked by edges (with high principal curvature). Wireframes are a good match for polyhedral structures like mechanical parts, furniture or building interiors. In particular, since wireframes focus on the edge structure, they are best suited for piece-wise smooth objects with few pronounced crease edges (whereas they are less suitable for smooth objects without defined edges or for very rough ones with edges everywhere). We emphasise that wireframes are not only a "compression technique" to save storage. Their biggest advantage in many applications is that they are easy to manipulate and edit, automatically or interactively in CAD software, because they make the salient contours and their connectivity explicit. Reconstructed wireframes can drive and help to create 3D CAD models for manufacturing parts, metrology, quality inspection, as well as visualisation, animation, and rendering.
Inferring the wireframe from a noisy point cloud is a challenging task. We can think of the process as a sequence of steps: find the corners, localise them accurately (as they are not contained in the point cloud), and link them with the appropriate edges. However, these steps are intricately correlated. For example, corner detection should "know" about the subsequent edge detection: curvature is affected by noise (as any user of an interest point detector can testify), so to qualify as a corner
a 3D location should also be the plausible meeting point of multiple, non-collinear edges. Here we introduce PC2WF, an end-to-end trainable architecture for point cloud to wireframe conversion. PC2WF is composed of a sequence of feed-forward blocks, see Fig. 1 for the individual steps of the pipeline. First a "backbone" block extracts a latent feature encoding for each point. The next block identifies local neighbourhoods ("patches") that contain corners and regresses their 3D locations. The final block links the corners with an overcomplete set of plausible candidate edges, collects edge features by pooling point features along each edge, and uses those to prune the candidate set to a final set of wireframe edges. All stages of the architecture that have trainable parameters support back-propagation, such that the model can be learned end-to-end. We validate PC2WF with models from the publicly available ABC dataset of CAD models, and with a new furniture dataset collected from the web. The experiments highlight the benefit of explicit, integrated wireframe prediction: on the one hand, the detected corners are more complete and more accurate than with a generic corner detector; on the other hand, the reconstructed edges are more complete and more accurate than those found with existing (point-wise) edge detection methods.

heading: 2 RELATED WORK

text:
Relatively little work exists on the direct reconstruction of 3D wireframes. We review related work for the subtasks of corner and edge detection, as well as works that reconstruct wireframes in 2D or polyhedral surface models and geometric primitives in 3D.
Corner Detection. Corner points play a fundamental role in both 2D and 3D computer vision. A 3D corner is the intersection point of ≥3 (locally) non-collinear surfaces. Corners have a well-defined location and a local neighbourhood with non-trivial shape (e.g., for matching). Collectively the set of corners often is sufficient to tightly constrain the scale and shape of an object. Typical local methods for corner detection are based on the 2nd-moment matrix of the points (resp. normals) in a local neighbourhood (Głomb, 2009; Sipiran & Bustos, 2010; 2011), a straight-forward generalisation of the 2D Harris operator first proposed for 2D images (Harris et al., 1988). Also other 2D corner detectors like Susan (Smith & Brady, 1997) have been generalised to 3D (Walter et al., 2009).
Point-level Edge Point Detection. A large body of work is dedicated to the detection of 3D points that lie on or near edges. The main edge feature is high local curvature (Yang & Zang, 2014). Related features, such as symmetry (Ahmed et al., 2018), change of normals (Demarsin et al., 2007), and eigenvalues (Bazazian et al., 2015; Xia & Wang, 2017) can also be used for edge detection. Hackel et al. (2016; 2017) use a combination of several features as input for a binary edge-point classifier. After linking the points into an adjacency graph, graph filtering can be used to preserve only edge points (Chen et al., 2017). EC-Net (Yu et al., 2018) is the first method we know of that detects edge points in 3D point clouds with deep learning.
Learning Structured Models. Many methods have been proposed to abstract point clouds into more structured 3D models, e.g., triangle meshes (Lin et al., 2004; Remondino, 2003; Lin et al., 2004), polygonal surfaces (Fang et al., 2018; Coudron et al., 2018), simple parametric surfaces (Schnabel et al., 2007; 2008; Li et al., 2019). From the user perspective, the ultimate goal would be to reverseengineer a CAD model (Gonzalez-Aguilera et al., 2012; Li et al., 2017b; Durupt et al., 2008). Several works have investigated wireframe parsing in 2D images (Huang et al., 2018; Huang & Gao, 2019). LCNN (Zhou et al., 2019a) is an end-to-end trainable system that directly outputs a vectorised wireframe. The current state-of-the-art appears to be the improved LCNN of Xue et al. (2020), which uses a holistic "attraction field map" to characterise line segments. Zou et al. (2018) estimate the 3D layout of an indoor scene from a single perspective or panoramic image with an encoder-decoder architecture, while Zhou et al. (2019b) obtain a compact 3D wireframe representation from a single image by exploiting global structural regularities. Jung et al. (2016) reconstruct 3D wireframes of building interiors under a Manhattan-world assumption. Edges are detected heuristically by projecting the points onto 2D occupancy grids, then refined via least-squares fitting under parallelism/orthogonality constraints. Wireframe extraction in 2D images is simplified by the regular pixel grid. For irregular 3D points the task is more challenging and there has been less work.
Another related direction of research is 3D shape decomposition into sets of simple, parameterised primitives (Tulsiani et al., 2017; Li et al., 2017a; Zou et al., 2017; Sharma et al., 2018; Du et al., 2018). Most approaches use a coarse volumetric occupancy grid as input for the 3D data, which
works well for shape primitive fitting but only allows for rather inaccurate localisation of edges and vertices. Li et al. (2019) propose a method for fitting 3D primitives directly to raw point clouds. A limiting factor of their approach is that only a fixed maximum number of primitive instances can be detected. This upper bound is hard-coded in the architecture and prevents the network from fitting more complex structures. Nan & Wonka (2017) propose Polyfit to extract polygonal surfaces from a point cloud. Polyfit first selects an exhaustive set of candidate surfaces from the raw point cloud using RANSAC, and then refines the surfaces. Similarly to our PC2WF, Polyfit works best with objects made of straight edges and planar surfaces. The concurrent work Wang et al. (2020) proposed a deep neural network that is trained to identify a collection of parametric edges.
In summary, most 3D methods are either hand-crafted for restricted, schematic settings, or only learn to label individual "edge points". Here we aim for an end-to-end learnable model that directly maps a 3D point cloud to a vectorised wireframe.

heading: 3 METHOD

text:
Our full architecture is depicted in Fig. 1. In the following we describe each block and, where necessary, discuss training and inference procedures. We denote a point cloud of N 3D points with P = {pi}Ni=1 where pi ∈ R3 represents the 3D coordinates of point i. The 3D wireframe model of the point cloud P is denoted byW = (V, E) and it is defined, analogously to an undirected graph, by a set of vertices V which are connected by a set of edges E ⊆ V × V . As the vertices represent points in the 3D space we can think of them as being described by 3D coordinates vi ∈ V ⊂ R3. Overall Pipeline. Our feed-forward pipeline consists of four blocks: (1) a convolutional backbone that extracts per-point features; (2) a vertex detector that examines patches of the point cloud and decides which ones contain vertices; (3) a vertex localiser that outputs the location of the vertex within a patch; (4) an edge detector that instantiates candidate edges and prunes them to a wireframe.
Backbone. PC2WF first extracts a feature vector per 3D point that encodes its geometric context. Our pipeline is compatible with any (hand-coded or learned) function that outputs a fixed-size descriptor vector per point. We use Fully Convolutional Geometric Features (FCGF, Choy et al., 2019b), which are compact and capture broad spatial context. The backbone operates on sparse tensors (Choy et al., 2019a) and efficiently computes 32-dimensional features in a single, 3D fully-convolutional pass.
Vertex Detector. This block performs binary classification of local patches (neighbourhoods in the point cloud) into those (few) that contain a corner and those that do not. Only patches detected to contain a corner are passed on to the subsequent block. While one could argue that detecting the presence of a vertex and inferring its 3D coordinates are two facets of the same problem, we found it advantageous to separate them. Detecting first whether a patch is likely to contain a corner, then constructing its 3D coordinates reduces the computational cost, as we discard patches without corners early. Empirically it also reduces false positives and increases localisation accuracy.
Our patch generation is similar to EC-Net (Yu et al., 2018). A patch contains a fixed number M of points, chosen by picking a patch centroid and finding the closest (M − 1) points in terms of geodesic distance on the underlying surface. The geodesic distance avoids "shortcuts" in regions with thin structures or high curvature. To approximate the geodesic distance, the entire point cloud is linked into a k-nearest neighbour graph, with edge weights proportional to Euclidean distance. Point-to-point distances are then found as shortest paths on that graph. During training we randomly draw positive samples that contain a corner and negative ones that do not. To increase the diversity of positive samples, the same corner can be included in multiple patches with different centroids. For the negative samples, we ensure to draw not only patches on flat surfaces, but also several patches near edges, by doing this negative samples with strong curvature are well represented. For inference, patch seeds are drawn using farthest point sampling. The vertex detector takes as input the (indexed) features of the M points in the patch, max-pooled per dimension to achieve permutation invariance, and outputs a scalar vertex/no_vertex probability. Its loss function Lpat is binary cross-entropy.
Vertex Localiser. The vertex detector passes on a set of P patches predicted to contain a corner. The M points pi of such a patch form the input for the localisation block. The backbone features fi ∈ RC and the 3D coordinates pi ∈ R3 of all M points are concatenated and fed into a multi-layer perceptron with fully connected layers, ReLU activations and batch normalisation. The MLP outputs a vector of M scalar weights wi, where ∑ i wi = 1, such that the predicted vertex location is the
weighted mean of the input points, v = ∑ wipi. The prediction vj is supervised by a regression loss
Lvert = 1P ∑P
i ‖vi − vGTi ‖22, summed over all P corner patches. Predicting weights wi rather than directly the coordinates x̃ safeguards against extrapolation errors on unusual patches. We note that the localiser not only improves the corner point accuracy but also improves efficiency, by making it possible to use farthest point sampling rather than testing every input point.
Edge Detector. The edge detection block serves to determine which pairs of (predicted) vertices are connected by an edge. Candidate edges eij are found by linking two vertices vi and vj , see below. To obtain a descriptor for an edge, we sample theNs equally spaced query locationsQ = {qk}s−1k=0 along the line segment between the two vertices, including the endpoints: q0 = ṽi, qs−1 = ṽj . For each qk we find the nearest 3D input point pNN(k) (by Euclidean distance) and retrieve its backbone encoding fNN(k). This yields an (Ns × C) edge descriptor, which is max-pooled along its first dimension, inspired by the ROI pooling in Faster-RCNN (Ren et al., 2015) and LOI pooling in LCNN (Zhou et al., 2019a). The resulting ( 1strideNs × C) descriptor is flattened and fed through an MLP with two fully connected layers, which returns a scalar edge/no_edge score.
During training we select a number of vertex pairs from both the ground truth vertex list {vi}Gi=1 and the predicted vertex list {ṽi}Ki=1, and draw positive and negative sets of edge samples, E+, E−. We empirically found that evaluating all vertex pairs contained in E+, E− during training leads to a large imbalance between positive and negative samples. Similar to Zhou et al. (2019a), we thus draw input edges for the edge detector from the following sets:
(a) Positive edges between ground truth vertices: This set comprises all true edges in the ground truth wireframe Egt+ = E (b) Negative edges between ground truth vertices: Two situations are relevant: "spurious edges", i.e., connections between two ground truth vertices that do not share an edge (but lie on the same surface, such that there are nearby points to collect features). And "inaccurate edges" where one of the endpoints is not a ground truth vertex, but not far from one (to cover difficult cases not far from a correct edge). Formally:
Egt- ={evi,vj =(vi, vj) | vi, vj ∈ V, eij /∈ E ,∀p on evi,vj ,∃p′ ∈ P, ‖p− p′‖2 < } ∪ {ei,pk =(vi, pk) | (vi, vj) ∈ E , pk ∈ P, 1 ≤ ‖vj − pk‖2 ≤ 2}
(c) Positive edges between predicted vertices: Connections between two "correct" predicted vertices that have both been verified to coincide with a ground truth wireframe vertex up to a small threshold +. Formally:
Epred+ = {eṽi,ṽj = (ṽi, ṽj) | min ‖ṽi − vk‖2 < +,min ‖ṽj − vl‖2 < +, (vk, vl) ∈ Egt+} (d) Negative edges between predicted vertices: These are (i) "wrong links" as in Egt-, between "correctly" predicted vertices; and (ii) "hard negatives" where exactly one of the two vertices is close
to a ground truth wireframe vertex, to cover "near misses". Epred- ={eṽi,ṽj =(ṽi, ṽj) | min ‖ṽi − vk‖2 < −,min ‖ṽj − vl‖2 < −, (vk, vl) ∈ Egt−} ∪ {eṽi,ṽj =(ṽi, ṽj) | 1 ≤ ‖ṽi − vk‖2 ≤ 2, ‖ṽj − vl‖2 ≤ 2, vk, vl ∈ V} Fig. 2 visually depicts the different edge sets. To train the edge detector we randomly sample positive examples from E+ = Egt+ ∪ Epred+ and negative examples from E− = Egt- ∪ Epred-. As loss function Ledge we use the balanced binary cross entropy. During inference, we go through the fully connected graph of edge candidates connecting any two (predicted) vertices. Candidates with a too high average distance to the input points (i.e., not lying on any object surface) are discarded. All others are fed into the edge detector for verification.
End-to-end training. When training the complete network, we minimise the joint loss function with balancing weights α and β: L = Lpat + αLvert + βLedge. Non-Maximum Suppression (NMS) is a standard post-processing step for detection tasks, to suppress redundant, overlapping predictions. We use it (i) to prevent duplicate predictions of vertices that are very close to each other, and (ii) to prune redundant edges.

heading: 4 EXPERIMENTS

text: We could not find any publicly available dataset of point clouds with polyhedral wireframe annotations. Thus, we collect our own synthetic datasets: a subset from ABC (Koch et al., 2019) and a Furniture dataset. ABC is a collection of one million high-quality CAD models of mechanical parts with explicitly parameterised curves, surfaces and various geometric features, from which ground truth wireframes can be generated. We select a subset of models with straight edges. It consists of 3,000 samples, which we randomly split into 2,000 for training, 500 for validation, and 500 for testing. For the furniture dataset we have collected 250 models from Google 3DWarehouse for the categories bed, table, chair/sofa, stairs, monitor and render ground truth wireframes. Examples are shown in the supplementary material. To generate point clouds, we use the virtual scanner of Wang et al. (2017). We place 14 virtual cameras on the face centres of the truncated bounding cubes of each object, uniformly shoot 16,000 parallel rays towards the object from each direction, and compute their intersections with the surfaces. Finally, we jitter all points by adding Gaussian noiseN (0, 0.01), truncated to [−0.02, 0.02]. The number N of points varies between ≈ 100k−200k for different virtually scanned point clouds. For details, see the supplementary material.

heading: 4.1 EVALUATION MEASURES

text:
We first separately evaluate the vertex detection and edge detection performance of our architecture, then assess the reconstructed wireframes in terms of structural average precision and of a newly designed wireframe edit distance.
Mean Average precision mAPv for vertices. To generate high quality wireframes, the predicted vertex positions must be accurate. This metric evaluates the geometric quality of vertices, regardless of edge links. A predicted vertex is considered a true positive if the distance to the nearest ground truth vertex is below a threshold ηv. For a given ηv we generate precision-recall curves by varying
the detection threshold. Average precision (APv) is defined as the area under this curve, mAPv is averaged over different thresholds ηv .
Point-wise precision and recall for edges. We do not have a baseline that directly extracts 3D wireframe edges. Rather, existing methods label individual input points as "lying on an edge", and produce corresponding precision-recall curves (Hackel et al., 2016; Yu et al., 2018). To use this metric, we label a 3D point as "edge point" if its distance to the nearest wireframe edge is below the average point-to-point distance. As for APv, we can now check whether a predicted "edge point" is correct up to ηe, and compute APe and mean average precision (mAPe) over different ηe.
Structural average precision for wireframes. The above two evaluation metrics looks at vertices and edges separately, in terms of geometry. In order to comprehensively evaluate the generated wireframe, we also need to take into account the connectivity. The structural average precision (sAP, Zhou et al., 2019a) metric, inspired by mean average precision, can be used to assess the overall prediction. This metric checks if the two end points (ṽi, ṽj) of a detected edge both match the end points (vk, vl) of a ground truth edge up to a threshold ηw, i.e., minvk∈V ‖ṽi − vk‖2 +minvl∈V ‖ṽj − vl‖2 < ηw, (vk, vl) ∈ E . We report sAP for different ηw and mean sAP (msAP).
Wireframe edit distance (WED). In order to topologically compare wireframes, we have designed a quality measure based on edit distance. We consider wireframes as geometric graphs drawn in 3D space. Distance measures commonly used in computational geometry and graph theory, such as Hausdorff distance and Frechet distance, resistance distance, or geodesic distance, do not seem to apply to our situation. Inspired by Cheong et al. (2009), we propose a wireframe edit distance (WED). It is a variant of the graph edit distance (GED), which measures how many elementary graph edit operators (vertex insertion/deletion, edge insertion/deletion, etc.) are needed to transform one graph to another. Instead of allowing arbitrary sequences of operations, which makes computing the GED NP-hard, we fix their order, see Fig. 3: (1) vertex matching; (2) vertex translation; (3) vertex insertion; (4) edge deletion; (5) edge insertion. Let the ground truth wireframeWgt = (Vgt, Egt) and the predicted wireframeWo = (Vo, Eo). First, we match each vertex voi inWo to the nearest ground truth vertex vgtu inWgt, then translate them at a cost of cv · ‖voi vgtu ‖. New vertices are inserted where a ground truth vertex has no match (at no cost, as cost will accrue during edge insertion). After all vertex operations, we perform edge deletion and insertion based on ground truth edges at a cost of ce · ‖e‖, where ‖e‖ is the length of deleted/inserted edges. The final WED is the sum of all cost terms.

heading: 4.2 RESULTS AND COMPARISONS

text:
Vertex detection. We validate the PC2WF vertex detection module and compare to a Harris3D baseline (with subsequent NMS to guarantee a fair comparison) on the ABC dataset, Tab. 1. Exemplary visual results and precision-recall curves are shown in Fig. 4 and Fig.5. Harris3D often fails to accurately localise a corner point, and on certain thin structures it returns many false positives. The patch size M used in our vertex detector has an impact on performance. Patch sizes between 20 and 50 achieve the best performance, where the precision stays at a high level over a large recall range. Patch size 1 leads to low precision (although still better than Harris3D), confirming that per-point features, even when computed from a larger receptive field, are affected by noise and insufficient to find corners with acceptable false positive ratio. We refer the interested reader to the supplementary material for a more exhaustive ablation study.
Edge prediction. Due to the limited number of methods able to extract wireframes from 3D point clouds, we compare PC2WF to recent algorithms that detect edge points, such as FREE (Bazazian et al., 2015), ECD (Ahmed et al., 2018), FEEM (Xia & Wang, 2017), Contour Detector (Hackel et al., 2016) and EC-Net (Yu et al., 2018). We also compare with Polyfit (Nan & Wonka, 2017), which is the only method able to reconstruct a vectorial representation similar to ours from a point cloud. Since Polyfit extracts planar surfaces of the object, we must convert that representation into a wireframe, which amounts to identifying the plane intersections. Precision-recall curves for all methods are shown in Fig. 6. Visual results are shown in Fig. 8. PC2WF outperforms all baselines based on hand-crafted features like FREE, ECD, FEEM and Contour Detector, as well as the deep learning method EC-Net, across all quality measures (Tab. 2). A visual comparison between the ground truth, PC2WF, EC-Net Yu et al. (2018), and Polyfit is shown in Fig. 9. One can clearly see the advantage of predicting vector edges rather than "edge points", as they lead to a much sharper result. The inevitable blur of edge points across the actual contour line, and their irregular density, make vectorisation a non-trivial problem. Polyfit and PC2WF show comparable performance for this specific point cloud. PC2WF failed to localise some corners and missed some small edges, whereas Polyfit failed to reconstruct the lower part of the armchair.
Wireframe Reconstruction. We visualise PC2WF’s output wireframes in Fig. 10. Structural precision-recall curves with various patch sizes are shown in Fig. 7. For additional examples of output predictions, including cases with curved edges, please refer to the supplementary material. The results are aligned with the ones of the vertex module. Moderate patch sizes between 20 and 50 achieve the best performance. Tab. 3 shows the structural average precision with patch size 50, which exceeds the one of Polyfit. The results in terms of the wireframe edit distance are shown in Tab. 4 for PC2WF and Polyfit. The average number of predicted vertices (21.7) and ground truth vertices (20.1) per object are close, such that only few vertex insertions are needed in most cases. Although all predicted vertices need some editing, the WEDv caused by those edits is small (0.2427), meaning that the predictions are accurate. On the contrary, the 2.6 edges that need to be edited on
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Recall
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Pr ec
isi on
f=0.2 f=0.3 f=0.4 f=0.5
f=0.5
f=0.6
f=0.7
f=0.8
Patch size=1 Patch size=20 Patch size=50 Patch size=100 Harris3D
Figure 5: Vertex prediction accuracy on ABC dataset. 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Recall
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Pr ec
isi on
f=0.2 f=0.3 f=0.4 f=0.5
f=0.5
f=0.6
f=0.7
f=0.8
FREE ECD FEEM Contour EC-NET PC2WF
Figure 6: Edge detection accuracy on ABC dataset. 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Recall
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Pr ec
isi on
f=0.2 f=0.3 f=0.4 f=0.5
f=0.5
f=0.6
f=0.7
f=0.8
Patch size=1 Patch size=20 Patch size=50 Patch size=100
Figure 7: Wireframe accuracy on ABC dataset.
average increase WEDe a lot more (1.4142) and dominate the WED, i.e., the inserted/deleted edges have significant length.

heading: 5 CONCLUSION

text:
We have proposed PC2WF, an end-to-end trainable deep architecture to extract a vectorised wireframe from a raw 3D point cloud. The method achieves very promising results for man-made, polyhedral
objects, going one step further than low-level corner or edge detectors, while at the same time outperforming them on the isolated vertex and edge detection tasks. We see our method as one further step from robust, but redundant low-level vision to compact, editable 3D geometry. As future work we aim to address the biggest limitation of our current method which is the inability to handle wireframes with strongly curved edges.

title: RAW POINT CLOUDS


summaries: This paper studies gradient-based stochastic optimization algorithms which incorporate (estimates of) the noise statistics in the adaptive stepsize design. Starting from the standard analysis of SGD with adaptive steps (Thm 1) the authors show in Cor 1 how, using a second-moment-dependent learning rate, one can “accelerate” (see comment later) the convergence of SGD. Next, the authors show (Thm 3) that one can recover a similar result by estimating the second moment using an exponential moving average.

summaries: This paper studies the problem of stochastic optimization where the gradient noise process is non-stationary. Based on a general convergence results based on a general sequence for the second moments of the stochastic gradient norms and a general stepsize sequence, the authors propose to use an online estimation procedure for the gradient norm second moments, in order to mimic the behavior of the ``idealized'' stepsize sequence. Finite-time convergence rates are established for the algorithms with adaptive stepsize, leading to an acceleration effect in certain regimes for the non-stationarity.

summaries: The objective of the paper is to provide a theoretical justification for the value of using adaptive learning steps. The paper presents two results. The first is essentially of theoretical interest, and assumes that the noise level indicators defined in Eq. (1) [but which are difficult to understand at this level of the paper] are known. The second is more practical: it shows that a variant of the RMSprop algorithm achieves the same results as the "theoretical" algorithm.

abstractText: We investigate stochastic optimization under weaker assumptions on the distribution of noise than those used in usual analysis. Our assumptions are motivated by empirical observations in training neural networks. In particular, standard results on optimal convergence rates for stochastic optimization assume either there exists a uniform bound on the moments of the gradient noise, or that the noise decays as the algorithm progresses. These assumptions do not match the empirical behavior of optimization algorithms used in neural network training where the noise level in stochastic gradients could even increase with time. We address this nonstationary behavior of noise by analyzing convergence rates of stochastic gradient methods subject to changing second moment (or variance) of the stochastic oracle. When the noise variation is known, we show that it is always beneficial to adapt the step-size and exploit the noise variability. When the noise statistics are unknown, we obtain similar improvements by developing an online estimator of the noise level, thereby recovering close variants of RMSProp (Tieleman and Hinton, 2012). Consequently, our results reveal why adaptive step size methods can outperform SGD, while still enjoying theoretical guarantees.

authors:
A. Agarwal
M.J. Wainwright
P.L. Bartlett
P.K. Ravikumar

title: Information-theoretic lower bounds on the oracle complexity of convex optimization

venue: In Proceedings of Advances in Neural Information Processing Systems (NIPS),

authors:
N. Agarwal
B. Bullins
X. Chen
E. Hazan
K. Singh
C. Zhang
Y. Zhang

title: The case for full-matrix adaptive regularization

venue: arXiv preprint arXiv:1806.02958,

authors:
Y. Arjevani
Y. Carmon
J.C. Duchi
D.J. Foster
N. Srebro
B. Woodworth

title: Lower bounds for non-convex stochastic optimization

authors:
M.G. Azar
I. Osband
R. Munos

title: Minimax regret bounds for reinforcement learning

venue: In International Conferences on Machine Learning (ICML),

authors:
O. Besbes
Y. Gur
A. Zeevi

title: Stochastic multi-armed-bandit problem with non-stationary rewards

venue: In Advances in neural information processing systems,

authors:
L. Bottou
F.E. Curtis
J. Nocedal

title: Optimization methods for large-scale machine learning

venue: Siam Review,

title: Convex optimization: Algorithms and complexity

venue: arXiv preprint arXiv:1405.4980,

authors:
X. Chen
S. Liu
R. Sun
M. Hong

title: On the convergence of a class of ADAM-type algorithms for non-convex optimization

venue: In International Conference on Learning Representations (ICLR),

authors:
Y. Drori
O. Shamir

title: The complexity of finding stationary points with stochastic gradient descent

venue: arXiv preprint arXiv:1910.01845,

authors:
J. Duchi
E. Hazan
Y. Singer

title: Adaptive subgradient methods for online learning and stochastic optimization

venue: Journal of Machine Learning Research,

authors:
C. Fang
C.J. Li
Z. Lin
T. Zhang

title: Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator

authors:
S. Gadat
F. Panloup

title: Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity

venue: arXiv preprint arXiv:1709.03342,

authors:
S. Ghadimi
G. Lan

title: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework

venue: SIAM Journal on Optimization,

title: Stochastic first-and zeroth-order methods for nonconvex stochastic programming

authors:
K. He
X. Zhang
S. Ren
J. Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
H. Huang
C. Wang
B. Dong

title: Nostalgic Adam: weighting more of the past gradients when designing the adaptive learning rate

venue: In Proceedings of the 28th International Joint Conference on Artificial Intelligence,

authors:
A. Jadbabaie
A. Rakhlin
S. Shahrampour
K. Sridharan

title: Online optimization: Competing with dynamic comparators

venue: In Artificial Intelligence and Statistics,

authors:
C. Jin
Z. Allen-Zhu
S. Bubeck
M.I. Jordan

title: Is q-learning provably efficient

authors:
C. Jin
P. Netrapalli
M.I. Jordan

title: Accelerated gradient descent escapes saddle points faster than gradient descent

venue: In Conference On Learning Theory,

authors:
A. Jofré
P. Thompson

title: On variance reduction for stochastic smooth convex optimization with multiplicative noise

venue: Mathematical Programming,

authors:
D.P. Kingma
J. Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

title: Online to offline conversions, universality and adaptive minibatch sizes

authors:
K.Y. Levy
A. Yurtsever
V. Cevher

title: Online adaptive methods, universality and acceleration

authors:
X. Li
F. Orabona

title: On the convergence of stochastic gradient descent with adaptive stepsizes

venue: In The 22nd International Conference on Artificial Intelligence and Statistics,

authors:
L. Liu
H. Jiang
P. He
W. Chen
X. Liu
J. Gao
J. Han

title: On the variance of the adaptive learning rate and beyond

authors:
M. Liu
Y. Mroueh
J. Ross
W. Zhang
X. Cui
P. Das
T. Yang

title: Towards better understanding of adaptive gradient algorithms in generative adversarial nets

authors:
J. Ma
D. Yarats

title: On the adequacy of untuned warmup for adaptive optimization

venue: arXiv preprint arXiv:1910.04209,

authors:
S. Merity
N.S. Keskar
R. Socher

title: Regularizing and optimizing LSTM language models

authors:
A. Mokhtari
S. Shahrampour
A. Jadbabaie
A. Ribeiro

title: Online optimization in dynamic environments: Improved regret rates for strongly convex problems

venue: IEEE 55th Conference on Decision and Control (CDC),

authors:
E. Moulines
F.R. Bach

title: Non-asymptotic analysis of stochastic approximation algorithms for machine learning

authors:
A. Nemirovski
A. Juditsky
G. Lan
A. Shapiro

title: Robust stochastic approximation approach to stochastic programming

authors:
A.S. Nemirovsky
D.B. Yudin

title: Problem complexity and method efficiency in optimization

authors:
A. Rakhlin
O. Shamir
K. Sridharan

title: Making gradient descent optimal for strongly convex stochastic optimization

authors:
L. Rosasco
S. Villa
B.C. Vũ

title: Convergence of stochastic proximal gradient algorithm

venue: Applied Mathematics & Optimization,

authors:
M. Staib
S.J. Reddi
S. Kale
S. Kumar
S. Sra

title: Escaping saddle points with adaptive gradient methods

authors:
A.L. Strehl
M.L. Littman

title: An analysis of model-based interval estimation for markov decision processes

venue: Journal of Computer and System Sciences,

authors:
T. Tieleman
G. Hinton

title: Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude

venue: COURSERA: Neural networks for machine learning,

authors:
R. Ward
X. Wu
L. Bottou

title: Adagrad stepsizes: Sharp convergence over nonconvex landscapes

authors:
J. Zhang
S.P. Karimireddy
A. Veit
S. Kim
S.J. Reddi
S. Kumar
S. Sra

title: Why adam beats sgd for attention models

authors:
J. Zhang
T. He
S. Sra
A. Jadbabaie

title: Why gradient clipping accelerates training: A theoretical justification for adaptivity

venue: In International Conference on Learning Representations,

authors:
D. Zhou
Y. Tang
Z. Yang
Y. Cao
Q. Gu

title: On the convergence of adaptive gradient methods for nonconvex optimization

venue: arXiv preprint arXiv:1808.05671,

authors:
Z. Zhou
Q. Zhang
G. Lu
H. Wang
W. Zhang
Y. Yu

title: Adashift: Decorrelation and convergence of adaptive learning rate methods

authors:
F. Zou
L. Shen

title: On the convergence of weighted adagrad with momentum for training deep neural networks

venue: arXiv preprint arXiv:1808.03408,

authors:
F. Zou
L. Shen
Z. Jie
W. Zhang
W. Liu

title: A sufficient condition for convergences of adam and rmsprop

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

heading: 1 INTRODUCTION

text:
Stochastic gradient descent (SGD) is one of the most popular optimization methods in machine learning because of its computational efficiency compared to traditional full gradient methods. Great progress has been made in understanding the performance of SGD under different smoothness and convexity conditions (Agarwal et al., 2009; Arjevani et al., 2019; Drori and Shamir, 2019; Ghadimi and Lan, 2012; 2013; Nemirovsky and Yudin, 1983; Rakhlin et al., 2012). These results show that with a fixed step size, SGD can achieve the minimax optimal convergence rate for both convex and nonconvex optimization problems, provided the gradient noise is uniformly bounded.
Yet, despite the theoretical minimax optimality of SGD, adaptive gradient methods (Duchi et al., 2011; Kingma and Ba, 2014; Tieleman and Hinton, 2012) have become the methods of choice for training deep neural networks, and have received a surge of attention recently (Agarwal et al., 2018; Chen et al., 2019; Huang et al., 2019; Levy, 2017; Levy et al., 2018; Li and Orabona, 2019; Liu et al., 2019; 2020; Ma and Yarats, 2019; Staib et al., 2019; Ward et al., 2019; Zhang et al., 2019; 2020; Zhou et al., 2018; 2019; Zou and Shen, 2018; Zou et al., 2019). Instead of using fixed stepsizes, these methods construct their stepsizes adaptively using the current and past gradients. Despite advances in the literature on adaptivity, theoretical understanding of the benefits of adaptation is very limited.
We provide a different perspective on understanding the benefits of adaptivity by considering it in the context of non-stationary gradient noise, i.e., the noise intensity varies with iterations. Surprisingly, this setting is rarely studied, even for SGD. To our knowledge, this paper is the first work to formally study stochastic gradient methods in this varying noise scenario. Our main goal is to show that:
Adaptive step-sizes can guarantee faster rates than SGD when the noise is non-stationary.
We focus on this goal based on several empirical observations (Section 2), which lead us to model the noise of stochastic gradient oracles via the following iteration dependent quantities:
m2k := E[‖g(xk)‖2], or σ2k := E[‖g(xk)−∇f(xk)‖2], (1)
where g(xk) is the stochastic gradient and ∇f(xk) the true gradient at iteration k. Notation (1) provides more fine-grained description of noise behavior than uniform bounds on the variance by
permitting iteration dependent noise intensities. It is intuitive that one should prefer smaller stepsizes when the noise is large and vice versa. Thus, under non-stationarity, an ideal algorithm should adapt its stepsize according to the parameters mk or σk, suggesting a potential benefit of adaptive stepsizes.
Contributions. The primary contribution of our paper is to show that a stochastic optimization method with adaptive stepsize can achieve a faster rate of convergence (by a factor that is polynomialin-T ) than fixed-step SGD. We first analyze an idealized setting where the noise intensities are known, using it to illustrate how to select noise dependent stepsizes that are provably more effective (Theorem 1). Next, we study the case with unknown noise, where we show under an appropriate smoothness assumption on the noise variation that a variant of RMSProp (Tieleman and Hinton, 2012) can achieve the idealized convergence rate (Theorem 3). Remarkably, this variant does not require the noise levels. Finally, we generalize our results to nonconvex settings (Theorems 12 and 14).

heading: 2 MOTIVATING OBSERVATION: NONSTATIONARY NOISE IN DEEP LEARNING

text:
Neural network training involves optimizing an empirical risk minimization problem of the form minx f(x) := 1 n ∑n i=1 fi(x), where each fi represents the loss function with respect to the i-th data or minibatch. Stochastic methods optimize this objective randomly sampling an incremental gradient ∇fi at each iteration and using it as an unbiased estimate of the full gradient. The noise intensity of this stochastic gradient is measured by its second moments or variances, defined as,
1. Second moment: m2(x) = 1n ∑n i=1 ‖∇fi(x)‖2;
2. Variance: σ2(x) = 1n ∑n i=1 ‖∇fi(x)−∇f(x)‖2, where∇f(x) is the full gradient,
To illustrate how these quantities evolve over iterations, we empirically evaluate them on three popular tasks of neural network training: ResNet18 training on Cifar10 dataset for image classification1, LSTM training on PTB dataset for language modelling2; transformer training on WMT16 en-de for language translation3. The results are shown in Figure 1, where both the second moments and variances are evaluated using the default training procedure of the original code.
On one hand, the variation of the second moment/variance has a very different shape in each of the considered tasks. In the CIFAR experiment, the noise intensity is quite steady after the first iteration, indicating a fast convergence of the training model. In LSTM training, the noise level increases and converges to a threshold. While, in training Transformers, the noise level increases very fast at the early epochs, then reaches a maximum, and turns down gradually.
On the other hand, the preferred optimization algorithms in these tasks are also different. For CIFAR10, SGD with momentum is the most popular choice. While for language models, adaptive methods such as Adam or RMSProp are the rule of thumb. This discrepancy is usually taken as granted, based on empirical validation; and little theoretical understanding of it exists in the literature.
1Code source for CIFAR10 https://github.com/kuangliu/pytorch-cifar 2Code source for LSTM https://github.com/salesforce/awd-lstm-lm 3Code source for Transformer https://github.com/jadore801120/attention-is-all-you-need-pytorch
Based on the observations made in Figure 1, a natural candidate emerges to explain this discrepancy in the choice of algorithms: the performance of stochastic algorithms varies according the characteristics of gradient noise encountered during training. Despite this behavior, noise level modeling has drawn surprisingly limited attention in prior art. Reference (Moulines and Bach, 2011) studies convergence of SGD assuming each component function is convex and smooth; extensions to the variation of the full covariance matrix are in (Gadat and Panloup, 2017). A more fine-grained stochastic oracle assumes that the variances grow with the gradient norm as σ2 + c‖∇f(x)‖2, or grow with the suboptimality σ2 + c‖x−x∗‖2 (Bottou et al., 2018; Jofré and Thompson, 2019; Rosasco et al., 2019). Unfortunately, these existing oracles fail to express the variation of noise observed in Figure 1. Indeed, the norm of the full gradient, represented as the difference between the orange and the blue line, is significantly smaller compared to the noise level. This suggests that noise variation is not due to the gradient norm, but due to some implicit properties of the objective function. This observation motivates us to introduce the following non-stationary noise oracle: Definition 1 (non-stationary noise oracle). The stochasticity of the problem is governed by a sequence of second moments {mk}k∈N or variances {σk}k∈N, such that, at the kth iteration, the gradient oracle returns an unbiased gradient g(xk) such that E[g(xk)] = ∇f(xk), and either
(a) with second moment E[‖g(xk)‖2] = m2k; or (b) with variance E[‖g(xk)−∇f(xk)‖2] = σ2k.
The non-stationary noise oracle is a relaxation of the standard uniform noise oracle in which case mk or σk are constant. By introducing the time dependency, we aim to understand how the variation of noise influences the convergence rate of optimization algorithms. An example that falls into this category is when the noise is additive to the gradient, namely g(xk) ∼ ∇f(xk) +N (0, σ2k). We emphasize that our goal is to demystify the correlation between the noise intensity and the performance of optimization algorithm, instead of explaining why certain shape of noise occurs. In general, the variation in noise is a consequence of the combination on data distribution, training model and optimization method, which is complex and highly non trivial. We simplify it by assuming that the noise intensity is decoupled from its location, meaning that, the parameters mk or σk only depend on the iteration number k, but do not depend on the specific location where the gradient is evaluated. This is empirically justified as the pattern of the noise is mostly determined by the task instead of the optimization algorithms, see Appendix A. The simplification helps to focus on the shape of noise, taking a first step towards the goal: characterize the convergence rate of adaptive algorithms under non-stationary noise.

heading: 3 THE BENEFIT OF ADAPTIVITY UNDER NONSTATIONARY NOISE

text:
In this section, we investigate the influence of nonstationary noise in an idealized setting where the noise parameters mk are known. For brevity, we will first focus on the convex setting and present our results based on the second moment parameters mk. We defer the discussion on nonconvex problems and variants on variance parameters σk to Section 5. One reason that we prioritize the second moment than the variance is to draw a connection with the well-known adaptive method RMSProp (Tieleman and Hinton, 2012) and Adam (Kingma and Ba, 2014). One common feature shared by both algorithms is that they scale the step sizes inversely to an exponential moving average of estimated second moments. Below, we start from the idealized case assuming the second moments are known and show why inverse scaling could speed up convergence.
Let f be convex and differentiable. We consider the problem minx f(x), where the gradient is given by the nonstationary noise oracle defined in Definition 1. We assume that the optimum is attained at x∗ and we denote f∗ the minimum of the objective. We are interested in studying the convergence rate of a stochastic algorithm with update rule
xk+1 = xk − ηkg(xk), (2) where ηk are stepsizes that are oblivious of the iterates {xk}k∈N.
Theorem 1. Under the second moment oracle given in Definition 1 (a), the weighted average xT = ( ∑T k=1 ηkxk)/( ∑T k=1 ηk) obtained by the update rule (2) satisfies the suboptimality bound
E[f(xT )− f∗] ≤ ‖x1 − x∗‖2 +
∑T k=1 η 2 km
2 k∑T
k=1 ηk . (3)
Although the theorem follows from standard analysis, it leads to valuable results as explained below. Corollary 2. Denote M = maxmk and R = ‖x1 − x∗‖. We have the following convergence rate:
1. SGD with constant stepsize: if ηk = η = R√∑T k=1m 2 k , then
E[f(xT )− f∗] ≤ 2R √∑T k=1m 2 k
T = 2RM√ T ·
√ 1 T ∑T k=1m 2 k
M2 . (constant baseline)
2. SGD with idealized stepsize: if ηk = R√Tmk , then
E[f(xT )− f∗] ≤ 2R √ T∑T
k=1 1 mk
= 2RM√ T ·
1 M
1 T ∑T k=1 1 mk . (idealized baseline)
To facilitate comparison, we have normalized the convergence rates with respect to the conventional rate 2RM/ √ T (Nemirovski et al., 2009). In the standard setting, the values of mk are unavailable, but the uniform bound M is known, in such a case taking mk = M recovers the standard result.
When the values of mk are given, both constant baseline and idealized baseline benefits from it, improving upon the conventional rate 2RM/ √ T . The improvement factor in constant baseline has
depends on the average of the second moments √∑
m2k/T , while as the improvement factor in idealized baseline depends on the average of the harmonic sum 1T ∑ 1/mk. In particular, from Jensen’s inequality E[X]−2 ≤ E[X−2], we have ( 1T ∑ k 1 mk )−2 ≤ 1T ∑ km 2 k, implying that the idealized baseline is always better than the constant baseline. This result is rather expected, as the stepsizes are adapted to the noise intensity.
As a consequence, the accumulations of the parameters mk in different forms governed the convergence rate. To further illustrate such difference, we consider an illustrative synthetic noise model, mimicking the shape of noise we observed in the training of Transformer (see Figure 1(c)). Example 1. Consider the following piece-wise linear noise model with γ = 5(1− T−α)/T .
mk =  1 Tα if k ∈ [1, T 5 ]; γ(k − 2T5 ) + 1 if k ∈ ( T 5 , 2T 5 ]; 1 if k ∈ ( 2T5 , 3T 5 ]; γ( 3T5 − k) + 1 if k ∈ ( 3T 5 , 4T 5 ];
1 Tα if k ∈ ( 4T 5 , T ].
0.0 0.2 0.4 0.6 0.8 1.0 Iteration # 1e6
0.0
0.2
0.4
0.6
0.8
1.0
m k
alpha = 1/9 alpha = 1/6 alpha = 1/4
In this example, the maximum noise intensity M is 1, and the minimum intensity is 1/Tα, inducing a large ratio of order Tα. Following the bounds developed in Corollary 2, the performance of the constant baseline maintains the standard O(1/ √ T ) convergence rate, while as the idealized baseline converges at O(1/T 1 2 +α). Hence a nontrivial acceleration of order Tα is obtained by using the idealized stepsize, and this acceleration can be arbitrarily large as α increases.
This example is encouraging, showing that the speedup due to adaptive stepsizes can be polynomial in the number of iterations, especially when the ratio between the maximum and the minimum noise intensity is large. However, explicit knowledge on mk is required to implement these idealized stepsizes, which is unrealistic. The next sections of the paper demonstrates that estimating the moment bound in an online fashion can achieve a convergence rate comparable to the idealized setting.

heading: 4 ADAPTIVE METHODS: ONLINE ESTIMATION OF MOMENTS

text:
From now on, we assume that the moment bounds mk are not given. To address the non-stationarity, we estimate the noise intensity based on an exponential moving average, a technique commonly used in adaptive methods. More precisely, the moment estimator m̂k is constructed recursively as
m̂2k+1 = βm̂ 2 k + (1− β)‖gk‖2, (ExpMvAvg)
Algorithm 1 Adaptive SGD (x1, T, c,m)
1: Initialize m̂21 = ‖g(x1)‖2. 2: for k = 1, 2, ..., T do 3: Evaluate stochastic gradient gk at xk. 4: xk+1 = xk − ηkgk with ηk = cm̂k+m . 5: m̂2k+1 = βm̂ 2 k + (1− β)‖gk‖2. 6: end for 7: return xT = ( ∑T i=1 ηixi)/( ∑T i=1 ηi).
where gk is the k-th stochastic gradient and β is the decay paramter. Then we choose the stepsizes inversely proportional to m̂k+1, leading to Algorithm 1.
Algorithm 1 could be viewed as a “norm" version of RMSProp (Tieleman and Hinton, 2012): the exponential moving average is performed coordinate-wise in RMSProp, whereas we use the full norm of gk to update the moment estimator m̂k+1. Such a simplification via a full norm variant has also been analyzed in the uniformly bounded noise setting (Levy, 2017; Levy et al., 2018; Li and Orabona, 2019; Ward et al., 2019)—we leave investigation of the more advanced coordinate-wise version as a topic of future research.
Another important component of the stepsize is the correction constant m, the term appearing in the denominator. This constant provides a safety threshold when m̂k underestimates mk, which is commonly used in the practical implementation of adaptive methods, and even beyond, in reinforcement learning as so-called exploration bonus (Azar et al., 2017; Jin et al., 2018a; Strehl and Littman, 2008).
To show the convergence of the algorithm, we need to impose a regularity assumption on the sequence of noise intensities. Otherwise, previous estimate may not provide any information of the next one. Assumption 1. We assume that an upper bound M on mk is given, i.e. maxkmk ≤M such that
(a) The fourth moment of gk is bounded by M4, namely, E[(‖gk‖2 −m2k)2] ≤M4,∀k. (b) The total variation on mk is bounded, namely ∑ k |m2k −m2k+1| ≤ D2 with D2 = Ω(M2).
The bounded fourth moment ensures concentration of ‖gk‖2, which is necessary to guarantee the quality of the online estimator. In particular, this assumption is satisfied when ‖gk‖ follows a mk sub-Gaussian distribution. Though stronger than bounded variance, this assumption does not lead to better convergence rates for SGD, as many existing results (including lower bounds) require sub-Gaussian or bounded noise, see Agarwal et al. (2009); Ghadimi and Lan (2013) .
The bounded total variation assumption should be viewed as a regularity condition on the sequence of noise. It is motivated and common in the dynamic online learning literature (Besbes et al., 2014; Jadbabaie et al., 2015; Mokhtari et al., 2016). A key aspect of it is to avoid infinite oscillation, such as the pathological setting where m2k = 1 and m2k+1 = M , in which case the total variation scales with the number of iterations T . The specific constant in D2 = Ω(M2) depends on the shape of the noise. When mk is increasing in the first half and decreasing in the second half, as in the Transformer experiments and Example 1, the total variation is bounded by D2 ≤ 2M2. More generally, if the noise can be decomposed into K piece-wise monotone fragments, then the bound D2 ≤ KM2 holds. With the above assumptions, we are now ready to present our convergence result. Theorem 3. Under Assumptions 1, with probability at least 1/2, the iterates generated by Algorithm 1 using parameters β = 1− 2T−2/3, m = 4 √ D2 +M2T− 1 9 ln(T ) 1 2 , c = R√
T satisfy
f(xT )− f∗ ≤ 2RM√T · 32 M
1 T ∑T k=1 1 mk+m .
Remark 4. Our result directly implies a 1− δ high probability style convergence rate, by restarting it 2 log(1/δ) times. An additional log(1/δ) dependency will be introduced in the complexity, as in standard high probability results Fang et al. (2018); Jin et al. (2018b); Nemirovski et al. (2009).
The key to prove the theorem is to effectively bound the estimation error |m̂2k − m2k| relying on concentration, and on bounded variation in Assumption 1. In particular, the choice of the decay
parameter β is critical, determining how fast the contribution of past gradients decays. Because of the non-stationarity in noise, the online estimator m̂k is biased. The proposed choice of β carefully balances the bias error and the variance error, leading to sublinear regret, see Appendix C.
Due to the correction constant m, the obtained convergence rate inversely depends on ∑T k=1 1 mk+m ,
instead of the idealized dependency ∑T k=1 1 mk
. This additional term makes the comparison less straightforward and we now discuss different scenarios for obtaining a better understanding.

heading: 4.1 DISCUSSION OF THE CONVERGENCE RATE

text:
To illustrate the difference between convergence rates, we first consider the synthetic noise model introduced in Example 1. The detailed comparison is presented in Table 1, where we observe two regimes regarding the exponent α:
• When 0 ≤ α ≤ 19 , the rate of the adaptive algorithm matches (idealized baseline) up to logarithmic dependency, and is Tα better than the (constant baseline).
• When 19 ≤ α, the adaptive convergence rate no longer matches the (idealized baseline). Nevertheless, it is always T 1 9 faster than the (constant baseline).
In both cases, the adaptive method achieves a non-trivial improvement, polynomial in T , compared to the (constant baseline). Even though the improvement T 1 9 might seem in-significant, it is the first result showing a plausible non-trivial advantage of adaptive methods over SGD under nonstationarynoise. Further, note that the adaptive convergence rate does not always match the (idealized baseline) when α is large. Such a discrepancy comes from the correction term m, which makes the stepsize more conservative than it should be, especially when mk is small.
The above comparison relies on the specific choice on the noise model given in Example 1. Now we formalize some simple conditions allowing comparison in more general settings.
Corollary 5. If the ratio M/(minkmk) ≤ T 1 9 , then adaptive method converges in the same order as the (idealized baseline), up to logarithmic dependency.
This result is remarkable since the adaptive method does not require any knowledge of mk values, and yet it achieves the idealized rate. In other words, the exponential moving average estimator successfully adapts to the variation in noise, allowing faster convergence than constant stepsizes.
Corollary 6. Let m2avg = ∑ m2k/T be the average second moment. If M/mavg ≤ T 1 9 , then adaptive method is no slower than the (constant baseline), up to logarithmic dependency.
The condition in Corollary 6 is strictly weaker than the condition in Corollary 5, which means even though an adaptive method may not match the idealized baseline, it could still be non-trivially better than the constant baseline. This case happens e.g., when α > 19 in Table 1, where the adaptive method is O(T 19 ) faster than the constant baseline. Indeed, O(T 19 ) is the maximum improvement one can expect according to our current analysis.
Corollary 7. Recall that M is an upper bound on mk, i.e., maxmk ≤M . Therefore 1. The convergence rate of the constant baseline is no slower than O(2RM/ √ T ).
2. The convergence rate of the adaptive method is no faster than Õ(2RM/T 12 + 19 ).
The order of maximum improvement O(T 19 ) is determined by the specific choice of m in Theorem 3, which is chosen to be Õ(MT− 19 ). Indeed, the correction term is helpful when the estimator m̂k underestimates the true value mk, avoiding the singularity at zero. Hence, the choice of m is related
to the average deviation between m̂k and mk. Under a stronger concentration assumption, we can strengthen the maximum improvement to O(T 16 ), as shown in Appendix E. The noise model in Example 1 provides a favorable scenario where the maximum improvement is attained. However, in some scenarios, the convergence rate of an adaptive method can be slower than the constant baseline. Adversarial scenario. If mk = 1/Tα for all i ∈ [1, T ] except at T/2 it takes the value mT/2 = 1 with α > 1/9, then the convergence rate of both constant and idealized baselines are O(T− 1 2 ), while the adaptive method only converges in Õ(T− 1−2α2 ). The subtle change at iteration T/2 amplifies the exponential moving average estimator and requires a non-negligible period to get back to the constant level. It is clear that the estimator becomes less meaningful under such a subtle change.
Overall, it is hard to provide a complete characterization of the variation in noise. In Corollary 5 and 6, we show that when the ratio between the maximum and the minimum/average second moment is not growing too fast, adaptive methods do improve upon SGD.

heading: 5 EXTENSIONS OF THM 3

text:
In this section, we discuss several extensions to Thm 3. The results are nontrivial but the analysis is almost the same. Hence we defer the exact statements and proofs to appendices. Addressing the variance oracle. So far, we have focused on the noise oracle based on the second moment mk and made the connection with existing adaptive methods. However, there is some unnaturalness underlying the non-stationary oracle on mk. Indeed, it is hard to argue that mk is iterate independent since m2k = σ 2 k + ‖∇f(xk)‖2. Even though the influence of ‖∇f(xk)‖2 might be minor when the variance σ2k is high (e.g. as in Figure 1), it is still changing mk. In contrast, the variance σk is an intrinsic quantity coming from the noise model, which could be iterate independent. Hence the variance oracle is theoretically more sound. We now present the necessary modifications in order to adapt to the variance oracle.
First, in order to estimate the variance, we need to query two stochastic gradients gk and g′k at the same iterate, then we construct the estimator following the recursion
σ̂2k+1 = βσ̂ 2 k + (1− β)‖gk − g′k‖2.
Second, the smoothness condition on f is required, i.e., L-Lipschitzness on the gradient of f . In this case, it is necessary to ensure that the step-size being not larger than 1/2L. This translates to an additional constraint on the correcting constant m. More precisely, the stepsize is given by
ηk = c σ̂k+m with m ≥ 2cL.
Note that the L-smoothness condition is not required in the second moment oracle. This is why the second moment oracle is more suitable to nonsmooth setting (see Section 6.1 of Bubeck (2014)). A complete algorithm for the variance oracle is provided in Algorithm 2. The convergence results are essentially the same by replacing mk with σk, see Appendix H. Extension to nonconvex setting. We also provide an extension of our analysis to non-convex smooth setting. In which case, we characterize the convergence with respect to the gradient norm ‖∇f(xk)‖2, i.e., convergence to a stationary point. The conclusions are very similar to the one in the convex setting and the results (Theorems 12 and 14) are deferred to Appendix F. Variants on stepsizes. To go beyond the second moment of noise, one could apply an estimator of the form m̂pk+1 = βm̂ p k + (1− β)‖gk‖p when the p-th moment of the gradient is bounded. This allows stepsize of the shape ηk ∝ 1/(m̂pk +mp) 1/p as in ADAM, Adamax Kingma and Ba (2014).

heading: 6 EXPERIMENTS

text: In this section, we describe two sets of experiments that verify the faster convergence of Algorithm 1 against vanilla SGD. The first experiment is on linear regression with synthetic noise described in Example 1 and the second set of experiments is on neural network training.

heading: 6.1 SYNTHETIC EXPERIMENTS

text:
In the synthetic experiment, we generate a random linear regression dataset using the sklearn4 library. We design the stochastic oracle as full gradient with injected Gaussian noise, whose coordinate-wise
4scikit-learn.org/stable/modules/generated/sklearn.datasets.make_regression.html
standard deviation σ is shown in the left figure of Fig 2. We then run the four algorithms discussed in this work: standard baseline, idealized baseline, Alg 1 and Alg 2. We finetune the step sizes for each algorithm by grid-searching among 10k, where k is an integer. We repeat the experiment for 10 runs and show the average training trajectory as well as the function suboptimality in Fig 2. We observe that the performance is ranked as follows: idealized baseline, Alg 2, Alg 1 and standard baseline.

heading: 6.2 NEURAL NETWORK TRAINING

text:
We demonstrate how the proposed algorithm performs in real-world neural network training. We first tested our algorithm on Cifar10 classification task. We then implement our algorithm into the AWD-LSTM codebase described in Merity et al. (2018). We see from Figure 3 that our proposed algorithm can achieve slightly better performance than baselines. Despite our main contribution being providing theoretical analysis for the fast convergence of adaptive methods with moment estimation, these results show that our analysis can also lead to efficient and practical algorithm design.
Besides convergence, we also measured noise level during neural network training with different optimizers and found that the noise pattern is mostly determined by the learning task instead of by the optimization algorithm. Details can be found in Appendix A.

heading: 7 CONCLUSIONS

text:
This paper discusses convergence rates of stochastic gradient methods in an empirically motivated setting where the noise level is changing over iterations. We show that under mild assumptions, one can achieve faster convergence than the fixed step SGD by a factor that is polynomial in number of iterations, by applying online noise estimation and using adaptive step sizes. Our analysis, therefore provides one explanation for the recent success of adaptive methods in neural network training.
There is much more to be done along the line of non-stationary stochastic optimization. Under our current analysis, there is a gap between the adaptive method and the idealized method when the noise variation is large (see second row in Table 1). A natural question to ask is whether one could reduce this gap, or alternatively, is there any threshold preventing the adaptive method from getting arbitrarily close to the idealized baseline? Moreover, could one attain further acceleration by combining momentum or coordinate-wise update techniques? Answering these questions would provide more insight and lead to a better understanding of widely used adaptive methods.
Perhaps a more fundamental question is regarding the iterate dependency: the setting where the momentsmk or the variance σk are functions of the current update xk, not just of the iteration index k. Significant effort needs to be spent to address this additional correlation under appropriate regularity conditions. We believe our work lays the foundation to address this challenging research problem.

heading: A ADDITIONAL EXPERIMENT DETAILS AND RESULTS

text:
In this section, we provide more details on our experiment setup. The code for reproducing noise estimation and neural network training on AWS-LSTM model is uploaded in the supplementary. The code for Cifar10 classification can be uploaded upon request.
A.1 DETAILS ON PTB TRAINING
Our implementation is based on the author’s github repository 5. The original codebase trains the network using clipped gradient descent followed by an average SGD (ASGD) algorithm to prevent overfitting. As generalization error is beyond our discussion, we focus on the first phase (which takes about 200 epochs) by removing the ASGD training part. Aside of the number of epochs, all other parameters are the same as the default training procedure. For our algorithm, we update the clipping value to be 0.25, and set the hyperparameters of Algorithm 1 as ηk = 5, β = 0.95,m = 0.01.
A.2 DETAILS ON CIFAR10 TRAINING
Our implementation is based on a pytorch implementation 6 of the original ResNet paper(He et al., 2016). We train the ResNet18 model on Cifar10 dataset for 200 epochs. The baseline uses SGD with learning rate initialized as 0.1. The learning rate is decayed by 10 at epochs 100, 150. We eventually achieves approximately 95% validation accuracy. For our algorithm, we set ηk = 1, β = 0.99,m = 0.01 and use the same learning rate schedule as the baseline.
A.3 NOISE BEHAVIOR FOR DIFFERENT ALGORITHMS
In this subsection, we include one interesting observation on the noise pattern of neural network training. From Figure 1, we see that the noise pattern looks very different for different task. One may naturally wonder whether the difference results from the particular training task or from the optimization algorithms. Noticing that each of these three tasks are trained with a different algorithm (Cifar10 with momentum SGD; PTB with clipped SGD; En-De translation with ADAM), we retrained the Cifar10 task and the PTB language modelling with Adam. and rerun the En-De translation experiment with momentum SGD. We found that the En-De translation task diverges when trained with SGD even when learning rate is 0.001. Hence we only report the results from the other two experiments in Figure 4.
From Figure 4, we see that the pattern looks very similar to the original plots in Figure 1. Hence these experiments suggest that the noise pattern is mostly determined by the learning task instead of by the optimization algorithms.
5Code source for LSTM https://github.com/salesforce/awd-lstm-lm 6Code source for CIFAR10 https://github.com/kuangliu/pytorch-cifar

heading: B PROOF OF THEOREM 1

text:
Proof. The iterate suboptimality have the following relationship: ‖xk+1 − x∗‖2 = ‖xk − ηkgk − x∗‖2 = ‖xk − x∗‖2 − 2ηk〈gk, xk − x∗〉+ η2k‖gk‖2. Rearrange and take expectation with respect to gk we have 2ηk(f(xk)− f∗) ≤ 2ηk〈∇f(xk), xk − x∗〉
≤ E‖xk+1 − x∗‖2 − E‖xk − x∗‖2 + η2km2k Sum over k and take expectation we get
E[ T∑ k=1 2ηk(f(xk)− f∗)] ≤ ‖x1 − x∗‖2 + T∑ k=1 η2km 2 k
Then from convexity, we have
E[f(xT )− f∗] ≤ ‖x1 − x∗‖2 +
∑T k=1 η 2 km
2 k∑T
k=1 ηk ,
where xT = ( ∑T i=1 ηixi)/( ∑T i=1 ηi). Corollary 2 follows from specifying the particular choices of the stepsizes.

heading: C KEY LEMMA

text:
Lemma 8. Under Assumptions 1, taking β = 1− 2T−2/3, the total estimation error of the m̂2k based on (ExpMvAvg) is bounded by:
E [ T∑ k=1 |m̂2k −m2k| ] ≤ 2(D2 +M2)T 2/3 ln(T 2/3)
Proof. On a high level, we decouple the error in a bias term and a variance term. We use the total variation assumption to bound the bias term, and use the exponential moving average to reduce variance. Then we pick β to balance the two terms.
From triangle inequality, we have T∑ k=0 E [ |m̂2k −m2k| ] ≤ T∑ k=1 E [ |m̂2k − E[m̂2k]| ]︸ ︷︷ ︸ Variance term + T∑ k=1 ∣∣E[m̂2k]−m2k∣∣︸ ︷︷ ︸ Bias term
(4)
We first bound the bias term. By definition of m̂k, we have E[m̂2k]−m2k = βE[m̂2k−1] + (1− β)m2k−1 −m2k
= β(E[m̂2k−1]−m2k−1) + (m2k−1 −m2k) Hence by recursion,
E[m̂2k]−m2k = βk−1 (E[m̂21]−m21)︸ ︷︷ ︸ =0 +βk−2(m21 −m22) + · · ·+ (m2k−1 −m2k)
Therefore, the bias term could be bounded by T∑ k=1 ∣∣E[m̂2k]−m2k∣∣ ≤ T∑ k=1 k−1∑ j=1 βk−1−j ∣∣m2j −m2j+1∣∣
= T−1∑ k=1 ∣∣m2k −m2k+1∣∣ T−1−k∑ j=0 βj
≤ 1 1− β T−1∑ k=1 ∣∣m2k −m2k+1∣∣ ≤ D 2
1− β (From Assumption (1))
The first inequality follows by traingle inequality. The third inequality uses the geometric sum over β. To bound the variance term, we remark that
m̂2k = (1− β)g2k−1 + (1− β)βg2k−2 + · · ·+ (1− β)βk−2g21 + βk−1g20 .
Hence from independence of the gradients, we have E [ |m̂2k − E[m̂2k]| ] ≤ √ Var[m̂2k]
= √
Var[(1− β)g2k−1] + Var[(1− β)βg2k−2] + · · ·+ Var[(1− β)βk−2g21 ] + Var[βk−1g20 ] ≤ √ (1− β)2 + (1− β)2β2 + · · ·+ (1− β)2β2(k−2) + β2(k−1)M2,
where M2 is an upperbound on the variance. The first inequality follows by Jensen’s inequality. The second equality uses independence of gi given g1, ..., gi−1. The last inequality follows by assumption 1.
We distinguish two cases, when k is small, we simply bound the coefficient by 1, i.e.√ (1− β)2 + (1− β)2β2 + · · ·+ (1− β)2β2(k−2) + β2(k−1) ≤ 1
When k is large such that k ≥ 1 + γ, with γ = 12(1−β) ln( 1 1−β ), we have β 2(k−1) ≤ 1− β, thus√
(1− β)2 + (1− β)2β2 + · · ·+ (1− β)2β2(k−2) + β2(k−1)
≤ √ (1− β)2 1− β2 + β2(k−1)
≤ √ (1− β)2 1− β2 + (1− β)
≤ √ 2(1− β)
The second inequality follows by k ≥ 1 + γ, with γ = 12(1−β) ln( 1 1−β ). Therefore, when k ≥ 1 + γ,
E [ |m̂2k − E[m̂2k]| ] ≤ √ 2(1− β)M
Therefore, substitute in the above equation into the
T∑ k=1 E [ |m̂2k − E[m̂2k]| ] = γ∑ k=1 E [ |m̂2k − E[m̂2k]| ] + T∑ k=γ+1 E [ |m̂2k − E[m̂2k]| ] ≤ (γ + (T − γ) √ 2(1− β))M2
Summing up the variance term and the bias term yields,
T∑ k=0 E [ |m̂2k −m2k| ] ≤ D 2 1− β + (γ + (T − γ) √ 2(1− β))M2 (5)
Taking β = 1− T−2/3/2 yields,
T∑ k=0 E [ |m̂2k −m2k| ] ≤ 2(D2 +M2)T 2/3 ln(T 2/3) (6)

heading: D PROOF OF THEOREM 3

text:
On a high level, the difference between the adaptive stepsize and the idealized stepsize mainly depends on the estimation error |m̂2k −m2k|, which has a sublinear regret according to Lemma C. Then we carefully integrate this regret bound to control the derivation from the idealized algorithm, reaching the conclusion.
Proof. By the update rule of xk+1, we have,
‖xk+1 − x∗‖2 = ‖xk − ηkgk − x∗‖2 = ‖xk − x∗‖2 − 2ηk〈gk, xk − x∗〉+ η2k‖gk‖2.
Noting that the stepsize ηk is independent of gk, taking expectation with respect to gk conditional on the past iterates lead to
2ηk(f(xk)− f∗) ≤ 2ηk〈∇f(xk), xk − x∗〉 = E[2ηk〈gk, xk − x∗〉|xk, · · · , x1] = −E[‖xk+1 − x∗‖2|xk, · · · , x1] + ‖xk − x∗‖2 + η2km2k.
Recall that R = ‖x1 − x∗‖, taking expectation and sum over iterations k, we get
E[2( ∑T k=1 ηk)(f(xT )− f∗)] ≤ R2 + E[ ∑T k=1 η 2 km 2 k].
Hence by Markov’s inequality, with probability at least 3/4, 2( ∑T k=1 ηk)(f(xT )− f∗) ≤ 4E[2( ∑T k=1 ηk)(f(xT )− f∗)] ≤ 4(R2 + E[ ∑T k=1 η 2 km 2 k]). (7)
Now we can upper bound the right hand side, indeed
T∑ k=1 E[η2km2k] = c2 T∑ k=1 E [ m2k (m̂k +m)2 ]
≤ c2 (
T∑ k=1 E [ m2k − m̂2k (m̂k +m)2 ] + T∑ k=1 E [ m̂2k (m̂k +m)2 ])
≤ c2 ( 1
m2 T∑ k=1 E [ |m2k − m̂2k| ] + T
)
≤ c2 ( (M2 +D2)T 2/3 ln(T 2/3)
m2 + T
) ≤ 3c2T (8)
The last inequality follows by the choice on m. Hence, from Eq. (7), we have with probability at least 3/4,
2( ∑T k=1 ηk)(f(xT )− f∗) ≤ 4(R2 + 3c2T ) (9)
Next, by denoting (x)+ = max(x, 0), we lower bound the left hand side,
1
c
∑ ηk = ∑ 1 m̂k +m
= ∑ 1 mk +m + ∑( 1 m̂k +m − 1 mk +m ) ≥ ∑ 1
mk +m − ∑ (m̂k −mk)+ (mk +m)(m̂k +m)
≥ ∑ 1 mk +m − ∑ (m̂k −mk)+√ mk +m ·m3/2
≥ ∑ 1 mk +m − ∑ 1 2 ( (m̂k −mk)2+ m3 +
1
mk +m ) = 1
2 ∑ 1 mk +m − 1 2m3 ∑ (m̂k −mk)2+ (10)
Finally, by Markov’s inequality, with probability 3/4∑ (m̂k −mk)2+ ≤ 4E[ ∑ (m̂k −mk)2+] ≤ 4E[ ∑ (m̂k −mk)2] ≤ 8(D2 +M2)T 2/3 ln(T 2/3).
Following the choice of m = 4 √ D2 +M2T− 1 9 ln(T ) 1 2 , we have
1
2m3 T∑ k=1 (m̂k −mk)2+ ≤ T 4(M +m) ≤ 1 4 T∑ k=1
1
mk +m
Consequently, together with (9) and (10), we know that with probability at least 1− 14 − 1 4 = 1/2,
f(xT )− f∗ ≤ 4(R2 + 3c2T )∑
k c
4(mk+m)
≤ 2R√ T · 32T∑
k 1
(mk+m)
, (11)
where the last inequality follows by setting c = R√ T .
Remark 9. For more general choices of stepsize ηk = 1(m̂pk+mp)1/p , the upper bound in Eq.(8) holds exactly as in the above proof, and the lower bound in Eq.(10) follows from∑
ηk = ∑ 1
(m̂pk +m p)1/p = ∑ 1
(mpk +m p)1/p
+ ∑( 1
(m̂pk +m p)1/p − 1 (mpk +m p)1/p ) = ∑ 1
(mpk +m p)1/p
+ ∑ (mpk +mp)1/p − (m̂pk +mp)1/p
(m̂pk +m p)1/p(mpk +m p)1/p ≥ ∑ 1
(mpk +m p)1/p
− ∑ (m̂k −mk)+
(m̂pk +m p)1/p(mpk +m
p)1/p (Minkowski inequality)
≥ ∑ 1
(mpk +m p)1/p
− ∑ (m̂k −mk)+
m3/2(mpk +m p)1/2p
≥ 1 2 ∑ 1 (mpk +m p)1/p − 1 2m3 ∑ (m̂k −mk)2+.

heading: E PROOF WITH CONCENTRATE NOISE

text:
In this section, we add additional constraints on noise concentrations.
Assumption 2. The expected absolute value is not very different from the square root of the second moment, i.e. 2E[‖g(x)‖] ≥ √ E[‖g(x)‖2].
The constant “2” in the assumption above is arbitrary and can be increased to any fixed constant. The above assumption is satisfied if g(x) follows Gaussian distribution. It is also satisfied if for some fixed constant γ, p(‖g(x)‖ ≥ r) ≤ γE[‖g(x)‖]3r−4, for all r ≥ γE[‖g(x)‖]. We assume that the total variation on the first moment is bounded.
Assumption 3. We denote λk = E[‖gk‖], and assume that an upper bound M such that
(a) The second moment of gk is bounded by M2, namely, E[‖gk‖2] ≤M2,∀k. (b) The total variation on the first moment λk is bounded by∑
k |λk − λk+1| ≤ D = Ω(M). (12)
Under this stronger assumption, we can perform our online estimator on the first moment E[‖gk‖] instead of the second moment, replacing line 6 of Algorithm 1 by
m̂k+1 = βm̂k + (1− β)‖gk‖. (13)
The theorem below shows the convergence rate of the new algorithm.
Theorem 10. Under assumptions 2, 3,with m = 16(D + M)T−1/6 ln(T ), c = R√ T , Algorithm 1 with update rule (13) achieves convergence rate
f(xT )− f∗ ≤ 2R√ T · 12T∑
k 1
(mk+m)
, (14)
With a better concentration of the online estimator, we could allow a less conservative correction constant m, in the order of MT− 1 6 . It is this parameter that controls the maximum attainable improvement compared to the constant baseline. Indeed, we again consider the noise example 1, given in Table 2. In this case, the adaptive method can obtain an improvement of order T 1 6 compared to the constant baseline, while as previously only T 1 9 is achievable.
The proof of the result follows a similar routine as the proof of Theorem 3. We start by presenting an equivalent lemma of Lemma 8. Lemma 11. Under assumption 3, we can achieve the following bound on total estimation error.
E[ T∑ k=1 |m̂k − λk|] ≤ 2(D +M)T 2/3 ln(T 2/3)
Proof. The proof is the same as the proof of Lemma 8, by replacing the second m2k by the first moment λk = E[‖gk‖].
Proof of Theorem 10. By Assumption 2, we can use first moment of gk to bound the second moment. Hence, Eq. (7) implies that with probability at least 3/4,
2( ∑T k=1 ηk)(f(xT )− f∗) ≤ 4(R2 + E[4 ∑T k=1 η 2 kλ 2 k]). (15)
Now we upper bound the right hand side, indeed T∑ k=1 E[η2kλ2k] = c2 T∑ k=1 E [ λ2k (m̂k +m)2 ]
≤ c2 (
T∑ k=1 E [ λ2k − m̂2k (m̂k +m)2 ] + T∑ k=1 E [ m̂2k (m̂k +m)2 ])
≤ c2 (
T∑ k=1 E [ (λk − m̂k)(λk + m̂k) (m̂k +m)2 ] + T )
≤ c2 ( 2M
m2 T∑ k=1 E [|λk − m̂k|] + T
)
≤ c2 ( 4(M +D)MT 2/3 ln(T 2/3)
m2 + T
) ≤ 2c2T
Hence by Markov inequality, with probability at least 3/4, 2( ∑T−1 k=0 ηk)(f(xI)− f∗) ≤ 4E[2( ∑T−1 k=0 ηk)(f(xI)− f∗)] ≤ 4(R2 + 2c2T )
Next, we lower bound the left hand side, 1
c
∑ ηk = ∑ 1 m̂k +m
= ∑ 1 λk +m + ∑( 1 m̂k +m − 1 λk +m ) ≥ ∑ 1
λk +m − ∑ (m̂k − λk)+ (m̂k +m)(λk +m)
≥ ∑ 1
λk +m − 1 m2
∑ (m̂k − λk)+
By Markov’s inequality and Lemma 11, with probability 3/4, we have∑ (m̂k − λk)2+ ≤ 4E[ ∑ |m̂k − λk|] ≤ 8(D +M)T 2/3 ln(T 2/3).
Following the choice of m = 16(D +M)T− 1 6 ln(T ), we have
1
m2 E[(m̂k − λk)+] ≤
T 2(M +m) ≤ 1 2 ∑ 1 λk +m
Consequently, we know that with probability at least 1− 14 − 1 4 = 1/2,
f(xT )− f∗ ≤ 4(R2 + 2c2T )∑
k c
2(λk+m)
≤ 2R√ T · 12T∑
k 1
(mk+m)
, (16)
by setting c = R√ T and the fact that λk ≤ mk.
F VARIANCE ORACLE AND EXTENSION TO NONCONVEX SETTING
In this section, we show that we can adapt our algorithm to the variance oracle in Definition 1 (b), where E[‖gk −∇f(xk)‖2] = σ2k. To avoid redundancy, we present the result in the nonconvex smooth setting. We make the following smoothness assumptions. Assumption 4. The function is L−smooth, i.e. for any x, y, ‖∇f(x)−∇f(y)‖ ≤ L‖x− y‖.
Remark that the L-smoothness condition is not required in the second moment oracle. This is why the second moment assumption is usually imposed in the non-differentiable setting (see Section 6.1 of Bubeck (2014)). We first provide the convergences of SGD serving as the baselines. Theorem 12 (Nonconvex baselines). Under the variance oracle in Definition 1 (b) and Assumption 4, the convergence of SGD using update xk+1 = xk − ηkgk with ηk ≤ 12L satisfies
E[‖∇f(xI)‖2] ≤ f(x1)− f∗ + L2
∑T k=1 η 2 kσ
2 k∑T
k=1 ηk , (17)
where I is an random variable with P(I = i) ∝ ηi.
This convergence result is very similar to the one shown in the convex setting in Theorem 1. Instead of bounding the function suboptimality, the upper bound is only available on the norm of the gradient, implying convergence to a stationary point. We remark that an additional requirement on the stepsize is required, namely ηk ≤ 1/2L. This is not surprising since taking a large stepsize will not be helpful due to the L-smoothness condition. Hence, we can not take a stepsize inversely depending on σk when the noise is small. This restriction makes the comparison on convergence rate less straightforward. To facilitate the discussion on convergence rate, we make an additional assumption on the lower bound of the variance σk.
Algorithm 2 Variance Adaptive SGD (x1, T, c,m)
1: Initialize σ̂1 = ‖g1−g′1‖ 2 2 , where g1, g ′ 1 are two independent stochastic gradients at x1. 2: for k = 1, 2, ..., T do 3: Query two independent stochastic gradient gk, g′k at xk. 4: Update xk+1 = xk − ηk(gk + g′k)/2 with ηt = cσ̂k+m and m ≥ 2cL. 5: Update σ̂2k+1 = βσ̂ 2 k + (1− β) ‖gk−g′k‖ 2 2 6: end for 7: return xI where I is the random variable such that P(I = i) ∝ ηi.
Assumption 5. For any k ∈ [1, T ], σk ≥ √ 8L(f(x1)− f(x∗))/ √ T .
We emphasize that the above condition is not necessary to derive convergence analysis, but only for the clarity in terms of comparison on different convergence rate. This assumption help us focus on the case when noise (instead of the shape of the deterministic function) dominates the convergence rate and determines the step size. In otherword, our step size choice under this setting satisfies ηk ≤ 1/2L, leading to the following convergence rate: Corollary 13. Let ∆ = f(x1)− f∗. We have the following two convergence rate bounds for SGD:
1. SGD with constant stepsize: if ηk = η = √
2∆ L ∑ k σ 2 k , then
E[‖∇f(xI)‖2] ≤ √
2L∆ ∑T k=1 σ 2 k T = √ 2L∆ T · √∑T k=1 σ 2 k T . (constant baseline)
2. SGD with idealized stepsize: if ηk = 1σk √ 2∆ LT , then
E[‖∇f(xI)‖2] ≤ √ 2LT∆∑T k=1 1 σk
= √
2L∆ T · T∑T k=1 1 σk . (idealized baseline)
The resulting convergence rate are similar as the convex setting. We now modify the adaptive algorithm to make use of the variance oracle and the smoothness assumption. The through algorithm is presented in Algorithm 2. Particularly, we keep an exponential moving average of the variance instead of the moments, using two stochastic gradients gk and g′k at the same iterate,
σ̂2k+1 = βσ̂ 2 k + (1− β)
‖gk − g′k‖2
2 .
In particular, E[‖gk − g′k‖2/2] is an unbiased estimator of σ2k. To provide the convergence analysis of the algorithm, we make the following assumptions on the variation of the variance. Assumption 6. We assume an upper bound on σ2k = E[‖gk −∇f(xk)‖2], i.e. maxk σk ≤M . We also assume that the total variation in σk is bounded. i.e. ∑ k |σ2k − σ2k+1| ≤ D2 = 4M2.
With the above assumptions, algorithm 2 achieve the following convergence rate. Theorem 14. Under the assumptions 4, 6 and T large enough such that lnT ≤ T 1/3, algorithm 2 with c = √ 2∆ LT , m = 4 √ D2 +M2T−1/9 ln(T )1/2 + 2cL, achieves with probability 1/2,
‖∇f(xI)‖2 ≤ √ 2L∆
T · 32T∑
k 1
(σk+m)
.
The above theorem is almost the same as Theorem 3, and hence all the remarks for Theorem 3 also applies in the nonconvex case.

heading: G PROOF OF THEOREM 12

text:
Proof. By L-smoothness, we have
f(xk+1) ≤ f(xk)− ηk〈gk,∇f(xk)〉+ Lη2k
2 ‖gk‖2
Rearrange and take expectation with respect to gk, we get( ηk −
Lη2k 2
) ‖∇f(xk)‖2 ≤ f(xk)− f(xk+1) +
Lη2k 2 E[‖gk −∇f(xk)‖2].
From the condition ηk ≤ 12L , we have,
ηk 2 ‖∇f(xk)‖2 ≤ f(xk)− f(xk+1) + L 2 η2kσ 2 k.
Sum over k and take expectation,
E[ T∑ k=1 ηk‖∇f(xk)‖2] ≤ f(x0)− f(x∗) + L 2 ∑ k η2kσ 2 k.
Denote I as the random variable such that P(I = i) ∝ ηi. We know
( T∑ k=1 ηk)E[‖∇f(xI)‖2] ≤ f(x0)− f(x∗) + L 2 T∑ k=1 η2kσ 2 k.
This yields the desired convergence rate in (17).

heading: H PROOF OF THEOREM 14

text:
The proof is almost identical to the proof of Theorem 3. We start by presenting an equivalent theorem of Lemma 8 below.
Lemma 15. Under assumption 6, we can achieve the following bound on total estimation error using the estimator (ExpMvAvg):
E[ T∑ k=γ |σ̂2k − σ2k|] ≤ 2(D2 +M2)T 2/3 ln(T 2/3)
Proof. This follows by exactly the same proof as Theorem 8 and the fact that E[‖g − g′‖2] = 2E[‖g −∇f‖2].
Proof of Theorem 14. The first part of the proof follows the schema as in the proof of Theorem 12, when ηk ≤ 1/2L, we know that
E[( T∑ k=1 ηk)‖∇f(xI)‖2] ≤ ∆ + L 2 ∑ k E[η2kσ2k].
The rest of the proof is exactly the same as the proof of Theorem 3. We can upper bound the right hand side, indeed
T∑ k=1 E[η2kσ2k] = c2 T∑ k=1 E [ σ2k (σ̂k +m)2 ]
= c2 ( T∑ k=1 E [ σ2k − σ̂2k (σ̂k +m)2 ] + T∑ k=1 E [ σ̂2k (σ̂k +m)2 ])
≤ c2 ( 1
m2 T∑ k=1 E [ |σ2k − σ̂2k| ] + T
)
≤ c2 ( 2(M2 +D2)T 2/3 ln(T 2/3)
m2 + T
) ≤ 3c2T
The last inequality follows by the choice of parameters that M 2+D2
m2 ≤ 1 16
T 1/3
ln(T ) . Hence by Markov inequality, with probability at least 3/4,
( ∑T k=1 ηk)‖∇f(xI)‖2 ≤ 4E[( ∑T k=1 ηk)‖∇f(xI)‖2] ≤ 4(∆ + 3Lc2T 2 )
Next, we lower bound the left hand side as in (10),
1
c
∑ ηk = ∑ 1 σ̂k +m ≥ 1 2 ∑ 1 σk +m − 1 2m3 ∑ (σ̂k − σk)2+ (18)
Finally, by Markov’s inequality, with probability 3/4,∑ (σ̂k − σk)2+ ≤ 4E[ ∑ (σ̂k − σk)2+] ≤ 4E[ ∑ (σ̂k − σk)2] ≤ 8(D2 +M2)T 2/3 ln(T 2/3). Following the choice of m = 4 √ D2 +M2T− 1 9 ln(T ) 1 2 + 2cL, we have
1
2m3 T∑ k=1 (σ̂k − σk)2+ ≤ T 4(M +m) ≤ 1 4 T∑ k=1
1
σk +m
Together with (18) implies that with probability 3/4,
∑ ηk ≥ c
4 T∑ k=1
1
σk +m
Consequently, we know that with probability at least 1− 14 − 1 4 = 1/2,
‖∇f(xI)‖2 ≤ 4(∆ + 3Lc 2T 2 )∑
k c
4(σk+m)
≤ √ 2L∆
T · 32T∑
k 1
(σk+m)
, (19)
by setting c = √
2∆ LT .